MIT 6.S081 lec14、15总结 —— File systems、Crash recovery

Lec14 File systems

• 文件系统背后的机制有关的内容

  • 对于硬件的抽象是如何实现的
  • 实现crash safety
  • 如何在磁盘上排布文件系统
  • 性能

• 文件系统具有的类似的结构。按照分层的方式进行理解：

  • 在最底层是磁盘，也就是一些实际保存数据的存储设备，正是这些设备提供了持久化存储。
  • 在这之上是buffer cache或者说block cache，这些cache可以避免频繁的读写磁盘。这里我们将磁盘中的数据保存在了内存中。
  • 为了保证持久性，再往上通常会有一个logging层。许多文件系统都有某种形式的logging，我们下节课会讨论这部分内容，所以今天我就跳过它的介绍。
  • 在logging层之上，XV6有inode cache，这主要是为了同步（synchronization），我们稍后会介绍。inode通常小于一个disk block，所以多个inode通常会打包存储在一个disk block中。为了向单个inode提供同步操作，XV6维护了inode cache。
  • 再往上就是inode本身了。它实现了read/write。
  • 再往上，就是文件名，和文件描述符操作。

• How file system uses disk

  • SSD/HDD存储设备连接到了电脑总线之上，总线也连接了CPU和内存。一个文件系统运行在CPU上，将内部的数据存储在内存，同时也会以读写block的形式存储在SSD或者HDD。这里的接口还是挺简单的，包括了read/write，然后以block编号作为参数。虽然我们这里描述的过于简单了，但是实际的接口大概就是这样。
  • **磁盘驱动通常会使用一些标准的协议，例如PCIE，与磁盘交互。从上向下看磁盘驱动的接口，大部分的磁盘看起来都一样，你可以提供block编号，在驱动中通过写设备的控制寄存器，然后设备就会完成相应的工作。这是从一个文件系统的角度的描述。**尽管不同的存储设备有着非常不一样的属性，从驱动的角度来看，你可以以大致相同的方式对它们进行编程。
  • 而文件系统的工作就是将所有的数据结构以一种能够在重启之后重新构建文件系统的方式，存放在磁盘上。虽然有不同的方式，但是XV6使用了一种非常简单，但是还挺常见的布局结构。
    • block0要么没有用，要么被用作boot sector来启动操作系统。
    • block1通常被称为super block，它描述了文件系统。它可能包含磁盘上有多少个block共同构成了文件系统这样的信息。我们之后会看到XV6在里面会存更多的信息，你可以通过block1构造出大部分的文件系统信息。
    • 在XV6中，log从block2开始，到block32结束。实际上log的大小可能不同，这里在super block中会定义log就是30个block。
    • **接下来在block32到block45之间，XV6存储了inode。**我之前说过多个inode会打包存在一个block中，一个inode是64字节。
    • 之后是bitmap block，这是我们构建文件系统的默认方法，它只占据一个block。它记录了数据block是否空闲。
    • 之后就全是数据block了，数据block存储了文件的内容和目录的内容。

