CMU15445-2022 P4 Concurrency Control

煤渣

Lock Manager

基本概念

lock manager 为每个资源（表/行）维护一个请求队列，这个队列根据请求的顺序排序。队列记录了每一个请求的事务、锁级别、是否授予等。lock manager 用哈希表建立从资源到队列的索引，我们称这个哈希表为lock table，在p4中分别为 table_lock_map 和 tuple_lock_map。
下图为一个lock table的例子。这个table维护了三张表锁请求。其中绿色表示授予了锁，蓝色表示正在等待。图中txn5已经获取了tableA的锁，正在等待tableB锁授予。图片参考 Database System Concepts  844页。



lock_table

lock manager处理锁请求流程：

• 当一个新的加锁请求到达时，如果请求队列存在，他在对应资源的请求队列末尾添加一条记录，否则创建一个新的队列。
  
  
  
  • 如果资源没有没有被锁住，那么授予锁。
    
  • 如果已经有事务获取了锁，检查锁的兼容性，如果兼容并且先前锁请求都被授予，才能获取锁，否则只能等待。这里保证了锁的请求不会饥饿。
    
  
  
• 当解锁请求到达时，lock manger把对应的加锁记录从请求队列中移除。检查后续等待获取请求能否被授予锁。
  

以上图为例，对某个表A。

• t1时刻，txn1 事务发起锁请求，创建了一个新的 request queue，直接授予锁。
  
• t2时刻，txn2 事务发起 SIX 锁请求，但是 SIX 与 S 不兼容，所以 txn2 阻塞在队列中
  
• t3时刻，txn3 发起 IS 锁请求，尽管 IS 锁与 授予了的S 锁甚至 SIX 锁都兼容，但是因为 txn2 没有被授予，所以 txn3 也不能被授予。
  
• t4时刻，txn1解锁，这时 txn1 和 txn2 同时被授予。
  

关于同时这个词，究竟是txn2还是txn1先被授予，都是可以的，并不和原则违背。下文会有详细解释。
LockTable流程

在bustub中，事务记录了获取锁的集合，所以在授予锁之前，先要进行一些检查，因此，具体的流程如下，以LockTable为例。

• 根据隔离级别，判断锁的请求是否合理，如果不合理，把事务设为abort，抛出事务异常。是否合理注释中已经有详细的解释，简单说下。(1):REPEATABLE_READ shrinking 阶段不允许加任何锁。(2): READ_COMMITTED shrinking 阶段只允许加S IS锁。(3):READ_UNCOMMITTED 只允许X IX锁。
  
• 检查锁是否要升级，以及升级是否合理，如果不合理，abort，throw。如果重复申请相同的锁，直接返回。
  尽管我们可以在 request_queue 中去检查，但是因为事务自己维护了加锁资源的集合，我们可以在进入临界区之前自行检查，减少 lock_manager 锁的争用。
  
• lock_table_map如果没有对应的请求队列，那么添加一条请求队列，添加记录，授予锁。
  
• 如果有相应的请求队列。
  
  
  • 如果要进行锁升级，
    
    
    • 检查锁升级是否冲突，冲突，abort, throw
      
    • 删除旧的记录，同时删除事务中的记录。
      
    • 将一条新的记录插入在队列最前面一条未授予的记录之前
      
    
    
  • 锁不用升级，将新的记录添加在请求队列末尾。
    
  • 检查兼容性，等待在条件变量上
    
  • 通过了兼容性检查，授予锁
    
  
  
• 更新事务的加锁集合。
  

// 等待在条件变量上
while(!checkCompability()){
    que->cv_.wait(lock)
}
// 另一种写法
que->cv_.wait(lock,[&](){
    return checkCompability();
})这里强调一下加锁顺序，在通过前两步检查后，

• 首先锁住全局的 lock_table_map，
  
• 如果能找到对应的请求队列，先锁住队列，然后解锁全局 lock_table_map，在进行下面的授予流程。顺序不能相反，否则事务的顺序会发生混乱。
  
• 如果不能找到，添加一条新队列，授予，然后解锁全局 lock_table_map
  

锁升级示意

锁升级示例，正在升级的锁请求应优先于同一资源上的其他等待锁定请求。
UnLockTable流程

UnlockTable 请求解锁正好相反，

• 检查是否持有要解锁的锁
  
• 检查是否还持有相应表的行锁
  
• 加锁全局 lock_table_map
  
• 找到对应请求队列，加锁request_queue，解锁 lock_table_map
  
  
  • 删除加锁记录
    
  • 在条件变量上 notify_all() 唤醒所有等待的线程
    
  • 解锁 request queue
    
  
  
