Lab4

由于五一临近考试，再加上后续还需要准备各种机试以及408等，整个Lab4做的比较的草率，基本上只实现了最基础的功能，Leaderboard Bonus的各种优化都没去实现，确实是没时间了，在这里也只能简单记录一下

Task1 - Lock Manager

当事务尝试读取或者修改Tuple时，TableHeap和Executor类都会使用 Lock Manager去尝试在一个Tuple上获取锁（通过RID）

支持表级别和Tuple级别的锁，以及读未提交，读提交，可重复读三种隔离级别，Lock Manager通过隔离级别进行加锁

Hints

通过LockRequestQueue来保存等待获取的锁，对于Tuple和对于Table
考虑何时进行锁升级，进行锁升级时，需要对LockRequestQueue做什么
当获取到锁之后，通过条件变量来通知尝试获取锁的事务
需要对事务的状态进行维护，如GROWING，SHRINKING，当进行了unlock时，就涉及到状态的切换（具体取决于隔离级别）
通过*lock_set_来记录一个事物获取的所有的锁，当事务进行提交时，lock_manager释放其相关的锁
将一个事务的状态设置为ABORTED隐含地中止了该事务，但直到TransactionManager::Abort被调用时才会显式地中止。你应该通读这个函数和提供的测试，以了解它的作用，以及你的锁管理器在中止过程中是如何使用的。

实验手册当中并没有提供太多有用的信息，在lock_manager.h的注释当中，涉及到了具体应当如何实现，这里挑有用的翻译一下，按照整个注释提供的信息，捋顺一下基本就能够完成功能了。

LOCK NOTE

LockTable()和LockRow()均为阻塞的方式，应当等到锁授予之后再return，对于中止的事务应当拒绝授予，并返回false
支持的锁模型：
- Table级的支持所有类型的锁
- Tuple级别的不支持意向锁
隔离级别：只有符合当前隔离级别的锁，并且根据当前情况允许，才能授予锁，例如，READ_UNCOMMITTED下不支持S/IS/SIX锁，相似的X/IX锁在SHRINKING阶段同样不支持
- REPEATABLE_READ：可以获取所有级别的锁，只有在GROWING阶段才能够获取锁
- READ_COMMITTED：可以获取所有级别的锁，在GROWING阶段可以获取所有的锁，在SHRINKING阶段只能获取IS，S锁
- READ_UNCOMMITED：只支持IX,X锁，并且只在GROWING阶段可以获取
在在Tuple上获取锁的时候，需要保证首先在Tuple所属的Table上获取到对应的锁，
锁升级：对于一个当前事务已经上锁过的资源：
- 要获取的和之前上锁的类型一致，直接返回
- 不允许多个事务同时进行锁升级，通过一个标志位来进行判断
- 如果锁模型不一样，考虑对其进行升级，允许的类型如下：
  1 2 3 4
  * IS -> [S, X, IX, SIX] * S -> [X, SIX] * IX -> [X, SIX] * SIX -> [X]
如果对一个事务授予了一个锁，那么需要对事务的锁集合进行适当的更新

UNLOCK NOTE

UnlockTable() UnlockRow()尝试在某一资源上释放锁，需要确保当前事务持有该锁，如果没有持有该锁就释放则抛出异常
只有在没有持有该Table所下属的Tuple时，才能释放Table上的锁，否则抛出异常
事务状态更新：根据隔离级别，释放锁会导致事务从GROWING想SHRINKING转变，只有释放S/X锁才会改变事务状态。
- REPEATABLE_READ：释放S/X导致转变为SHRINKING
- READ_COMMITTED：释放X锁导致向SHRINKING转变，释放S锁无影响
- READ_UNCOMMITED：释放X锁导致向SHRINKING转变，READ_UNCOMMITTED不支持S锁

Lock

根据上述，基本可以捋清楚整个LockTable的过程，主要分为几个阶段，前几个阶段一直尝试抛出异常，中止掉一些特殊情况，之后才尝试对锁进行获取。

1.异常处理

可能有的异常为：

锁类型不支持：READ_UNCOMMITED下尝试获取S/IS/SIX，
阶段错误，即在Shrinking阶段尝试获取锁：
- REPEATBLE_READ条件下尝试获取任意类型的锁
- READ_COMMITTED条件下获取X IX SIX
- READ_UNCOMMITTED条件下获取任意类型的锁
对于LockRow，还有还未在Table上加锁就在Row上加锁

