第 40 章 文件系统实现

第 40 章 文件系统实现

文件系统是纯软件，其核心机制可通过简单文件系统（VSFS，典型 UNIX 文件系统的简化版）来理解。理解文件系统需把握两个关键方面：数据结构（磁盘上的数据组织方式）和访问方法（系统调用如何映射到这些结构）。

整体组织与数据结构

磁盘被划分为固定大小的块（如 4KB）。VSFS 的磁盘布局包含以下区域：

• 数据区域 (Data Region)：占据磁盘绝大部分空间，用于存放用户数据。
• Inode 表 (Inode Table)：存放 inode 结构数组。每个 inode 保存一个文件的元数据。
• 分配结构 (Allocation Structures)：记录块的分配状态。VSFS 使用位图 (Bitmap)：
  • 数据位图 (Data Bitmap)：记录数据块的空闲/分配状态。
  • Inode 位图 (Inode Bitmap)：记录 inode 的空闲/分配状态。
• 超级块 (Superblock)：包含文件系统全局元数据（如 inode 和数据块总数、inode 表起始位置、标识文件系统类型的幻数）。挂载时操作系统首先读取超级块。

文件组织：inode

inode（索引节点）保存文件的元数据，通过 inode 号（inumber）隐式引用。文件系统可通过 inumber 直接计算出 inode 在磁盘上的扇区地址：

blk = (inumber * sizeof(inode_t)) / blockSize;
sector = ((blk * blockSize) + inodeStartAddr) / sectorSize;

元数据内容

inode 包含文件类型、大小、分配块数、权限、时间戳以及数据块指针。

表：ext2 的 inode 结构示例

大小（字节）	名称	inode 字段的用途
2	mode	读/写/执行权限
2	uid	所有者
4	size	字节数
4	time/ctime/mtime/dtime	访问/创建/修改/删除时间
2	links count	硬链接数
4	blocks	分配的块数
60	block	15 个磁盘指针
…	…	其他 OS 相关或 ACL 字段

数据块寻址机制

多级索引 (Multi-level Index)

• 直接指针：直接指向数据块（通常 12 个，优化小文件访问）。
• 间接指针 (Indirect pointer)：指向包含直接指针的块。
• 双重/三重间接指针：支持 GB 级甚至更大的文件。
• 设计依据：大多数文件很小（约 2KB），多级索引树的不平衡设计正是为了优化小文件访问，同时兼顾大文件。

表：文件系统测量汇总

观察结果	详情
大多数文件很小	约 2KB 是常见大小
大多数字节保存在大文件中	少数大文件使用了大部分空间
文件系统大约一半是满的	保持约 50% 占用率
目录通常很小	大多数少于 20 个条目

其他寻址方案

• 范围 (Extent)：使用指针加长度（块数）指定连续的磁盘区域。不如指针灵活，但元数据更紧凑。
• 链表 (Linked list)：inode 仅指向首块，首块指向下一块。FAT 文件系统通过在内存中维护文件分配表（FAT）来优化其随机访问性能。

目录组织

目录被视为特殊类型的文件，其 inode 被标记为“目录”类型。目录的数据块包含 (条目名称, inode 号) 列表。

示例目录数据结构：

inum	reclen	strlen	name
5	4	2	.
2	4	3	..
12	4	4	foo

• 包含 .（当前目录）和 ..（父目录）。
• 删除文件会在目录中留下空白，通常通过保留 inode 号（如 0）或复用记录长度（reclen）来处理。

空闲空间管理

VSFS 通过数据位图和 inode 位图管理空闲空间。分配新文件时，扫描位图寻找空闲项并标记为已用。 现代文件系统常采用 预分配 (Pre-allocation) 策略，在需要数据块时寻找一系列连续空闲块（如 8 块）分配给新文件，以保证磁盘上的连续性并提升性能。

访问路径：读取和写入

读取文件

以 open("/foo/bar", O_RDONLY) 并读取 1 块为例：

1. 路径遍历：从根目录 / 开始。根目录的 inode 号是固定已知的（通常为 2）。
2. 读取根 inode → 读取根目录数据块，找到 foo 的 inode 号。
3. 读取 foo inode → 读取 foo 目录数据块，找到 bar 的 inode 号。
4. 读取 bar inode 到内存，进行权限检查并分配文件描述符。
5. 读取数据 (read)：查询 bar 的 inode 找到数据块位置 → 读取数据块 → 写入更新 inode 的最后访问时间。

注意：单纯的读取操作不会访问分配结构（位图）。

写入文件

写入涉及分配新块，开销显著。写入单个新数据块需要 5 次 I/O：

1. 读取数据位图。
2. 写入数据位图（标记已分配）。
3. 读取 inode。
4. 写入 inode（更新块指针）。
5. 写入真正的数据块。

创建文件（如 /foo/bar）开销更大，涉及：读取/写入 inode 位图、写入新 inode、读取/写入目录数据块、读取/写入目录 inode 等多达 10 次 I/O。

缓存和缓冲

为降低高昂的 I/O 成本，文件系统积极利用内存。

缓存 (Caching) 降低读取开销

• 统一页面缓存 (Unified Page Cache)：现代操作系统采用动态划分，将虚拟内存页面和文件系统页面集成，根据需求灵活分配内存，避免了早期固定大小缓存的内存浪费。
• 缓存命中可消除路径遍历和文件读取带来的大量磁盘 I/O。

写缓冲 (Write Buffering) 优化写入性能

写入必须落盘以保证持久性，但将写入在内存中延迟（通常 5~30 秒）有以下优势：

1. 批处理 (Batching)：将多次元数据更新（如位图修改）合并为单次 I/O。
2. 调度 (Scheduling)：在内存中缓冲写入，便于系统优化后续 I/O 的磁盘调度。
3. 避免写入 (Avoidance)：若文件创建后迅速被删除，延迟写入可直接抵消这些磁盘操作。

权衡：延迟写入存在系统崩溃导致数据丢失的风险。需要强持久性的应用（如数据库）可通过 fsync()、直接 I/O 或绕过文件系统使用原始磁盘来强制落盘。