任务

 lab6 的任务是实现基于日志的回滚和恢复。任务要求如下：

  • 对整个 page 做物理日志，读入时记录原始内容，用于回滚

  • 基于 STEAL/NO-FORCE 将 page 写回磁盘前，先写日志

STEAL/NO-FORCE 指的是：

  • 允许将未提交事务所作的修改落盘
  • 事务提交时不强制马上落盘

允许 STEAL/NO-FORCE 如何实现事务的一致性呢？那就是使用预写日志，在将数据写入磁盘前，先写日志，只要日志落盘了，即使数据没有落盘，也可以通过日志恢复。

通过文档、注释和代码，我们可以知道我们要实现的日志格式大致如下图所示：

  • 日志的开头是一个 int 类型的整数，标识 log 的类型，比如 begin、update、commit、abort等
  • BEGIN 后面是事务 ID，表示该事务开启了事务
  • COMMIT 后面也是事务 ID，表示事务提交了
  • ABORT 后面除了事务 ID 还有一个 BEGIN 的偏移量，方便快速找到该事务开始的地方
  • UPDATE 后面除了事务 ID，还记录了修改前和修改后的值，可以用于 redo 或者 undo
  • CHECKPOINT 会记录活跃的事务 ID 以及 checkpoint 的起始位置和当前的 offset。数据库恢复时可以从 checkpoint 开始恢复

exercise 1

实现 LogFile.rollback。

实现 rollback，我们需要读取日志，从 begin 出开始，依次读取 log，遇到 update 就将数据改为 before value。需要注意的是回滚时记得将 page 标记为 dirty，完成后需要持久化。大致逻辑如代码所示

1
2
3
4
5
6
7
8
9
10
11
12
public void rollback(TransactionId tid) {
    Long startOffset = tidToFirstLogRecord.get(tid.getId());
    raf.seek(startOffset);

    while (raf.getFilePointer() < currentOffset) {
        if (type == UPDATE_RECORD && txid == tid.getId()) {
            writePage(beforeImage);
        } else {
            // do nothing
        }
    }
}

exercise 2

实现 LogFile.recover()，让数据库可以根据日志文件恢复状态

由于实现了 checkpoint，所以日志中会有 checkpoints，我们可以直接从 checkpoint 开始恢复，丢掉检查点之前提交的日志。因为 checkpoint 保证在这个时刻，所有对数据做出的修改都会落盘。如果遇到 ABORT 日志，根据 offset 回滚即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void recover() throws IOException {
    recoveryUndecided = false;
    raf.seek(0);
    long checkpoint = raf.readLong();
    if (checkpoint valid) {
        raf.seek(checkpoint);
    }
    while (raf.getFilePointer() < len) {
        switch (type) {
            case UPDATE_RECORD:
                // 重放数据
            case COMMIT_RECORD:
                // 提交事务
            case ABORT_RECORD: 
                // 找到事务开始的位置，回滚
            case CHECKPOINT_RECORD:
                // 继续往后读
        }
    }
}

下面我们来看一下 lab 帮我们实现的 checkpoint 的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/** Checkpoint the log and write a checkpoint record. */
public void logCheckpoint() throws IOException {
    Set<Long> keys = tidToFirstLogRecord.keySet(); // 拿到活跃事务 ID
    force(); // 强制刷盘
    Database.getBufferPool().flushAllPages();

    raf.writeInt(CHECKPOINT_RECORD); // 写入 checkpoint 类型的日志
    raf.writeLong(-1); //no tid , but leave space for convenience

    raf.writeInt(keys.size()); 
    while (els.hasNext()) { // 写活跃事务 ID 和起始位置
        Long key = els.next();
        raf.writeLong(key);
        raf.writeLong(tidToFirstLogRecord.get(key));
    }

    //once the CP is written, make sure the CP location at the
    // beginning of the log file is updated
    endCpOffset = raf.getFilePointer();
    raf.seek(0); // 将 checkpoint 起始地址写到日志的开头，方便恢复使用
    raf.writeLong(startCpOffset);
    raf.seek(endCpOffset);
    raf.writeLong(currentOffset);
    currentOffset = raf.getFilePointer();

    logTruncate(); // 防止日志过多，需要截断日志
}

checkpoint 主要做了几件事

  1. 将所有 page 刷盘
  2. 按照格式写 checkpoint 相关信息，需要将 cp 的起始位置写到日志文件开头，方便 recovery
  3. 截断日志，为了防止日志过多，需要丢弃不需要的日志。它会从 cp 开始读取，然后读取活跃事务列表，记录最小的偏移量，然后这个偏移量之前的日志就可以丢弃了。具体逻辑是创建一个临时文件，重写从最小偏移量开始的日志，注意并不是照搬原来的 log，因为记录的偏移量可能不同了。