16 文件、目录与文件系统实现 — 从 open() 到 inode 的访问路径Copy Anchor Link

1. 这一章讲什么Copy Anchor Link

前两章给了硬件(磁盘慢在哪、RAID 怎么冗余)。本章建文件系统 本身:先讲接口层(open/read/write、目录和硬链接怎么用), 再讲实现层——一个非常简单的教学文件系统 vsfs 把磁盘切成 超级块、位图、inode 表、数据区四块,然后带你把 open("/foo/bar") 一路走到磁盘块;最后用 FFS 回答「为什么这么简单的东西 曾经只有 2% 的磁盘带宽」——答案是局部性,而局部性要用 磁盘感知的布局来换。

2. 顶层全景Copy Anchor Link

  接口层:文件 = 字节数组(low-level 名字 = inode 号)
    目录 = (名字, inode 号) 对的列表;路径遍历 = 沿目录逐级查
    硬链接 = 多个名字指向同一 inode(links count 记引用数)
        │
  磁盘布局(vsfs,64 块玩具盘):
    [S 超级块 | i inode 位图 | d 数据位图 | I inode 表 ×5 | D 数据区 ×56]
    inode = 文件的元数据:类型/大小/权限/时间/数据块指针(12 直接 +
            1 一级间接 + 1 二级间接 → 4GB 文件)
        │
  访问路径:open("/foo/bar") =
    读根 inode(号 2)→ 读根目录数据找 foo(号 44)→ 读 foo inode
    → 读 foo 目录数据找 bar → 读 bar inode ── 每次 open 至少 4 次读!
  write 还要再加:位图找空闲块、更新 inode、更新目录 ── 建个文件至少 4 次写
        │
  FFS 的答案:磁盘感知
    盘分柱面组;组内全套结构(超级块副本+位图+inode+数据)
    策略一句话:相关的放一起(文件和它同目录的兄弟、inode 和它的数据块)

图说:四层从外到内——接口、布局、访问路径、性能补救。

3. 核心原理Copy Anchor Link

3.1 接口层三句话Copy Anchor Link

文件对程序就是一个字节数组,用 open/read/write/close 操作; 文件名是给人看的,系统内部的低级名字(low-level name)是 inode 号。目录是特殊的文件,内容是一串 (名字, inode 号) 对 外加两个固定条目 .(自己)和 ..(父目录)¹。 硬链接让两个文件名指向同一 inode,inode 里的 links count 记 被引用了几次,归零才真正释放——所以「删文件」的动词其实是 unlink:从某个目录里摘掉一个名字²。软链接(存路径的文本文件) 与它相对,书里也给了对照。

3.2 vsfs 的磁盘布局:四块结构Copy Anchor Link

把分区看成一串 4KB 块,书里用 64 块的玩具盘(照抄骨架)³:

图说:布局的核心思想是数据与元数据分家;位图是分配结构, 只在「要分新块」时才查——读文件根本不需要碰它⁴。

inode 怎么找到:inode 号是纯计算。读 inode 32: 偏移 = 32 × 256B = 8192;inode 表起于 12KB → 字节地址 20KB → 扇区 20×1024/512 = 扇区 40,一次磁盘读拿下⁵。

inode 怎么指向数据——多级索引(主线例子的账)。 inode 里放不下大文件的全部块指针,解法是一棵故意不平衡的树: 12 个直接指针 + 1 个一级间接 + 1 个二级间接⁶。

• 12 个直接指针 × 4KB = 48KB:小文件的零跳读。
• 一级间接指针指向一块「指针块」(4KB ÷ 4B = 1024 个指针): 文件到 (12+1024)×4KB ≈ 4MB。
• 二级间接再套一层:+(1024×1024) 块 → 文件轻松过 4GB⁷。

为什么故意不平衡?实测的文件系统「真理」之一:大多数文件很小 (最常见的尺寸约 2KB)——12 个直接指针让绝大多数文件的读 一跳直达⁸。另一个候选设计是区段(extent): 「起始块 + 长度」两段表示连续区域,元数据紧凑, ext4/XFS 用它(等会儿 LFS 和闪存章还会遇到这个取舍)。

3.3 主线例子:open 然后 read,一次要走多少块Copy Anchor Link

文件 /foo/bar(12KB = 3 块)。open 的完整路径(书里的 图 40.3 时序)⁹:

1. 根 inode 号是「众所周知」的(2 号)。读含 2 号 inode 的块。
2. 从根 inode(文件树的起点,叫根目录,即 "/")找到根目录的数据块,读它,在里面找字符串 "foo" → 得到 foo 的 inode 号(假设 44)。
3. 读 44 号 inode;顺指针读 foo 的目录数据块,找 "bar" → bar 的 inode 号(假设 55)。
4. 读 55 号 inode(open 完成——至此 4 次磁盘读)。

然后每次 read():按 inode 里的直接指针读数据块(每块一次读)。 注意 open 已经做了全部寻路,read 只是顺序消费 inode 里的指针¹⁰。

