本章要解决什么

上一章我们站在用户这一边，学会了 open/read/write/link/unlink 这些接口。这一章翻到接口的另一面：用一个极简的文件系统 vsfs（Very Simple File System），看看"文件""目录""inode 号"在磁盘上到底是什么样子，一次 open("/foo/bar") 会引发多少次磁盘读写。

文件系统是纯软件：和 CPU、内存虚拟化不同，这里不需要新的硬件支持。正因为自由度大，才有了从 AFS 到 ZFS 的各种设计。vsfs 是一个简化版的 UNIX 文件系统，后面几章（FFS、日志、LFS）都是在它的基础上改进"性能"或"崩溃一致性"。所以这一章是整个持久化部分的地基——请把本页的两个模拟器都亲手玩一遍。

核心概念速览

思考文件系统的方式

原书建议从两个方面理解任何一个文件系统：

1. 数据结构（data structures）：磁盘上用什么结构组织数据和元数据？vsfs 用最简单的"块数组"；更复杂的文件系统（如 SGI XFS）用 B 树之类的树形结构。
2. 访问方法（access methods）：进程调用 open()、read()、write() 时，文件系统要读哪些结构、写哪些结构？效率如何？

整体组织：64 个块的 vsfs

先把磁盘分区切成大小相同的块（block），vsfs 选常用的 4KB。假设分区非常小，只有 64 个块（编号 0–63）。接下来一步步决定这些块里放什么——点下面的按钮，跟着原书的推理顺序把布局"搭"出来；点任意一个块可以查看它的用途。

推理顺序是这样的：

• 数据区（data region）：文件系统里绝大部分空间应该留给用户数据。先预留最后 56 块（8–63）。
• inode 表（inode table）：每个文件的元数据放在一个 inode 里。inode 通常只有 128 或 256 字节；按 256 字节算，一个 4KB 块能放 16 个 inode。拿 5 块（3–7）做 inode 表，就有 5 × 16 = 80 个 inode——这也就是这个文件系统最多能容纳的文件数（在更大的磁盘上可以分配更大的 inode 表）。
• 分配结构（allocation structures）：要知道哪些 inode、哪些数据块是空闲的。vsfs 用两个位图：inode 位图（块 1）和数据位图（块 2）。一整块 4KB 的位图可以追踪 32K 个对象，对 80 个 inode 和 56 个数据块来说大材小用，但图简单。
• 超级块（superblock）：剩下的块 0 放超级块，记录"有 80 个 inode、56 个数据块、inode 表从块 3 开始"之类的全局信息，外加一个标识文件系统类型的魔数。挂载（mount）时操作系统先读超级块，初始化各种参数，再把这个卷接到目录树上。

inode：文件的"档案卡"

inode 是 index node（索引节点）的缩写：最早的 UNIX 把这些节点存成数组，用编号去索引它。每个 inode 由一个数字隐式标识，叫 i-number，也就是上一章说的文件的低级名字（low-level name）。在 vsfs 这种简单的文件系统里，给定 i-number，就能直接算出它在磁盘上的位置：

blk    = (inumber * sizeof(inode_t)) / blockSize;              // 第几个 inode 块
sector = ((blk * blockSize) + inodeStartAddr) / sectorSize;   // 该块的起始扇区

原书的例子：inode 表从 12KB 开始（超级块 0KB、inode 位图 4KB、数据位图 8KB），每个 inode 256 字节。要读 inode 32：表内偏移 32 × 256 = 8192，加上起始地址 12KB 得到 20KB；磁盘不能按字节寻址，只能按 512 字节的扇区读，所以发出读扇区 20 × 1024 / 512 = 40 的请求，把包含 inode 32 的整块（iblock 2，也就是块 5）读进来。自己换几个数试试：

inode 里存着关于文件的几乎一切：类型（普通文件、目录……）、大小、分配了多少块、权限与属主、各种时间，以及数据块在哪里。这些统称为元数据（metadata）——文件系统里凡不是纯用户数据的信息都叫元数据。下面是简化的 ext2 inode（原书 Figure 40.1）：

注意：inode 里没有文件名。名字存在目录里（见后文）；ext2 甚至把文件类型也记在目录项里。这正是硬链接能成立的原因——多个名字可以指向同一个 inode。

