《Operating Systems: Three Easy Pieces》学习笔记(三十三) 局部性和快速文件系统
问题：性能不佳
传统文件系统的问题：
- 碎片化，主要是外部碎片导致文件的块分布
过于分散，增加了磁盘寻道成本 - 原始块太小导致的文件被分为
太多块，提高了定位成本，因为每读一个块都需要定位一次
FFS：磁盘意识是解决方案
以上问题的原因是把磁盘当作内存看待，过于依赖随机访问，忽视了底层的磁盘寻道特性
组织结构：柱面组
磁盘是由一环环磁道构成，主要的耗时是跨磁道导致的磁头移动（重定位），两次读取磁道越远，该延迟越长
利用这个特性将相邻的磁道组成分组，避免同一文件分布在过远的磁道上，该分组称为柱面组
每个柱面组都有独立的文件系统必须组件（超级块，位图，inode 块，数据块等），相当于独立的文件系统，将文件的所有部分都集中在同一组中，就减少了寻道成本，也减少了碎片
策略：如何分配文件和目录
- 将文件数据块放置于和 inode 相同的柱面组中（通常访问完 inode 就立即访问数据了，减少重新寻道时间）
将文件数据块放置于和目录相同的柱面组中（通常某个目录下的文件会被连续访问）
如/dir1/1.txt、/dir1/2.txt、/dir1/3.txt 和/dir99/4.txt，1、2、3 三个文件会和 dir1 目录会放在同一柱面组中，4 和 dir99 目录放在同一个柱面组中
测量文件的局部性
文件的访问规律一般具有局部性，也就是下次访问大概率会访问相邻的文件
SEER 是一项数据访问统计计划
图中 x 轴表示文件的路径距离，也就是文件到另一文件需要行走的步数，文件自己和自己的距离为 0；和同一目录其他文件为 1；在不同目录时，需要先逐步回退到共同祖先目录，再逐步进入目标目录，也就是树状图的寻路过程，层次式状态机的寻路过程也是同理
图中 y 轴表示文件路径距离小于等于 x 轴值时的情况的比例，如小黑点的线上，有 7% 左右的访问都是同一文件（路径为 0），有 40% 左右的访问都是同目录下的（路径为 0 或 1，包括访问自己）
大文件例外
对于大文件，一般不把所有内容都塞满在一个柱面组中，但这会让同一柱面组的其他文件无家可归，比如在同一目录下再创建个文件，就要被分配到其他柱面组了，破坏了局部性
FFS 将大文件一定数量的块分配到第一个块组（例如，12 个块，或 inode 中可用的直接指针的数量（这种情况为 48 KB））之后，FFS 将文件的下一个“大”块（即第一个间接块（间接指针指向的块）指向的那些部分）放在另一个块组中（可能因为它的利用率低而选择）。然后，文件的下一个块放在另一个不同的块组中，依此类推。
在磁盘上分散文件块会损害性能，特别是在顺序文件访问的相对常见的情况下。但当分块大小足够大时，传输耗时就能摊销掉寻道耗时。
假设磁盘的平均定位时间（即寻道和旋转）是 10ms。进一步假设磁盘以 40MB/s 的速率传输数据。如果我们的目标是花费一半的时间来寻找数据块，一半时间传输数据（从而达到峰值磁盘性能的 50%），那么需要每 10ms 定位开销导致 10ms 的传输数据。
随着数据块大小增加，寻道时间所占比例就越小：
补充：这里还利用了大文件的头部部分字节会被更加频繁访问的特性，一般文件会把描述文件类型的信息（如jpg格式图片）放在头部，会被更频繁的读取。
关于 FFS 的其他几件事
子块
为了让极小的文件不单独占用一个块，可以把块再细分成子块，这样就能在一个块中放好几个文件，当文件大小增长到 4KB 以上时在将该文件挪到新块中。通常通过修改 libc 库利用缓冲技术让这些子块同时写入或读出，就好像是一个块一样
针对磁盘的优化
具体来说，在顺序读取期间出现了问题。FFS 首先发 出一个请求，读取块 0。当读取完成时，FFS 向块 1 发出读取，为时已晚：块 1 已在磁头下方旋转，现在对块 1 的读取将导致完全旋转。
通过交错放置块，在下一块经过磁头之前，FFS 有足够的时间发出请求。
其他
- 长文件名
- 符号链接
- 原子重命名rename()
小结
FFS 最大的优点是在设计时考虑了底层磁盘的特性，不同的存储介质的特性大相径庭，必须使用特定的优化手段才能发挥真正的性能。