CMU15445 2022fall project4

这个project整体难度稍微高于project3，主要难点在于task1。

Task1

这部分实现一个锁管理器处理事务对表和行的加锁解锁，是这个project中最复杂的部分。

问题：

• 关于为什么在各个隔离级别下，锁要设计成下面这样？

  REPEATABLE_READ:
     The transaction is required to take all locks.
     All locks are allowed in the GROWING state
     No locks are allowed in the SHRINKING state
  
  READ_COMMITTED:
     The transaction is required to take all locks.
     All locks are allowed in the GROWING state
     Only IS, S locks are allowed in the SHRINKING state
  
  READ_UNCOMMITTED:
     The transaction is required to take only IX, X locks.
     X, IX locks are allowed in the GROWING state.
     S, IS, SIX locks are never allowed
  

  1.在课程学习的过程中，我以为2PL就是在GROWING阶段加锁，在SHRINKING阶段解锁，看到上面这个锁的设计时，有点一脸懵逼，为什么上面的READ_COMMITTED可以在SHRINKING阶段加读锁？其实这个问题不难理解，二阶段锁是一个宽泛的概念，通过变种的二阶段锁来完成不同的隔离级别要求，比如上面的REPEATABLE_READ级别，GROWING阶段只允许加锁，SHRINKING阶段在不允许加锁的同时也隐含了不允许解锁，统一在Commit时解锁，因为要想解决不可重复读和脏读这两个问题，就得使用这种严格的二阶段锁。

  2.为什么READ_UNCOMMITTED级别不允许加S, IS, SIX？READ_UNCOMMITTED级别的主要特点是它允许读取未提交的数据，这意味着它不会等待其他事务释放锁或完成其操作。因此，加S、IS或SIX锁都会引入额外的等待和同步机制，这与READ_UNCOMMITTED级别的设计初衷相违背。

• 为什么要使用线程等待模型？

这种模型允许多个线程以线程安全的方式协作和共享资源，同时只有在满足特定条件时才执行特定的操作。使用条件变量可以减少轮询（一个低效且占用CPU的检查条件方式），因为它允许线程在条件不满足时休眠，从而提高了程序的效率和响应性。

注意点

为了方便的进行内存管理，将一些变量定义成共享指针或许更好用一些。

Lock

1.检查事务状态， 不同级别的事务隔离级别下的锁设计，给行加锁时额外需要注意锁的类型，检查是否有表锁。

2.获取对应表的锁请求队列

如果不存在，直接创建一个队列和一个新的请求节点，并把锁直接授予（因为此时说明在此表上不存在任何锁请求），同时加入table_lock_set_中，返回true。

如果存在，获取队列并进入下一步。

记得锁上table_lock_map_latch_和lock_request_queue.latch_，并及解锁table_lock_map_latch_。

3.升级锁

遍历锁请求列表上，当前事务在这张表上的其他锁请求。

• 当前表上如果有其它事务也在进行锁升级，则同时只允许一个锁升级，直接终止当前事务，抛出 UPGRADE_CONFLICT 异常。

• 当前锁请求等级如果等于之前的等级，直接返回true，表示重复锁请求。

• 然后检查升级是否兼容，锁不兼容直接终止事务并抛出INCOMPATIBLE_UPGRADE异常，锁兼容时，尝试升级锁。

升级锁的步骤：

• 删除原来的请求锁节点，在事务的对应table_lock_set_中删除当前请求。
• 创建新的锁升级后的节点插入锁请求队列（插入的位置位于第一个没有授予锁的锁请求节点之前），并把upgrading_设置为当前锁请求的事务id。
• 阻塞直到获取锁成功。
• 把upgrading_设置为INVALID_TXN_ID，设置granred_为true，将tableid插入table_lock_set_中，返回true。

4. 处理普通锁请求

步骤和上面的升级锁类似，不过这次应该插入到队尾，根据FIFO机制来获取锁。