多级索引：inode 怎样指向数据块

inode 设计里最重要的决定之一：怎样记录数据块的位置。最简单的办法是放若干个直接指针（direct pointer），每个指针是一个磁盘块地址。但这样文件最大只能是"块大小 × 直接指针数"——12 个直接指针 × 4KB = 48KB，显然不够。

于是引入间接指针（indirect pointer）：它不指向用户数据，而是指向一个装满指针的块。4KB 的块、4 字节的地址，一个间接块能装 1024 个指针，文件可以长到 (12 + 1024) × 4KB = 4144KB。还不够？再加双重间接指针（double indirect pointer）：它指向一个"装满间接块指针"的块，又多出 1024 × 1024 ≈ 100 万个块，文件可以超过 4GB：(12 + 1024 + 1024²) × 4KB。再往上是三重间接指针。这棵"一边倒"的不平衡树就叫多级索引（multi-level index）。

为什么要用这么不平衡的树？因为几十年的测量一再发现同样的"事实"（原书 Figure 40.2，来自 Agrawal 等人的研究）：

既然大多数文件很小，就为小文件优化：12 个直接指针让 inode 直接覆盖 48KB，读小文件不需要任何额外的索引块；只有大文件才付出读间接块的代价。ext2、ext3、NetApp WAFL 和原始 UNIX 文件系统都采用多级索引。

目录的存储

在 vsfs 里（很多文件系统也一样），目录的组织非常简单：它的数据块里就是一串 (名字, inode 号)。名字可变长，所以每项还带长度。原书的例子：目录 dir（inode 5）里有 foo、bar、foobar_is_a_pretty_longname 三个文件，inode 号分别为 12、13、24。

• inum：inode 号；reclen：这条记录占的总字节数（名字加上可能剩余的空间）；strlen：名字的实际长度（含结尾的 \0，所以 foo 是 4）；name：名字本身。
• 每个目录都有两项特殊记录：. 指向自己，.. 指向父目录（这里是根，inode 2）。
• 删除文件（unlink()）会在目录中间留下空洞，可以用保留的 inode 号（如 0）标记为空闲。这也是需要 reclen 的原因：新建的名字可以复用一条更大的旧记录，记录里就留有多余空间。

目录存在哪里？文件系统通常把目录当作一种特殊的文件：它也有一个 inode（类型字段标为"目录"），inode 指向若干数据块（也可以有间接块），这些数据块就放在普通的数据区里。所以磁盘布局不需要任何改变。线性列表也不是唯一选择：XFS 把目录存成 B 树，创建文件时检查"名字是否已存在"就不必扫描整个列表。

空闲空间管理

文件系统必须知道哪些 inode 和数据块是空闲的，分配新文件 / 新目录时才有地方放。vsfs 用两个位图：

• 创建文件：在 inode 位图里找一个空闲 inode 分配给它，把那一位标成 1，并（最终）把位图写回磁盘。
• 分配数据块：同理，在数据位图里找空位。
• 预分配（pre-allocation）策略：ext2/ext3 给新文件分配数据块时，会找一串连续的空闲块（比如 8 块）一起分配，保证文件至少有一部分在磁盘上是连续的，提高后续顺序读写的性能。

模拟器：仿 vsfs.py 观察磁盘状态的变化

下面的模拟器复现了原书作业工具 vsfs.py 的模型：一个只有 8 个 inode、8 个数据块的小文件系统，开始时只有根目录（inode 0，数据块 0）。每执行一个操作，就能看到 inode 位图、inode 表、数据位图、数据块发生了什么变化（黄框 = 本步改动，红色虚线 = 本步释放）。显示格式与 vsfs.py 相同：

• inode：[d a:0 r:2] 表示目录（d）、数据块地址 0、引用计数 2；[f a:-1 r:1] 是还没有数据块的空文件；[] 是空闲 inode。
• 数据块：目录块显示目录项 [(.,0) (..,0) (g,1)]；文件块显示一个字母，代表它的内容；[] 是空闲块。
• 和 vsfs.py 一样，每个文件最多只有 1 个数据块；分配策略是"找编号最小的空闲项"。

访问路径：读和写一个文件时发生了什么