2.获取到Table对应的LockRequestQueue

通过锁保护并发安全，如果存在则直接获取，然后释放锁，如果不存在则创建一个。

LockRequestQueue所记录的是对于一个Table上相关的锁的持有情况，即只有确定需要要申请锁，才将锁加入到其中，之后只有锁释放的时候，才将其从队列当中移除，因此主要起到两个作用：

记录当前Table当前Table上锁的申请顺序，根据申请顺序来确定是否需要授予锁或者进行锁升级
维护已经申请下来的锁，控制并发，直至释放锁时才将其从队列当中移除

而如果当中只有一个且为当前事务新创建的Lock_Reqeust的话，则证明当前没有任何一个事务在当前资源上申请锁或者持有锁，那么自己就是优先级最高的，即不需要等待其他的锁授予完，也不需要锁升级，也不需要检查是否冲突，直接授予锁即可。

3.检查锁升级

如上面所说，该Table的queue当中同时存在申请锁和持有锁的记录，根据granted字段来判断

首先判断是否需要进行锁升级，即当前的事务之前是否有在该资源上持有锁，如果有，则考虑进行锁升级，如果没有则跳过这一步，直接尝试加锁

锁升级的前提条件为当前没有任何其他的事务在进行锁升级，通过一个标志位来判断，如果有则中止事务，抛出异常。该标志位在进行锁升级时置为当前事务的tid，在完成锁升级，即获取到了锁之后，置为一个空的tid。

到目前已经满足的锁升级的外部条件，即当前事务之前在该资源上持有了一个锁，并且没有其他的事务正在进行锁升级，此时需要判断内部条件，即锁的类型是否满足升级条件：

1
2
3
4
   *        IS -> [S, X, IX, SIX]
   *        S -> [X, SIX]
   *        IX -> [X, SIX]
   *        SIX -> [X]

如果之前持有的锁的等级高于当前持有的锁，那么清空标志位，结束锁升级，也不需要授予新的锁，直接返回。
如果当前的锁满足升级条件，那么释放之前的锁，将锁升级的过程视为一次新的锁的获取，设置升级的标志位，在第一个还未授予的Lock_Reqeust之前添加一个新的LockRequest从而可以保证可以立刻对其进行锁升级，如果不满足升级条件，则中止事务，抛出异常

4.获取锁

我目前初步的想法是如果能执行到这一步，则证明无需进行锁升级，常规加锁，即获取到资源对应的队列，新建一个LockRequest请求，将其添加到队列当中。之后根据队列当中的锁情况来进行锁的获取。

最开始我的想法是单独创建一个线程，不断的去轮询所有队列，如果发现可以授予锁，那么则授予锁，并通过条件变量来通知调用Lock的线程，告知其已经授予锁，可以从阻塞当中苏醒返回，而调用Unlock的线程只需要释放锁，不需要传递或者发出任何信号。整体实现上有点像6.824当中日志提交向上层告知Apply信息的过程，但是后来想了想，也看了一下别人的博客的思路，感觉没必要那么麻烦。信号发送的工作交给调用Unlock的线程即可，大致思路如下：

调用Lock将新创建的LockRequest加入到队列当中
之后通过条件变量的形式，反复判断是否满足获取锁的条件，如果不满足则通过条件变量阻塞
如果有其他的线程释放锁了，通过notify_all进行通知，那么此时就会从阻塞当中恢复，重新判断一次是否能够加锁，如果能则加锁并返回一个false，跳过条件变量，后续直接返回

GrantLock

单独封装成一个函数，在作为条件变量while的进入条件，遍历当前的队列，如果在此次申请的锁之前还有未授予的锁(granted == false)，那么无法授予，返回false，交给条件变量去等待。如果当前的锁为队列当中第一个未授予的，那么判断是否兼容，如果不兼容则返回false，等待发生冲突的锁释放，兼容则返回true，授予锁并跳过条件变量。

在调用GrantLock时队列当中至少存在一个lock_request，即当前事务新创建的，如果不存在则证明出现了问题，返回false

Unlock

Unlock的思路比较简单，首先同样先处理异常情况，如果unlock时发现在对应的资源上未持有锁，抛出异常。对于UnlockTable还需要检查是否有该Table对应的Row上面的锁还未释放，如果有，抛出异常