• 磁盘上存储的inode

  • 一个64字节的数据结构。

    • 通常来说它有一个type字段，表明inode是文件还是目录。

    • nlink字段，也就是link计数器，用来跟踪究竟有多少文件名指向了当前的inode。

    • size字段，表明了文件数据有多少个字节。

    • 不同文件系统中的表达方式可能不一样，不过在XV6中接下来是一些block的编号，例如编号0，编号1，等等。XV6的inode中总共有12个block编号。这些被称为direct block number。这12个block编号指向了构成文件的前12个block。举个例子，如果文件只有2个字节，那么只会有一个block编号0，它包含的数字是磁盘上文件前2个字节的block的位置。

    • **之后还有一个indirect block number，它对应了磁盘上一个block，这个block包含了256个block number，这256个block number包含了文件的数据。**所以inode中block number 0到block number 11都是direct block number，而block number 12保存的indirect block number指向了另一个block。

    • 基于上面的内容，XV6中文件最大的长度是多少呢？

      (256 + 12) *1024字节

  • 目录（directory）

    • 文件系统的酷炫特性就是层次化的命名空间（hierarchical namespace），你可以在文件系统中保存对用户友好的文件名。大部分Unix文件系统有趣的点在于，一个目录本质上是一个文件加上一些文件系统能够理解的结构。在XV6中，这里的结构极其简单。每一个目录包含了directory entries，每一条entry都有固定的格式：

      • 前2个字节包含了目录中文件或者子目录的inode编号，
      • 接下来的14个字节包含了文件或者子目录名。

    • 对于实现路径名查找，这里的信息就足够了。假设我们要查找路径名“/y/x”，我们该怎么做呢？

      • 从路径名我们知道，应该从root inode开始查找。通常root inode会有固定的inode编号，在XV6中，这个编号是1。我们该如何根据编号找到root inode呢？从前一节我们可以知道，inode从block 32开始，如果是inode1，那么必然在block 32中的64到128字节的位置 (偏移 1 * 64 )。所以文件系统可以直接读到root inode的内容。

      • 对于路径名查找程序，接下来就是扫描root inode包含的所有block，以找到“y”。该怎么找到root inode所有对应的block呢？根据前一节的内容就是读取所有的direct block number和indirect block number。

      • 结果可能是找到了，也可能是没有找到。如果找到了，那么目录y也会有一个inode编号，假设是251，
        我们可以继续从inode 251查找，先读取inode 251的内容，之后再扫描inode所有对应的block，找到“x”并得到文件x对应的inode编号，最后将其作为路径名查找的结果返回。

• sleep lock

  • 

  • 既然sleep lock是基于spinlock实现的，为什么对于block cache，我们使用的是sleep lock而不是spinlock？

    对于spinlock有很多限制，其中之一是加锁时中断必须要关闭。所以如果使用spinlock的话，当我们对block cache做操作的时候需要持有锁，那么我们就永远也不能从磁盘收到数据。或许另一个CPU核可以收到中断并读到磁盘数据，但**是如果我们只有一个CPU核的话，我们就永远也读不到数据了。**出于同样的原因，也不能在持有spinlock的时候进入sleep状态（注，详见13.1）。所以这里我们使用sleep lock。sleep lock的优势就是，我们可以在持有锁的时候不关闭中断。我们可以在磁盘操作的过程中持有锁，我们也可以长时间持有锁。当我们在等待sleep lock的时候，我们并没有让CPU一直空转，我们通过sleep将CPU出让出去了。

Lec15 Crash recovery

• 这里我们关心的crash或者故障包括了：在文件系统操作过程中的电力故障；在文件系统操作过程中的内核panic。panic可能是由内核bug引起，它会突然导致你的系统故障，但是你肯定期望能够在重启之后还能使用文件系统。
  而很多文件系统的操作都包含了多个步骤，如果我们在多个步骤的错误位置crash或者电力故障了，存储在磁盘上的文件系统可能会是一种不一致的状态，之后可能会发生一些坏的事情。主要关注的问题**如何解决这些不一致的状态**？

• 例子

  • 创建一个文件，这里多个步骤的顺序是（注，实际步骤会更多）：

    • 分配inode，或者在磁盘上将inode标记为已分配
    • 之后更新包含了新文件的目录的data block

    如果在这两个步骤之间，操作系统crash了。这时可能会使得文件系统的属性被破坏。这里的属性是指，每一个磁盘block要么是空闲的，要么是只分配给了一个文件。即使故障出现在磁盘操作的过程中，我们期望这个属性仍然能够保持。如果这个属性被破坏了，那么重启系统之后程序可能会运行出错，比如：

    • 操作系统可能又立刻crash了，因为文件系统中的一些数据结构现在可能处于一种文件系统无法处理的状态。
    • 或者，更可能的是操作系统没有crash，但是数据丢失了或者读写了错误的数据。

  这里的问题并不在于操作的顺序，而在于我们这里有多个写磁盘的操作，这些操作必须作为一个原子操作出现在磁盘上。

logging

• 很好的特性

  • 确保文件系统的系统调用是原子性的
  • 支持快速恢复（Fast Recovery）
  • 可以非常的高效

• logging的基本思想还是很直观的。首先，你将磁盘分割成两个部分，其中一个部分是log，另一个部分是文件系统，文件系统可能会比log大得多。

