CMU15-445 2021 Fall Lab通关复盘
经历数周断断续续的码代码，CMU15-445 2021 Fall 的Lab终于全线通关。
本文用于总结4个Lab的大思路，复盘总结其中的关键实现部分，尤其是锁的实现。
1. BUFFER POOL
实现LRU算法的Buffer Pool，对Buffer Pool的操作要加latch
- LRU算法不能驱逐正在使用的Page（Pinned Page）
- 有Dirty Flag的Page在驱逐前要写回到磁盘
进一步提升并行性，采用Parallel Buffer Pool，将不同的page id映射到相应的Buffer Pool。
2. EXTENDIBLE HASH INDEX
数据库的索引主要有两种实现方式，B+树，和哈希表。
这一部分主要实现一种动态哈希，是extendible hash表
- 每一个hash值都指向一个Page
- 哈希表会根据数据规模，动态增大或者缩小
Hash表为了支持并发访问，采用了读写锁（Read-Write Lock）
需要注意的是，这里的Read-Write Lock是针对hash table
- 对于修改hash table的内部结构的操作，加Write Lock。比如merge，split。
- 对于其他操作，加Read Lock，比如insert，remove。
Page Latches
还需要注意，对于page本身的读写也要上锁，读加Read Lock，修改加Write Lock。
3. Concurrency Control
实现volcano model即可
4. Concurrency Control
Isolation Level
这一部分要求实现三种隔离级别，分别是Repeatable Read，Read Committed和Read Uncommitted。
实现思路如下，按课件即可
-
Serializable: strict 2PL, 加index lock (不要求实现)
- Repeatable Read: strict 2PL, 不加index lock
- Read Committed: 2PL, S-lock立即放锁，X-lock在Shrinking阶段放锁
- Read Uncommitted: 2PL, 不加S-lock
Read Uncommitted由于不加S-lock，所以可以读到其他TX修改但未提交的数据。
Read Committed读时需要S-lock，由于正在修改的数据此时有X-lock，当前线程阻塞，无法读取修改的数据。因此只能读到committed的数据。
Repeatable Read持有S-lock知道Shrinking阶段，一旦在TX某一刻拿到S-lock，之后的任何线程想要拿X-lock修改这一数据，都需要等S-lock释放，即TX committed之后。
关于幻读：
Serializable 解决了幻读的问题，方法就是加index lock。
幻读出现的原因，就是TX只能给已经存在的records加锁，而不能给尚未出现的records加锁！
所以解决方案就是，给Index上锁，禁止插入或删除records
Conflict serializability 成立的条件之一是，要保证records是固定的！
Lock Manager
主要是按照书上实现的lock table
每一个队列都有自己的latch，用于每个队列结构的修改；整个map有一个latch，用于map结构的修改。
每一个队列都有一个condition variable, 用于队列中的通知
需要实现的API主要有三个，LockShared, LockExclusive, LockUpgrade, Unlock
Deadlock Prevention
2PL并不能解决死锁的问题，使用Wound-Wait算法
核心就是，老事务（早开启的事务）优先拿锁，对于队列里其他事务，全部Abort
- 对于新加入队列的S-lock request，当队列里有X-lock request的更小事务，Abort队列里的这个事务
- 对于新加入队列的X-lock request，当队列里有任何更小事务，Abort队列里的这个事务
对于S-lock和X-lock分开对待，是因为Lock Manager中S-lock和S-lock之间不会造成死锁
Concurrent Query Execution
这一部分，主要是并行的实现query execution，调用Lock Manager，根据不同的isolation level实现即可。