ext3

大部分 logging 系统需要遵循以下规则：

• write ahead rule：先把事务的所有写记录到log中，然后才更新
• freeing rule：log 块未写入fs前不可被复用

xv6 logging 回顾

• 用户程序可能调用write/create修改fs，其第一作用对象是缓存块
• 在系统调用中，每个syscall的一系列的写操作会被包装在 begin_op 和 end_op 中，使其成为一个原子操作
• 在 end_op 前，所有的写操作只会操作缓存中的块，并将其 pin，记录它的块号、以及本事务写操作的个数
• end_op 会将所有本事务的缓存块写入到log中，然后写入 log header
  • 成功写入log header后，此事务便被成功记录，可以进行崩溃恢复，这是 commit point
• 然后将log中的数据复制到对应的块中；最后清理log header

在崩溃恢复时，需要有程序可以阅读 log 区，以识别是否需要进行崩溃恢复

问题

xv6 的logging有一些问题：

• xv6 只有一个log header块，所以其系统调用只能一个一个执行，这意味着必须等待缓慢的磁盘操作
• 另外，数据被写入了磁盘两次，一次是log，另一次是实际写入数据块

ext3 fs log format

ext3文件系统就是基于今天要阅读的论文，再加上几年的开发得到的，并且ext3也曾经广泛的应用过。ext3是针对之前一种的文件系统（ext2）logging方案的修改，所以ext3就是在几乎不改变之前的ext2文件系统的前提下，在其上增加一层logging系统。所以某种程度来说，logging是一个容易升级的模块。

缓存

与xv6类似，ext3也有缓存块，其写回策略为 write-back。于是缓存中的数据可分为：干净块、脏块、pinned 块

• 干净：与磁盘数据一致
• 脏：有写入
• pinned：稍后会写入 log

transaction 信息

可以维护多个在不同阶段的transaction的信息，每个信息包含：

• 序列号
• 本事务的一系列块号
• 一系列handle，handle对应了系统调用，并且这些系统调用是transaction的一部分，会读写cache中的block

磁盘布局

与xv6一样：

• 会有一个文件系统树，包含了inode，目录，文件等等
• 会有bitmap block来表明每个data block是被分配的还是空闲的
• 在磁盘的一个指定区域，会保存log

log 区

• log 最开始是 super block，包含 第一个 有效事务的起始块号、以及其序列号
• 每个事务包含了：
  • 开始的 descriptor block，记录了log块对应的块号
  • log data block
  • 当事务完成并commit后，会有一个commit block

因为log中可能有多个transaction，commit block之后可能会跟着下一个transaction的descriptor block，data block和commit block。所以log可能会很长并包含多个transaction。

我们可以认为super block中的起始位置和序列号属于最早的，排名最靠前的，并且是有效的transaction。

磁盘上的这些事务都是 commit 过的，正在进行的事务在内存中。且内存中同一时间只有一个正在进行的事务，当结束当前事务时，会将其写入log，并在末尾放上一个 commit block

magic number：区分 log data

在crash之后的恢复过程会扫描log，为了将descriptor block和commit block与data block区分开，descriptor block和commit block会以一个 32bit的魔法数字 作为起始

这个魔法数字不太可能出现在数据中，并且可以帮助恢复软件区分不同的block。

ext3 如何提升 logging 性能

• asynchronous syscall：syscall修改完缓存块就返回，不用等待写磁盘操作
  • 当然，可以选择等待
• batching 批量执行：可以将多个系统调用打包成一个transaction
• concurrency 并发（这个似乎是前面两个带来的副产物）

异步syscall

这带来了几个好处：

• I/O concurrency：系统调用能够快速返回并继续计算，磁盘可以并行的写入数据
• 使得大量的批量执行变得容易。

但是也带来一个缺点：

• syscall 返回不代表实际存盘，此时断电则可能丢失数据

所以对于某些关键数据，unix 提供了fsync(fd)，使得对于该文件，所有的syscall都是在数据存盘后才返回，即同步I/O

