CMU 15-445 2021 Fall Project4 Concureency Control

CMU 15-445
,

项目 4 我们需要为 DBMS 实现一个锁管理器，并且利用锁管理器来实现并发的执行查询计划。锁管理器负责追踪事务涉及到的元组级的锁（行锁），并且基于隔离级别来授予/释放共享锁（Shared Lock）和排它锁（Exclusive Lock）。

任务如下：

  1. Task #1 - Lock Manager
  2. Task #2 - DeadLock Prevention
  3. Task #3 - Concurrent Query Execution

本次项目的难度集中在 Task #1 和 Task #2，如果一些概念不清楚的话很容易到处出现问题，所以在写之前先把隔离级别、两段式锁还有 Wound-Wait 等概念理清楚再来动手写代码。并且一定一定听项目说明中说的先把 transaction.h和 lock_manager.h 中的 API 了解清楚。

https://juejin.cn/post/7208793045479505980

TASK #1 - LOCK MANAGER AND TASK #2 - DEADLOCK PREVENTION

任务 1 中我们要实现一个全局的锁管理器，每次有事务要访问/修改某个元组时，我们就用锁管理器对这个元组上锁，并且锁管理器要根据事务的隔离级别来授予或者释放锁。任务 2 需要使用 WOUND-WAIT 算法实现死锁预防

在 2PL 下各个隔离级别的行为：

  • Read Uncommitted：读取不需要获取锁，但是写需要获取排他锁，用完直接释放，不需要等待提交。
  • Read Committed：读取需要共享锁，写需要排他锁，用完直接释放，不需要等待提交。
  • Repeatable Read：读取需要共享锁，写需要排他锁，不能直接释放，必须等到事务提交或者中止时才能释放。

清楚了在 2PL 下各个隔离级别下的不同行为，再来实现 Lock Manager。

NeedWait

我实现了一个 NeedWait 函数来判断事务是否需要阻塞等待，并且使用 WOUND-WAIT 来实现死锁预防，基本的使用方式如下：

1
2
3
4
5
6
7
8
std::unique_lock<std::mutex> guard(latch_);
// ...
while (NeedWait(txn, rid, LockMode::EXCLUSIVE)) {
	lock_table_[rid].cv_.wait(guard);
    if (txn->GetState() == TransactionState::ABORTED) {
      return false;
    }
}

NeedWait 函数传入事务想要获取的锁的类型，根据锁类型来判断是否需要阻塞等待：

  1. 事务想要获取共享锁：如果等待队列中有已经授予的排他锁，那么事务阻塞等待。
  2. 事务想要获取排他锁：如果等待队列中有已经授予的锁，那么事务阻塞等待。

初步判断过后，如果不需要阻塞等待，直接能拿到锁，就返回 false，没有必要再进行死锁预防了（现在并不会产生竞态）。但是如果需要阻塞等待，这时再进行死锁预防，进行死锁预防前将返回值置为 false。

Wound-Wait 概念如下：

  1. Timestamp(T**n) < Timestamp(Tk)*, then Tn forces Tk to be killed − that is Tn “wounds” Tk. *T**k is restarted later with a random delay but with the same timestamp(k).
  2. Timestamp(T**n) > Timestamp(Tk)**, then Tn is forced to “wait” until the resource is available.

将返回值置为 false，遍历等待队列：

  • 当遇到一个事务的 id 比自己大（这个事务比自己年轻）并且这个事务与自己冲突时，就将其强制中止，接着跳过这轮循环；
  • 当遇到一个事务的 id 比自己小并且这个事务与自己冲突时，就需要阻塞等待；
  • 遍历结束后，如果发生了中止，就进行一次通知，唤醒那些被中止的事务返回；
  • 及时清理掉等待队列中被中止的事务，否则会出现一个 younger 在等待一个被中止的 older 释放锁。

最后返回最终的判断结果。

NeedWaitUpgrade

这个函数用作 LockUpgrade，由于 LockUpgrade 是在持有共享锁的情况下升级，所以不需要初步判断是否需要等待，直接进行死锁预防即可，并且需要获取的锁类型固定是排他锁。

同样将返回值置为 false，遍历等待队列：

  • 当遇到一个事务的 id 比自己大并且这个事务与自己冲突时，就将其强制中止，接着跳过这轮循环；
  • 否则是肯定要等待的，因为要获取的是排他锁。
  • 遍历结束后，如果发生了中止，就进行一次通知，唤醒那些被中止的事务返回；
  • 及时清理掉等待队列中被中止的事务。

最后返回最终的判断结果。

LockShared

