8. 文件系统

• 文件系统概述
• 文件系统 crash & logging

• ext3

  1. 文件系统概述

  1.1 文件系统层次

  文件系统中核心的数据结构为 inode 和 file descriptor，后者主要提供给用户进程使用。从分层的角度来看，文件系统的层次如下： :::warning

• 在最底层是磁盘，也就是一些实际保存数据的存储设备，正是这些设备提供了持久化存储。

• 在这之上是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。
• 再往上，就是文件名，和文件描述符操作。 :::

  1.2 磁盘结构

  从文件系统的角度来看磁盘，磁盘就是一个 block 数组，从 0 开始，一直到磁盘的最后。而文件系统的工作就是将所有的数据结构以一种能够重启之后重新构建文件系统的方式，存放在磁盘上。虽然有不同的方式，但是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 存储了文件的内容和目录的内容。

2. 文件系统 crash & logging

2.1 Crash

这个问题可能出现的场景可能是这样，当你在运行 make 指令时，make 与文件系统会有频繁的交互，并读写文件，但是在 make 执行的过程中断电了，可能是你的笔记本电脑没电了，也可能就是停电了，之后电力恢复之后，你重启电脑并运行ls指令，你会期望你的文件系统仍然在一个好的可用的状态。
这里我们关心的 crash 或者故障包括了：

• 在文件系统操作过程中的电力故障
• 在文件系统操作过程中的内核panic

包括XV6在内的大部分内核都会 panic，panic 可能是由内核bug引起，它会突然导致你的系统故障，但是你肯定期望能够在重启之后还能使用文件系统，xv6 解决该问题的方式是 logging。

2.2 logging

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

• （log write）当需要更新文件系统时，我们并不是更新文件系统本身。假设我们在内存中缓存了bitmap block，也就是block 45。当需要更新bitmap时，我们并不是直接写block 45，而是将数据写入到log中，并记录这个更新应该写入到block 45。对于所有的写 block 都会有相同的操作，例如更新 inode，也会记录一条写 block 33 的log。所以基本上，任何一次写操作都是先写入到log，我们并不是直接写入到block所在的位置，而总是先将写操作写入到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。

2.2.1 log

整个 logging system 有一个全局唯一 log 结构来维护相关信息

// Contents of the header block, used for both the on-disk header block
// and to keep track in memory of logged block# before commit.
struct logheader {
  int n;
  int block[LOGSIZE];
};
struct log {
  struct spinlock lock;
  int start;
  int size;
  int outstanding; // how many FS sys calls are executing.
  int committing;  // in commit(), please wait.
  int dev;
  struct logheader lh;
};
struct log log;

2.2.2 begin_op

xv6 文件系统的操作都由 begin_op 与 end_op 操作包起来，begin_op 的代码如下：

void
begin_op(void)
{
  acquire(&log.lock);
  while(1){
    if(log.committing){
      sleep(&log, &log.lock);
    } else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){
      // this op might exhaust log space; wait for commit.
      sleep(&log, &log.lock);
    } else {
      log.outstanding += 1;
      release(&log.lock);
      break;
    }
  }
}

正常情况下 ，递增 log.outstanding ，该参数表示操作期间（begin_op ~ end_op）文件系统系统调用的次数。
如果当前正在 commit 或者 log block 不够，则进入 sleep 状态，等待条件满足。

2.2.3 log_wirte

该操作主要更新 log header，log header 主要记录了当前有几块 log block 需要更新lh.n，对应 log block 的 block 编号是多少 lh.block。
首次执行 log_write 时，log.lh.n == 0 ,因此会触发 Add new block。
后续如果重复更新某个 log block

