局部性与快速文件系统

原始UNIX文件系统为何极慢

超级块、全部inode和数据区被分成三大块依次摆放。inode和它的数据往往相隔很远，空闲链表很快变成一堆散落的小洞，新文件只能东一块西一块地填。512字节的块又让每次传输都要重新定位磁头。结果是逻辑上连续的文件在物理上跳来跳去，实测带宽只有磁盘峰值的2%左右。

柱面组：把相关东西关进同一个小房间

FFS把整盘切成许多柱面组（现代实现改叫块组）。每个组自带一份超级块副本、inode位图、数据位图、inode表和数据块。只要把一个目录和它下面的文件都放进同一组，后续的打开、读、写几乎都在几毫米的磁道范围内完成，长距离寻道被消灭。

三条简单启发式决定放哪里

新建目录时挑当前目录最少、空闲inode还够用的组；普通文件跟着父目录走，并且尽量拿到连续块；特别大的文件才被故意拆到多个组以免某个组被撑爆。不相关的文件则被赶到别的组。结果是“相关的在一起，不相关的离得远”。

位图如何取代碎片化的空闲链表

旧空闲链表很快变成随机指针，分配器只能拿到孤立的小块。每组一张inode位图和一张数据位图让“找一大段连续空闲块”变成一次简单的位扫描。分配器还可以一眼看出哪些组已经太满，从而把新数据均匀洒开，长期保持各组负载平衡。

常见误区

• 误以为现代文件系统仍能看见真正的柱面几何——磁盘只导出逻辑块地址，因此实现里用的是块组。
• 忘记每组都复制超级块是为了损坏后仍能挂载。
• 觉得块越大内部碎片越多就一定更差——FFS选4 KB是在内部碎片和定位次数之间做的折中。

最低标准 C11 · 完整程序 · 下载 .c

#include <stdio.h>

int main(void) {
    printf("Simulating FFS locality-aware allocation\n\n");
    printf("Cylinder/Block Groups:\n");
    printf("  Group 0: [SB][ib][db] inodes... data blocks (home dir + files)\n");
    printf("  Group 1: [SB][ib][db] inodes... data blocks (usr files)\n");
    printf("  Group 2: [SB][ib][db] inodes... data blocks (tmp files)\n\n");
    printf("Heuristic: Place new directory in group with fewest dirs.\n");
    printf("Then place its files in the same group for locality.\n");
    printf("Large sequential files get consecutive blocks inside the group.\n");
    printf("This avoids the random seeks of the original UNIX FS.\n");
    return 0;
}

在本地编译

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-41-ffs.c -o example && ./example

预期结果

Simulating FFS locality-aware allocation

Cylinder/Block Groups:
  Group 0: [SB][ib][db] inodes... data blocks (home dir + files)
  Group 1: [SB][ib][db] inodes... data blocks (usr files)
  Group 2: [SB][ib][db] inodes... data blocks (tmp files)

Heuristic: Place new directory in group with fewest dirs.
Then place its files in the same group for locality.
Large sequential files get consecutive blocks inside the group.
This avoids the random seeks of the original UNIX FS.

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

用户先创建目录 /work，再在其中创建两个小文件。按照FFS的策略，这两个文件最可能出现在哪个组？为什么？

继续查证

• OSTEP chapter PDF

标准草案与官方章节会更新；版本标记只说明示例最低要求。