• 关于上面的阻塞进程直至获取锁成功这个步骤，我们应该如何判断可以获得锁呢？

其实要检查当前升级的锁请求和在这个队列中靠前的那些事务的锁请求是否可以兼容，判断方法为下图。

此升级请求前不存在未授予的锁请求，因为我们刚刚把它插入到了第一个未授予的锁请求之前，所以当前状态只需要判断是否和前面那些已授予的锁请求兼容。

但如果是一个普通请求在阻塞时，如若能获取锁，他需要和前面未授予的锁请求相兼容，因为讲义中要求我们所有兼容的锁请求需要一起被授予，这一点很重要。

Unlock

1. 解锁表锁时需要检查当前表上是否有行锁，如果有，则直接abort并抛出TABLE_UNLOCKED_BEFORE_UNLOCKING_ROWS异常，同时检查当前表请求队列是否存在。
2. 获取锁请求队列
   • 设置SHRINKING状态
   • 删除请求并删除对应lock_set中的请求
   • notify_all该请求队列上的条件变量，通知其他节点
3. 找不到对应的事务请求说明节点不存在，抛异常。

Task 2

这部分实现一个后台运行的检测环程序，框架已经搭建好了，实现起来比较轻松，后台程序的执行在LockManager的构造和析构函数中实现的。

  LockManager() {
    enable_cycle_detection_ = true;
    cycle_detection_thread_ = new std::thread(&LockManager::RunCycleDetection, this);
  }

  ~LockManager() {
    enable_cycle_detection_ = false;
    cycle_detection_thread_->join();
    delete cycle_detection_thread_;
  }

注意GetEdgeList返回的所有边的vector仅仅用于测试程序使用的。

可以定义一个有序集合把所有事务id都保存下来，方便后面的使用。

1.AddEdge函数中构造txn_set_和waits_for_

2.RemoveEdge函数和GetEdgeList函数比较简单，主要看HasCycle和DFS，而RunCycleDetection负责把他们组织起来，可以最后再实现。

DFS

• 从小到大对事务节点进行DFS，如果找到一个环就返回。

• 找环时定义一个path_set_用于保存搜索的路径，从路径中选择事务id最大的（也就是最年轻的节点）进行返回。

• DFS时还需要定义一个finish_set_用于保存已经遍历过的节点，利用waits_for_获取当前事务节点所等待的事务节点，记得排序一下，保证确定性，记得DFS过程中的恢复现场，将节点从path_set_中拿出。

RunCycleDetection

• 先遍历所有的表请求队列和行请求队列，通过AddEdge构造出waits_for_，同时保存事务id对应的表id和行id，用于后面唤醒两个队列的其他事务
  • 关于怎么构造waits_for_，遍历队列时，保存所有已授予锁的节点，如果存在未授予锁的节点，将它和它前面已授予锁的节点进行组合为一条边
• 循环判断是否有环，如果有，根据返回的事务节点，删掉wait_for_中含有当前事务节点的边（包括到达它的边和从它出发的边）
• 记得清空一下所有用到的类内变量

Task 3

这部分负责对三个算子进行事务并发控制，这三个主要负责和真实的数据打交道，其他的都是一些中间产物。

SeqScanExecutor

• 在READ_COMMITTED和REPEATABLE_READ级别下，获取表之前给表加IS锁，获取行之前给行加S锁，READ_UNCOMMITTED级别下不需要加写锁。

• 读取完成时，在READ_COMMITTED级别下，释放所有锁。

InsertExecutor and DeleteExecutor

• 获取表之前加IX锁，获取行之前加X锁。

• WriteSet已经在调用InsertTuple中维护了，我们只需要调用事务的AppendIndexWriteRecord维护索引记录即可。

Summary

完结撒花！！！

后面的可选阶段我还是没做，希望能快点找到实习，然后回来再肝一下并深挖一下这么好的开源项目。