单机数据持久-局部性和快速文件系统type
status
date
slug
summary
tags
category
icon
password
Property
老UNIX 文件系统的数据结构在磁盘上看起来像这样：
超级块（S）包含有关整个文件系统的信息：卷的大小、有多少inode、指向空闲列表块的头部的指针等等。磁盘的inode 区域包含文件系统的所有inode。最后，大部分磁盘都被数据块占用。
老文件系统的好处在于它很简单，支持文件系统试图提供的基本抽象：文件和目录层次结构。与过去笨拙的基于记录的存储系统相比，这个易于使用的系统真正向前迈出了一步。与早期系统提供的更简单的单层次层次结构相比，目录层次结构是真正的进步。
问题：性能不佳
老UNIX文件系统将磁盘当成随机存取内存。数据遍布各处，而不考虑保存数据的介质是磁盘的事实，因此具有实实在在的、昂贵的定位成本。例如，文件的数据块通常离其inode非常远，因此每当第一次读取inode 然后读取文件的数据块时，就会导致昂贵的寻道。
更糟糕的是，文件系统最终会变得非常碎片化（fragmented），因为空闲空间没有得到精心管理。空闲列表最终会指向遍布磁盘的一堆块，并且随着文件的分配，它们只会占用下一个空闲块。结果是在磁盘上来回访问逻辑上连续的文件，从而大大降低了性能。
例如，假设以下数据块区域包含4 个文件（A、B、C 和D），每个文件大小为两个块：
如果删除B 和D，则生成的布局为：
可用空间被分成两块构成的两大块，而不是很好的连续4 块。假设现在希望分配一个大小为4 块的文件E：
E 分散在磁盘上，因此，在访问E时，无法从磁盘获得峰值（顺序）性能。你首先读取E1和E2，然后寻道，再读取E3和E4。这个碎片问题一直发生在老UNIX 文件系统中，并且会影响性能
另一个问题：原始块大小太小（512 字节）。因此，从磁盘传输数据本质上是低效的。较小的块是好的，因为它们最大限度地减少了内部碎片（internal fragmentation，块内的浪费），但是由于每个块可能需要一个定位开销来访问它，因此传输不佳。
如何组织文件系统数据结构以提高性能？在这些数据结构之上，需要哪些类型的分配策略？如何让文件系统具有“磁盘意识”？
伯克利的一个小组决定建立一个更好、更快的文件系统，称之为快速文件系统（Fast File System，FFS）。思路是让文件系统的结构和分配策略具有“磁盘意识”，从而提高性能。
组织结构：柱面组
第一步是更改磁盘上的结构。FFS 将磁盘划分为一些分组，称为柱面组（cylinder group，而一些现代文件系统，如Linux ext2 和ext3，就称它们为块组，即block group）。一个具有10 个柱面组的磁盘：
这些分组是FFS 用于改善性能的核心机制。通过在同一组中放置两个文件，FFS 可以确保先后访问两个文件不会导致穿越磁盘的长时间寻道。
因此，FFS 需要能够在每个组中分配文件和目录。每个组看起来像这样：
出于可靠性原因，每个组中都有超级块（super block）的一个副本（例如，如果一个被损坏或划伤，你仍然可以通过使用其中一个副本来挂载和访问文件系统）。
在每个组中，需要记录该组的 inode 和数据块是否已分配。每组的 inode 位图（inode bitmap，ib）和数据位图（data bitmap，db）起到了这个作用，分别针对每组中的inode 和数据块。位图是管理文件系统中可用空间的绝佳方法，因为很容易找到大块可用空间并将其分配给文件，这可能会避免旧文件系统中空闲列表的某些碎片问题。
最后，inode 和数据块区域就像之前的极简文件系统一样。像往常一样，每个柱面组的大部分都包含数据块。
策略：如何分配文件和目录
有了这个分组结构，FFS 现在必须决定，如何在磁盘上放置文件和目录以及相关的元数据，以提高性能。很简单：相关的东西放一起（以此推论，无关的东西分开放）。
因此，为了遵守规则，FFS 必须决定什么是“相关的”，并将它们置于同一个区块组内。相反，不相关的东西应该放在不同的块组中。为实现这一目标，FFS 使用了一些简单的放置推断方法。
首先是目录的放置。FFS 采用了一种简单的方法：找到分配数量少的柱面组（因为希望跨组平衡目录）和大量的自由inode（因为希望随后能够分配一堆文件），并将目录数据和inode 放在该分组中。当然，这里可以使用其他推断方法（例如，考虑空闲数据块的数量）。
对于文件，FFS 做两件事。首先，它确保（在一般情况下）将文件的数据块分配到与其inode 相同的组中，从而防止inode 和数据之间的长时间寻道（如在老文件系统中）。其次，它将位于同一目录中的所有文件，放在它们所在目录的柱面组中。因此，如果用户创建了4个文件，/dir1/1.txt、/dir1/2.txt、/dir1/3.txt 和/dir99/4.txt，FFS 会尝试将前3 个放在一起（同一组），与第四个远离（它在另外某个组中）。
应该注意的是，这些推断方法并非基于对文件系统流量的广泛研究，或任何特别细致的研究。相反，它们建立在良好的老式常识基础之上。目录中的文件通常一起访问（想象编译一堆文件然后将它们链接到单个可执行文件中）。因为它们确保了相关文件之间的寻道时间很短，FFS 通常会提高性能。
测量文件的局部性
为了更好地理解这些推断方法是否有意义，分析文件系统访问的一些跟踪记录，看看是否确实存在命名空间的局部性。
具体来说，进行SEER 跟踪，并分析了目录树中不同文件的访问有多“遥远”。例如，如果打开文件f，然后跟踪到它重新打开（在打开任何其他文件之前），则在目录树中打开的这两个文件之间的距离为零（因为它们是同一文件）。如果打开目录dir 中的文件f（即dir/f），然后在同一目录中打开文件g（即dir/g），则两个文件访问之间的距离为1，因为它们共享相同的目录，但不是同一个文件。换句话说，距离度量标准衡量为了找到两个文件的共同祖先，必须在目录树上走多远。它们在树上越靠近，度量值越低。
图展示了SEER跟踪中看到的局部性，针对SEER集群中所有工作站上的所有SEER跟踪。x 轴是差异度量值，y 轴是具有该差异值的文件打开的累积百分比。具体来说，对于SEER 跟踪，你可以看到大约7%的文件访问是先前打开的文件，并且近40%的文件访问是相同的文件或同一目录中的文件（即0 或1 的差异值）。因此，FFS的局部性假设似乎有意义（至少对于这些跟踪）。
有趣的是，另外25%左右的文件访问是距离为2 的文件。当用户以多级方式构造一组相关目录，并不断在它们之间跳转时，就会发生
这种类型的局部性。例如，如果用户有一个src目录，并将目标文件（.o 文件）构建到obj 目录中，并且这两个目录都是主proj 目录的子目录，则常见访问模式就是proj/src/foo .c 后跟着proj/obj/foo.o。这两个访问之间的距离是2，因为proj 是共同的祖先。FFS 在其策略中没有考虑这种类型的局部性，因此在这种访问之间会发生更多的寻道。
大文件例外
在FFS 中，文件放置的一般策略有一个重要的例外，它出现在大文件中。如果没有不同的规则，大文件将填满它首先放入的块组（也可能填满其他组）。以这种方式填充块组是不符合需要的，因为它妨碍了随后的“相关”文件放置在该块组内，因此可能破坏文件访问的局部性。
因此，对于大文件，FFS 执行以下操作。在将一定数量的块分配到第一个块组（例如，12 个块，或inode 中可用的直接指针的数量）之后，FFS 将文件的下一个“大”块（即第一个间接块指向的那些部分）放在另一个块组中（可能因为它的利用率低而选择）。然后，文件的下一个块放在另一个不同的块组中，依此类推。
如果没有大文件例外，单个大文件会将其所有块放入磁盘的一部分。使用一个包含10 个块的文件的小例子。以下是FFS 没有大文件例外时的图景：
有了大文件例外，可能会看到像这样的情形，文件以大块的形式分布在磁盘上：
在磁盘上分散文件块会损害性能，特别是在顺序文件访问的相对常见的情况下（例如，当用户或应用程序按顺序读取块0～9 时）。可以通过仔细选择大块大小，来改善这一点。
具体来说，如果大块大小足够大，大部分时间仍然花在从磁盘传输数据上，而在大块之间寻道的时间相对较少。每次开销做更多工作，从而减少开销，这个过程称为摊销（amortization）。
假设磁盘的平均定位时间（即寻道和旋转）是10ms。进一步假设磁盘以40MB/s 的速率传输数据。如果目标是花费一半的时间来寻找数据块，一半时间传输数据（从而达到峰值磁盘性能的50%），那么需要每10ms 定位开销导致10ms 的传输数据。所以问题就变成了：为了在传输中花费10ms，大块必须有多大？
基本上，如果以40 MB/s 的速度传输数据，每次寻找时只需要传输409.6KB，就能花费一半的时间寻找，一半的时间传输。同样，可以计算达到90%峰值带宽所需的块大小（结果大约为3.69MB），甚至达到99%的峰值带宽（40.6MB！）。越接近峰值，这些块就越大。
但是，FFS 没有使用这种类型的计算来跨组分布大文件。相反，它采用了一种简单的方法，基于inode 本身的结构。前12 个直接块与inode 放在同一组中。每个后续的间接块，以及它指向的所有块都放在不同的组中。如果块大小为4KB，磁盘地址是32 位，则此策略意味着文件的每1024个块（4MB）放在单独的组中，唯一的例外是直接指针所指向的文件的前48KB。
磁盘驱动器的趋势是传输速率相当快，因为磁盘制造商擅长将更多位填塞到同一表面。但驱动器的机械方面与寻道相关（磁盘臂速度和旋转速度），改善相当缓慢。这意味着随着时间的推移，机械成本变得相对昂贵，因此，为了摊销所述成本，必须在寻道之间传输更多数据。
关于FFS的其他几件事
FFS 也引入了一些其他创新。特别是，设计人员非常担心容纳小文件。事实证明，当时许多文件大小为2KB 左右，使用4KB 块虽然有利于传输数据，但空间效率却不太好。因此，在典型的文件系统上，这种内部碎片（internal fragmentation）可能导致大约一半的磁盘浪费。
FFS 设计人员采用很简单的解决方案解决了这个问题。他们决定引入子块（sub-block），这些子块有512 字节，文件系统可以将它们分配给文件。因此，如果创建了一个小文件（比如大小为1KB），它将占用两个子块，因此不会浪费整个4KB 块。随着文件的增长，文件系统将继续为其分配512 字节的子块，直到它达到完整的4KB 数据。此时，FFS 将找到一个4KB 块，将子块复制到其中，并释放子块以备将来使用。
这个过程效率低下，文件系统需要大量的额外工作（特别是执行复制的大量额外I/O）。因此，FFS 通常通过修改libc库来避免这种异常行为。该库将缓冲写入，然后以4KB 块的形式将它们发送到文件系统，从而在大多数情况下完全避免子块的特殊情况。
FFS 引入的第二个巧妙方法，是针对性能进行优化的磁盘布局。那时候（在SCSI 和其他更现代的设备接口之前），磁盘不太复杂，需要主机CPU 以更加亲力亲为的方式来控制它们的操作。当文件放在磁盘的连续扇区上时，FFS 遇到了问题。
具体来说，在顺序读取期间出现了问题。FFS 首先发出一个请求，读取块0。当读取完成时，FFS 向块1 发出读取，为时已晚：块1 已在磁头下方旋转，现在对块1 的读取将导致完全旋转。
FFS 使用不同的布局解决了这个问题。通过每次跳过一块（在这个例子中），在下一块经过磁头之前，FFS 有足够的时间发出请求。实际上，FFS 足够聪明，能够确定特定磁盘在布局时应跳过多少块，以避免额外的旋转。这种技术称为参数化，因为FFS 会找出磁盘的特定性能参数，并利用它们来确定准确的交错布局方案。
使用这种类型的布局只能获得50%的峰值带宽，因为你必须绕过每个轨道两次才能读取每个块一次。幸运的是，现代磁盘更加智能：它们在内部读取整个磁道并将其缓冲在内部磁盘缓存中（由于这个原因，通常称为磁道缓冲区，track buffer）。然后，在对轨道的后续读取中，磁盘就从其高速缓存中返回所需数据。因此，文件系统不再需要担心这些令人难以置信的低级细节
FFS 还增加了另一些可用性改进。FFS 是允许长文件名的第一个文件系统之一，因此在文件系统中实现了更具表现力的名称，而不是传统的固定大小方法（例如，8 个字符）。此外，引入了一种称为符号链接的新概念。正如第40 章所讨论的那样，硬链接的局限性在于它们都不能指向目录（因为害怕引入文件系统层次结构中的循环），并且它们只能指向同一卷内的文件（即inode 号必须仍然有意义）。符号链接允许用户为系统上的任何其他文件或目录创建“别名”，因此更加灵活。FFS 还引入了一个原子
rename()操作，用于重命名文件。