Qifan Wang
The Jungle Book
A blog for programming

MIT 6.S081 Lecture 15: Crash Recovery, Logging

The power of imagination makes us infinite.

6.S081第十五课，需要阅读课本第八章的 logging 章节，学习文件系统的崩溃恢复与日志知识。

Crash recovery

崩溃发生在意外场景，如用户在写入文件系统，然后电源故障，机器重新启动。OS需要保证此时的文件系统仍然可用。

崩溃也会发生在多步操作的中间，可能违反 FS invariant (违反 invariant 就是陷入 inconsistent 状态)。这个 inconsistent FS 可能会重新导致崩溃，更糟糕的是没有崩溃发生，之后用户通过 FS 读写到错误数据。

OS设计者希望，在重启后运行恢复代码使得，

  1. 文件系统内部的 invariant 被维护(maintain FS internal invariant)。比如，不会有 block 同时在 free list 和 文件中。
  2. 所有最后的FS操作被磁盘保留。比如，昨天 data I 写入操作被保留，但在崩溃发生时没有 data I 的写入，所以用户可能要检查最后的 FS 操作。
  3. 没有操作执行顺序的异常。

但有时设计上的正确性与性能是矛盾的。比如，磁盘写入很慢，

  • 为了安全，写入操作应该尽快执行
  • 为了速度，先不直写磁盘，通过 batch 批处理，write-back cache 回写缓存，sort by track 排序磁盘轨道等操作高效写入。

崩溃恢复是一个 recurring problem ，其在很多存储系统会出现，比如数据库。近年有许多研究工作完成了一些巧妙的 performance/correctness tradeoffs 。一个常见的解决方案是用日志记录。

Logging solution

大部分 OS 用 logging(== journaling) 实现崩溃恢复，以完成

  • 原子化有关崩溃的系统调用
  • 更快的恢复(no hour-long)

这个课程将从 xv6 log 系统和 Linux EXT3 文件系统两方面介绍 logging 。

logging 的基础思想是，

  • 原子化一个系统调用的所有写入/无写入。原子操作看作一个事务 transaction
  • 记录这个系统调用的所有即将的写入(all writes the sys call will do)于磁盘 log 中。(log)
  • 然后记录 done 在磁盘中。(commit)
  • 然后执行 FS 磁盘写入。(install)

当发生崩溃，恢复代码将检查，

  • 如果 done 记录在 log 中， 重新执行写入(replay all writes in log)
  • 如果 log 没有 done，则忽略这条 log

这种 log 模式也被称为 WRITE-AHEAD LOG(WAL)。其规则简单说就是先记录所有写入于磁盘log，并确保这些写入被标记 committed，然后执行一个事务的所有写入。

这种规则的优势，

  • 一旦执行一个写入操作，同事务的其他写入也必须被执行。事务保证了原子化。
  • 在第一个事务完成写入后，其他后来事务的写操作必须是可获取的，因为被记录在日志中。

日志就像魔法。为复杂可变的数据结构实现崩溃恢复是困难的。在现存的存储系统中，logging 也常常是分层的。分层 logging 可以于高性能兼容。(下次课)

Overview of xv6 logging

