并发控制

在数据库系统中，并发控制（Concurrency Control）旨在保证多个事务（transaction）同时执行时的数据一致性与正确性。由于事务可能会同时访问和操作相同的数据对象，如果缺乏有效的并发控制机制，就可能导致诸如丢失更新、不可重复读、脏读等一致性问题。

现代数据库系统通常需要支持高并发的事务处理以提升资源利用率和系统吞吐量。然而，事务并发执行会引发隔离性破坏和数据不一致等风险，因此必须依赖系统化的并发控制策略，从而确保事务在满足ACID特性的前提下安全、正确地进行。

数据库系统采用多种策略来管理并发事务，这些策略可以分为几大类：

基于锁的并发控制

锁是并发控制中最常用的机制。我们可以将锁比作房间的钥匙：只有拿到钥匙的人才能进入房间进行操作。在数据库中，锁确保同一时刻只有符合条件的事务能够访问特定的数据项。 数据库中主要有两种基本的锁模式：

• 共享锁（S锁）：允许事务读取数据项，但不能修改。多个事务可以同时持有同一数据项的共享锁，就像多个人可以同时阅读同一本书的复印件。
• 排他锁（X锁）：允许事务读取和写入数据项。同一时刻只能有一个事务持有某个数据项的排他锁，就像只有一个人可以拿着原版书进行批注。

锁的兼容性

不同类型的锁之间存在兼容性关系，这决定了多个事务能否同时持有同一数据项上的不同锁：

让我们通过一个银行转账的例子来理解锁的工作原理：

|
-- 事务T1: 从账户B转50元到账户A
BEGIN TRANSACTION T1;
LOCK-X(B);  -- 对账户B加排他锁
READ(B);
B := B - 50;
WRITE(B);
UNLOCK(B);  -- 释放账户B的锁
LOCK-X(A);  -- 对账户A加排他锁  
READ(A);
A := A + 50;
WRITE(A);
UNLOCK(A);  -- 释放账户A的锁
COMMIT;

这个例子为我们展示了事务如何通过锁来保护数据的完整性。

并发执行可能出现的问题

当多个事务并发执行且缺乏适当的控制时，可能出现以下问题：

数据不一致问题

考虑这样一个场景：小明的银行账户有100元，小红的账户有200元。现在有两个操作同时进行：

1. 事务T1要显示两个账户的总金额
2. 事务T2要从小红账户转50元给小明

如果没有适当的并发控制，可能出现T1读到小明账户增加了50元，但还没有读到小红账户减少50元的情况，导致显示的总金额变成了350元，这显然是错误的。

死锁问题

死锁是并发控制中的一个重要问题。想象两个人同时需要使用两把钥匙，每个人都拿着一把，等待对方释放另一把，结果谁都无法继续进行。

在数据库中，当两个或多个事务相互等待对方释放锁时，就会产生死锁。系统必须检测并解决这种情况，通常通过回滚其中一个事务来打破僵局。

锁机制的实现

数据库系统通常使用锁管理器来协调锁的申请和释放。锁管理器维护一个锁表，记录每个数据项上的锁信息：

当事务请求锁时，锁管理器会检查兼容性，决定是立即授予锁还是让事务等待。

这种基于锁的方法虽然能有效保证数据一致性，但也可能带来性能开销。在接下来的学习中，我们将探讨更高级的锁协议和其他并发控制方法。

两阶段锁定协议

两阶段锁定协议是确保事务可串行化的重要方法。就像登山一样，这个协议将事务的锁操作分为两个阶段：「上山阶段」和「下山阶段」。

• 增长阶段（Growing Phase）：事务可以获取新的锁，但不能释放任何已有的锁。就像爬山过程中只能向上攀登，不能回头下山。
• 缩减阶段（Shrinking Phase）：事务可以释放锁，但不能获取新的锁。就像下山过程中只能往下走，不能再向上攀登。

一旦事务释放了任何一个锁，它就进入了缩减阶段，此后不能再申请任何新的锁。 让我们通过一个网上购物的例子来理解两阶段锁定：

|
-- 事务：用户购买商品
BEGIN TRANSACTION 购买商品;
 
-- 增长阶段：获取所需的锁
LOCK-S(用户账户);    -- 检查用户余额
LOCK-X(商品库存);    -- 准备减少库存
LOCK-X(订单表);      -- 准备创建订单
 
-- 执行业务逻辑
READ(用户账户);
READ(商品库存);
IF 余额足够 AND 库存充足 THEN
    UPDATE(商品库存);  -- 减少库存
    INSERT(订单表);    -- 创建订单
END IF;
 

协议的变体

严格两阶段锁定在基本协议基础上增加了一个限制：所有排他锁必须保持到事务提交或回滚时才能释放。这样可以避免级联回滚的问题。 想象这样的情况：如果事务A修改了数据后立即释放锁，事务B读取了这个修改后的数据，但随后事务A因为某种原因回滚了。这时事务B读到的就是「脏数据」，也需要被回滚，形成级联效应。

严格两阶段锁定通过持有排他锁直到事务结束来避免这个问题，它要求所有锁（包括共享锁和排他锁）都必须保持到事务结束。这进一步简化了调度，确保事务可以按照提交顺序进行串行化。

锁转换机制

为提升并发处理能力，现代数据库系统通常支持锁的升级（Upgrade）与降级（Downgrade）机制：

• 锁升级：指事务将已持有的数据项的共享锁（S锁）提升为排他锁（X锁）。典型场景是事务初期以读操作为主，仅需共享锁，后续判断需进行写操作时，申请将共享锁升级为排他锁，以保证对数据项的独占访问并完成写操作。
• 锁降级：指事务将已持有的排他锁（X锁）降级为共享锁（S锁）。该操作通常在完成对数据项的写操作后进行，以释放对写操作的独占控制，从而允许其他事务继续对同一数据项进行并发读取，提升系统整体并发性。

