23. 文件系统的实现

File Allocation Table

要设计并实现一个文件系统，我们首先需要关注并解决存储媒介带来的两大核心挑战：

读写放大 (Read/Write Amplification)：现代存储设备（无论是机械硬盘还是固态硬盘）的物理特性决定了，它们最高效的读写方式是操作连续的大块数据区域，我们称之为一个块 (Block)。如果需要修改一个块中哪怕一个字节的数据，也必须将整个块读入内存、修改、再完整写回。这种“操作少量数据却导致整块数据被读写”的现象就是读写放大，它会严重影响性能。
局部性 (Locality)：程序的内存访问行为通常具有局部性原理 (Principle of Locality)，即在一段时间内，访问的地址会集中在某个区域。文件系统可以通过合理的数据排布，让物理上相邻的数据块在逻辑上也相关联（例如，属于同一个文件），从而在读取一块数据时，可以利用预读机制将后续可能被访问的数据也加载到内存缓存中，提高效率。

在软盘上实现文件系统

我们的需求是为一个存储容量很小的设备（如软盘）设计一个文件系统。在这种场景下，使用复杂的树形数据结构（如 B+ 树）会因为元数据本身占用过多空间而显得浪费。因此，一个简单的链式结构是更合适的选择。

目录的实现

在简单的文件系统中，目录本身可以被实现为一个普通的文件。这个文件的特殊之处在于，它的内容遵循一种固定格式，即一个目录项数组。

1
2
3
4
5
6
// 一个简单的目录项 (dentry) 结构
struct dentry {
    char filename[256];        // 文件名
    unsigned int start_block;  // 文件数据起始块的编号
    unsigned int size;         // 文件大小 (以字节为单位)
};

当我们需要打开一个目录时，文件系统只需读取这个文件的内容，并将其解析为一个 struct dentry 数组即可。

文件数据的存储

用链表来组织一个文件的所有数据块，主要有两种实现思路。

方法一：在每个数据块后放置指针
这种方法非常直观。每个数据块的末尾都留出一小块空间，用于存放下一个数据块的地址或编号。
- 优点：实现简单，逻辑清晰。
- 缺点：
  1. 极差的随机访问性能：要访问文件的第 N 个数据块，必须从第一个块开始，依次读入前 N-1 个块来找到第 N 块的指针。这需要 N-1 次磁盘 I/O，对于大文件而言是毁灭性的。
  2. 空间浪费：每个数据块都不能被 100% 用来存储文件内容，必须牺牲一部分空间给指针。
方法二：将指针集中存放在文件系统的某个区域
为了解决上述问题，我们可以将所有数据块的“链表指针”抽离出来，集中存放在一个被称为文件分配表 (File Allocation Table, FAT) 的核心数据结构中。
FAT 本质上是一个大数组。数组的下标与磁盘上的数据块编号一一对应。数组中存储的值则是该文件链表中的下一个数据块的编号。
它是如何工作的？
1. 一个文件的起始块号记录在它的目录项 (dentry) 中。
2. 假设文件从第 100 号块开始，我们查询 FAT[100]，如果值为 105，那么 105 号块就是文件的第二个数据块。
3. 接着我们查询 FAT[105]，得到下一个块号，如此往复，直到遇到一个特殊的文件结尾标记。
- 优点：
  1. 大幅改善的随机访问：虽然仍然需要遍历链表，但这个遍历过程发生在 FAT 表内部。因为 FAT 表相比整个磁盘要小得多，可以被完整加载到内存中缓存。要访问第 N 个数据块，只需要在内存中进行 N-1 次数组查询，这比 N-1 次磁盘 I/O 快了几个数量级。
  2. 数据块纯净：数据块可以 100% 用于存储文件内容，没有元数据混入。
- 写回策略：对文件结构的修改（如新增/删除数据块）可以先在内存中的 FAT 缓存上进行，然后利用延迟写回 (Write-back Caching) 机制，在稍后的某个时刻一次性将更新后的 FAT 表写回磁盘，合并了多次 I/O 操作，提升了性能。