xv6 log 结构表示， [buffer cache, in-memory log block # array, FS tree on disk, log header and blocks on disk]

在写入时，向 in-memory array 写 blockno ，并保持数据在 buffer cache 中(pinned)，这之后，

  • 在 commit 阶段，
    • 将 buffer 写入磁盘 log 中。(log block)
    • 等到磁盘完成写入。(synchronous)
    • 写 log header 所在的磁盘扇区：写内容是 blockno 与 非零 n 值
  • commit 之后，
    • 执行 log 记录的写入(install)。目标位置是写入 FS 的最终位置，也是 unpin blocks 。
    • 为磁盘上的 log header 的 n 写零值。

实际上，磁盘上 log header 的 n 值指示是否 commit 完成。

  • 非零值代表 committed ，log 内容是合法的，是一个完整的事务。
  • 零值代表 not committed，可能不是完整的，恢复过程应该忽略这个日志。
  • 为 n 写非零值就是 commit point ，也是提交时刻。

xv6 disk layout with block numbers

   2: log head
   3: logged blocks
  32: inodes
  45: bitmap
  46: content blocks

如果崩溃发生在一个事务中间，xv6会根据日志进行处理。崩溃后，内存已经丢失，留下的内容仅在磁盘上。重启时，在使用 FS 前，xv6 kernel 会调用 recover_from_log()。如果 log header 中记录了 commit，内核将从 log 复制 block 到硬盘中真实的写入位置(replay)。无论，

  • crash before commit
  • crash during commit – commit point?
  • crash during install_trans()
  • crash just after reboot, while in recover_from_log()

只要有记录 commit 且没有其他干预(比如写入的硬件限制，硬盘突然没了)，内核能够不止一次的 replay the log 。

xv6 假设磁盘是 fail-stop (失败即可停止，没有做到一半的操作)。磁盘要么正确地写，要么完全不做这次失败的写入。因此保证了，

  • no partial writes (each sector write is atomic)
  • no wild writes
  • no decay of sectors (no read errors)
  • no read of the wrong sector

Challenges

日志系统也带来了许多挑战(兼顾性能)，

challenge: prevent write-back from cache

一个系统调用可以安全地更新一个 cached block ，直到对应事务 commit ，cached block 才会被写入 FS 。但试想，缓存空间有限，可能会移出一些 entry 以读取或缓存其他数据。而一旦移出，就需要写 FS 才行(至少写log否则无处存数据)。比如，

  • write dirty inode to log
  • write dirty block to log
  • evict dirty inode
  • commit

这样频繁写会影响效率(明明可以等到需要写FS时再写）。xv6 解决方案(也是通用的解决方案)是，

  • 保证 buffer cache 足够大
  • 在 buffer cache 中 pin dirty block，保证其不会被移出，完成 commit 后再 unpin block

challenge: system’s call data must fit in log

log 既然要存写入的内容，就需要保证系统调用的数据在 log 中有足够空间可以放下。而 xv6 的解决方案是，

  • 每次系统调用需要写入时，计算 block 数量的上限，设置 log size >= upper bound 。
  • 将一些系统调用拆散成多个事务。比如，写入大量数据的 write() 就不是原子的。但 OS 需要保证在正确的 commit 位置进行 replay 操作。

challenge: allowing concurrent system calls

并发写FS是十分常见的。所以 OS 必须允许来自不同的调用方的写入操作被记录在 log 中。在 commit 阶段，必须将它们全部写入 log 。但又不能为仍在事务中的调用写log(会破坏原子性)。

xv6 的解决方案是，如果系统调用的数据不能 fit in log ，将不允许这个调用开始执行。这个调用必须等待其他并发调用完成并 commit 。所以当 in-progress calls 的数量归零后，xv6 会

  • commit
  • free up log space
  • wake up waiting calls

challenge: a block may be written multiple times in a transaction

写入仅影响内存中 cached block 。所以一个 cached block 可能反映多个 uncommitted transactions。但 install 仅发生在没有 in-progress transactions 时，所以 installed block 仅反映 committed transactions。这也是所谓的 write absorbtion ，有利于性能。

Conclusion

这节课主要讲了 FS 的 logging 设计。通过看 xv6 日志系统其特点，

  • 由于 WAL 保证了正确性
  • 良好的磁盘吞吐量：由于 log 会自然批处理写，但磁盘的 data block 会写两次(commit 阶段一次，install 阶段一次)。
  • 保证并发

但现实得FS logging 可以设计得更高效，这里 xv6 的低效来自，

  • 每个 block 被写两次 (log and install)
  • 即便少量字节被修改，整个 block 也会被 log
  • 每次写 log block 需要同步。可以批量写 log block ，仅在写 log head 时同步。
  • log writes 与 install writes 都是迫切的(eager)。但它们可以是惰式的(lazy)，以便更多 write absorbtion 的可能。p.s. 但还是先 commit 再 install 。
  • 如果写操作没有 fit in log 会带来性能的损失。比如，在截断文件(truncating file)时，unlink 调用会写很多 block (dirty many blocks)。

logging 的设计本质上是 safety/performance 的取舍，为了保证正确提高性能，复杂的设计与实现应该是不可避免的。

Reference

  1. 6.S081
  2. 课本

Table of Contents