知道了磁盘上有什么，接下来追踪系统调用的访问路径（access path）。假设文件系统已经挂载，超级块已在内存中，其他一切（inode、目录）都还在磁盘上。

读文件 /foo/bar

执行 open("/foo/bar", O_RDONLY) 时，文件系统先要找到 bar 的 inode，但它手里只有路径名，所以必须遍历路径（traverse the pathname）：

1. 一切遍历从根目录开始。根的 inode 号必须是"众所周知"的（根没有父目录可查），大多数 UNIX 文件系统里是 2。读入包含 inode 2 的块（第一个 inode 块）。
2. 从根 inode 里的指针找到根目录的数据块，读进来，在里面找 foo 这一项，得到 foo 的 inode 号（比如 44）。
3. 递归：读 foo 的 inode，再读 foo 的目录数据，找到 bar 的 inode 号。
4. 最后把 bar 的 inode 读进内存，做权限检查，在进程的打开文件表里分配一个文件描述符返回给用户。

之后每次 read()：查 inode 找到下一块的地址 → 读数据块 → 更新 inode 的最后访问时间（一次写），并更新内存中打开文件表里的偏移。close() 只需释放文件描述符，不产生磁盘 I/O。

创建并写文件 /foo/bar

写文件可能需要分配新块（除非是覆盖写），于是每次写不仅要写数据，还要决定用哪个块，并更新相应结构。一次分配型写入逻辑上产生 5 次 I/O：读数据位图、写数据位图、读 inode、写 inode（记录新块地址）、写数据块本身。

创建文件更贵：要分配 inode，还要在目录里分配空间。读 inode 位图、写 inode 位图、写新 inode（初始化）、写目录数据（名字 → inode 号）、读写目录 inode（更新大小和时间）……再加上路径遍历，原书例子里一次 create 就是 10 次 I/O。如果目录需要变大，还得再分配数据块（数据位图 + 新目录块）。

下面的模拟器逐行复现原书 Figure 40.3（读）和 Figure 40.4（创建 + 三次写）的时间线表格，时间向下增长。你还可以改变路径深度、调用次数，或者打开"页缓存"看看 I/O 数量怎样骤减。

两个结论值得记住：

• open 产生的 I/O 与路径长度成正比：路径上每多一层目录，就要多读它的 inode 和（至少一块）数据。目录很大时，可能要读很多数据块才找到目标项。
• 写比读更糟，创建更糟：读文件，每块 3 次 I/O；写新文件，每块 5 次 I/O；创建 10 次 I/O——而且这些 I/O 散布在磁盘各处（位图、inode 表、数据区），全是寻道。

原书脚注里的"小谜题"：创建 bar 时为什么要先读它还没初始化的 inode？因为 inode 很小（256B），而磁盘按块（4KB）读写，同一块里还有别的 inode。要更新其中一个，只能先读整块、改其中一部分、再写回——读-改-写（read-modify-write）。

缓存与缓冲

答案是利用内存（DRAM）缓存重要的块。没有缓存，打开 /1/2/3/.../100/file.txt 这样的长路径要做好几百次读。

从静态划分到统一页缓存

早期文件系统在启动时分配一块固定大小的缓存（大约占内存的 10%），用 LRU 之类的策略决定保留哪些块。问题是这种静态划分（static partitioning）很浪费：文件系统暂时用不着 10% 的内存时，这些页也不能挪作他用。现代操作系统采用动态划分（dynamic partitioning）：把虚拟内存页和文件系统页合并成统一页缓存（unified page cache），谁需要更多内存就多给谁。

有了缓存，第一次打开文件可能产生大量 I/O 来读目录的 inode 和数据，但之后再打开同一个文件（或同一目录下的文件），基本都会命中缓存，不需要 I/O。在上面的时间线模拟器里把缓存切到"有页缓存"就能看到：读 /foo/bar 并读 3 块，从 14 次 I/O 降到 9 次（冷）甚至 1 次（热）。

写缓冲

写就不一样了：读 I/O 可以被足够大的缓存完全消除，但写最终必须到达磁盘才能持久。不过写缓冲（write buffering）仍有三大好处：