write 和「创建文件」才是写放大之源:新建 /foo/bar.txt 要写 inode 位图、新 inode、数据位图、数据块、父目录数据块、 父目录 inode——至少 4–6 次写(书里旁注的感恩清单)¹¹。 这些写多数会先躺在页缓存里(本库 10 章的统一页缓存),但迟早落盘 ——「迟早」就是第 17 章崩溃一致性的问题。

3.4 FFS:2% 的带宽是怎么丢的,怎么找回来Copy Anchor Link

老 UNIX 文件系统的惨状(书中引 McKusick 等的测量): 带宽从开局的 20% 一路跌到 2%¹²。三个病根:

1. 块太小(512B):每个块都要付一次寻道+旋转,传输占比极低;
2. inode 离数据远:先读 inode 再读数据,必 seek;
3. 自由列表碎片化:删删建建之后,「下一个空闲块」散在全盘, 一个逻辑上连续的文件物理上七零八落(书里 A1A2__C1C2 的例子: 删了 B、D 再建四块的 E,得到 E1E2__C1C2__E3E4 的碎片布局)¹³。

FFS 的药方(1984,Berkeley):让文件系统「磁盘感知」—— 接口不变(同组 API),内部全改¹⁴。

结构:盘分柱面组(cylinder group:同一半径的磁道在各面上的 合集;现代盘隐藏几何,Linux 用「块组」代替)。每组自带全套 ——超级块副本(可靠)、inode 位图、数据位图、inode 表、数据区。 好处一:相关文件放同组,来回不跨长寻道;好处二:超级块有备份¹⁵。

策略一句话:「相关的放一起,不相关的放远」¹⁶:

• 目录 → 挑「目录少、空闲 inode 多」的组(均衡 + 余量);
• 文件 → 数据块和它的 inode 同组;同目录的文件同组。 书里的对照图:FFS 法让 /a/c /a/d /a/e 同住 1 组; 朴素轮转法把它们摊到 3 组,名字局部性丢失¹⁷。

这条策略不是精细研究出来的,书里的原话是「good old-fashioned common sense」——但实测站得住:SEER 访问轨迹里, 约 40% 的文件访问是「同一个文件或同一目录」(距离 0 或 1), 另有 25% 距离为 2¹⁸。编译一个项目「源文件一群、.o 一群」的 访问模式,正好是同目录局部性的现实版。

块大小也顺带治了:4KB 大块 + 内部碎片可接受(多数文件也 不止 512B 了),传输效率立起来。结果是 FFS 把带宽从 2% 拉回到 接近盘峰值,还定下了此后四十年的范式:接口不变、内部自由进化 ——今天所有现代文件系统都是 FFS 的儿孙¹⁹。

4. 作者的判断与证据Copy Anchor Link

书里给了证据的判断:

• open 访问路径的每一次磁盘读都有结构对应(图 40.3);
• 「大多数文件很小」等六条测量结论引自 Agrawal 等的研究⁸;
• FFS 的局部性假设有 SEER 轨迹的量化验证(40% 距离 ≤1)¹⁸。

作者的判断(立场):

• inode 多级索引的「不平衡树」被点名为有意的设计, 依据是工作负载的测量——这是「结构跟随测量」的示范;
• 对 FFS 策略的评价很直白:常识 + 实测,不是什么高深理论—— 这句话本身是个方法论立场。

5. 边界与局限Copy Anchor Link

• vsfs/FFS 都假设磁盘几何可知;现代盘只导出逻辑块号, 所以「柱面」只剩历史意义,但「分组的局部性」思想活着 (ext4 的块组、SSD FTL 的通道并行,都是它的后代)。
• 本章没有覆盖:缓存(写入缓冲策略)、崩溃一致性(下一章)、 日志结构(再下一章)——文件系统四大话题,此处只解决「布局与访问」。
• 目录的线性扫描在大目录下是瓶颈(XFS 用 B 树,书里给了指针); 创建文件要检查重名,所以 create 的代价随目录大小线性涨。

6. 可带走的Copy Anchor Link

1. 心智模型两问(书里旁注的原话):盘上有什么结构? 每个系统调用读写哪些结构?——答得出这两问,文件系统就懂了。
2. inode 号是计算出来的,不是查出来的:号 × 大小 + 表起点 = 磁盘地址。
3. 多级索引的不平衡是故意的:为「多数文件小」优化; 设计数据结构前先测工作负载。
4. open 的寻路成本是 O(路径深度) 次磁盘读; 路径缓存(dcache)为什么存在,从这里就能推出来。
5. 「相关的放一起」是普适策略:文件系统的柱面组、数据库的聚簇索引、 编译器的结构体字段排布,全是一个思想。
6. 接口稳定、内部革新——FFS 留下的最大遗产其实是这条工程政治智慧。

7. 原文地图Copy Anchor Link