// Caller has modified b->data and is done with the buffer.
// Record the block number and pin in the cache by increasing refcnt.
// commit()/write_log() will do the disk write.
//
// log_write() replaces bwrite(); a typical use is:
//   bp = bread(...)
//   modify bp->data[]
//   log_write(bp)
//   brelse(bp)
void
log_write(struct buf *b)
{
  int i;

  acquire(&log.lock);
  if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
    panic("too big a transaction");
  if (log.outstanding < 1)
    panic("log_write outside of trans");

  // 先检索是否已经准备好更新这块 log block 了，如果之前已经记录了，则无需其他操作。
  for (i = 0; i < log.lh.n; i++) {
    if (log.lh.block[i] == b->blockno)   // log absorption
      break;
  }
  log.lh.block[i] = b->blockno;
  if (i == log.lh.n) {  // Add new block to log?
    bpin(b);
    log.lh.n++;
  }
  release(&log.lock);
}

2.2.4 end_op

end_op 主要负责：

• 检查当前是否可以进入 Commit 阶段

• 有可能 begin_op 会由于 log space 不足（根据 log.outstanding 的值来计算需要多少 log space），陷入 sleep 状态，因此尝试 wakeup log，因为此时已经结束了一次 outstanding operation，log.outstanding -= 1

  // called at the end of each FS system call.
  // commits if this was the last outstanding operation.
  void
  end_op(void)
  {
  int do_commit = 0;
  
  acquire(&log.lock);
  log.outstanding -= 1;
  if(log.committing)
    panic("log.committing");
  if(log.outstanding == 0){
    do_commit = 1;
    log.committing = 1;
  } else {
    // begin_op() may be waiting for log space,
    // and decrementing log.outstanding has decreased
    // the amount of reserved space.
    wakeup(&log);
  }
  release(&log.lock);
  
  if(do_commit){
    // call commit w/o holding locks, since not allowed
    // to sleep with locks.
    commit();
    acquire(&log.lock);
    log.committing = 0;
    wakeup(&log);
    release(&log.lock);
  }
  }
  

  2.2.5 commit

  Commit 阶段分为几个步骤：

• 将 log block 的数据从内存中写入到磁盘

• 将 log header 的数据从内存中写入到磁盘（记录了这次 commit 要写入几块 block 到 log block），此处写完基本上 Commit 阶段的任务就已经完成了

• 准备进入下一个 Install 阶段，Install 完毕后清空 log header 的记录

  static void
  commit()
  {
  if (log.lh.n > 0) {
    write_log();     // Write modified blocks from cache to log
    write_head();    // Write header to disk -- the real commit
    install_trans(0); // Now install writes to home locations
    log.lh.n = 0;
    write_head();    // Erase the transaction from the log
  }
  }
  

  2.2.6 install_trans

  Install 阶段就是将数据从 log block 真正落地到实际的 data block

  // Copy committed blocks from log to their home location
  static void
  install_trans(int recovering)
  {
  int tail;
  
  for (tail = 0; tail < log.lh.n; tail++) {
    struct buf *lbuf = bread(log.dev, log.start+tail+1); // read log block
    struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst
    memmove(dbuf->data, lbuf->data, BSIZE);  // copy block to dst
    bwrite(dbuf);  // write dst to disk
    if(recovering == 0)
      bunpin(dbuf);
    brelse(lbuf);
    brelse(dbuf);
  }
  }
  

  到此一次完整的 logging 就结束了。

  2.2.7 小结

  logging 最重要的地方在于遵循 write ahead rule 原则，每一个阶段只有当其真正落地到磁盘之后，才标记完成。
  一次 logging 的步骤如下：

  1. log write : 更新 log header，记录有哪些 block 需要写入到 log block
  2. commit log：将 log header 中保存的 block 更新到 log block 落地到磁盘中
  3. install log：将 log block 的数据 copy 到实际数据需要落地的位置
  4. clean log : 清理 log 记录

2.3 recover_from_log

这里主要做系统故障时，重启系统时的恢复工作

static void
recover_from_log(void)
{
  read_head();
  install_trans(1); // if committed, copy from log to disk
  log.lh.n = 0;
  write_head(); // clear the log
}

其主要步骤如下：

