写在前面：这是本系列的第二十三篇。

文件系统为我们实现了树（和图）状的目录结构，并提供了丰富的 API 让我们实现增删改查。实际上，文件系统就是在底层存储系统（Block I/O，块设备）之上，实现的一个支持修改、查询操作的数据结构。

本讲内容：我们将化身文件系统的架构师，探索如何在极度受限的磁盘块上设计数据结构，从 1980 年代的 FAT 文件系统一路演进到现代文件系统的终极形态。

什么是文件系统？

Block devices (块设备)… 以块为单位进行 read 和 write 的设备。

块设备上的数据结构 Abstract DataType (ADT)

• 文件系统的本质，就像我们在内存里设计数据结构一样。
• 只不过，底层的介质不是 Random Access Memory (RAM)，而是 Block I/O (块设备)。
• 内存里的 new/delete 非常快，但在 M5 (mymalloc) 实验中，大家可能没考虑过物理“块”的问题，而在磁盘上，读写放大是致命的。

// 在 C++ 的视角下，文件系统就是这样一棵多态的对象树
struct FSObject {
    virtual ~FSObject() = default;
};

struct File : FSObject {
    vector<char> content; // 字节序列
};

struct Directory : FSObject {
    map<string, unique_ptr<FSObject>> children; // 目录包含子对象
};

用块设备虚拟块设备 (LVM)

Logical Volume Manager (LVM，逻辑卷管理器)

LVM 支持一些极其极客的骚操作… 比如瞬间打快照、无缝热扩容。

今天的文件系统可以扩容了：AI 时代的正确解决方法

• 我们需要知道的仅仅是“什么可以做”。
• 有一天，你在公司的服务器上看到了 LVM。
• 你多嘴问一句：LVM 可以做什么？
• 世界上的技术知识已经多到“不可能全部搞清楚”了，但这不妨碍我们很好地使用它们。
• 遇到问题：“我有一个 LVM vg1，如何将分区扩容到 100%？”
• AI 会精准提供有效的命令线索：vgdisplay, lvextend, resize2fs。
• Anyway, LVM 在操作系统的眼里，它依旧只是一个被虚拟出来的块设备。

---

File Allocation Table (FAT)

我们要如何在块设备上实现这个巨大的“数据结构”？

实现文件系统：敌人和朋友

敌人：读/写放大

• 存储设备的物理特性：被迫只能读写连续的一块数据（通常是 512B 或 4KB）。
• 不能像 Memory Hierarchy 那样随心所欲地操作单字节。

朋友：局部性

• 适当地排布数据，使得临近的数据有“一同访问”的倾向。
• 允许数据暂时停留在内存（Buffer Cache），延迟写回磁盘。

需求分析：时间回到 1980 年

5.25" 软盘：单面 160 KiB

• 一共只有 320 个 512B 扇区 (sectors)。
• 在这样简陋的设备上实现文件系统，应该选用怎样的数据结构？

系统特征：

• 相当小的文件系统。目录中一般只有几个、十几个文件。
• 以小文件为主 (都在几个 block 以内)。
• 文件的实现方式： 本质上就是 struct block * 的链表。任何复杂的高级数据结构（比如 B+ 树）在这里都显得极其浪费。
• 目录的实现方式： 目录就是一个普通的文件（被称为“目录文件”），操作系统会把它的内容解读成 struct dentry[] 数组。

用链表存储数据：两种设计抉择

1. 在每个数据块的末尾放置 Next 指针

• 优点： 实现简单、无须单独开辟全局存储空间。
• 缺点： 数据的大小不再是 $ 2^k $（如果 block size 为 512，可用数据区就只剩 508 字节）。这会导致跨块拷贝极其痛苦。
• lseek 读放大极其严重：想读文件的最后一个字节，必须把前面的所有块全读一遍才能顺藤摸瓜找到最后！

2. 将所有指针集中存放在文件系统的某个独立区域

• 优点： 局部性极好；lseek 可以在内存里瞬间算完，速度飞快。
• 缺点： 集中存放的数据一旦损坏，整个磁盘的数据链将彻底丢失！

微软的选择：FAT (集中保存所有指针)

先算一笔账：

• 160 KB 的软盘，320 个扇区。
• 用 12-bit entry（FAT12）来存指针，总共只要 480B。
• 惊人事实：只需要 1 个扇区，就能存下整个磁盘的 next[] 数组！哪怕容量翻倍，也就 2 个扇区。

File Allocation Table (文件分配表)：

• 既然这么小，那就在内存里直接缓存一份 FAT 数组的副本（反正读一次磁盘也是最少读 512B）。
• 有了内存缓存，结合延迟写回，读/写放大的问题就完全解决了！

FAT 链接存储文件的原理：

• int next[];
• next[i] == 0: Free (本块未分配)。
• next[i] == -1: EOF (本块是文件的最后一个块)。
• 可靠性问题的补救： 集中存储容易坏？那就连续存 $ n $ 份副本（通常是 FAT1 和 FAT2 两份）！

目录树实现：目录文件

目录就是个普通文件。

• 只是在 metadata 里打了个标记 (mode = directory)。
• DOS 时代的经典：“8 + 3” 文件名规范（如 AUTOEXEC.BAT）。文件名最多 8 个字符，扩展名 3 个字符，默认中间有一个点。

历史的包袱：

• 总有一天，8 + 3 文件名会不够用的（比如你想存一个长长的 MP3 名字）。
• 微软想出的补丁极其猥琐：用连续的几个“短目录项”强行拼凑成一个长文件名（VFAT）。

极客实践：直接观察与恢复 FAT