• 判断事务是否需要进入SHRINKING状态。
  
• 更新事务锁集合
  

兼容性检查

这里有一个非常有意思的点是，notify_all()会唤醒所有等待在这个条件变量上的线程，而且顺序是不一定的。究竟应该怎么去检查唤醒的线程是否应该被授予锁，而不被唤醒顺序影响，当时困扰了我很久。
举个例子：



理想的唤醒顺序

• t1时刻 txn1 持有S 锁，阻塞了 txn2 , txn3
  
• t2时刻 txn1 解锁, txn2 先被唤醒，被授予了锁
  
• t3时刻 txn3 被唤醒，与持有锁 txn3 兼容，并且没有其它txn在等待，被授予了锁
  

这是一个理想的情况。

但是如果txn3先被唤醒：



非理想唤醒顺序

• t2 时刻 txn3 唤醒了，但是 txn2 没有被授予锁，所以继续阻塞
  
• t3 时刻 txn2 唤醒了，正常授予了锁
  

尽管txn2 后续解锁会唤醒 txn3 但是 txn3 明明可以与 txn2 同时被授予锁，却延后直到 txn2 解锁。
所以在进行兼容性检查时，不能简单查看先前记录中的granted字段判断是否被授予，而是应该重新计算先前的记录是否应该被granted，不能受到notify唤醒顺序的影响。这里就是我上文同时的意思，txn2 txn3不论唤醒先后顺序如何，应该都被授予锁。
Deadlock Detection

2PL不可避免的会产生死锁，所以要及时检测死锁打破依赖。这一节比较简单，bustub 会在创建 lock_manger 时，在后台创建一个周期的死锁检测线程。
每次死锁检测线程唤醒后都要检测死锁，流程如下:

• 遍历所有request_queue，建立一个 wait-for grapth 。
  
• 建图完成后，用DFS算法检测环
  
• 如果有环，找出换种最年轻的事务，也就是 txn_id 最大的事务
  
  
  
  • 将事务设为abort状态
    
  • 找到事务正在等待资源的request_queue。因为有table和tuple两种，所以需要额外的手段记录一下。
    
  • notify_all 将 request_queue上所有线程唤醒
    
    
    
    • 这里需要修改一下 上文的等待条件
      
    • 如果事务唤醒后发现自己已经abort，在request_queue中将自己删除，抛异常，返回
      
    
    
  
  
• 重复直到没有环
  

Concurrent Query Execution

这一节主要是根据隔离级别选择合适的表锁和行锁，并且判断是否需要手动解锁。
事务abort，commit 时会自动先解锁行锁再解锁表锁。abort 时还会自动对写集合中的操作回退。具体可以看一下 transaction_manager.cpp 文件。
事务abort时，需要回退写操作，table_heap.cpp 已经为我们维护了tuple WriteSet，我们只要在相应文件中维护一下 IndexWriteSet 。
加锁tip:

在 init() 中锁表，在 next() 中锁tuple。

• REPEATABLE_READ, 执行器中只加锁不解锁，需要自行判断一下应该加什么锁。
  
  
  
  • REPEATABLE_READ实行 严格的两阶段锁，最后 abort 或 commit 统一释放持有的锁，所以不会出现不可重复读，脏读。
    
  • 可能出现幻读。
    
  
  
• READ_COMMITTED，因为READ_COMMITTED 在GROWING状态解S锁不影响事务状态，需要提前解锁（锁未被升级的情况下）。
  
  
  
  • READ_COMMITTED 在GROWING状态，会解 S 锁，所以会两次读到不一样的数据。
    
  • 不会出现脏读，因为前一个修改数据的事务要加X锁，直到提交才会释放，对外界是完全隔离的。
    
  
  
• READ_UNCOMMITTED，读不加锁，写加锁。
  
  
  
  • READ_UNCOMMITTED对读不加锁，所以会读到未提交的数据。
    
  
  

另外需要注意一下执行过程中会自动发生锁的升级，所以还需要额外的逻辑判断是否已经持有锁或升级的锁，这时候就不要再申请了。
因为事务在声请锁时可能会发生死锁被lock_manger abort，抛出事务异常，所以执行器在加锁过程时要try catch捕获事务异常，再抛出执行异常。
官方给的测试用例比较弱，针对兼容性检查和隔离度测试我写了一些测试文件。测试文件中包括了autograde上卡了我比较多的测试，我也复现了出来。欢迎取用：
GitHub - wuxiao889/bustub_test