所有的UNIX都有这个系统调用。这也可称为 flush，将写操作刷新到磁盘中

批量执行

• 在任何时候，ext3只会有一个open transaction
• 一个transaction可以包含多个不同的 syscalll

所以ext3是这么工作的：它首先会宣告要开始一个新的transaction，接下来的几秒所有的系统调用都是这个大的transaction的一部分

例如，每5秒钟都会创建一个新的transaction，一次性向磁盘写入这个包含了可能有数百个更新的大transaction。

批量执行带来了几个好处：

• 多个 syscall 均摊固有损耗，固有损耗包括：
  • 写 descriptor block和commit block
  • 磁盘旋转——只用旋转一次，就可以执行完一堆
• 更容易触发 write absorption，极大地减少了磁盘的写入次数：
  • 如果操作反复更新同一个block，批量执行使得可以在内存中反复修改它，然后将结果存盘
• 便于 disk scheduling，使磁盘尽量以顺序写入的方式调度这些写入：
  • 写log就是顺序写入，同样的数据分多次写肯定不如一次写完块
  • 驱动程序可以将写请求按轨道号排序，从而调度磁盘，尽量以顺序的方式写入

concurrency

• 允许多个并行系统调用，同一个事务的syscall可以直接修改本事务缓存块
• 可以有多个不同状态的 transaction 同时存在， 不同状态的事务包含：
  • 一个 open 事务
  • 多个正在 commit 到 log 的事务
  • 多个 commit 过、正在 install 的事务
  • 多个正在 clean 的事务

concurrency之所以能帮助提升性能，是因为它可以帮助我们并行的运行系统调用，我们可以得到多核的并行能力。如果我们可以在运行应用程序和系统调用的同时，来写磁盘，我们可以得到I/O concurrency，也就是同时运行CPU和磁盘I/O。这些都能帮助我们更有效，更精细的使用硬件资源。

问题：正在 commit 的缓存块被更新

——很可能丢失数据

解决方案是基于拷贝的 commit：将所有本事务相关的块拷贝一份，然后commit

• 正在 commit 的缓存块被更新会更新另一份，而不是原来的缓存块
• 为了保证效率，这里使用 cow 拷贝

ext3 fs syscall

• 每个 syscall 都需要声明一系列写操作的开始和结束，即 start 和 end

• start 会用 handle 标识当前 syscall 属于哪个 transaction，从而跟踪写操作

• 在调用 syscall 时，会传递直接修改缓存块，修改缓存块的函数会拿到handle和blockno，从而 将 blockno 与事务关联起来

• stop 使用 handle 作为参数，它不会结束本事务，而是代表着本事务中正在进行的syscall少了一个

• 当本事务中的所有 syscall stop 后即可 commit 事务

ext3 transaction commit

• 每隔5秒，文件系统都会commit当前的open transaction

• 首先需要 阻止任何新的 syscall

  • 新的syscall需要等待——这会损害性能

• 等待本事务所有 syscall stop；拷贝所有相关的block

  • 写入log data block时即用的副本
  • cow copy

• 如果剩余的 log 空间足够大，开始commit前为后续 syscall open 一个新的事务

  • 否则，等待至有足够的log空间
  • 需要预先声明需要多大的log空间
  • fs会记录每个事务的大小，从而得知需要等待多久

• 根据记录写 descriptor block，包含记录本事务所有被修改了的 blockno

• 写 data block。前面二者完成后写 commit block

  • 写完 commit block 后即达到 commit point

• install log

• install 后即可 re-use 原来的 log空间

  • 没有clean？

繁忙 fs 系统

可能没有足够的 log 空间，所以或许不能直接 commit 一个新的transaction，需要等待某个事务完成

• 也就不能开始任何syscall

如果空出来的空间不够大，还是需要继续等待，直到等到足够大的空间

ext3 crash recovery

