Appearance
文件系统：inode、链接、分配与磁盘调度
一句话总览：文件系统在「块设备（只认 read_block(id) / write_block(id) 的字节序列）」之上，实现一棵目录树 + 随机访问的文件这一数据结构。面试核心是 inode 模型、硬/软链接、三种文件分配方式、空闲空间管理、磁盘调度算法 与 崩溃一致性（Page Cache / 日志）。
一、文件系统的职责
- 命名与组织：把无结构的磁盘块，抽象成有名字、有层级（目录树）的「文件」。
- 抽象接口：
open/read/write/lseek/close、mkdir/rmdir/link/unlink/rename等一组系统调用。 - 地址映射：把「文件的第 N 个字节」翻译为「某块设备的某个块」。
- 管理元数据：权限、属主、时间戳、大小、块指针。
- 空间管理：分配 / 回收数据块，维护空闲空间。
- 一致性与持久化：崩溃后仍能恢复到一致状态（日志 / fsck）。
从「文件」到磁盘：应用程序视角是一个字节流；文件系统视角是 逻辑块（如 4 KB）；磁盘视角是物理扇区 / 页。虚拟内存把「虚拟地址 → 物理页」，文件系统把「文件逻辑块号 → 物理块号」，两者思路高度一致。
二、文件的逻辑结构
| 逻辑结构 | 组织方式 | 优点 | 缺点 |
|---|---|---|---|
| 顺序文件 | 记录按顺序排列 | 顺序读写快、支持定长随机访问 | 插入 / 删除代价高 |
| 索引文件 | 建立索引表指向各记录 | 支持随机访问、可不定长 | 索引表额外开销 |
| 索引顺序文件 | 分组 + 组内顺序 + 组间索引 | 兼顾两者，是主流折中 | 实现较复杂 |
目录结构：从早期的单级 / 两级目录，到树形目录（现代主流），再到支持共享的有向无环图（DAG，靠链接实现）。目录项（directory entry）里存的是「文件名 → inode 号」的映射，而不是文件内容。
三、inode 详解
Q1. inode 存了什么？为什么不存文件名？ ⭐
答案
inode（索引节点）是文件的元数据容器，典型字段：
- 类型、权限（mode）、硬链接计数（
links）； - 属主
uid/ 属组gid； - 大小（
size）、占用块数； - 时间戳：
atime（访问）、mtime（内容修改）、ctime（元数据变更）； - 数据块指针（直接 / 间接索引）、以及 extent、xattr 等扩展。
关键点：inode 里没有文件名。 文件名存在目录项里（目录本质上是一个「文件名 → inode 号」的特殊文件）。这样设计的好处：
- 一个 inode 可被多个名字指向（硬链接）——名字与文件解耦，删除一个名字只是把
links减一； - 目录项可以做得很小，便于目录的查找与缓存；
- 重命名文件时只改目录项，inode 及其数据块完全不动，
mv同分区因此是 O(1)。
查看：stat file 可看到 inode 号、链接数、时间戳等。
Q2. inode 与数据块如何映射？最大文件多大？
答案
经典 ext2/ext3 用多级索引：inode 里有 12 个直接指针 + 1 个一级间接 + 1 个二级间接 + 1 个三级间接。
以 4 KB 块、4 字节指针 为例，每个间接块可放 4096 / 4 = 1024 个指针：
| 层级 | 块数 | 大小 |
|---|---|---|
| 12 个直接指针 | 12 | 48 KB |
| 1 个一级间接 | 1024 | 4 MB |
| 1 个二级间接 | 1024² | 4 GB |
| 1 个三级间接 | 1024³ | 4 TB |
最大文件 ≈ 4 TB + 4 GB + 4 MB + 48 KB。小文件只用直接指针（快），大文件才逐级展开（省 inode 空间）。ext4 改用 extent（连续区段） 描述，一个 extent 记录「起始块 + 长度」，大幅减少大文件的元数据项数，并支持延迟分配、多块分配等优化。
Q3. 系统如何从路径找到数据块？
答案
以 /home/a.txt 为例（简化）：
- 读超级块得到 inode 表位置、块大小、inode 位图、块位图；
- 从根 inode 出发，逐级读目录文件，解析目录项拿到下一级 inode 号；
- 最终拿到
a.txt的 inode，读其中的块指针 / extent； - 得到逻辑块到物理块的映射，通过块设备驱动读数据。
内核用 dentry cache（目录项缓存） 与 inode cache 缓存这条路径上的热点，避免每次都走磁盘。
四、硬链接 vs 软链接（符号链接）
| 维度 | 硬链接（hard link） | 软链接 / 符号链接（symbolic link） |
|---|---|---|
| 本质 | 目录项指向同一个 inode | 一个独立文件，内容是目标路径字符串 |
| inode | 与原文件共享同一 inode | 有自己的 inode |
| 创建 | ln a b | ln -s a b |
| 跨文件系统 | 不可以 | 可以 |
| 指向目录 | 通常不允许（避免环） | 允许 |
| 删除原文件 | 数据仍在（links 减 1，减到 0 才真正释放） | 变成悬空链接（dangling），访问报错 |
| 访问开销 | 与原文件相同 | 多一次「解析路径」的开销 |
| 大小 | 与目标相同（同一个 inode） | 等于路径字符串长度 |
记忆点：rm 减少的是链接计数；只有当 links == 0 且无人打开该文件时，块才被回收。一个「已删除但仍被进程打开」的文件会占着空间（lsof | grep deleted）——这正是「删了文件空间没释放」的经典原因。
五、文件分配方式
Q4. 连续、链式（FAT）、索引三种分配方式对比？
答案
| 方式 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 连续分配 | 文件占磁盘上一段连续块，目录记「起始块 + 长度」 | 顺序/随机访问都极快、磁头移动少 | 易产生外部碎片、文件增长困难（需预留 / 搬迁） |
| 链式分配 | 每个块末尾存下一块指针，目录记首块 | 无外部碎片、易增长 | 只支持顺序访问、指针占空间、一块损坏链即断 |
| FAT 变体 | 把链接指针集中到一张 FAT（文件分配表） | 指针集中、便于随机访问、可缓存 | FAT 表可能很大、需常驻内存 |
| 索引分配 | 每个文件一个索引块，记录所有数据块号（即 inode 多级索引） | 支持随机访问、无外部碎片、易增长 | 小文件也需索引块开销；大文件要多级索引 |
现代通用文件系统基本走索引分配（extent 化） 的路线。
六、空闲空间管理
| 方法 | 做法 | 备注 |
|---|---|---|
| 空闲表 | 记录「起始块 + 空闲长度」 | 类似连续分配，适合小而少 |
| 空闲链表 | 把所有空闲块链起来 | 分配/回收简单，遍历慢 |
| 位示图（bitmap） | 每一位对应一块，0 空闲 1 占用 | 支持快速查找连续块（ext/xfs 用），需常驻内存 |
| 成组链接 | 把空闲块分组，首块记录下一组块号 | 大量空闲块时节省链指针，UNIX 经典 |
现代多用位示图 + 空闲链表/树混合（如 ext 的块位图、ext4 的 extent 树）。
七、磁盘调度算法
硬盘（HDD）访问时间 = 寻道时间 + 旋转延迟 + 传输时间，其中寻道占大头，故调度目标是减少磁头移动。
经典题目：请求磁道序列 98, 183, 37, 122, 14, 124, 65, 67，磁头当前在 53，默认向磁道号增大方向移动。
text
FCFS : 53→98→183→37→122→14→124→65→67 移动 640 道
SSTF : 53→65→67→37→14→98→122→124→183 移动 236 道
SCAN : 53→65→67→98→122→124→183→199→37→14 移动 331 道（电梯，扫到端点再折返）
C-SCAN: 53→65→67→98→122→124→183→199→0→14→37 回到起点且回程不服务
LOOK : 53→65→67→98→122→124→183→37→14 移动 299 道（折返到最远请求即止）Q5. 各磁盘调度算法特点？
答案
- FCFS：按到达顺序，公平但寻道多，适合请求稀疏。
- SSTF（最短寻道时间优先）：每次选最近的请求。寻道少，但可能长期忽略远端请求（饥饿）。
- SCAN（电梯）：单方向服务到端点（或最远请求）再折返，兼顾效率与公平，无饥饿。
- C-SCAN：只在一个方向服务，回头不服务直接跳回起点，使各磁道等待时间更均匀。
- LOOK / C-LOOK：SCAN 的改进版，不必走到物理端点，到最远请求即折返，实际更常用。
SSD 无磁头，天然随机访问，不需要传统磁盘调度；多用 mq-deadline / kyber / none 等按队列与公平性调度（如 blk-mq）。文件系统层的 IO 调度（合并、排序、延迟）更多是为了提升吞吐与减少写放大。
八、Page Cache、写回与「崩溃会不会丢数据」
Q6. 进程写文件后崩溃，数据会丢吗？ ⭐
答案
关键看有没有 fsync。
write()默认只写入内核的 Page Cache（把页标记为 dirty）就返回，并未落盘；内核由回写线程（pdflush/kworker）按dirty_expire_centisecs、dirty_ratio等参数异步刷盘（默认数十秒级）。- 因此：只
write不fsync时崩溃 → 数据很可能丢失。 fsync(fd)同步「文件数据 + 全部元数据」；fdatasync(fd)只同步数据 + 必要元数据（size、块索引），更轻；sync()同步整个系统所有文件系统（只在关机/命令行用，性能杀手）。- 更极端：即便
fsync返回，若磁盘/SSD 自身的写缓存未落盘（无掉电保护），仍可能丢——需 FUA / flush / barrier 强制设备落盘（O_DIRECT则以牺牲缓存换取更强的落盘语义）。
工程结论：想要持久化，写完必须 fsync；要保证「重命名原子替换」这类模式安全，还需 fsync 目录（因为目录项是元数据）。这正是很多数据库 / 配置持久化的必备动作。
Q7. Buffered IO、O_DIRECT、Page Cache 的关系？
答案
- 默认是 Buffered IO：读写都经过 Page Cache，读写一致、可预读、可合并写，性能好；但崩溃语义弱（未 fsync 会丢）。
O_DIRECT：绕过 Page Cache，直接对接块设备，由应用自己管理缓存（数据库如 MySQL、RocksDB 常用）。代价是失去预读与合并，性能和语义都要自己拿捏。- 两者可混用但要小心一致性：同一文件被两种方式同时访问时，Page Cache 与设备内容可能不一致。
九、日志文件系统与崩溃一致性
Q8. 为什么需要日志（Journaling）？它怎么保证崩溃一致？ ⭐
答案
问题：一次「追加写文件」在底层是多块写——分配数据块（改块位图）、写数据块、更新 inode（size/索引），至少三个位置的写。若崩在中间，文件系统就会处于不一致状态（数据块已写但位图没标、inode 指向了没写的块……）。更糟的是，磁盘的写缓存会乱序落盘，多块写的顺序毫无保证。
思路一：fsck。崩溃后扫描整个磁盘，按已有图结构「猜」出最可能的一致状态。代价是全盘扫描、极慢，大磁盘上不可接受（还应防范 fsck 自己再崩）。
思路二：Write-Ahead Log（日志 / WAL，是现代主流）：
- 写
TxBegin； - 把本次事务要改的所有块先写入日志区；
- flush（确保日志落盘）；
- 写
TxEnd（提交标记）并 flush ——「数据落盘 happens-before 提交标记落盘」； - checkpoint：把日志里的修改**重放（replay）**到文件系统真实位置，然后回收日志空间。
崩溃恢复：若崩在提交标记之前 → 事务视为未提交，忽略；若崩在提交标记之后 → replay 日志即可恢复到一致状态。无需扫描全盘，这是日志相对 fsck 的核心优势。
工程优化：
- 批处理（batching）：多次系统调用合并成一个事务（xv6 / jbd2），减小日志开销；
- Checksum（ext4）：不再写 TxBegin/TxEnd，直接记事务长度 + 校验和，兼作日志完整性校验；
- Metadata journaling（ext4 默认）：只对 inode / 位图等元数据记日志，数据块直接写。好处是快，代价是文件内容可能丢失但目录结构始终一致（不会出现损坏的元数据）。
十、VFS（虚拟文件系统）
VFS 是内核里的一层抽象接口，让上层系统调用（open/read/write）对任意具体文件系统都通用。核心对象：
| 对象 | 含义 |
|---|---|
super_block | 一个已挂载的文件系统实例 |
inode | 一个文件/目录的元数据（通用字段 + 具体 FS 私有数据） |
dentry | 目录项，维护路径缓存 |
file | 进程视角的「已打开文件」，含偏移量与操作集 |
file_operations | 具体 FS 实现的操作函数表（vtable） |
于是 ext4、xfs、btrfs、nfs、procfs、tmpfs、FUSE 都能挂到同一棵挂载树上，用户几乎察觉不到差异——「Everything is a file」正是靠 VFS 兑现。
十一、高频 Q&A
Q9. df 与 du 结果不一致？
答案
du 统计目录树实际占用的块；df 看文件系统层面的已用/可用空间。差异来源：
- 文件已删除但仍被进程打开（
links == 0但 fd 仍在），块未回收 →df有、du无； - 稀疏文件、保留块（ext4 默认给 root 预留 5%）、inode / 元数据本身占用、被挂载点遮盖的目录等。
排查常用：lsof | grep deleted。
Q10. 为什么 ls -l 里目录的链接数是「子目录数 + 2」？
答案
目录里的 .（自身）和 ..（父目录）各算一个链接，加上每个子目录都有指向父目录的 ..，因此链接数 = 子目录数 + 2。普通文件的链接数就是指向它的硬链接个数。
Q11. 为什么通常不允许对目录做硬链接？
答案
硬链接指向同一 inode，若允许用户对目录建硬链接，容易在目录树中制造环，使 find、遍历、fsck 陷入无限循环或产生歧义。因此普通用户不能 ln 目录（root 也受限）；需要「目录别名」时用符号链接。
Q12. 删除文件到底发生了什么？
答案
unlink(path)：从目录项里去掉「名字 → inode」这条映射，并把 inode 的 links 减一。只有当 links == 0 且没有任何进程打开它时，才回收 inode 和数据块（位图置空）。若文件仍被打开，块会保留到最后一个 fd 关闭——这就是「文件删了、空间还在」的机制。
Q13. 一次「原子地替换文件内容」怎么写才安全？
答案
经典模式：写临时文件 → fsync(tmp)（保证数据落盘）→ rename(tmp, target)（目录项替换，rename 在同一文件系统内是原子的）→ fsync(dir)（保证目录项落盘）。缺了最后的目录 fsync，崩溃后可能丢掉这次重命名。