Project4：Concurrency Control

0 前言&要求

该部分是做一些并发控制的功能，在DBMS中实现一个Lock Manager，使用其来支持并发执行。锁管理器负责跟踪向事务发出的行级锁，并支持根据隔离级别适当的加上或释放共享锁或排他锁。

LM的基本思想是：维护一个关于活动事务当前持有的锁的内部数据结构，然后事务在访问数据项之前向LM发出锁请求，LM将根据情况决定锁授予该事务、阻止该事务还是终止该事务。在Task1中就要实现LM中的相关API

LockShared(Transaction, RID)：Transaction txn试图对记录id RID获取一个共享锁。这应该在等待时被阻塞，并且应该在授予时返回true。如果事务回滚(中止)则返回false。
LockExclusive(Transaction, RID)：Transaction txn图对记录id RID进行排他锁。这应该在等待时被阻塞，并且应该在授予时返回true。如果事务回滚(中止)则返回false。
LockUpgrade(Transaction, RID)：Transaction txn试图在记录id RID上将共享锁升级为排他锁。这应该在等待时被阻塞，并且应该在授予时返回true。如果事务回滚(中止)则返回false。这还应该中止事务，如果另一个事务已经在等待升级其锁，则返回false。
Unlock(Transaction, RID)：解锁由事务持有的给定记录id标识的记录。

在设计时，还需要考虑隔离级别READ_UNCOMMITED，READ_COMMITTED和REPEATABLE_READ。LM将根据事务隔离级别来授予或释放锁。

Task2是说实现的锁要注意进行死锁预防，使用WOUND-WAIT算法来决定中止哪些事务。

Task3也就是将实现好的LM应用到Lab3中Executor里，以此增加对并发查询的支持。

1 实验分析

1.1 数据结构

Lock_Manager中有一个lock_table_哈希表，它的类型为std::unordered_map<RID, LockRequestQueue>。其中，又包含了LockRequestQueue和LockRequest。

class LockRequest {
    public:
    LockRequest(txn_id_t txn_id, LockMode lock_mode) : txn_id_(txn_id), lock_mode_(lock_mode), granted_(false) {}

    txn_id_t txn_id_;
    LockMode lock_mode_;
    bool granted_;
};

class LockRequestQueue {
    public:
    std::list<LockRequest> request_queue_;
    std::condition_variable cv_;
    txn_id_t upgrading_ = INVALID_TXN_ID;
};

表示了，对于每个RID（也就是每个tuple），都有一个请求队列LockReuqestQueue，其中有一个list<LockRequest> request_queue_;来存储当前对该tuple的锁请求事务，LockRequest也就是用于描述该事务的id，锁类型，是否授予信息的。

请求队列

在《数据库系统概念》中有关锁管理器的算法。

锁管理器算法

1.2 死锁预防

wound-wait通过使用抢占与事务回滚来实现死锁预防。当事务$T_i$申请的数据项被$T_j$所持有，当$T_i$的时间戳大于$T_j$的时间戳时（$T_i$比$T_j$年轻），允许$T_i$等待。否则，$T_j$回滚（$T_j$被$T_i$伤害）。

1.3 2PL

实验建议使用严格两阶段封锁协议来实现某些隔离级别，也就是整个事务分为两个阶段，前一个阶段为加锁（GROWING），后一个阶段为解锁（SHINKING）。在加锁阶段，事务只能加锁，也可以操作数据，但不能解锁，直到事务释放第一个锁，就进入解锁阶段，此过程中事务只能解锁，也可以操作数据，不能再加锁。

1.4 隔离级别

实验需要支持三种隔离级别：

READ_UNCOMMITED：读未提交，这种在需要时加写锁即可，因为允许脏读的发生，读锁不需要加
READ_COMMITED：读已提交，这要解决脏读的问题，解决方案就是读时上读锁，读完解读锁；写时上写锁，但等到commit时才解写锁；读时上读锁，读完解读锁。这样，永远不会读到未commit的数据，因为上面有写锁。
REPEATABLE_READ：可重复读，这需要解决不可重复读的问题了。也就是一个事务在读两次数据不会被其他事务的写干扰，这里需要用到二阶段封锁协议（2PL）。这样，第二次读取时，前一次的读锁还在，避免了中途被修改

2 实验过程

2.1 LockShare（共享锁）

首先检查txn是不是aborted，是则返回false；

然后检查txn的隔离级别，如果是READ_UNCOMMIED，是不需要共享锁的，将事务状态设置为ABORTED，返回false

检查txn的状态是否是shrinking。根据2PL的性质，该状态下不能申请锁，设置事务状态为ABORTED，返回false

判断该事务是否为该tuple加锁过，如果加锁过，返回true

然后遍历锁请求队列lock_table[rid].request_queue，如果当前事务（txn）为老事务并且占用独占锁的为新事务，则将新事务（遍历到的事务）abort掉；

如果当前事务为新事务，老事务为独占锁，则等待，但也要向队列中插入该事务以及sharedlockset中进行标记，然后发出等待信号。

如果遍历过程没有出现以上情况，说明锁队列为空或占用锁队列的均为共享锁，将当前事务状态设置为GROWING并且向队列添加事务即可。

2.2 LockExeclusive（排他锁）

与共享锁流程大同小异。要注意，如果是shrinking，根据2PL，不能继续申请锁，并且要在可重复读的隔离级别下。

而且，既然是获取排他锁，那么其和其他锁都是不相容的，也就是说，要求该次请求必须为第一个请求，锁才能授予。那么在遍历队列时，如果当前事务为新事务，则要直接abort。

2.3 LockUpgrade（锁升级）

同样的，但锁升级需要判断该锁是否已经授予，如果已经授予，则返回false即可。否，则标记正在上锁。

遍历队列，如果当前事务为老事务，则abort掉新事务的排他锁；当前事务为新事务，则进行等待。

否则，进行锁升级，取出对头元素，设置为排他锁。

2.4 UnLock（解锁）

比较简单，遍历锁队列时，找到该事务，将该事务解锁（从队列中删除），再notify所有在该队列中睡眠的事务，因为这种情况下可能会有多个事务都获得锁。然后记得从事务对应的LockSet中删除该RID。还需要记得将事务状态设置为shrinking（repeatable read如果unlock是要shirnking的，read commited如果unlock的是sharelock则不用）。

2.5 并发执行器

这个部分是增加对并发query execution的支持。

seq_scan_executor

该executor就是在渎之前要加读锁，并且要注意未提交读情况不需要加锁。并且在Next结尾，如果隔离级别为READ_COMMITED，则直接释放该锁

update_executor

更新则要加锁独占锁，如果该锁已经被读锁占用，则进行升级锁，否则，加上独占锁。同样，提交读才需要解锁

这里要记得记录事务变更

IndexWriteRecord write_record(tuple_rid, table_info_->oid_, WType::DELETE, new_tuple, index->index_oid_,
                              exec_ctx_->GetCatalog());
write_record.old_tuple_ = old_tuple;
txn->GetIndexWriteSet()->emplace_back(write_record);

insert_executor

和更新一样

delete_executor

同上= =