操作系统学习——文件系统崩溃一致性
文件系统的崩溃一致性
待读文章：All File Systems Are Not Created Equal
基于先代文件系统之上的应用程序级崩溃一致性协议（crash-consistency protocol）。
状态更新来持久化状态，依赖底层文件系统。
主要贡献：
- BOB 工具
- ALICE 工具
BOB 工具
BOB 工具，用来测试这种一致性的满足情况（不同应用文件系统的），测试方法解释，转自文件系统天生就是不平等的-实现崩溃一致性应用的复杂性 | 简书，整体看还是一种 testing 的方法（自底向上抓取）。
BOB 主要是为了测试文件系统的 Persistence Properties。对于一个给定的文件系统，当在发生崩溃之后，有哪些可能的状态，这个就是用 Persistence Properties 来确定的。
那这个 BOB 是怎么做的呢？首先 BOB 会一个简单的场景去压力测试 Persistence Properties（譬如，一批特定 size 的持续写入来验证 overwrite 的原子性）。BOB 会收集这个场景产生的 block I/O，然后重新排序这些收集的 blocks，选择性的将一些写入到磁盘去产生一个合法的磁盘 state。用这种方式，BOB 能产生一批在崩溃之后，多个对应不同 disk states 的唯一的磁盘 images 。然后 BOB 会在各自的 image 上面执行文件系统的 recovery ，并检查 Persistence Properites 是否继续满足（譬如 Write 是原子的）。
抽取 I/O 操作，重新排列，构建磁盘映像（disk image）。这些磁盘映像是磁盘的物理状态，应对应 crash state 抽象模型的部分状态。然后在各个磁盘映像中执行恢复过程，如果操作是原子的？crash-consistency 的，则应该恢复成功。
ALICE 工具
ALICE 的原理其实比较简单，就是通过 trace 应用程序的 system call 来直接构建文件的 state。
主流 Linux/Unix 文件系统架构简介
FFS-style 文件系统：代表文件系统有最初的 BerkeleyFFS 和 Ext2，具有的优点是简单、高性能、易于修复和恢复数据，但是每次系统崩溃需要全盘 fsck，无数据一致性保障，无正规的防御磁盘崩溃的措施。
日志(Journaling)文件系统：最为流行的现代文件系统架构，典型代表文件系统有 Ext3、Reiserfs 以及其他多种文件系统。日志文件系统加入对近期提交到文件系统的事务的 log，log 顺序地写到磁盘上的一个保留的位置。文件系统的主体不会更改，直到事务完整地写到 log 中为止。日志使得文件系统可以快速从崩溃状态恢复，因为可以“回放”log，完成任意未半完成状态（文件系统的更改信息已经写到了 log 中，但是还没有写到文件系统中）的操作。日志文件系统存在的问题包括两次写问题（每个操作必须写磁盘两次，一次是写到 log 中，另一次是写到文件系统中最终的位置）以及受限的日志空间带来的多种性能问题。此外，日志文件系统也没有改善磁盘崩溃的情况。
日志结构（Log-structured）文件系统：典型代表文件系统 LFS。Log-structured 文件系统在文件系统研究社区反响强烈，但是从未用于主流商业产品用途。Log-structured 的主要设计思想是：首先，以 log 的方式将更新写出，这将一组随机写 IO 转换成一个大的连续的写入流，写操作更为高效；其次，整个文件就是一个巨大的连续事务 log，对文件的更新直接追加到 log 中（解决了 Journaling 文件系统的两次写问题），数据的更新不会在本地覆盖写——从这个意义上看 log-structured 文件系统也是一种 Copy-on-write(COW)文件系统。Log-structured 文件系统的主要问题是系统需要大的空闲的 segments 磁盘空间，这些空闲的 segments 由“cleaner”线程创建。非完全空闲的 segments 中的已分配的 blocks 必须移出到其他的 segments 中。尽管对 cleaner 的优化进行了多年的研究，cleaner 线程的开销仍然非常高。此外，计算空闲空间的总数也很困难，因为 COW 文件系统直到数据块的新的拷贝写入成功的时候才会释放该数据块的旧的拷贝块，而一次操作需要完成的数据块拷贝的数量是不可预测的。最后，强制重分配数据块需要在每次写操作的时候做一个“good”的分配决策，而本地更新文件系统仅需要做一次的“good”分配决策。
软更新（Soft updates）文件系统：Soft updates 是对 Berkeley FFS 的优化，在文件系统崩溃的时候，保留磁盘上的文件系统格式数据（也就是元数据），使得无需执行 fsck 程序就可挂载文件系统。Soft updates 仔细调整对文件系统的更新顺序，因而任意时刻文件系统发生崩溃，除去部分“leaked”（标记为已分配，实际上是空闲的）的 inodes 和 blocks 外，文件系统数据是一致的。后台 fsck 程序运行在文件系统的快照上，找出这些未引用的 blocks 并将其再次标记为空闲。Soft update 是的负面影响主要是极度复杂，难于理解和实现，并且每个文件系统操作需要其自己独特设计的 update 代码。当前已知的仅有一个实现的 soft updates 实例。
写时拷贝（copy-on-write(COW)）文件系统：最新趋势的文件系统架构。COW 文件系统的典型代表是 WAFL (Write Anywhere File Layout, Network Appliance 的内部文件系统)、ZFS 以及 Btrfs。这些文件系统以树的方式组织文件 blocks。当一个 block 更新的时候，就分配一个新的 block，链接 block 的指针指向更新后的 block——当然也会引起这些指针所在的 block 的更新产生。当一组一致的更新写到磁盘之后，root block 自动更新为指向新的 blocks 树，该新的 blocks 树包含最新的分配信息。这种结构方式极其易于实现文件系统快照技术，而且集中了文件系统一致性代码。COW 文件系统的不足之处与 Log-structured 文件系统相似——每次写操作要强制重分配，同时不确定完成一次更新需要多少的磁盘空间。同时，好的同步性能需要加入某种 journal，使得 COW 文件系统的实现更复杂。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！