之后即可遍历队列，找到当前事务持有的锁，将其释放，通知其他线程，让其重新进行一次竞争，尝试获取锁，最后根据锁的类型和隔离级别来判断是否转换为SHRINKING。

当事务提交或者中止时，会将当前事务持有的所有的锁进行释放，因此需要集合来维护当前事务所持有的所有的锁，在事务类当中已经给出，因此在lock unlock的过程当中，一旦锁的持有情况有变化，就对对应的集合进行更新。

Task2 - Deadlock Detection

通过一个后台线程去不断的检测是否存在死锁，建立一个相互等待的图，去发现是否存在循环，如果存在则证明有死锁，打破循环

相关API：

AddEdge(t1,t2)：添加一条从t1到t2的边，如果存在的话就什么都不需要做
RemoveEdge(t1,t2)：如果存在则移除一条边
HasCycle(txn_id)：通过dfs去寻找是否存在循环，如果存在循环，则存储循环当中最新的事务id，并返回true，并且返回找到的第一个循环
GetEdgeList()：返回所有存在的边，用于进行结果检测
RunCycleDetection()：循环检测的主体

Hint

不需要维护一个图，每当后台线程唤醒时建立一个表，之后销毁
为保证dfs的确定性，每次选择最低的事务id为第一个，而下一个进行遍历的也选择最低的事务id
线程唤醒时，需要打破所有的循环
对于中止的事务，不加以考虑，不画边和节点
通过静态GetTransaction方法来获取一个事务的指针
std::this_thread::sleep_for进行休眠，时长为CYCLE_DETECTION_INTERVAL
当一个事务等待另外一个事务时，添加一条边，可能会有多个事务在同一个对象上持有锁，因此存在一等多的情况
事务中止时，需要将State设置为ABORTED
当一个事务中止时，需要通知该事务被中止

Task2的核心就是dfs，通过dfs在有向图当中检测是否有环，首先扫描当前的锁情况，通过一个集合记录当前所有的事务的tid，由于需要保证dfs的结果是确定的，因此每次从最小的txn_id，即最早创建的事务开始遍历，当遍历到一个txn_id之后，就将其加入到活跃集合当中，如果后续的搜索过程当中再次找到了该集合，那么就证明出现了环，此时挑选一个最新的事务，即txn_id最大的事务进行中止。dfs结束之后，就将其从活跃数组当中清除，并且可以将其添加到安全集合当中，之后在对其他的节点进行判断时，只要遍历到该节点，就证明后续并不存在环，可以直接返回。

当发现了死锁，并将事务设置中止之后，通知正在等待锁的事务，此时苏醒之后需要检查当前事务的状态是否中止，如果中止，则结束加锁的过程，直接返回。

该后台线程会和正在获取和释放锁的线程之间存在并发安全问题，访问相关数据结构时需要加锁保护。

Task3 - Concurrent Query Execution

对之前的Next() 方法进行修改，当事务进行上锁和解锁失败时，应当抛出异常。

当事务中止时，需要对该事务涉及到的table上的tuple 还有index进行undo操作，通过在事务当中维护一个写集合来实现，当事务终止时，将该集合传递给Abort

获取锁失败时，应该抛出ExecutionException异常，告知上层。

在一个事务当中，应当考虑会对数据进行多次查询，针对不同的隔离级别进行处理

在加锁上，由于支持了意向锁，因此在Init方法当中先通过意向锁锁住整个表，之后在Next方法当中在加写锁或者读锁锁住单个Tuple。根据隔离级别再考虑合适释放掉锁。

隔离级别

REPEATABLE_READ：采用严格两阶段锁协议，因此只加锁不解锁，最终由commit或者abort统一释放锁，在Init当中加表级的意向锁，在Next当中对Tuple加读写锁
READ_COMMITTED：在Init当中加表级的意向锁，在Next当中添加行级别的锁，对于S锁，读取完就可以释放，无论是否为Growing。X锁为保证对外隔离，需要在事务提交时进行释放。可以保证读取到的都是已经提交的数据，但是无法提供可重复读，在一次事务当中的读取的数据并不一致。
READ_UNCOMMITTED：读操作无需加锁，因此会读取到写入但是还未提交的数据，写操作在Init当中加意向锁，Next当中加X锁，最后由事务统一释放。