1. 系统启动完毕，调用 init_log 初始化 logging system
2. logging system 调用 recover_from_log 准备恢复数据
3. recover_from_log 首先从磁盘读取 log header 结构
4. 调用 install_trans 恢复数据，如果 log header 中发现没有 log block 需要迁移数据的，那么 nothing happen ~
5. 删除 commit 记录（清空 log header）

3. Ext3

基本上是 xv6 课程抄录的一些笔记

3.1 问题

XV6的 logging 有什么问题？为什么 Linux 不使用与 XV6 完全一样的 logging 方案？这里的回答简单来说就是 XV6 的 logging 太慢了。
XV6中的任何一个例如 create/write 的系统调用，需要在整个 transaction 完成之后才能返回。所以在创建文件的系统调用返回到用户空间之前，它需要完成所有 end_op 包含的内容，这包括了：

• 将所有更新了的block写入到log
• 更新 header block
• 将 log 中的所有 block 写回到文件系统分区中
• 清除header block

之后才能从系统调用中返回。在任何一个文件系统调用的 commit 过程中，不仅是占据了大量的时间，而且其他系统调用也不能对文件系统有任何的更新。所以这里的系统调用实际上是一次一个的发生，而每个系统调用需要许多个写磁盘的操作。这里每个系统调用需要等待它包含的所有写磁盘结束，对应的技术术语被称为 synchronize。XV6的系统调用对于写磁盘操作来说是同步的（synchronized），所以它非常非常的慢。在使用机械硬盘时，它出奇的慢，因为每个写磁盘都需要花费10毫秒，而每个系统调用又包含了多个写磁盘操作。所以XV6每秒只能完成几个更改文件系统的系统调用。如果我们在SSD上运行XV6会快一些，但是离真正的高效还差得远。
另一件需要注意的更具体的事情是，在XV6的 logging 方案中，每个block都被写了两次。第一次写入到了log，第二次才写入到实际的位置。虽然这么做有它的原因，但是 ext3 可以一定程度上修复这个问题。

3.2 Ext3 如何提升性能

ext3 通过3种方式提升了性能：

• 首先，它提供了异步的（asynchronous）系统调用，也就是说系统调用在写入到磁盘之前就返回了，系统调用只会更新缓存在内存中的block，并不用等待写磁盘操作。不过它可能会等待读磁盘。
• 第二，它提供了批量执行（batching）的能力，可以将多个系统调用打包成一个 transaction。
• 最后，它提供了并发（concurrency）。

3.2.1 Asynchronous（异步）

应用程序可以调用一些文件系统的系统调用，但是应用程序可以很快从系统调用中返回并继续运算，与此同时文件系统在后台会并行的完成之前的系统调用所要求的写磁盘操作。这被称为 I/O concurrency，如果没有异步系统调用，很难获得 I/O concurrency.

3.2.2 Batching（批量执行）

第二个 ext3 使用的技术是批量执行（batching）。在任何时候，ext3只会有一个open transaction。ext3中的一个transaction可以包含多个不同的系统调用。所以ext3是这么工作的：它首先会宣告要开始一个新的transaction，接下来的几秒所有的系统调用都是这个大的transaction的一部分。我认为默认情况下，ext3每5秒钟都会创建一个新的transaction，所以每个transaction都会包含5秒钟内的系统调用，这些系统调用都打包在一个transaction中。在5秒钟结束的时候，ext3会commit这个包含了可能有数百个更新的大 transaction。
为什么这是个好的方案呢？