当决定释放某段log空间时，文件系统会更新 super block的指针 将其指向当前最早的transaction的起始位置。

• 恢复软件会读取super block，并找到log的起始位置

  • crash或许会打断任何在进行中的transaction

• 不断地根据 descriptor 扫描，寻找 log 的结束位置，直到：

  • commit block 后的下一个块不以魔数开头
  • 或者以~开头，则是descriptor，但根据他找到的不是一个commit block
    • 这可能是一个正在commit的事务，但未commit成功
    • 这里不会有偶然，data block的魔数开头被替换为全0，这必然是一个descriptor

• 恢复所有有效的事务，然后启动os

鉴别 descriptor/commit block

descriptor 与 commit 以32bit的魔法数字开头，如果一个 data block 以~开头，则会在descriptor中标记这个block，并把log中的data block开头用全0替换，在写入实际块时，恢复原来的魔法数字

其他细节

为什么新transaction需要等前一个transaction中系统调用执行完成

t1使用t2释放的y的inode为x创建文件，但是t2丢失了…此时x和y就共用一个inode

文件系统线程

有一个文件系统线程会做这里所有的工作，但也可以是多个…只要加锁

descriptor/commit 匹配

如果T8在crash的时候还没有commit，并且T5的commit block正好在T8的descriptor block所指定的位置，这样会不会不正确的表明T8已经被commit了（注，这时T8有一个假的commit block）？

二者序列号不同，不能匹配

为什么不在descriptor block实现commit block？

XV6与这个提议非常像，完全可以这么做，虽然需要在完成后返回去修改descriptor block，但至少在ext3中这么做了不会牺牲性能、可以节省一个commit block的空间

Linux文件系统的后续版本实现了你的提议，ext4做了以下工作来更有效的写commit block。

ext4会同时写入所有的data block和commit block，它并不是等待所有的data block写完了之后才写的commit block。

但是这里有个问题，磁盘可以无序的执行写操作，所以磁盘可能会先写commit block之后再写data block。如果中间有了crash，那么我们有了commit block，但是却没有全部的data block。

ext4通过在commit block中增加校验和来避免这种问题。所以commit block写入之后发生了crash，如果data block没有全写入那么校验和不能得出正确的结果，恢复软件可以据此判断出错了。ext4可以通过这种方式在机械硬盘上写入一批block而避免磁碟旋转，进而提升磁盘性能。

log中的data block是怎么写入到文件系统中的？

ext3有三种模式：

• journaled data：先写log data再写实际块
• ordered data：将metadata block写入log，而data会被直接写到实际位置
• writeback

ordered data是最流行的模式，这种模式要快得多，但是它也会导致更多的复杂性。

假设你执行一个写操作导致一个新的block被分配给一个文件，并将包含了新分配block编号的inode写入到log中并commit，在实际写入文件内容至刚刚分配的data block之前发生crash。在稍后的恢复流程中，你将会看到包含了新分配的block编号的inode，但是对应data block里面的内容却属于之前使用了这个data block的旧的文件。如果你运行的是一个类似Athena的多用户系统，那么可能就是一个用户拥有一个文件，其中的内容又属于另一个用户已经删除的文件，如果我们不是非常小心的处理写入数据和inode的顺序就会有这样的问题。

ext3的ordered data通过先写入文件内容到磁盘中，再commit修改了的inode来解决这里的问题。如果你是个应用程序，你写了一个文件并导致一个新的文件系统data block被分配出来，文件系统会将新的文件内容写到新分配的data block中，之后才会commit transaction，进而导致inode更新并包含新分配的data block编号。如果在写文件数据和更新inode之间发生了crash，你也看不到其他人的旧的数据，因为这时就算有了更新了的data block，但是也没关系，因为现在不仅inode没有更新，连bitmap block也没更新，相应的data block还处于空闲状态，并且可以分配给其他的程序，你并不会因此丢失block。这里的效果就是我们写了一个data block但是最终并没有被任何文件所使用。