|
-- 锁转换示例
BEGIN TRANSACTION;
 
LOCK-S(商品信息);     -- 先获取共享锁读取商品
READ(商品信息);
 
IF 需要修改商品 THEN
    UPGRADE(商品信息);  -- 将共享锁升级为排他锁
    WRITE(商品信息);
    DOWNGRADE(商品信息); -- 修改完成后可以降级为共享锁
END IF;
 
COMMIT;

图基锁定协议

当我们对数据项的访问模式有先验知识时，可以设计出不需要严格遵循两阶段的锁定协议。树协议就是这样一个例子，它将数据项组织成树状结构。 在树协议中，数据项被排列成一个有向无环图，通常是树形结构。每个数据项都有其父节点和子节点的关系。

树协议的规则

树协议只使用排他锁，并遵循以下规则：

1. 事务的第一个锁可以加在任何数据项上
2. 后续的锁只能加在当前已持有锁的数据项的子节点上
3. 数据项可以在任何时间被解锁
4. 一个数据项被解锁后，不能再次被同一事务加锁

树协议的优势

• 无死锁保证：树协议天然避免了死锁问题，因为事务按照树的层次结构获取锁，不会形成循环等待。
• 提前释放锁：与两阶段锁定不同，树协议允许事务在获取新锁的同时释放已有的锁，这可以提高并发性。

考虑一个文件系统的例子：

|
-- 事务：访问文件 /home/user/documents/report.txt
LOCK-X(/);                    -- 锁定根目录
LOCK-X(/home);               -- 锁定home目录
UNLOCK(/);                   -- 可以释放根目录锁
LOCK-X(/home/user);          -- 锁定user目录
UNLOCK(/home);               -- 释放home目录锁
LOCK-X(/home/user/documents); 

尽管树协议有很多优点，但它也有一些局限：

• 额外的锁开销：为了访问某个数据项，可能需要锁定从根到该数据项路径上的所有节点，即使这些中间节点并不需要被访问。
• 预先知识要求：需要事先了解数据项的访问模式，才能构建合适的树结构。

多粒度锁定

在实际的数据库系统中，锁定的「粒度」可以有很大差异。我们可以锁定一行记录、一个表、甚至整个数据库。不同的锁粒度适用于不同的应用场景。 想象一个图书馆的管理系统：我们可以采用细粒度锁来锁定某一本具体的书，这样其他读者仍然可以借阅同一书架上的其他书籍。也可以使用中等粒度锁来锁定某个书架或某个分类的所有书，适合进行分类整理工作。当需要进行全馆盘点时，可能需要粗粒度锁来锁定整个图书馆。

为了高效地管理不同粒度的锁，数据库系统引入了意向锁的概念。意向锁表示事务打算在更低层次上设置某种类型的锁。

• 意向共享锁（IS锁）：表示事务打算在子节点上设置共享锁
• 意向排他锁（IX锁）：表示事务打算在子节点上设置排他锁
• 共享意向排他锁（SIX锁）：表示整个子树被共享锁定，同时打算在某些子节点上设置排他锁

多粒度锁的兼容性

考虑一个学生管理系统的例子：

