SimpleDB-Lab6

0.实验目标

在本实验中，我们将要实现基于日志的中止回滚和崩溃恢复。源码中提供了定义日志格式的代码，并在事务期间的适当时间将记录附加到日志文件中。我们将使用日志文件的内容完成回滚和恢复。

源码中提供的日志代码产生了用于物理上整页undo和redo的记录。当页是首次读入时，代码记住了整页的原始内容做为前置镜像。当事务更新页时，相应的日志记录包含已存储的前置镜像以及修改后的页面做为后置镜像。我们将使用前置镜像在中止期间进行回滚，在recovery期间undo丢失的事务，后置镜像用于在recovery期间redo成功的事务。

我们可以不做整个页面的物理撤销(那么ARIES必须做逻辑撤销)，因为我们正在做页面级别的锁定，并且因为我们没有索引，在撤销时索引的结果可能与最初编写日志时的结构不同。页面级锁定简化事情的原因是，如果一个事务修改了一个页面，那么它一定有一个排他锁，这意味着没有其他事务同时修改它，因此我们可以通过覆盖整个页面来撤销对它的修改。

BufferPool已经实现了通过删除脏页来中止事务，并且通过强制在提交时将脏页刷新至磁盘来假装实现原子提交。日志允许更加灵活的缓冲区管理(STEAL & NO-FORCE)，测试代码会在特定的时机调用BufferPool.flushAllPages()方法来验证这种灵活性。

1. LogFile.rollback()

a. 要修改的文件

• src/simpledb/storage/LogFile.java

b. 实现说明

• steal/no-force策略

  • lab6要实现的是simpledb的日志系统，以支持回滚和崩溃恢复；在lab4事务中，我们并没有考虑事务执行过程中，如果机器故障或者停电了数据丢失的问题，bufferpool采用的是no-steal/force的策略，而这个实验我们实现的是steal/no-force策略，两种策略的区别如下:
  • steal/no-steal: 是否允许一个uncommitted的事务将修改更新到磁盘
    • 如果是steal策略，那么此时磁盘上就可能包含uncommitted的数据，因此系统需要记录undo log，以防事务abort时进行回滚（roll-back）。
    • 如果是no steal策略，就表示磁盘上不会存在uncommitted数据，因此无需回滚操作，也就无需记录undo log。
  • force/no-force:
    • force策略表示事务在committed之后必须将所有更新立刻持久化到磁盘，这样会导致磁盘发生很多小的写操作（更可能是随机写）。
    • no-force表示事务在committed之后可以不立即持久化到磁盘， 这样可以缓存很多的更新批量持久化到磁盘，这样可以降低磁盘操作次数（提升顺序写），但是如果committed之后发生crash，那么此时已经committed的事务数据将会丢失（因为还没有持久化到磁盘），因此系统需要记录redo log，在系统重启时候进行前滚（roll-forward）操作。

• 日志格式和检查点

  simpleDB日志相关逻辑主要集中在LogFile中，本节我们来看看simpleDB中几种日志格式和checkpoint机制。

  log file的格式如下所述:

  • 开头checkpoint指向最新的CHECK_POINT类型的记录。之后均为记录。记录共有五种类型，分别为BEGIN_RECORD、UPDATE_RECORD、COMMIT_RECORD、ABORT_RECORD和CHECK_POINT。
  • 所有记录都有type、tid和offset这三个字段。UPDATE_RECORD还有前置镜像before image和后置镜像after image，分别用于回滚和更新磁盘中的Page。CHECK_POINT中还有记录活跃事务的数量，并记录每个活跃事务的tid和该事务第一条记录的偏移量。（活跃事务指的是截至当前CHECK_POINT时刻，还没有成功commit或abort的事务）

注：图片参考MIT 6.830数据库系统，对原图进行一些修正。

c. 实现目标

• 通过LogTest系统测试的TestAbort和TestAbortCommitInterleaved子测试。

d. 实现记录

• 回滚：rollback(tid)
  • LogFile中有成员变量tidToFirstLogRecord，将tid映射到该事务第一条记录的偏移量。因此可以获取到事务第一条记录。遍历之后的所有记录，若为UPDATE_RECORD，并且是该事物的记录，则将before image写入磁盘对应Page（将最后一条更新记录写入）。

2. LogFile.recover()

a. 要修改的文件

• src/simpledb/storage/LogFile.java

b. 实现说明

• redo log与undo log

  • 为了支持steal/no-force策略，即我们可以将未提交事务的数据更新到磁盘，也不必在事务提交时就一定将修改的数据刷入磁盘，我们需要用日志来记录一些修改的行为。在simpledb中，日志不区分redo log和undo log，格式较为简单，也不会记录事务执行过程中对记录的具体修改行为。
  • 对于redo log，为确保事务的持久性，redo log需要事务操作的变化，simpledb中用UPDATE格式的日志来保存数据的变化，在每次将数据页写入磁盘前需要用logWrite方法来记录变化：

  public synchronized void logWrite(TransactionId tid,Page before,Page after)

  • 这样，对于这些脏页，即使断电丢失数据了，我们也可以通过事务id来判断事务是否已经提交（这里提交事务会记录另一种格式的日志），如果事务已经提交，则重启时根据日志的内容就可以把数据恢复了；总而言之，通过这样的方式，可以让simpledb支持崩溃恢复；

  • 对于undo log，我们采用的是在page中使用一个变量oldData保存一份当前页旧的快照数据：

  public abstract class BTreePage implements Page {
      ...
  	protected byte[] oldData;
  }
  
  public class BTreeRootPtrPage implements Page {
      ...
  	private byte[] oldData;
  }
  
  public class HeapPage implements Page {
      ...
      byte[] oldData;
  }    

  • 数据页一开始的旧数据是空的，那什么时候会对旧数据进行更新呢？答案是事务提交时，当事务提交时，就意味着这个修改已经是持久化到磁盘了，新的事务修改后就数据页的数据就是脏数据了，而在新事务回滚时，由于我们采用的是steal策略，脏页可能已经在页面淘汰时被写入磁盘中了，那么该如何进行恢复呢？答案是before-image，即oldData，通过上一次成功事务的数据，我们可以恢复到事务开始前的样子，这样，就可以实现了事务的回滚了。

c. 实现目标

• 通过所有的LogTest系统测试。

d. 实现记录

• 恢复：recover()
  • 从开头checkpoint获取最新的CHECK_POINT，遍历之后的所有记录（checkpoint为-1就从头遍历）。COMMIT_RECORD中记录着提交的tid，UPDATE_RECORD中记录着前置镜像before image和后置镜像after image。若事务已提交（出现在COMMIT_RECORD），则将磁盘Page更新为after image；否则回滚为before image。
  • 活跃事务需要另外处理，若活跃事务没有提交，则需要将其回滚为before image。

小结

• 测试结果：