在执行器当中，会接收到加锁\解锁操作从下层抛出的异常，因此需要捕获下层的异常，并重新对外抛出一个统一的异常，并且加锁\解锁操作也可能会失败，如果失败同样需要向上抛出一个加锁失败的异常，因此加锁的形式大致如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
  try {
    if (exec_ctx_->GetTransaction()->GetIsolationLevel() != IsolationLevel::READ_UNCOMMITTED) {
      auto is_locked = exec_ctx_->GetLockManager()->LockTable(
          exec_ctx_->GetTransaction(), LockManager::LockMode::INTENTION_SHARED, table_info_->oid_);
      if (!is_locked) {
        throw ExecutionException("SeqScan Executor Get Table Lock Failed");
      }
    }
    // LOG_DEBUG("SeqScan Init::table_name:%s table_id,%d", table_info_->name_.c_str(), table_info_->oid_);
  } catch (TransactionAbortException e) {
    throw ExecutionException("SeqScan Executor Get Table Lock Failed " + e.GetInfo());
  }

隔离级别

在Task1和Task3上，在注释当中已经给出了非常详细的加锁解锁以及各种方向上的指导，只要将其翻译成代码级别上整个Lab就实现好了。基本上不怎么需要特别的动脑子，全程被喂饭，加上个人基础不太好，因此感觉还是有必要捋顺一下四种隔离级别在实现上的不同，以及各自针对的情况。

四种隔离级别的差别主要聚焦于读操作上，对于写操作，为了保证数据库一致性，只有写入的锁只有数据提交时才能够释放，如果中途释放锁，写入的操作结果可能会被其他的覆盖，从而违反了数据库一致性。单独看写锁的话，都是采用了严格两阶段锁的策略，保证一致性，同时避免级联中止。

READ UNCOMMITTED

最宽松的隔离级别，根据上表可以看到脏读不可重复读幻读都会发生

在实现上读操作不需要加锁，写操作和其他的一致，因此所有读相关的锁都不支持，如果想尝试加[S,IS,SIX]，都会抛出异常。由于只支持写锁，在shrinking阶段，任何加锁操作都是不允许的，会抛出异常。

因此并不保证读取到的数据一定是提交的数据，由于并没有加读锁和其他的事务进行互斥，其他的事务一旦写入之后就可以被读取，因此当读取到之后，如果写入数据的事务中止回滚，那么读取到的数据就变成了脏数据产生脏读。

READ COMMITTED

相比于读未提交解决了脏读的问题，但是依旧会出现不可重复读和幻读

在实现上读操作需要在Table上加IS，在Row上加S，并且当完成一次读取之后即可将锁释放，无需等待事务的提交。释放S锁并不会导致事务从growing向shrinking转变。

由于通过S锁进行互斥，从而保证那些正在写入的事务在提交前不应被读取到，能够读取到的数据一定是提交之后稳定写入的数据。

REPEATABLE READ

在读提交的基础上又解决了不可重复读的问题，存在幻读。

实现上加锁策略和READ COMMITTED并没有区别，但是在释放锁上读写锁全部采用严格两阶段锁的策略，此次事务会一直持有读锁，从而中途不可能被其他的事务重新写入更新，在一次事务当中读取的数据全部为一致的。

shrinking阶段不允许添加任何的锁，释放S X锁就会向shrinking进行转变。

可串行化

最严格的隔离级别，简单来说就是在该隔离级别下，事务的执行可以等价成一次不存在并发的串行执行。最简单的判断是否为可串行化的方法就是交换一系列不冲突的指令，从而看原本的事务调度是否可以被分为两个在时间上完全错开的串行调度，简单用读写来表示，一次通过交换或重拍转换成串行结果如下：

Summary

整个Lab4大致就是这样，由于几天后就要考试因此整个Lab4做的比较粗糙，记录写的也很粗糙。只实现了最基本的功能，能够通过所有测试，期间还因为一个智能指针的问题卡了很久，不过未经优化的QPS几乎垫底，不过目前也没有时间做什么优化了，只能暂时搁置了。不过这也算是我用cpp写的头一个比较完整的项目，也算是克服了对cpp的恐惧。后续的话精力应该主要放在机试和408复习上了，928前应该不打算开新的Lab了，后续复习的额外时间打算看一看rocksdb和一些c++还有cmake相关的工程基础。

Lab4#

Task1 - Lock Manager#

相关数据结构#

Lock#

Unlock#

Task2 - Deadlock Detection#

Task3 - Concurrent Query Execution#

隔离级别#

Summary#