这个函数用于获取某个元组的共享锁，调用该函数的线程会阻塞到成功获取锁或者该事务中止。在尝试获取锁之前，先根据 2PL 和 事务的隔离级别，来提前做一些判断：

  1. 如果该事务已经中断，直接返回 false。
  2. 如果该事务处于 Shrinking 阶段，就意味着不能再获取锁了，直接中止事务，并抛出异常。
  3. 如果该事务的隔离级别是 Read UnCommitted，就意味着该事务进行读的时候不需要获取锁，直接中止事务，并抛出异常。
  4. 如果事务已经获取了共享锁，那么就直接返回 true。

然后新建一个 LockRequest，并将其插入到对应的等待队列中去，开始调用 NeedWait 进行判断，如果该事务在等待时中止了，就返回 false。当成功获取了共享锁时，把该线程在等待队列中的 LockRequest 的 granted 属性设置为 true，该事务进入 Growing 阶段，将获取到的共享锁放入事务的 SharedLockSet 中并返回 true。

LockExclusive

该函数的实现跟 LockShared 非常类似，需要注意的就是即使事务的隔离级别是 Read Uncommitted 它也是要获取排他锁来进行写操作的，这时候不能直接中止。

LockUpgrade

之前对锁升级的概念存在误区，写成了先将共享锁释放掉，再去尝试获取排他锁，后来在一篇帖子中看到了这样一段话：

Upgrade: A S(A) can be upgraded to X(A) if Ti is the only transaction holding the S-lock on element A.

https://www.geeksforgeeks.org/lock-based-concurrency-control-protocol-in-dbms

即一个元组的共享锁在只有一个事务持有时，就可以将其升级成排他锁，所以锁升级是在该事务持有共享锁的情况下进行的，否则锁升级好像就没有什么意义了，就是直接获取排他锁。

同样，在等待升级锁之前，也可以先进行一系列判断：

  1. 如果事务已经中断、事务没有持有该元组的共享锁或已经有事务（lock_table_[rid].upgrading_ != INVALID_TXN_ID）在等待升级时直接返回 false。
  2. 如果事务已经持有排他锁则直接返回 true。
  3. 如果事务处在 Shrinking 阶段，直接中断事务并抛出异常。

接下来调用 NeedWaitUpgrade 去尝试升级锁。如果升级成功，把该线程在等待队列中的 LockRequest 的 lock_mode_ 属性设置为排他锁，并将该等待队列的 upgrading_ 设置为 INVALID_TXN_ID，然后把排他锁放进 ExclusiveLockSet 中，将之前的共享锁从 SharedLockSet 中移除，并返回 true。

Unlock

  1. 先判断事务有没有占用该元组的锁，如果没有直接返回。
  2. 开始遍历等待队列，如果找到了自己，就将对应的 LockRequest 移除，并发起一次通知。
  3. 如果没有找到直接返回 false。
  4. 如果事务的隔离级别是 Repeatable Read，并且处于 Growing 阶段，那么事务此时进入 Shrinking 阶段。
  5. 将锁从事务的 LockSet 中移除。

TASK #3 - CONCURRENT QUERY EXECUTION

任务 3 要将我们实现的锁管理器应用起来，去修改以下 Executor：

SeqScanExecutor

在所确定访问的元组后，即遍历到了那个位置的时候（这个时候 rid 才能确定，函数参数是用作返回值的，遍历时还是空值）去获取共享锁。在将参数的值设置好后再将锁释放（Read Uncommitted、Read Committed 隔离级别下直接释放，如果是 Repeatable Read 则不需要自己编写代码）。

InsertExecutor

在所确定访问的元组后获取排他锁（如果已有排他锁就不需要获取，如果已有共享锁就进行升级，否则再获取排他锁）。更新完索引还要往 index_write_set_ 中插入一条记录，注意 tuple 字段填的是插入表的那个元组。最后释放锁。

UpdateExecutor

总体跟 InsertExecutor 类似，但是 UpdateExecutor 在将元组更新后，还需要插入一条记录到 table_write_set_ 中，tuple 字段是更新前的元组。并且再往 index_write_set_ 中插入记录时，还需要将记录的 old_tuple_ 字段也附上，即更新前的元组。最后释放锁。

DeleteExecutor

跟 InsertExecutor 几乎完全一致。

Conclusion

四个项目终于都完成了，虽然 Project 4 实现起来没有 Project 2 这么困难，但是感觉理解的并没有那么清晰，还需要阅读更多的资料再结合项目代码好好读一遍，而且这次提交了连 leaderboard 都没有，还有很大的优化空间。