Unix 文件系统

FAT 文件系统虽然巧妙，但仍有其局限性，无法满足现代操作系统的复杂需求：

支持链接：我们希望多个文件名可以指向同一个文件实体。
支持高效的任意大小文件随机访问：对于非常大的文件，在 FAT 表中线性扫描仍然耗时。我们需要一种能实现 O(1) 或 O(logN) 复杂度查找的数据结构。

为了解决这些问题，Unix 文件系统引入了一个核心概念：inode (索引节点)。

inode 是一个独立于文件名的元数据结构，它存储了除文件名之外的、关于一个文件的所有信息，例如：

文件模式（权限位）
所有者和用户组 ID
文件大小
时间戳（创建、修改、访问时间）
用于索引文件数据块的数据结构

inode 的引入将文件名和文件元数据彻底分离。目录项 (dentry) 的作用被简化为只维护 文件名 -> inode 编号 的映射关系。这天然地支持了硬链接 (Hard Link)：多个不同的目录项可以包含相同的 inode 编号，指向同一个文件实体。

为了解决高效随机访问问题，ext2 文件系统的 inode 采用了一种非常经典的多级索引结构：

1
2
3
4
5
6
7
8
// ext2 inode 结构示意
struct ext2_inode {
    // ... 其他元数据 ...
    unsigned int direct_blocks[12];      // 12个直接指针
    unsigned int singly_indirect_block;  // 1个一级间接指针
    unsigned int doubly_indirect_block;  // 1个二级间接指针
    unsigned int triply_indirect_block;  // 1个三级间接指针
};

直接指针 (Direct Pointers)： inode 中直接包含 12 个指针，每个指针指向一个数据块。对于小文件（小于 12 个块），只需读取 inode 就可以获得所有数据块的位置，访问速度极快。
一级间接指针 (Singly Indirect Pointer)：如果文件大于 12 个块，文件系统会启用这个指针。它指向一个“指针块”，这个块里不存数据，而是存满了指向数据块的指针。假设一个块能存 1024 个指针，这一级就能多索引 1024 个数据块。
二级/三级间接指针 (Doubly/Triply Indirect Pointers)：以此类推，二级间接指针指向一个存储着一级间接指针块地址的块。这种树状的索引结构，仅需极少的几次磁盘读取（最多 4 次，inode -> 三级 -> 二级 -> 一级 -> 数据块），就能定位超大文件中任意一个数据块的位置，实现了真正高效的随机访问 (Random Access)。

存储器上的数据结构

传统上，文件系统的所有逻辑都实现在操作系统的内核 (Kernel) 中，因为它需要直接管理硬件并保证系统安全与性能。

然而，现代操作系统提供了一些机制，允许在用户空间 (User Space) 实现文件系统，最著名的就是 FUSE (Filesystem in Userspace)。

FUSE 的工作原理是，内核提供一个通用的文件系统驱动，当有文件操作请求时，该驱动会将请求转发给一个在用户空间运行的守护进程。这个进程负责实现所有的文件系统逻辑（如何解析路径、读取数据等），然后将结果返回给内核。

优点：开发、调试和测试变得极为方便，无需修改和重新编译内核。一个用户态文件系统的崩溃也不会影响整个系统的稳定性。这催生了大量创新的文件系统，如 sshfs（将远程服务器目录挂载到本地）、s3fs（将云存储挂载到本地）等。
缺点：每次文件操作都需要在内核态和用户态之间进行上下文切换 (Context Switch)，带来了额外的性能开销，通常不适用于对性能要求极致的场景。

File Allocation Table#

在软盘上实现文件系统#

Unix 文件系统#

存储器上的数据结构#

File Allocation Table

在软盘上实现文件系统

Unix 文件系统

存储器上的数据结构