• 步骤

  • （log write）当需要更新文件系统时，我们并不是更新文件系统本身。假设我们在内存中缓存了bitmap block，也就是block 45。当需要更新bitmap时，我们并不是直接写block 45，而是将数据写入到log中，并记录这个更新应该写入到block 45。对于所有的写 block都会有相同的操作，例如更新inode，也会记录一条写block 33的log。
  • （commit op）之后在某个时间，当文件系统的操作结束了，比如说我们前一节看到的4-5个写block操作都结束，并且都存在于log中，我们会commit文件系统的操作。这意味着我们需要在log的某个位置记录属于同一个文件系统的操作的个数，例如5。
  • （install log）当我们在log中存储了所有写block的内容时，如果我们要真正执行这些操作，只需要将block从log分区移到文件系统分区。我们知道第一个操作该写入到block 45，我们会直接将数据从log写到block45，第二个操作该写入到block 33，我们会将它写入到block 33，依次类推。
  • （clean log）一旦完成了，就可以清除log。清除log实际上就是将属于同一个文件系统的操作的个数设置为0。

• 原子性的原因 —— log的head的部分commit值要么是非0，要么为0

  • write ahead rule协议，也就是说在写入commit记录之前，你需要确保所有的写操作都在log中。
  • 在重启的时候，文件系统会查看log的commit记录值，如果是0的话，那么什么也不做。如果大于0的话，我们就知道log中存储的block需要被写入到文件系统中，很明显我们在crash的时候并不一定完成了install log，我们可能是在commit之后，clean log之前crash的。所以这个时候我们需要做的就是reinstall（注，也就是将log中的block再次写入到文件系统），再clean log。

• XV6的log结构如往常一样也是极其的简单。我们在最开始有一个header block，也就是我们的commit record，里面包含了：

  • 数字n代表有效的log block的数量
  • 每个log block的实际对应的block编号

File system challenges

• 第一个是cache eviction（缓存驱逐）。假设transaction还在进行中，我们刚刚更新了block 45，正要更新下一个block，而整个buffer cache都满了并且决定撤回block 45。在buffer cache中撤回block 45意味着我们需要将其写入到磁盘的block 45位置，这里会不会有问题？如果我们这么做了的话，会破坏什么规则吗？是的，如果将block 45写入到磁盘之后发生了crash，就会破坏transaction的原子性。
  所以对于还未写入log的缓存，需要先pin，提交commit后才能unpin

• 第二个挑战是，文件系统操作必须适配log的大小。 执行一次文件系统操作的log不够用
  在XV6中，总共有30个log block（注，详见14.3）。当然我们可以提升log的尺寸，在真实的文件系统中会有大得多的log空间。但是无所谓啦，不管log多大，文件系统操作必须能放在log空间中。如果一个文件系统操作尝试写入超过30个block，那么意味着部分内容需要直接写到文件系统区域，而这是不被允许的，因为这违背了write ahead rule。所以所有的文件系统操作都必须适配log的大小。
  如果写入的block数超过了30，那么一个写操作会被分割成多个小一些的写操作
  为什么XV6的log大小是30？因为在xv6，30比任何一个文件系统操作涉及的写操作数都大

• 最后一个要讨论的挑战是并发文件系统调用 不止一个事务在提交（执行多次文件系统操作）
  假设我们有一段log，和两个并发的执行的transaction，其中transaction t0在log的前半段记录，transaction t1在log的后半段记录。可能我们用完了log空间，但是任何一个transaction都还没完成。（t0和t1表示 不同的文件系统操作，而不是事务序号，xv6没有事务序号）

  现在我们能提交任何一个transaction吗？我们不能，因为这样的话我们就提交了一个部分完成的transaction，这违背了write ahead rule，log本身也没有起到应该的作用。**所以必须要保证多个并发transaction加在一起也适配log的大小。**所以当我们还没有完成一个文件系统操作时，我们必须在确保可能写入的总的log数小于log区域的大小的前提下，才允许另一个文件系统操作开始。

  **XV6通过限制并发文件系统操作的个数来实现这一点。**在begin_op中，我们会检查当前有多少个文件系统操作正在进行。如果有太多正在进行的文件系统操作，我们会通过sleep停止当前文件系统操作的运行，并等待所有其他所有的文件系统操作都执行完并commit之后再唤醒。这里的其他所有文件系统操作都会一起commit。有的时候这被称为group commit，因为这里将多个操作像一个大的transaction一样提交了，这里的多个操作要么全部发生了，要么全部没有发生。