cmu15545笔记-并发控制总结（Concurrency Control Summary）

• 二阶段锁：分为两个阶段，锁获取阶段和锁释放阶段，只有获取完所有锁以后才能释放锁。

由于获取完所有锁才会释放，所以依赖图不会成环（见“串行化与冲突操作”一节），但是由于我们无法对Abort操作加锁，并且插入或删除元素时也无法加锁，因此二阶段锁可以解决不可重复读和更新丢失，无法解决脏读和幻读。

级联回滚

脏读会带来级联回滚（Cascading Abort）的问题，见下图。

(T_2)读取了(T_1)未提交的数据，导致(T_1)回滚时，(T_2)也需要回滚。

强二阶段锁

强二阶段锁（String Strict 2PL）：不是操作结束后立刻解锁，而是在事务提交时统一解锁。

解决了脏读问题。因为由于事务提交前不释放锁，所以另一个事务无法读到刚修改的数据。

死锁检测和避免

一个死锁的例子：锁交错。

死锁检测：检测是否成环

时序图上体现为交叉，在依赖图上体现为环。

处理方式：选择一个事务进行回滚。

如何选择：依照年龄，执行进度，锁数量等。

如何回滚：全部回滚；部分回滚：设置savepoint，回滚到savepoint。

死锁避免：设置优先级，保证锁单向传递，不产生交错

• 事务的开始时间越早，优先级越高
• 分类：非抢占式（Wait-Die），抢占式（Wound-Wait）

	高->低	低->高
非抢占式	高优先级等待【爱幼】	低优先级放弃
抢占式	高优先级抢占	低优先级等待【尊老】

没有双向等待，也就不会产生交错，也就不会有死锁。

锁层级

数据库需要维护不同层级（Hierarchical）的锁来保证并发度。

意向锁：在给子层级加锁时，给父层级加意向锁，兼容矩阵如下。

实践应用

Select ... For Update

BEGIN; SELECT balance FROM Accounts WHERE account_id = 1 FOR UPDATE; UPDATE Accounts SET balance = balance - 100 WHERE account_id = 1; COMMIT; 

扣减余额时，先select再update：

• select时，account=1的tuple上的是S锁，父结点上的是IS锁；
• update时，accnount=1的tuple需要上X锁，父结点升级为ISX锁；
• 所以可以通过Select ... For Update，一开始就给tuple上X，给父结点上ISX锁

Select ... Skip Locked

可以跳过锁，避免阻塞。

例如：

SELECT task_id, task_data FROM task_queue WHERE status = 'pending' FOR UPDATE SKIP LOCKED LIMIT 1; 

• 一个任务表存储了待处理任务，每个任务由不同的线程负责处理：
• 每个线程获取一个未锁定的任务进行处理；
• 已被其他线程锁定的任务会被跳过，从而提高并发处理效率

实现的隔离级别

1. SERIALIZABLE：强二阶段锁+幻读预防措施（如索引锁，见后文）。
2. REPEATABLE READS：强二阶段锁。

OOC

乐观的并发控制（Optimistic Concurrency Control）。

原理

假设大多数时候没有冲突，先执行操作，操作结束后再进行一次验证。

• 如果确实没有冲突，提交事务，写入结果
• 如果有冲突，回滚，重新进行

三个阶段

1. 读取（Read Phase）：每个事务有一个私有的存储空间，当访问元组时，将访问结果读取到该空间中，后续的操作都在该空间进行。
2. 验证（Validation Phase）：赋予事务一个时间戳，并校验是否有冲突，即是否满足下面的条件。
   • (WriteSet(T1) ∩ ReadSet(T2) = Ø)
   • 如果此时事务2还处于读取阶段，那么还需要满足：(WriteSet(T1) ∩ WriteSet(T2) = Ø)
3. 写入（Write Phase）：写入结果，此时修改其他事务可见。

实现的隔离级别

如何解决并发问题：并发问题的图示见上文“串行化与冲突操作“一节

当处于验证阶段时，如果(T_1<T_2)：

• 由于读的是副本：不会出现脏读和不可重复读问题。

• 由于读的是副本：如果(WriteSet(T1) ∩ ReadSet(T2) ≠ Ø)

  (T_2)理应看到(T_1)的更新值，但是由于(T_1)还没有把结果写入磁盘，所以(T_2)读的是副本，而不是(T_1)的更新值。

  所以此时存在数据不一致问题，因此要保证(WriteSet(T1) ∩ ReadSet(T2) = Ø)

• (WriteSet(T1) ∩ WriteSet(T2) = Ø)：解决更新丢失问题。

• 没有解决幻读问题。

反例1：(WriteSet(T1) ∩ ReadSet(T2) ≠ Ø)，此时(T_2)没有读到(T_1)的更新。

反例2：(WriteSet(T1) ∩ WriteSet(T2) ≠ Ø)，可能出现更新丢失问题。

注：在验证阶段，我么都是与未提交的事务进行校验，称为前向校验（Forward Validation）。

当然也可以与已提交的事务进行校验，称为后向校验（Backward Validation）。

总结：

1. SERIALIZABLE：OOC+幻读预防措施（如索引锁，见后文）。
2. REPEATABLE READS：OOC。

处理幻读

主要采用索引锁（Index Lock）的方式。

在插入数据时，锁住索引见的间隙（Gap），从而阻止插入或删除。

更进一步：给索引锁也加上意向锁这个层级。

MVC

原理

基本思想：事务通过元组（Tuple）的版本，判断可见性。

• 版本：解决我能看到谁

  • 三元组 [begin-Txn, end-Txn, value]
  • 读操作：置begin-Txn
  • 写操作：置新值begin-Txn，旧值end-Txn

• 事务活动表：解决我能不能访问我看到的，必要时借助锁