|
-- 场景1：读取某个学生的具体信息
LOCK-IS(数据库);
LOCK-IS(学生表);
LOCK-S(学生记录#12345);
 
-- 场景2：修改某个学生的信息
LOCK-IX(数据库);
LOCK-IX(学生表);
LOCK-X(学生记录#12345);
 
-- 场景3：生成整个年级的成绩报告
LOCK-IS(数据库);
LOCK-S(学生表);  -- 直接锁定整个表

多粒度锁定特别适合那些既有大量小事务（访问少量数据）又有少量大事务（生成报告等）的混合工作负载环境。它在提供细粒度并发控制的同时，也支持高效的批量操作。

死锁处理

死锁就像城市交通中的死循环：四辆车分别到达十字路口的四个方向，每辆车都在等待前方的车先通过，结果谁也无法前进。 在数据库中，死锁发生在两个或多个事务相互等待对方释放资源的情况。

考虑这样一个电商场景：

事务T1持有用户表的锁，想要获取产品表的锁。同时，事务T2持有产品表的锁，想要获取用户表的锁。双方都在等待对方释放资源，形成了死锁。

死锁预防策略

资源排序法

最简单的死锁预防方法是为所有数据项建立一个全局顺序，要求所有事务按照这个顺序来申请锁。这就像交通规则中的「右转优先」一样，通过统一的规则避免冲突。

|
-- 预定义资源顺序：用户表(ID=1) < 产品表(ID=2) < 订单表(ID=3)
 
-- 正确的锁申请顺序
BEGIN TRANSACTION;
LOCK-X(用户表);    -- 资源ID=1，先申请
LOCK-X(产品表);    -- 资源ID=2，后申请
LOCK-X(订单表);    -- 资源ID=3，最后申请
-- 执行业务逻辑
COMMIT;

通过这种方式，所有事务都会按照相同的顺序申请资源，从而避免循环等待的产生。

一次性锁申请

另一种预防方法是要求事务在开始执行前就申请所有需要的锁。这就像在餐厅用餐前就把所有需要的餐具都准备好，避免用餐过程中的争抢。

|
-- 一次性申请所有锁
BEGIN TRANSACTION;
LOCK-X(用户表, 产品表, 订单表);  -- 同时申请所有锁
-- 只有所有锁都获得后才开始执行
UPDATE 用户表 SET ...;
UPDATE 产品表 SET ...;
INSERT INTO 订单表 ...;
COMMIT;

这种方法的缺点是可能导致资源利用率较低，因为事务会长时间持有可能不会立即使用的锁。

基于时间戳的死锁预防

Wait-Die 机制

Wait-Die（等待-死亡）机制使用事务的时间戳来决定冲突的处理方式。这是一种非抢占式的方法：

规则：当事务Ti请求事务Tj持有的资源时，如果Ti比Tj更「年长」（时间戳更小），则Ti等待；否则Ti被回滚（「死亡」）。

让我们通过一个具体例子来理解：

|
-- 假设有三个事务，时间戳分别为：
-- T1: 时间戳 = 10 (最老)
-- T2: 时间戳 = 15 
-- T3: 时间戳 = 20 (最新)
 
情况1: T1请求T2持有的资源
结果: T1等待 (因为T1更老)
 
情况2: T3请求T2持有的资源  
结果: T3被回滚 (因为T3更年轻)

Wound-Wait 机制

Wound-Wait（伤害-等待）机制是抢占式的方法：

规则：当事务Ti请求事务Tj持有的资源时，如果Ti比Tj更「年长」，则Tj被回滚（被「伤害」）；否则Ti等待。

|
-- 使用相同的时间戳例子：
 
情况1: T1请求T2持有的资源
结果: T2被回滚 (T1更老，可以「伤害」T2)
 
情况2: T3请求T2持有的资源
结果: T3等待 (T3更年轻，必须等待)

超时机制

超时机制是一种简单而实用的死锁预防方法。事务在等待锁时设置一个超时时间，如果在指定时间内未能获得锁，就自动回滚。

|
-- 伪代码示例
BEGIN TRANSACTION;
TRY {
    LOCK-X(资源A) TIMEOUT 30秒;
    LOCK-X(资源B) TIMEOUT 30秒;
    -- 执行业务逻辑
    COMMIT;
} CATCH (TimeoutException) {
    ROLLBACK;
    -- 可以选择重试或报告错误
}

超时机制的主要优点在于实现简单、易于集成。然而，其主要挑战在于合理设置超时时间参数：超时时间过短可能导致事务被误判为死锁并发生不必要的回滚，影响正常业务进程； 超时时间过长则可能延迟死锁的检测与恢复，降低系统整体响应效率。

死锁检测与恢复

Wait-For图

当系统不采用死锁预防时，就需要能够检测死锁的发生。最常用的方法是构建Wait-For图（等待图）。 Wait-For图是一个有向图。在这个图中，每个节点代表一个事务，而有向边Ti → Tj表示事务Ti正在等待事务Tj释放某个资源。

在上图中，T1、T2、T3形成了一个环，表示存在死锁。而T4和T5之间没有形成环，不存在死锁。

死锁检测算法

系统会定期运行死锁检测算法，通过分析Wait-For图（等待图）来判断是否存在环路从而检测死锁。检测频率需根据实际系统特性灵活设定：死锁高发时可采用高频检测以实现快速响应，代价是较高的CPU资源消耗；死锁较少则可降低检测频率以节省资源，但可能导致死锁持续时间较长。 实际中还可以采用事件驱动策略，每当事务进入等待状态时即触发检测，以在性能和及时性之间取得平衡。

死锁恢复策略

当检测到死锁时，系统需要选择一个或多个事务进行回滚来打破死锁。选择回滚事务的策略包括：

• 最小代价原则：选择回滚代价最小的事务。代价的计算通常考虑事务已经执行的时间长短、事务使用的资源数量多少、事务还需要完成的工作量大小，以及回滚会影响的其他事务数量等因素。

|
-- 死锁恢复示例
检测到死锁: T1 → T2 → T3 → T1
 
代价分析:
T1: 执行时间5秒，修改了10条记录
T2: 执行时间2秒，修改了3条记录  
T3: 执行时间8秒，修改了15条记录
 
选择: 回滚T2 (代价最小)

• 避免饥饿：为了防止某个事务总是被选为牺牲者，系统需要记录每个事务被回滚的次数，并将其纳入选择标准。
• 部分回滚：不是总是完全回滚事务，而是只回滚到足以打破死锁的程度。这需要系统维护更详细的事务状态信息。

在实际的数据库系统中，死锁处理通常结合多种方法：

死锁处理是数据库并发控制中的重要组成部分。虽然死锁无法完全避免，但通过合适的预防和恢复策略，我们可以将其影响降到最低，确保系统的稳定运行。

时间戳协议

时间戳协议采用了一种完全不同的并发控制思路：不是通过锁来控制访问顺序，而是预先为每个事务分配一个时间戳，然后根据这个时间戳来确定事务的执行顺序。这就像银行的排队系统一样，每个客户都有一个号码，按号码顺序提供服务。 在时间戳协议中，系统确保最终的执行结果等价于事务按时间戳顺序串行执行的结果。如果事务T1的时间戳小于事务T2，那么系统会保证最终效果就像T1在T2之前完全执行一样。

时间戳的分配方法

系统可以通过多种方式为事务分配时间戳：

• 系统时钟法：使用事务开始时的系统时间作为时间戳。这种方法简单直观，但在高并发情况下可能出现相同的时间戳。
• 逻辑计数器法：使用一个全局递增的计数器，每个新事务获得当前计数器的值，然后计数器加1。这确保了时间戳的唯一性和顺序性。

|
-- 时间戳分配示例
事务T1: 开始时间 = 10:15:30.123, 时间戳 = 1015301230123
事务T2: 开始时间 = 10:15:30.125, 时间戳 = 1015301250125  
事务T3: 开始时间 = 10:15:30.127, 时间戳 = 1015301270127
 
-- 或使用逻辑计数器
事务T1: 时间戳 = 1001

为了实现基于时间戳的并发控制，系统为每个数据项维护两个时间戳：

• 读时间戳 R-timestamp(Q)：表示成功读取数据项Q的所有事务中最大的时间戳
• 写时间戳 W-timestamp(Q)：表示成功写入数据项Q的事务的时间戳

读操作的处理

当事务Ti要读取数据项Q时，系统会检查以下条件：

|
-- 读操作规则
IF TS(Ti) < W-timestamp(Q) THEN
    -- Ti想读取的数据已被更新的事务修改
    回滚事务Ti
ELSE 
    -- 允许读操作，更新读时间戳
    执行 READ(Q)
    R-timestamp(Q) = MAX(R-timestamp(Q), TS(Ti))
END IF

这个规则确保事务不会读到「来自未来」的数据。

写操作的规则更加复杂，需要检查两个条件：

|
-- 写操作规则
IF TS(Ti) < R-timestamp(Q) THEN
    -- 已有更新的事务读取了这个数据
    回滚事务Ti
ELSE IF TS(Ti) < W-timestamp(Q) THEN
    -- 已有更新的事务写入了这个数据
    回滚事务Ti  
ELSE
    -- 允许写操作
    执行 WRITE(Q)
    W-timestamp(Q) = TS(Ti)
END IF

让我们通过一个银行转账的例子来理解时间戳协议的工作过程：

|
-- 初始状态：账户A=100, 账户B=200
-- R-timestamp(A)=0, W-timestamp(A)=0
-- R-timestamp(B)=0, W-timestamp(B)=0
 
-- 事务T1 (时间戳=10): 从A转50到B
-- 事务T2 (时间戳=15): 显示A+B的总额
 
执行序列：
 
T1: READ(A)  
   -- TS(T1)=10 >= W-timestamp(A)=0, 允许读取
   -- R-timestamp(A) = MAX(0,10) = 10
 
T2: READ(A)
   -- TS(T2)=15 >= W-timestamp(A)=0, 允许读取  
   -- R-timestamp(A) = MAX(10,15) = 15
 
T1: WRITE(A) // A = A - 50 = 50
   -- TS(T1)=10 < R-timestamp(A)=15, 违规！
   -- 回滚T1，因为T2已经读取了原始值
 
T2: READ(B)

在这个例子中，T1被回滚是因为T2已经读取了账户A的原始值。如果允许T1修改A，就会破坏T2读取时所基于的数据一致性。

Thomas写规则

标准的时间戳协议有时会过于严格。Thomas提出了一个写规则的优化，在某些情况下可以忽略「过时」的写操作而不是回滚事务。

|
-- Thomas写规则
IF TS(Ti) < R-timestamp(Q) THEN
    回滚事务Ti  -- 这个规则不变
ELSE IF TS(Ti) < W-timestamp(Q) THEN
    忽略写操作  -- 这里是优化：不回滚，而是忽略
ELSE
    执行 WRITE(Q)
    W-timestamp(Q) = TS(Ti)
END IF

这个优化基于这样的观察：如果一个写操作是「过时的」（即已有更新的事务写入了数据），那么这个过时的写操作实际上不会影响最终结果，可以安全地忽略。

解决饥饿问题

为应对长事务可能出现的饥饿现象，系统通常采用以下专业策略加以缓解：一方面，对于被回滚的事务，可以在其重启时保留原有时间戳，使其逐渐成为系统中“最老”的事务，从而优先获得完成执行的机会； 另一方面，当检测到某事务多次回滚且存在饥饿风险时，系统可暂时阻塞与其存在冲突的年轻事务，对相关数据项的新访问请求实行短暂延迟，以保障老事务顺利执行直至完成。

|
-- 饥饿避免示例
事务T1(时间戳=10): 第3次被回滚
系统检测: T1存在饥饿风险
 
策略: 暂时阻塞时间戳>10的新事务对相关数据项的访问
让T1有机会完成执行

时间戳协议为数据库并发控制提供了另一种思路。虽然它不适合所有场景，但在特定的应用环境中，它能够提供简单而有效的并发控制机制。

验证协议

验证协议基于一个乐观的假设：大多数事务实际上不会相互冲突。因此，我们可以让事务自由地执行，只在最后提交时检查是否有冲突发生。这就像在一个信任度很高的社区里，大家先各自工作，最后再统一检查是否有重叠或冲突。 这种方法特别适合读操作远多于写操作的环境，因为读操作之间通常不会产生冲突。

验证协议的三阶段结构

|
-- 读取阶段示例
BEGIN TRANSACTION 网购订单;
 
-- 所有操作都在本地工作区进行
本地读取(用户余额);
本地读取(商品价格);
本地读取(商品库存);
 
-- 写操作也是本地的，不影响数据库
本地写入(用户余额 = 用户余额 - 商品价格);
本地写入(商品库存 = 商品库存 - 1);
本地写入(订单记录);
 
-- 此时数据库状态完全没有改变！

验证规则的设计

为了确保可串行化，验证阶段需要检查事务之间的冲突。系统为每个事务记录三个时间戳：Start(Ti) 表示事务开始时间，Validation(Ti) 表示事务验证开始时间，Finish(Ti) 表示事务完成写入时间。 对于任意两个事务Ti和Tj，如果Validation(Ti) < Validation(Tj)，那么需要满足以下条件之一：

• 条件1：Finish(Ti) < Start(Tj)：这意味着Ti在Tj开始之前就完全结束了，显然没有冲突。
• 条件2：Ti写入的数据集合与Tj读取的数据集合没有交集，且Start(Tj) < Finish(Ti) < Validation(Tj)。这确保即使两个事务在时间上重叠，它们访问的数据也不会冲突。

让我们通过一个图书馆管理系统的例子来理解验证协议：

|
-- 场景：两个事务并发执行
 
-- 事务T1：借阅《数据库原理》
-- 事务T2：归还《算法导论》并借阅《数据库原理》
 
-- T1的执行过程：
T1_读取阶段:
  本地读取(数据库原理.状态) // 可借阅
  本地读取(用户A.借阅数量) // 当前2本
  本地写入(数据库原理.状态 = 已借出)
  本地写入(用户A.借阅数量 = 3)
 
-- T2的执行过程：
T2_读取阶段:
  本地读取(算法导论.状态

多版本并发控制

多版本并发控制（MVCC, Multi-Version Concurrency Control）是基于验证协议的高级并发控制机制，其核心思想是在系统中为每个数据对象维护多个历史版本。 这样，事务在执行读操作时可以访问其逻辑时间点对应的数据版本，从而实现读写操作的互不阻塞，大幅提升并发性。在实际实现中，每次写操作并不会覆盖原有数据，而是为数据项创建一个新的版本，历史版本根据时间戳进行管理。 MVCC 机制能够有效避免读-写冲突，降低死锁发生概率，是现代主流数据库管理系统支持快照隔离与高并发处理能力的重要基础。

多版本时间戳排序

在多版本时间戳排序中，每个数据版本都包含三类信息：

• 内容：代表数据的实际值
• 写时间戳：表示创建此版本的事务时间戳
• 读时间戳：记录读取此版本的最大事务时间戳。

读操作规则：事务Ti读取数据项Q时，选择写时间戳小于等于TS(Ti)的最新版本。

写操作规则：

|
-- 写操作处理
IF TS(Ti) < R-timestamp(最新版本) THEN
    回滚Ti  -- 有更新的事务已经读过了
ELSE
    创建新版本，写时间戳 = TS(Ti)
END IF

而随着时间推移，系统会积累大量历史版本。为了控制存储开销，需要定期清理不再需要的版本：

|
-- 版本清理策略
对于数据项Q的版本Qk和Qj:
IF W-timestamp(Qk) < W-timestamp(Qj) 
   AND W-timestamp(Qk) < 所有活跃事务的最小时间戳 THEN
    删除版本Qk  -- 不会再被任何事务使用
END IF

多版本两阶段锁定结合了锁机制和多版本的优点。它将事务分为两类：

• 只读事务：获得一个时间戳，按照多版本时间戳协议执行，不需要锁定。
• 更新事务：使用严格的两阶段锁定协议，在提交时为新版本分配时间戳。

|
-- 多版本两阶段锁定示例
 
-- 只读事务（获得时间戳25）
BEGIN READ_ONLY TRANSACTION;
READ(账户A);  -- 读取时间戳≤25的最新版本
READ(账户B);  -- 读取时间戳≤25的最新版本
计算总余额;
COMMIT;      -- 无需获得锁
 
-- 更新事务
BEGIN UPDATE TRANSACTION;
LOCK-X(账户A);  -- 获得排他锁
READ(账户A);    -- 读取最新版本
WRITE(账户A);   -- 创建新版本（时间戳=∞）
COMMIT;         -- 设置时间戳为当前计数器值+1

这种方法的优势是只读事务永远不会被阻塞，而更新事务之间通过锁来协调，避免了复杂的冲突检测。

验证协议和多版本控制特别适合以下场景：

• 读多写少的应用：如数据仓库、报表系统、内容管理系统等。
• 冲突率较低的环境：当事务之间实际冲突不多时，乐观方法能够显著提高性能。
• 需要快照一致性的场景：如生成报告时需要看到某个时间点的一致数据视图。

快照隔离

快照隔离是一种特殊的多版本并发控制技术，已经成为现代数据库系统（如Oracle、PostgreSQL、SQL Server）的主流实现。它的核心思想是为每个事务提供数据库在某个时间点的「快照」，事务在这个快照上独立工作，就像拥有了数据库的私有副本一样。 想象你在拍摄一张集体照片。快照隔离就像为每个事务拍摄一张当前数据库状态的照片，事务基于这张「照片」进行所有的读操作，不会看到其他事务的中间修改。

快照的工作机制

快照的创建

当事务开始时，系统为其创建一个快照，这个快照包含事务开始时刻所有已提交事务的修改结果。事务的所有读操作都基于这个快照进行。

|
-- 快照隔离示例
时间点T1: 账户A=100, 账户B=200 (所有数据已提交)
 
-- 事务T1开始，获得快照S1
-- 事务T2开始，获得快照S2 (与S1相同，因为没有新的提交)
 
T1: 修改账户A=150 (在私有工作空间中)
T2: 读取账户A     → 返回100 (基于快照S2)
T2: 读取账户B     → 返回200 (基于快照S2)
 
T1: 提交          → 账户A正式更新为150
 
-- 新事务T3开始，获得快照S3
T3: 读取账户A     → 返回150 (看到T1的提交结果)

写操作的处理

写操作在事务的私有工作空间中进行，不会立即影响其他事务的快照。只有在事务提交时，这些修改才会成为数据库的正式状态，并可能被后续事务的快照包含。

快照隔离的冲突检测

First-Committer-Wins 策略

在快照隔离中，当多个事务修改相同的数据项时，系统采用「首次提交者获胜」的策略来解决冲突。 让我们通过一个网购平台的例子来理解：

|
-- 初始状态：商品库存=5
 
-- 事务T1：用户A购买2件商品
-- 事务T2：用户B购买3件商品
 
-- 两个事务并发执行过程：
 
T1_开始: 读取库存=5 (基于快照)
T2_开始: 读取库存=5 (基于相同快照)
 
T1: 计算新库存=5-2=3
T2: 计算新库存=5-3=2
 
T1: 准备提交 → 检查冲突 → 无其他事务修改过库存 → 提交成功
    (库存更新为3)
 
T2: 准备提交 → 检查冲突 → 发现T1已修改库存 → 提交失败！
    (T2需要回滚并重试)

First-Updater-Wins 策略

另一种策略是在事务尝试修改数据时就进行冲突检测，而不是等到提交时。这种方法使用锁来协调更新操作：

|
-- First-Updater-Wins 示例
 
T1: 读取商品库存=5
T2: 读取商品库存=5
 
T1: 尝试更新库存 → 获得写锁 → 成功更新为3
T2: 尝试更新库存 → 等待T1释放锁
 
T1: 提交 → 释放锁
T2: 获得锁 → 检查当前库存=3 → 计算新值=3-3=0 → 更新成功

快照隔离的主要优势在于其高并发性能，读操作不会被阻塞，从而显著提升系统吞吐能力；同时，为每个事务提供一致的数据快照，有效避免了脏读和不可重复读等现象； 此外，相较于严格的串行化控制，其实现与维护相对更加简单。不过，快照隔离并非万无一失，例如它无法完全保障可串行化，典型问题如“写偏斜”（Write Skew）仍可能导致数据一致性被破坏。

写偏斜问题

写偏斜是快照隔离中一个重要的异常现象。让我们通过一个医院值班管理系统来理解：

|
-- 场景：医院规定至少要有一名医生值班
-- 当前状态：医生A值班=是，医生B值班=是
 
-- 事务T1：医生A申请下班
-- 事务T2：医生B申请下班
 
-- 执行过程：
T1_快照: 医生A=值班，医生B=值班  
T2_快照: 医生A=值班，医生B=值班
 
T1: 检查条件 → 发现医生B在值班 → 可以下班
    更新：医生A=不值班
 
T2: 检查条件 → 发现医生A在值班 → 可以下班  
    更新：医生B=不值班
 
-- 两个事务都成功提交！
-- 结果：医生A=不值班，医生B=不值班 (违反了业务规则)

这种情况下，每个事务单独看都是合理的，但组合起来违反了业务约束。 我们可以用下面的方法来解决写偏斜问题。在读取需要保护的数据时，可以使用 SELECT FOR UPDATE 来获取锁，强制串行化执行：

|
-- 改进的医生值班管理
 
BEGIN TRANSACTION;
 
-- 使用 FOR UPDATE 锁定相关数据
SELECT COUNT(*) FROM 医生值班表 
WHERE 值班状态='是' FOR UPDATE;
 
-- 现在其他事务无法同时执行相同的检查
IF 值班医生数量 > 1 THEN
    UPDATE 医生值班表 SET 值班状态='否' 
    WHERE 医生ID='A';
ELSE

或者在应用程序中添加额外的检查逻辑，在数据库约束之外提供保护：

|
-- 应用层解决方案
应用程序逻辑:
1. 开始事务
2. 检查当前值班医生数量
3. 如果数量>1，允许下班申请
4. 提交前再次检查（防止并发修改）
5. 如果检查失败，回滚并重试

快照隔离的应用

PostgreSQL的实现

PostgreSQL将快照隔离称为「可重复读」隔离级别，它通过多版本并发控制来实现：

|
-- PostgreSQL 快照隔离示例
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
 
SELECT * FROM 账户表 WHERE 账户ID='A001';
-- 这个查询结果在整个事务期间保持不变
 
UPDATE 账户表 SET 余额=余额-100 WHERE 账户ID='A001';
-- 如果有冲突，事务会被中止
 
COMMIT;

Oracle的实现

Oracle默认使用快照隔离（称为读提交隔离级别），并提供可串行化快照隔离作为更高级别的选项：

|
-- Oracle 可串行化快照隔离
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
 
-- 系统会自动检测可能导致非串行化的冲突
-- 并在必要时回滚事务

高级并发控制

插入和删除操作的特殊挑战

到目前为止，我们主要讨论的是读取和更新操作。然而，插入和删除操作给并发控制带来了新的挑战，因为它们改变了数据库中数据项的存在性。 删除操作与其他操作的冲突关系需要特别考虑：

• 删除与读取的冲突：如果一个事务删除了数据项，而另一个事务尝试读取它，会发生什么？
• 删除与写入的冲突：两个事务同时尝试删除同一个数据项？
• 删除与插入的冲突：删除一个数据项后，另一个事务插入同样标识的数据项？

|
-- 删除操作冲突示例
-- 场景：学生信息管理系统
 
-- 事务T1：删除学生记录
-- 事务T2：更新同一学生的成绩
 
T1: DELETE FROM 学生表 WHERE 学号='2021001';
T2: UPDATE 成绩表 SET 分数=95 WHERE 学号='2021001';
 
-- 在不同的并发控制协议下处理方式：
 
-- 两阶段锁定：
T1: 获得学生记录的排他锁
T2: 等待获得锁 → 最终发现记录已被删除 → 更新失败
 
-- 时间戳排序：
如果 TS(T1) < TS(T2): T1删除成功，T2更新失败
如果 TS(T2) <

插入操作的特殊性在于它创建了之前不存在的数据项。这给并发控制带来的主要问题是如何处理对「不存在数据」的访问：

|
-- 插入操作示例
 
-- 事务T1：插入新学生
-- 事务T2：查询该学生信息
 
T1: INSERT INTO 学生表(学号, 姓名) VALUES('2024001', '张三');
T2: SELECT * FROM 学生表 WHERE 学号='2024001';
 
-- 时序1：T2先执行
T2: 查询结果为空
T1: 插入成功
-- T2没有看到新插入的记录
 
-- 时序2：T1先提交
T1: 插入成功并提交
T2: 查询到新记录
-- T2看到了T1插入的记录

幻影现象

幻影现象是并发控制中一个微妙而重要的问题。它发生在事务根据某个条件查询数据时，另一个事务插入了满足该条件的新数据，导致前一个事务再次执行相同查询时看到了「幻影」记录。 让我们通过一个银行系统的例子来理解：

|
-- 幻影现象示例
-- 场景：银行风控系统检查大额交易
 
-- 事务T1：统计今日大额转账（金额>10万）
-- 事务T2：记录一笔12万的转账
 
-- 执行序列：
T1: SELECT COUNT(*) FROM 转账记录 
    WHERE 日期='2024-03-15' AND 金额>100000;
    -- 结果：3笔
 
T2: INSERT INTO 转账记录 
    VALUES('2024-03-15', 120000, ...);
    -- 插入新的大额转账
 
T1: SELECT COUNT

这个问题的根源在于：T1的查询条件锁定了现有的记录，但无法锁定「可能被插入的记录」。

传统的记录级锁定只能保护已存在的数据项，但无法保护「概念性」的数据集合。在上面的例子中，T1需要保护的不是具体的某些记录，而是「所有满足条件的记录集合」这个概念。

为了解决幻影问题，数据库系统引入了索引锁定协议。这个协议的基本思想是锁定索引节点，而不仅仅是数据记录。

基本原理：当事务需要根据某个条件查找记录时，它必须锁定索引中相关的叶子节点。这样，任何尝试插入满足相同条件的记录的事务都会在索引操作时遇到锁冲突。

|
-- 索引锁定协议示例
-- 假设在"金额"字段上有索引
 
T1: 查询 WHERE 金额>100000
    -- 锁定索引中 [100000, +∞) 范围对应的叶子节点
 
T2: 插入记录 金额=120000  
    -- 需要更新索引，尝试锁定相同的叶子节点
    -- 与T1冲突，必须等待
 
-- 这样就避免了幻影现象

谓词锁定是解决幻影问题的另一种理论方法。它的思想是直接对查询条件（谓词）加锁，而不是对具体的数据项加锁。

|
-- 谓词锁定概念
T1: SELECT * FROM 学生表 WHERE 年龄 > 20;
    -- 对谓词 "年龄 > 20" 加共享锁
 
T2: INSERT INTO 学生表 VALUES('张三', 22, ...);
    -- 检查新记录是否满足已锁定的谓词
    -- 满足 "年龄 > 20"，因此与T1冲突，需要等待
 
T3: INSERT INTO 学生表 VALUES('李四', 18, ...);  
    -- 不满足 "年龄 > 20"，可以正常插入

虽然谓词锁定在理论上很优雅，但在实际系统中实现复杂度极高，因此大多数数据库系统采用索引锁定作为实用的解决方案。

实战练习

为了练习并发控制，我们将使用以下表结构：

银行账户表 (bank_accounts)

|
CREATE TABLE bank_accounts (
    account_id INT PRIMARY KEY,
    user_name VARCHAR(50),
    balance DECIMAL(10,2),
    account_type VARCHAR(20), -- 'checking' 或 'savings'
    created_date TIMESTAMP,
    last_updated TIMESTAMP
);

转账记录表 (transfers)

|
CREATE TABLE transfers (
    transfer_id INT PRIMARY KEY AUTO_INCREMENT,
    from_account_id INT,
    to_account_id INT,
    amount DECIMAL(10,2),
    transfer_date TIMESTAMP,
    status VARCHAR(20), -- 'pending', 'completed', 'failed'
    FOREIGN KEY (from_account_id) REFERENCES bank_accounts(account_id),
    FOREIGN KEY (to_account_id) REFERENCES bank_accounts(account_id)

商品库存表 (products)

|
CREATE TABLE products (
    product_id INT PRIMARY KEY,
    product_name VARCHAR(100),
    stock_quantity INT,
    unit_price DECIMAL(8,2),
    category VARCHAR(50),
    last_restock_date TIMESTAMP
);

习题1：锁的兼容性

假设银行账户表中有一个账户的余额为1000元。两个事务同时开始执行：

事务T1：将账户余额增加500元 事务T2：读取账户余额并计算利息

请分析以下情况下的锁兼容性，并说明结果： 如果T1首先获得了共享锁，T2能否获得共享锁？如果T1首先获得了排他锁，T2能否获得共享锁？

|
-- 情况1：T1获得共享锁后，T2能否获得共享锁？
-- 答案：可以，因为共享锁与共享锁兼容
-- 两个事务都可以同时读取账户余额
 
-- 情况2：T1获得排他锁后，T2能否获得共享锁？
-- 答案：不可以，因为排他锁与共享锁不兼容
-- T2必须等待T1释放排他锁才能获得共享锁

习题2：两阶段锁定协议

考虑以下场景：用户购买商品的流程需要锁定用户账户表和商品库存表。

请写出符合两阶段锁定协议的事务SQL代码，确保在读取用户余额、检查商品库存、扣减余额和减少库存的过程中遵循增长阶段和缩减阶段的规则。

|
-- 正确的两阶段锁定实现
BEGIN TRANSACTION;
 
-- 增长阶段：获取所有需要的锁
LOCK-S(bank_accounts);  -- 检查用户余额
LOCK-X(products);       -- 修改商品库存
 
-- 执行业务逻辑
SELECT balance FROM bank_accounts WHERE account_id = ?;
SELECT stock_quantity FROM products WHERE product_id = ?;
 
IF balance >= price AND stock_quantity > 0

习题3：死锁检测

银行转账系统中，两个事务形成死锁：

• 事务T1：从账户A转100元到账户B
• 事务T2：从账户B转200元到账户A

请画出这个场景的等待图，并说明死锁检测算法会如何处理这种情况。

|
-- 等待图分析：
-- T1持有账户A的锁，等待账户B的锁
-- T2持有账户B的锁，等待账户A的锁
-- 形成环：T1 → T2 → T1
 
-- 死锁检测算法发现环路后，会选择一个事务进行回滚
-- 通常选择代价最小的事务（执行时间短、修改数据少的事务）
 
-- 可能的解决方案：
-- 1. 回滚T2，让T1继续执行
-- 2. 或者使用资源排序法：强制所有事务按账户ID顺序获取锁
--   例如：总是先锁定小ID账户，再锁定大ID账户

习题4：时间戳协议

在时间戳协议中，有三个事务的执行序列：

• T1 (时间戳=10)：读取账户A余额，写入账户A余额
• T2 (时间戳=15)：读取账户A余额
• T3 (时间戳=20)：写入账户A余额

请分析每个事务的读写操作是否会被允许，并解释原因。

|
-- 假设初始状态：W-timestamp(A) = 0, R-timestamp(A) = 0
 
-- T1 (TS=10) 读取账户A：
-- TS(T1)=10 >= W-timestamp(A)=0，允许读取
-- R-timestamp(A) = MAX(0,10) = 10
 
-- T1 写入账户A：
-- TS(T1)=10 >= R-timestamp(A)=10，允许写入
-- W-timestamp(A) = 10
 
-- T2 (TS=15) 读取账户A：
-- TS(T2)=15 >= W-timestamp(A)=10，允许读取
-- R-timestamp(A) = MAX(10,15) = 15
 
-- T3 (TS=20) 写入账户A：
-- TS(T3)=20 >= R-timestamp(A)=15，允许写入
-- W-timestamp(A) = 20
 
-- 结论：所有操作都被允许，事务可以按时间戳顺序串行执行

习题5：快照隔离中的写偏斜

医院值班系统中，医生值班表如下：

|
CREATE TABLE doctor_schedule (
    doctor_id INT PRIMARY KEY,
    doctor_name VARCHAR(50),
    is_on_duty BOOLEAN,
    shift_start TIMESTAMP,
    shift_end TIMESTAMP
);

两个事务同时执行：

• T1：医生A申请下班（需要确保至少有一名医生值班）
• T2：医生B申请下班（同样需要确保至少有一名医生值班）

在快照隔离级别下，这个场景是否会出现写偏斜问题？请解释原因并给出解决方案。

|
-- 快照隔离下的写偏斜问题：
 
-- 初始状态：医生A值班中，医生B值班中
 
-- T1快照：A值班，B值班
-- T2快照：A值班，B值班
 
-- T1检查：值班医生数=2 > 1，可以下班
--   更新：A不值班
 
-- T2检查：值班医生数=2 > 1，可以下班
--   更新：B不值班
 
-- 结果：两个医生都不值班，违反业务规则
 
-- 解决方案1：使用 SELECT FOR UPDATE
BEGIN TRANSACTION;
SELECT COUNT(*) FROM doctor_schedule WHERE is_on_duty = true FOR UPDATE;
-- 锁定满足条件的所有记录，防止并发修改
 
-- 解决方案2：应用层检查
-- 在事务提交前再次验证业务规则
-- 如果发现冲突，回滚并重试

习题6：幻影现象

在商品库存管理系统中，事务T1需要统计库存不足的商品数量：

|
SELECT COUNT(*) FROM products WHERE stock_quantity < 10;

同时，事务T2插入一个新的库存不足商品。

传统的记录级锁定下，T1的查询结果是否会出现幻影现象？请解释原因并给出避免幻影现象的方法。

|
-- 传统记录级锁定的问题：
-- T1查询时锁定现有的库存不足商品记录
-- 但无法锁定"可能被插入的新记录"
-- T2可以插入新的库存不足商品，导致T1重复查询时看到"幻影"记录
 
-- 避免方法1：索引锁定协议
-- 在stock_quantity字段建立索引
-- T1查询时锁定索引中 [0,9] 范围对应的叶子节点
-- T2插入新商品时需要更新索引，会遇到锁冲突
 
-- 避免方法2：串行化隔离级别
-- 使用可串行化隔离确保事务完全串行执行
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
 
-- 避免方法3：应用层处理
-- 在查询前后加互斥锁，防止并发插入

习题7：多版本并发控制

考虑商品表的更新场景： 在多版本并发控制下，如果事务T1 (时间戳=10) 读取了商品A的版本，然后事务T2 (时间戳=15) 更新了商品A，最后事务T3 (时间戳=20) 读取商品A，会看到哪个版本的数据？

|
-- 多版本并发控制的数据版本：
-- 版本1：商品A库存=100，写时间戳=5（初始版本）
-- 版本2：商品A库存=80，写时间戳=15（T2更新的版本）
 
-- T1 (TS=10) 读取：选择写时间戳 ≤ 10 的最新版本 → 版本1 (库存=100)
 
-- T2 (TS=15) 更新：创建新版本，写时间戳=15 → 版本2 (库存=80)
 
-- T3 (TS=20) 读取：选择写时间戳 ≤ 20 的最新版本 → 版本2 (库存=80)
 
-- 优势：T1读取旧版本，不会被T2的更新阻塞
-- T3看到T2的更新结果

习题8：事务隔离级别的选择

对于以下应用场景，请选择合适的隔离级别并解释原因：

1. 银行账户余额查询（允许脏读）
2. 银行转账操作（必须保证一致性）
3. 电商商品浏览（性能优先）
4. 财务报表生成（数据准确性优先）

|
-- 1. 银行账户余额查询（允许脏读）
-- 选择：READ UNCOMMITTED
-- 原因：允许读取未提交的数据，提高查询性能
-- 适用场景：对实时性要求高，不介意看到中间状态
 
-- 2. 银行转账操作（必须保证一致性）
-- 选择：SERIALIZABLE 或 REPEATABLE READ
-- 原因：防止所有并发问题，确保事务串行执行
-- 适用场景：涉及资金变动，必须保证ACID特性
 
-- 3. 电商商品浏览（性能优先）
-- 选择：READ COMMITTED 或 SNAPSHOT
-- 原因：平衡性能和一致性，避免脏读但允许不可重复读
-- 适用场景：读多写少，用户浏览商品信息
 
-- 4. 财务报表生成（数据准确性优先）
-- 选择：SERIALIZABLE
-- 原因：确保报表数据完全一致，不受并发事务影响
-- 适用场景：生成重要财务数据，需要绝对准确性