Project4——- CONCURRENCY CONTROL

Instroduction

前三个Lab中，我们分别完成了Buffer Pool、Hash Index、Executor的实现。但整个系统仍然缺少事务级别的查询，在本次Lab中，主要是通过实现一个Lock Manger来支持事务级别的并发查询，并且支持不同的隔离级别来适当授予和释放读写锁。

整个Lab分为三个部分：

Lock Manager的实现
死锁预防
完善Executor的代码以支持并发，并记录回滚所需信息

Lock Manager

第一个坑

刚看完整个实验要求并粗略读了代码框架后，我仍然有些迷糊，但记录了一些信息和疑问，在此记录一下：

对于一个Transaction，我们需要的是Tuple-Level的锁。
Lock Manager是对各个Tuple锁的封装
针对不同的隔离级别，对LockShared、LockExclusive、LockUpgrade、Unlock有何不同？

看到Lab的框架中，Lock Manager的构成主要如下，从理论来说，Lock Manager所提供的必要功能应该只有对Tuple的锁进行逻辑上的授予和回收，并不一定要真正的为其提供一个物理的Tuple锁。对于Lock Manager中的Latch的存在，只是为了合理地维护其保存的内部信息，例如源码中的lock_table_。

因此，在第一版的代码中，我并没有为每个Tuple提供一个锁（物理上的）。但这就引发了一个问题，当我在并发的情况下，同时想要获取多个Tuple的锁，这可能需要更改其请求队列中的信息，如果没有Tuple级别的锁，那我就必须在更改期间一直持有Lock Manager中的那个Latch，这就不能并发了，很不合理。最终，还是为每个Tuple的请求队列增加了一把锁tuple_mtx_来解决上诉问题，但这里需要注意的是，这个锁并不是说只有持有这个锁，才持有tuple的锁，这个锁在逻辑上只是维护并发时修改que信息的安全而设立的，仍然符合Lock Manager只是逻辑上的封装这一定义。

class LockManager {
    class LockRequestQueue {
        public:
        std::list<LockRequest> request_queue_;
        std::condition_variable cv_;
        txn_id_t upgrading_ = INVALID_TXN_ID;
        std::mutex tuple_mtx_;  // 并不是说只有持有这个锁，才持有tuple的锁，这个锁在逻辑上只是维护并发时修改que信息的安全而设立的
    };
    
 public:
  LockManager() = default;
  ~LockManager() = default;

  bool LockShared(Transaction *txn, const RID &rid);
  bool LockExclusive(Transaction *txn, const RID &rid);
  bool LockUpgrade(Transaction *txn, const RID &rid);
  bool Unlock(Transaction *txn, const RID &rid);
    
 private:
  std::mutex latch_;
  std::unordered_map<RID, LockRequestQueue> lock_table_;
};

第二个坑

第二个坑主要就是关于对于request_queue_的理解。在初看代码后，我对其的理解就是把它当成一个队列来使用，当有事务想要请求获得锁，就在队列末尾增加请求，然后重复检测自己的请求是否在队头，成功获取后就弹出队列，有点类似生产者消费者模型。当然请求在队头时也不能轻易地获取锁，还需要判断当前Tuple的状态（空闲、读、写），这个信息需要额外记录。

这样设计最大的问题就在于，请求的信息在成功获取锁后被丢掉了，这些信息是不能丢掉的，整个Lock Manager是需要记录当前各个Tuple的使用情况的，如果直接弹出队列，那么肯定需要重新记录一下这些信息。不是说这种实现不可行，主要原因就是增加了复杂性。所以我觉得这里的que类型使用的是list也算是一种暗示，与其把它理解成队列，不如理解成一张表，表内记录了所有想用的和在用的请求，这样后续就会方便很多。

明确后request_queue_的使用后，对于LockShared、LockExclusive、LockUpgrade以及Unlock的逻辑就相对明确了。

对于LockShared，在请求加入链表末尾后，判断其之前所有的请求是否都已经获取成功，并且其中没有写锁。如果成立，则授予请求。
对于LockExclusive，在请求加入链表末尾后，判断其是否在链表头。如果成立，则授予请求。
对于LockUpgrade，查找链表中的请求，如果不在读，就返回失败；否则，将原读请求删除，添加写请求至所有未成功获取的请求的最前面，然后判断，判断条件同LockExclusive。为什么要添加到最前面，因为我已经在读了，升级的优先级肯定高于其他请求。
对于Unlock，查找链表中的请求，然后将其删除，然后notify。

DEADLOCK PREVENTION

这个死锁是事务级别的锁，简单的例子就是：事务A在持有Tuple1的情况下想要持有Tuple2，事务B在持有Tuple2的情况下想要持有Tuple1。这就导致了死锁。对于死锁，常见的解决方式有两种，一种是死锁解除，一种是死锁预防。本次实验中，需要使用的方式是死锁预防。

死锁解除的方式通常是开一个后台进程，定期判断所有事务的等待关系是否存在环，如果存在环就说明发生了死锁，需要Abort掉一个Victim，Victim的选择方式有多种，比如按时间戳，按照执行进度，按照锁持有数量，按照回滚代价等。

死锁预防的方式则主要有两种，Wait-Die（老的等新的），Wound-Wait（老的抢新的）。这个名字怎么记呢，记住第一个单词的状态表示老的事务的状态即可。本次实现的Wound-Wait，代码中就是在check函数中添加了如下逻辑，如果老的事务在申请请求时，发现当前链表中，在它之前有事务比他新，则它可以直接将新的事务Abort掉。对于share中的Abort，只Abort掉比它新的写锁请求。这里有个疑惑就是，到底是无论是否持有都一律Abort掉，还是只Abort掉持有的事务，测试中是前者，认真思索了下，确实前者合理，假如一个事务比当前老的想要获取请求的新，且当前没有持有，那么如果当前没有把它Abort掉，那么在之后它由于在队列前，它先持有，老的还是无法持有，这就仍然有死锁的风险，虽然说老的在之后的check时会Abort掉前面持有的，但是老的在没有被notify的时候，是不会持续进行check的，不如一律Abort掉。

CONCURRENT QUERY EXECUTION

Isolation Level：

SERIALIZABLE：要X锁和S锁，按照S2PL协议使用，还需要对Index加锁
REPEATABLE READ：需要X锁和S锁，按照S2PL协议使用
READ COMMITTED：S锁用完就释放
READ UNCOMMITTED：不需要使用S锁

本次实验只用对下面三个等级进行实现。代码中主要分两个部分，一个LockShared和LockExclusive在REPEATABLE READ等级下，需要判断TXN的状态是否符合2PL的要求。另一个就是对各个Executor进行完善。

llf333

cmu15-445/645 2021 Project4