任务

 lab4 的任务时实现基于锁的事务。任务要求如下：

  • 实现 page 粒度的锁，实现对锁的管理

  • 使用 Strict two-phase locking 保证事务的 A 与 I；

  • 使用 NO-STEAL/FORCE 策略管理 buffer pool，保证持久性。也就是说不能将未提交事务的修改刷回磁盘，同时提交事务提交时，其做出的修改必须强制刷盘。因此你需要实现 undo，因为事务提交时必须刷盘（lab6 会实现基于 log 的恢复策略）

首先我们要思考，如何使用 S2PL 实现事务的原子性与隔离性。

S2PL 要求事务在需要时获取锁，直到事务在提交时才全部释放。通过加锁，我们自然而然地可以实现一定的隔离性。那么能够实现那种级别的隔离呢？

读未提交？我们能否读取到未提交事务做出的修改呢？答案是不能，因为数据加着锁呢

读已提交？事务提交后会释放所有的锁，所以我们只能读到事务提交后做出修改。

可重复读？那能不能做到可重复读呢？可以。因为我们使用的是 Strict 2PL，事务持有自己需要的锁，其他事务不能获取锁，所以数据根本不会被修改，所以可以实现可重复读

可串行化？可以，但是除了锁住数据外，可能还需要锁住与查询有关的信息。在 lab 中不需要实现

一个调度执行的效果等价于某个顺序执行事务的结果，那么我们就说该调度是 Serializable Schedule

然后是原子性，由于使用的是 NO-STEAL/FORCE 策略，所以需要使用 Shadow Page 的方法，对要修改的数据进行复制，然后在副本上修改，如果事务提交，可以将修改的副本作为主版本，如果事务中止，可以丢弃修改。lab4 比较简单，因为使用的是 page 级别的锁，所以可以直接在 Buffer Pool 中的 page 上修改，如果事务提交，直接刷盘，如果事务中止，将 page 从 Buffer Pool 中移除就可以了

1
2
3
4
5
6
7
8
9
10
11
12
public void transactionComplete(TransactionId tid, boolean commit) {
    for (PageId pageId : pageTable.keySet()) {
        if (holdsLock(tid, pageId)) {
            if (commit) {
                flushPage(pageId);
            } else {
                discardPage(pageId);
            }
            lockManager.releaseLock(tid, pageId);
        }
    }
}

知道了大致的思路，下面就可以开始完成 lab 了

exercise 1

实现 BufferPool 中获取锁和释放锁的逻辑，在读之前加读锁，写之前加写锁。事务提交时释放锁。需要注意的是我们需要自己实现锁管理器，因为我们需要记录哪些事务持有哪些锁，以及哪些锁被哪些事务持有。如果你想使用 Java 自带的读写锁，Good Luck。

我们为什么需要记录这些信息呢？因为在释放锁的时候，我们需要知道事务对哪些 page 加了锁，否则我们也不知道释放哪些锁，这时原生 API 做不到的。

还有一个问题，那就是 2PL 可能造成死锁。考虑两个操作，分别需要对所有 tuple 的某个 attribute 加 1 和 减 1，一个从左边开始扫描，一个从右边开始扫描，当他们相遇时，产生了死锁。所以我们还必须解决死锁问题。最简单的方法就是超时中止，也可以维护一个依赖图，检测是否会形成环

因为在 lab 中不管读写都会调用 BufferPool 的 getPage() 方法，所以我们需要重点在该方法上下功夫

exercise 2

实现 S2PL，调用 getPage() 可以解决这些问题。lab 中提出了两个获取和释放锁的场景

  1. 向 HeapFile 中添加 page 时如何写入磁盘，会不会有竞争条件产生。
  2. 寻找 空 slot 插入时，如果发现 page 没有空 slot 该怎么办。lab 给出的建议是释放锁，因为事务不会使用该 page 的数据，并不会造成影响。

lab 给出了第二个场景的解决方案，那么第一个场景会不会有竞争条件产生呢？

一个 page 是由 tableId 和 pageNumber 唯一标识的，当我们需要要给新 page 时，会将其加载到 BufferPool 中，也就是说会加上锁，并且在 lab 中，有了 pageId 就可以确定 page 在 file 中的位置，所以不会产生竞争条件。

跳出 lab，如果是先创建一个内存 page，然后再以追加的方式写回文件，会不会产生竞争条件呢？答案是会，所以在写 page 到 file 时需要加锁。而且这样需要其他机制维护 page 的位置，比如 page direction 或者 page list

exercise 3

实现 NO STEAL，即不能将未提交事务做出的需改写回磁盘。由于 lab 使用的 page 锁，page 中的数据不会被其他事务修改，所以在回滚时移出 BufferPool 即可。还需要注意的一点是，牺牲策略不应该将 dirty page 作为对象，因为 dirty page 可能是未提交事务做出的修改，一旦将 dirty 作为牺牲对象，就会打破 NO STEAL，产生问题

考虑一般的做法，应该使用 Shadow Page，将要修改的数据复制到副本中，然后在副本中做修改，读取也读取副本中的数据，以此保证可重复读。

exercise 4

实现 FORCE，即事务完成的逻辑。在事务提交时，将所有相关的 dirty pages 落盘，然后释放锁；事务中止时，回滚，并释放锁

exercise 5

解决死锁，可以采用超时中止的方法，也可以采用 wait-for graph，为了方便，我使用的时超时中止的方法

最后，lab 文档中说到，我们实现的 db 已经时 recoverable 了。这时为什么呢？因为采用 NO-STEAL/FORCE 不需要 redo 和 undo，当事务提交时，所有事务的修改都会落盘，并且所有为提交事务做的修改都不会落盘。也就是说，磁盘上没有多余的数据，也没有丢失的数据，所以不需要 redo 和 undo