Task1: Lock Manager

在这一步需要实现3种隔离级别，RU、RC、RR，需要实现总共五种锁，S、X、IS、IX、SIX。使用的并发控制协议是2PL。

需要实现四个函数：

• LockTable
• UnlockTable
• LockRow
• UnlockRow

LockTable

1. 判断事务状态，如果事务已经是Aborted的状态，那么直接返回false，不需要为中止的事务分配锁。
2. 判断事务是否已经持有锁了，事务在内部维护了锁集，所以可以直接用事务的成员函数去判断，如果已经拥有了当前申请的锁，那么直接返回true。
3. 判断事务是否可以申请该锁，判断依据是事务的状态是Growing还是Shrinking，还有隔离级别等。
4. 获取请求队列，由于请求队列是多个线程共享的数据结构，需要先调用table_lock_map_latch.lock()进行加锁保护。然后根据表的oid获取对应的请求队列，同时将请求队列加锁。注意，一定要将请求队列加锁之后再释放table_lock_map_latch。
5. 判断是否是锁升级。如果是锁升级，那么说明请求队列中一定含有这个事务先前已经得到的锁，且这个锁的等级应该比申请的要低，否则反向升级需要中止事务。
   1. 我们可以遍历请求队列去找到某个request，它的txn_id和当前的事务id相同的话，就说明找到了先前的锁请求，这个请求一定是grant的，如果不是，那么事务会一直阻塞，不可能又发出一个锁申请。
   2. 检测是否同时具有多个锁升级，我们只能支持一个锁升级请求，如果队列里原先就有锁升级请求，那么同样Abort。
   3. 如果检测无误，那么将这个请求插入到请求队列中，非grant的请求里最前面的位置，因为锁升级的优先级是最高的，队列按照FIFO规则处理。
6. 如果不是锁升级请求，那么构造一个锁请求，插入到请求队列的队尾。
7. 尝试申请资源，如果不成功，调用请求队列的条件变量进行阻塞，等待下一次唤醒时，再次尝试申请资源。
8. 成功申请到资源，退出循环，更新事务的锁集，如果是锁升级，那么将队列的锁升级标志清空。

LockRow

与LockTable基本相同，但是最开始还需要检查是否拥有了对应的表锁，不能不申请表锁直接拿行锁。

UnlockTable

1. 检查该事务是否已经解锁了所有该表下的行锁。
2. 检查该事务是否持有对应的表锁。
3. 都没问题，说明是一个合法的解锁请求，遍历请求队列找到对应的锁请求，将其删除，然后更新事务锁集，之后唤醒请求队列的条件变量，让先前阻塞的事务可以尝试申请资源。

UnlockRow

与UnlockTable基本一致。

Task2: Deadlock Detection

中心思想就是根据事务之间的资源争夺关系，建立一张waits-for图，然后在这个waits-for图中找到环路，环路意味着死锁，需要把环路中的某个节点Abort，从而打破环路。

1. 拿到table_lock和row_lock，从而能够遍历对应的请求队列来建立waits-for图。
   1. 事务A和事务B共同申请资源C，A拿到了，B阻塞。则B向A连一条边。
2. 执行DFS去检测waits-for图中的环路。要求DFS的结果是确定的，这意味着我们搜索的方向必须得固定，从拥有最小txn_id的节点出发，每次选择邻居节点时也需要选择最小txn_id的节点。找到环路后，返回环路中拥有最大txn_id的节点作为abort对象。
   1. 因此，在DFS前，需要对waits-for图中的节点进行一个排序，还要对waits-for图中的所有边进行排序。
3. 循环调用DFS，直到找不到环路为止。图中可能存在多个环，需要一次性把所有环打破。一旦找到环，就将事务置为Abort，然后在waits-for图中删除该点对应的所有边。
4. 最后，唤醒所有的请求队列，然后请求队列都去尝试一次获得资源。

Task3: Concurrency Execution

需要修改SeqScan，Insert，Delete三个算子，让这三个算子拥有并发执行的能力。

SeqScan

在Init阶段锁住表，在Next阶段锁tuple就是核心思想。

首先要检测exec_ctx_->IsDelete()，检测这个seqscan是否是为了删除做准备的，如果是，那么表锁需要申请IX锁，行锁需要申请X锁。
否则只需要IS锁，行锁申请S锁。

如果是X锁，需要一直持有锁，直到事务中止为止。
如果是S锁，那么视情况而定，首先RU级别不需要申请S锁，RC和RR级别都需要。RC级别可以在用完tuple后立马舍弃锁，RR则需要持有直到事务中止。

Insert

Init阶段用IX锁住表即可，不需要特意去锁住行，因为InsertTuple自动帮我们做到了这一点。

然后需要维护写集，通过这两个API，InsertTableWriteRecord与InsertIndexWriteRecord。

Delete

只要正确实现了SeqScan，那么Delete不需要申请任何锁，只需要维护好写集即可。

至此所有的project都完成了，感谢CMU！