1. 批处理（batch）：inode 位图在创建一个文件时被改了，片刻后又因为创建另一个文件被改——推迟写入，两次修改只需一次 I/O。
2. 调度：内存里攒了一批写，就可以对它们排序、调度，提高磁盘效率。
3. 避免写：应用创建一个文件又马上删掉，推迟写就能完全省掉这些 I/O。此时"懒"是一种美德。

因此大多数现代文件系统会把写在内存里缓冲 5 到 30 秒。这又是一个权衡：系统在刷盘前崩溃，这些更新就丢了；缓冲得越久，性能越好（批处理、调度、避免写）。

数据库这类应用不接受这种权衡，于是它们用 fsync() 强制落盘、用绕过缓存的直接 I/O（direct I/O）接口，或干脆使用裸磁盘接口（raw disk）完全绕开文件系统。大多数应用接受文件系统的默认选择，但需要时总有办法让系统按你的要求做。

先预测，再验证

inode bitmap  11100000
inodes        [d a:0 r:3] [d a:1 r:2] [f a:2 r:1] [] [] [] [] []
data bitmap   11100000
data          [(.,0) (..,0) (a,1) (c,2)] [(.,1) (..,0)] [a] [] [] [] [] []

动手实验

cd labs/40-fs-impl && make && ./sparse && ./fiemap && ./cache

$ ./sparse
== 1. 文件大小 vs 分配的数据块 ==
inode=1034668   size=0           blocks=0   (=  0 KB) links=1  <- 刚创建（空文件）
inode=1034668   size=1           blocks=8   (=  4 KB) links=1  <- 写入 1 字节后
inode=1034668   size=49153       blocks=16  (=  8 KB) links=1  <- 在偏移 48KB 处再写 1 字节
inode=1034668   size=1073741825  blocks=24  (= 12 KB) links=1  <- 在偏移 1GB 处再写 1 字节

== 2. 目录也是文件：条目多了，目录要分配更多数据块 ==
inode=1030428   size=4096        blocks=8   (=  4 KB) links=2  <- 空目录
inode=1030428   size=4096        blocks=8   (=  4 KB) links=2  <- 目录里有 51 个文件后
inode=1030428   size=12288       blocks=24  (= 12 KB) links=2  <- 目录里有 101 个文件后
inode=1030428   size=16384       blocks=32  (= 16 KB) links=2  <- 目录里有 201 个文件后
inode=1030428   size=36864       blocks=80  (= 40 KB) links=2  <- 目录里有 401 个文件后
inode=1030428   size=36864       blocks=80  (= 40 KB) links=2  <- 删掉 400 个文件后（目录不收缩）

$ ./fiemap
fiemap-test.dat: size=4259840 字节, inode=1030428, extent 数=2
  #   逻辑偏移(4K块) 物理位置(4K块) 长度(块) 标志
  0   0                  127213568          256        
  1   1024               127218688          16         LAST 

$ ./cache
== 写缓冲：write() 返回 ≠ 数据已落盘 ==
200 次 4KB 追加写，不 fsync   :     1.02 ms（平均每次    5.1 µs）
200 次 4KB 追加写，每次 fsync :   352.24 ms（平均每次 1761.2 µs）
写 64 MB：write() 循环用时     89.2 ms  ← 数据只是进了页缓存（脏页）
          随后 fsync() 用时     27.0 ms  ← 这时才等设备把脏页真正写下去

== 读缓存：第二次读几乎不碰磁盘 ==
第 1 次读（已尽量清缓存）  :     31.6 ms  ( 2023 MB/s)
第 2 次读（命中页缓存）    :     19.2 ms  ( 3340 MB/s)
O_DIRECT 读（绕过页缓存）  :     30.4 ms  ( 2105 MB/s)

自测题

常见误区与小结

和后续章节的联系：vsfs 完全不考虑磁盘的物理特性，数据块可能被放得很散——下一章的 FFS（快速文件系统）就是要让文件系统"懂磁盘"，改进局部性。上面看到的"一次创建 10 次写、分散在各处"如果中途断电怎么办？这就是第 42 章崩溃一致性（fsck 与日志）要解决的问题。而"写都要到处寻道"的问题，第 43 章的 LFS 给出了激进的答案：把所有写都变成顺序写。