• 首先它在多个系统调用之间分摊了transaction带来的固有的损耗。固有的损耗包括写 transaction 的 descriptor block 和 commit block；在一个机械硬盘中需要查找 log 的位置并等待磁碟旋转，这些都是成本很高的操作，现在只需要对一批系统调用执行一次，而不用对每个系统调用执行一次这些操作，所以batching可以降低这些损耗带来的影响。
• 另外，它可以更容易触发 write absorption。经常会有这样的情况，你有一堆系统调用最终在反复更新相同的一组磁盘block。举个例子，如果我创建了一些文件，我需要分配一些inode，inode或许都很小只有64个字节，一个block包含了很多个inode，所以同时创建一堆文件只会影响几个block的数据。类似的，如果我向一个文件写一堆数据，我需要申请大量的data block，我需要修改表示block空闲状态的bitmap block中的很多个bit位，如果我分配到的是相邻的data block，它们对应的bit会在同一个bitmap block中，所以我可能只是修改一个block的很多个bit位。所以一堆系统调用可能会反复更新一组相同的磁盘block。通过batching，多次更新同一组block会先快速的在内存的block cache中完成，之后在transaction结束时，一次性的写入磁盘的log中。这被称为write absorption，相比一个类似于XV6的同步文件系统，它可以极大的减少写磁盘的总时间。
• 最后就是disk scheduling。假设我们要向磁盘写1000个block，不论是在机械硬盘还是SSD（机械硬盘效果会更好），一次性的向磁盘的连续位置写入1000个block，要比分1000次每次写一个不同位置的磁盘block快得多。我们写log就是向磁盘的连续位置写block。通过向磁盘提交大批量的写操作，可以更加的高效。这里我们不仅通过向log中连续位置写入大量block来获得更高的效率，甚至当我们向文件系统分区写入包含在一个大的transaction中的多个更新时，如果我们能将大量的写请求同时发送到驱动，即使它们位于磁盘的不同位置，我们也使得磁盘可以调度这些写请求，并以特定的顺序执行这些写请求，这也很有效。在一个机械硬盘上，如果一次发送大量需要更新block的写请求，驱动可以对这些写请求根据轨道号排序。甚至在一个固态硬盘中，通过一次发送给硬盘大量的更新操作也可以稍微提升性能。所以，只有发送给驱动大量的写操作，才有可能获得disk scheduling。这是batching带来的另一个好处。

3.2.3 Concurrency（并发性）

ext3使用的最后一个技术就是 concurrency，相比XV6这里包含了两种 concurrency。 :::warning

• 首先ext3允许多个系统调用同时执行，所以我们可以有并行执行的多个不同的系统调用。在ext3决定关闭并commit当前的transaction之前，系统调用不必等待其他的系统调用完成，它可以直接修改作为transaction一部分的block。许多个系统调用都可以并行的执行，并向当前transaction增加block，这在一个多核计算机上尤其重要，因为我们不会想要其他的CPU核在等待锁。在XV6中，如果当前的transaction还没有完成，新的系统调用不能继续执行。而在ext3中，大多数时候多个系统调用都可以更改当前正在进行的transaction。

• 另一种ext3提供的并发是，可以有多个不同状态的transaction同时存在。所以尽管只有一个open transaction可以接收系统调用，但是其他之前的transaction可以并行的写磁盘。这里可以并行存在的不同transaction状态包括了：

  • 首先是一个open transaction
  • 若干个正在commit到log的transaction，我们并不需要等待这些transaction结束。当之前的transaction还没有commit并还在写log的过程中，新的系统调用仍然可以在当前的open transaction中进行。
  • 若干个正在从cache中向文件系统block写数据的transaction
  • 若干个正在被释放的transaction，这个并不占用太多的工作 :::

    3.3 Ext3 log 结构

    Ext3 的 log 结构与 XV6 非常相似。主要的区别在于 ext3 可以同时跟踪多个在不同执行阶段的 transaction。
    接下来我们详细看一下ext3的 log 中有什么，这与XV6中的 log 有点不一样。在 log 的最开始，是 super block。这是 log 的 super block，而不是文件系统的 super block。log 的 super block包含了 log 中第一个有效的 transaction 的起始位置和序列号。起始位置就是磁盘上 log 分区的 block 编号，序列号就是前面提到的每个 transaction都有的序列号。log 是磁盘上一段固定大小的连续的 block。log中，除了super block以外的block存储了 transaction。每个 transaction在log中包含了：

• 一个 descriptor block，其中包含了 log 数据对应的实际 block 编号，这与 XV6 中的 header block 很像。

