CMU 15445 Project 3 实现Lock Manag

此LAB 按照2017的要求

做到后面发现因为缺少极多信息，比如API的框架，一些CONFIG的参数。我无法完成2018的LAB3，所以此LOCK MANAGER的需求是按照2017的project 来实现的。
https://15445.courses.cs.cmu.edu/fall2017/project3/

要完成这个PROJECT，首先要看懂PPT 2PHASE LOCKING那节。
随后做掉https://15445.courses.cs.cmu.edu/fall2018/files/hw4-clean.pdf 作业的第一部分。
下面理解书上的

image.png

数据结构设计

这幅图的就是一个HASH TABLE的链表实现法。每一个VALUE里还要存所有的在访问这个KEY的TRANSACTION。
针对每个TRANSACTION 我们需要记录是否是GRANT的 ， TX ID ， 还有上锁的模式。
所以上述的图是3层结构。一个HASH表KEY是 RID， VALUE是LIST<TRANSACTION ITEM>
第二层结构里是个TX LIST 存了 属于这个RID的每一个TX ITEM
第三层 则是TX ITEM。

于是针对每个ITEM，会有如下结构。因为一个TRANSACTION 如果能GRANT，要么就GRANT了，要么就WAIT了。所以对每一个ITEM，我们用一个CONDITIONAL VARIABLE来控制WAIT 和 NOTIFY。

image.png

随后我们按照需求去构造那个LIST，最开始的设计MAP的VALUE 就是一个LIST<TXITEM>
但是再做UPGRADING的时候，发现要判断之前有没有正在等待锁升级的TRANSACTION，如果有，需要ABORT。所以加了一个变量来观察。就做了一层封装，同时为了增加并发度，做了一个针对TX LIST的粒度锁。这样可以避免锁整个LOCK TABLE。

image.png

最后是最外层结构的定义

image.png

算法实现

针对作业里面的这个图表，大概锁表会是如何呢？小伙伴可以画一画对锁表的理解会有帮助。

image.png

算法的核心 就是实现LOCK TEMPLATE 和 UNLOCK。
在LOCK TEMPLATE 中，大致分为4个模块
第一个模块是找到对应的TX LIST并且获得锁
第二个模块是针对LOCK UPGRADING，因为需要抹掉原来的读锁，才能升级为写锁。
第三个模块是判断是否可以GRANT。
第四个模块就是往TX LIST里插入，同时阻塞或者拿锁成功就往TXN 里面放入对应的RID记录。

image.png

在UNLOCK 里，首先要区分是否是S 2PL，是的话就要求只能在COMMIT 和ABORT的时候才可以释放锁。
随后定位到要删除的元素的TXLIST，从里面抹除，从TRANSACTIONS 的LOCK集合里抹除对应的RID。
然后判断是否TXLIST EMPTY，抹除对应的KEY。

最后判断是否可以GRANT 锁给其他的TX。

image.png

最后写了10个测试，测试1000次 通过

image.png image.png

代码提交到GIT PROJECT 3A
https://github.com/yixuaz/CMU-15445

3B 的 WAIT DIE 算法 也是十分简单。

这里先引用下PPT

image.png

就是要BLOCKING的时候，先看下持有锁的PRIOIRTY是不是比自己低，比自己低自己就等。不然自己就主动ABORT。

这边PRIORITY 是根据TIMESTAMP是不是更早，更早的TIMESTAMP 优先级就更高。
这里有个重要的点就是TIME STAMP 并不是真的要去拿当前时间自己去存。因为TXN MANAGER在分配TXN的时候，就会递增TXN ID。 所以我们可以假定ID小的那么时间就肯定要早。

image.png

所以TEST大概如下

image.png

大概思路是先去让TX 2 获得锁，那么3去拿的时候因为优先级低了，就ABORT自己，所以EXPECT FALSE。

随后让TX 0 去拿，这个时候因为优先级高 所以会WAIT
下面主线程里，TX 1 去拿，就比0低了，就ABORT.
最后TX 2释放掉。 TX0就可以拿到锁并释放。

这个逻辑也非常好实现，就是在判断GRANT = FALSE，在WAIT前 比较一下自己和前一个的TX ID。
为什么比较前一个就够了。因为这个LIST 的ID 只能是递减的，所以前一个的ID 一定是最小的。
加上如下代码

image.png

添加测试至20 个。测1000次。

image.png
image.png

一个锁顺序的BUG

下图先释放TABLE锁 再对LIST加锁 是会有问题的。正确的写法应该先要到LIST锁，再释放TABLE锁

image.png

因为我们在TABLE锁先释放了，另一个线程可以在UNLOCK率先抢到TABLE 锁随后紧接着拿下LIST锁，就有可能对整个TABLE做了修改（ERASE这个KEY）。那么之前那个LOCK线程缓存的那个LIST 其实就并没有被TABLE的HASH表锁应用。造成后来UNLOCK 时找不到对应的KEY的问题。

lock_manager_test: /home/zyx/Desktop/15445/sqlite-fall2017/src/concurrency/lock_manager.cpp:74: bool cmudb::LockManager::Unlock(cmudb::Transaction*, const cmudb::RID&): Assertion `it != txList.locks_.end()' failed.

代码文件上传至
https://github.com/yixuaz/CMU-15445/tree/master/project3B