• 所谓“快速格式化”（mkfs.fat），其实就是把 FAT 表清空而已。
• 所有的文件内容（包括目录文件里的数据）都还在磁盘的 Data 区里，只是在数据结构眼里，它们变成了无人认领的 “free block”。
• 数据恢复软件的原理：猜出文件系统的参数（SecPerClus, BytsPerSec），然后全局扫描特征码，强行把断掉的 next 关系拼接回来！

FAT 性能与可靠性总结

性能：

• 优势：对小文件简直太合适了，极其轻量。
• 劣势：大文件的随机访问是灾难。4 GB 的文件（假设 4 KB 一个 cluster），想跳到末尾，必须在内存里的 FAT 数组执行 $ 2^{20} $ 次 next 追溯操作。
• 在 FAT 时代，磁盘使用久了会产生严重的碎片 (fragmentation)，需要用“磁盘碎片整理程序”跑上一整夜。

---

UNIX 文件系统 (ext2 家族)

我们想要一个更好的文件系统！

基于真实世界的统计观察：

• 大多数文件都很小（约 2K 是最常见的）。
• 大多数的磁盘空间，却被少数极其巨大的文件占据（数据库、视频等）。
• 目录通常都很小：大部分目录包含的文件不到 20 个。
• 启示：如果目录项 <= 20，顺序遍历数组的性能远好于维护复杂的 B 树。

UNIX 文件系统的改进：iNode

改进 1：支持硬链接

• 文件系统的拓扑从 树 $ \rightarrow $ 图。
• 允许一个底层物理文件，存在多份引用。因此，struct node (数据本身) 和 struct edge (目录里记录的文件名) 必须分家！

改进 2：支持大文件 $ O(1) $ 随机读写

• UNIX 引入了 “iNode” (index node，索引节点) 的概念。
• 它保存了所有的元数据：Mode, Links, User/Group, Size, Time。
• 核心：它内部包含了一个多级索引的数据结构（类似于 map<int,int> 映射 file offset $ \rightarrow $ block id）。

ext2：联合数据结构 (Fast/Slow Path)

• “Superblock (超级块)”： 记录文件系统全局的元数据（inode 总数量、block 大小等）。

ext2 iNode 极具智慧的索引设计：

• 直接块 (Direct blocks): 指针直接指向数据块，用于满足绝大多数的小文件（极速读取）。
• 间接块 (Indirect / Double / Triple blocks): 当文件很大时，指针指向的是一个“存满指针的块”。通过二级、三级树状索引，轻松支撑起 TB 级别的巨型文件，并实现 $ O(1) $ 复杂度的随机寻址。

ext2 目录文件

在目录文件上实现的数据结构，本质上就是一个 map<string,int> (将文件名映射到 inode 号)。

ext2 性能与局限

• 局部性与缓存： bitmap 和 inode 都有集中存储的局部性，可通过内存缓存大幅减少读写放大。
• 大文件友好： 极速的 $ O(1) $ 随机读写，inode 在磁盘上连续存储，便于预取。
• 致命弱点： 可靠性依然是短板。存储 inode 的核心数据块一旦损坏，整个文件就灰飞烟灭了。系统断电极易造成文件系统不一致（后来 ext3/ext4 引入了日志 Journaling 来拯救它）。

---

现代文件系统 (Spicy 🌶️)

既然文件系统就是存储器上的数据结构，那黑客们玩的花活可就太多了！
比如引入 Persistent data structure, learned index…

1. 数据结构不一定要写在内核里 (FUSE)

FUSE: Filesystem in Userspace (用户态文件系统)

• 违背祖宗的决定：文件系统不在内核态跑，而在用户态跑！
• 内核里只放一个很小的 FUSE Kernel Module 负责转发协议 (/dev/fuse)。
• 开发者直接用普通的 C/Python/Go 代码调用 libfuse，就能手搓一个文件系统。极其适合开发网盘挂载工具（如 macFUSE）。

// 在用户态只需要实现这几个业务函数，你就能造一个文件系统
struct fuse_operations null_oper = {
    .getattr    = null_getattr,
    .truncate   = null_truncate,
    .open       = null_open,
    .read       = null_read,
    .write      = null_write,
};

2. Everything is a B-Tree (btrfs)

B-Tree Filesystem (btrfs)

• 反正只要“实现文件系统 API”就行，那干脆把整个底层换成极其强悍的 B 树！
• 彻底解决碎片问题，并顺带白嫖了无敌的高级特性：热扩缩容 (resize)、透明数据压缩、以及做快照不花钱（得益于 B 树的 Copy-on-Write 机制）。

Btrfs 的特点：

• 快照： 可以瞬间创建文件系统的快照（不消耗额外空间），方便备份和恢复。
• 原生 RAID 支持： 内置软件 RAID 控制，提高数据可靠性。
• 在线修复： 可以在线检查和修复底层错误，无需卸载重启。

3. 针对特定硬件极限优化的现代 FS

• Flash-Friendly Filesystem (f2fs): 华为/三星等手机里常用的底层文件系统，专为 NAND Flash 的擦写特性（磨损均衡、避免随机小写操作）量身定制，极大地延长了闪存寿命并减少卡顿。
• Enhanced Read-only Filesystem (erofs): 华为开源的只读文件系统。利用透明压缩技术，极限压缩系统分区的大小，专门为安卓系统的只读系统镜像优化，读取速度快得惊人。

---

总结

Take-away messages:

把文件系统理解成一个持久化设备上的 “数据结构”，我们就不难理解从古典时代到现代文件系统各种眼花缭乱的设计理念了。

本质上，所有的文件系统都是在为了适配特定的硬件物理特性（软盘、机械磁盘、SSD 闪存）、特定的读写 Workload（小文件碎片化、大文件吞吐），用当时最聪明的方式去组织数据，维护那棵迷人的树状目录结构，并支撑起极其高效的文件随机访问。