• 之后是针对每一个 block 编号的更新数据。
• 最后当一个 transaction 完成并 commit 了，会有一个 commit block

因为log中可能有多个 transaction，commit block 之后可能会跟着下一个 transaction 的 descriptor block，data block 和 commit block。所以 log 可能会很长并包含多个 transaction。我们可以认为 super block 中的起始位置和序列号属于最早的，排名最靠前的，并且是有效的 transaction。

这里有一些细节对于后面的内容很重要。在 crash 之后的恢复过程会扫描 log，为了将 descriptor block 和 commit block 与 data block 区分开，descriptor block 和 commit block 会以一个 32bit 的魔法数字作为起始。这个魔法数字不太可能出现在数据中，并且可以帮助恢复软件区分不同的 block。

3.4 Ext3 Commit 步骤

基于上面的系统调用的结构，接下来我将介绍 commit transaction 完整的步骤。每隔5秒，文件系统都会 commit 当前的 open transaction，下面是 commit transaction 涉及到的步骤：

1. 首先需要阻止新的系统调用。当我们正在 commit 一个 transaction 时，我们不会想要有新增的系统调用，我们只会想要包含已经开始了的系统调用，所以我们需要阻止新的系统调用。这实际上会损害性能，因为在这段时间内系统调用需要等待并且不能执行。
2. 第二，需要等待包含在 transaction 中的已经开始了的系统调用们结束。所以我们需要等待 transaction 中未完成的系统调用完成，这样 transaction 能够反映所有的写操作。
3. 一旦 transaction 中的所有系统调用都完成了，也就是完成了更新 cache 中的数据，那么就可以开始一个新的 transaction，并且让在第一步中等待的系统调用继续执行。所以现在需要为后续的系统调用开始一个新的transaction。
4. 还记得 ext3 中的 log 包含了descriptor，data 和 commit block吗？现在我们知道了 transaction 中包含的所有的系统调用所修改的block，因为系统调用在调用 get 函数时都将 handle 作为参数传入，表明了 block 对应哪个transaction。接下来我们可以更新 descriptor block，其中包含了所有在 transaction 中被修改了的block编号。
5. 我们还需要将被修改了的 block，从缓存中写入到磁盘的 log 中。之前有同学问过，新的 transaction 可能会修改相同的 block，所以在这个阶段，我们写入到磁盘 log 中的是 transaction 结束时，对于相关 block cache 的拷贝。所以这一阶段是将实际的 block 写入到 log 中。
6. 接下来，我们需要等待前两步中的写log结束。
7. 之后我们可以写入commit block。
8. 接下来我们需要等待写 commit block 结束。结束之后，从技术上来说，当前 transaction 已经到达了 commit point，也就是说 transaction 中的写操作可以保证在面对 crash 并重启时还是可见的。如果 crash 发生在写 commit block 之前，那么 transaction 中的写操作在 crash 并重启时会丢失。
9. 接下来我们可以将 transaction 包含的 block 写入到文件系统中的实际位置。
10. 在第9步中的所有写操作完成之后，我们才能重用 transaction 对应的那部分 log 空间。

3.5 小结

• log是为了保证多个步骤的写磁盘操作具备原子性。在发生 crash 时，要么这些写操作都发生，要么都不发生。这是 logging 的主要作用。
• logging的正确性由 write ahead rule 来保证。你们将会在故障恢复相关的业务中经常看到 write ahead rule 或者 write ahead log（WAL）。write ahead rule的意思是，你必须在做任何实际修改之前，将所有的更新 commit 到 log 中。在稍后的恢复过程中完全依赖 write ahead rule。对于文件系统来说，logging 的意义在于简单的快速恢复。log中可能包含了数百个 block，你可以在一秒中之内重新执行这数百个 block，不管你的文件系统有多大，之后又能正常使用了。
• 最后有关 ext3 的一个细节点是，它使用了批量执行和并发来获得可观的性能提升，不过同时也带来了可观的复杂性的提升。