第 8 章 - 磁盘块缓存 (The Disk Block Cache)

当系统中两个设备在访问较慢设备的频率上存在显著不匹配时，系统的整体吞吐量实际上可能会降低到较慢设备的水平。为了缓解这种情况，系统设计者通常会在设计中加入缓存，以降低访问慢速设备的成本。

缓存通过提供对驻留在慢速设备上的数据的更快访问来降低访问设备的成本。为此，缓存会将慢速设备上存在的数据副本保存在一个检索速度更快的区域。缓存之所以有效，是因为它提供数据的速度远快于从其在慢速设备上的实际位置检索相同数据的速度。换句话说，缓存将自身置于快速设备和慢速设备之间，并透明地为快速设备提供一种错觉，即较慢的设备比实际速度更快。

本章讨论与设计磁盘缓存相关的问题，如何决定在缓存中保留什么内容，如何决定何时从缓存中删除某些内容，以及所涉及的数据结构。

8.1 背景 (Background)

缓存使用一定数量的缓冲空间来保存常用数据的副本。访问缓冲空间的速度比访问底层的慢速设备要快。缓存使用的缓冲空间永远无法容纳底层设备的所有数据。如果缓存可以容纳慢速设备的所有数据，那么缓存将简单地取代慢速设备。当然，缓冲空间越大，缓存的效果就越好。缓存系统的主要任务是管理缓冲区中的数据块。

磁盘缓存使用系统内存来保存驻留在磁盘上的数据副本。要使用缓存，程序请求一个磁盘块，如果缓存中已经有该块，则直接从缓存中读取或写入该块，而无需访问磁盘。在读取操作中，如果请求的块不在缓存中，缓存会从磁盘读取该块，并在缓存中保留一份数据副本，同时满足请求。在向不在缓存中的块写入数据时，缓存会为新数据腾出空间，将其标记为“脏” (dirty)，然后返回。脏数据会在稍后更方便的时候刷新到磁盘（可能会将多次写入操作合并为一次写入）。

管理缓存主要在于决定在缓存已满时保留哪些内容以及剔除哪些内容。这种管理对缓存的性能至关重要。如果有用的数据过早地从缓存中被丢弃，缓存的性能将不如预期。如果缓存没有在适当的时候从缓存中丢弃旧数据，缓存的有效大小和效率将大大降低。

磁盘缓存的有效性是衡量请求的数据在缓存中被找到的频率。如果一个磁盘缓存可以容纳 1024 个不同的磁盘块，而一个程序请求的数据块从未超过 1024 个，那么缓存的有效性将是 100%，因为一旦缓存读入了所有块，就不再访问磁盘。在另一个极端情况下，如果一个程序随机请求数万个不同的磁盘块，那么缓存的有效性可能会接近于零，每个请求都必须访问磁盘。幸运的是，访问模式往往更具规律性，磁盘缓存的有效性也更高。

除了程序可能请求的块数之外，这些引用的局部性 (locality of those references) 也在缓存的有效性中起着作用。一个程序请求的块数可能多于缓存中的块数，但如果磁盘块的地址是顺序的，那么缓存仍然可能有用。在其他情况下，访问的磁盘块数可能多于缓存的大小，但其中一些磁盘块的访问次数可能远多于其他块，因此缓存将保留重要的块，从而降低访问它们的成本。大多数程序都具有高度的引用局部性，这有助于提高磁盘缓存的有效性。

8.2 缓冲缓存的组织 (Organization of a Buffer Cache)

磁盘缓存有两个主要需求。首先，给定一个磁盘块号，缓存应该能够快速返回与该磁盘块关联的数据。其次，当缓存已满并请求新数据时，缓存必须决定从缓存中丢弃哪些块。这两个需求需要两种不同的方法来访问底层数据。第一个任务，即在给定磁盘块地址的情况下有效查找数据块，使用了显而易见的哈希表解决方案。第二种访问方法需要一种能够快速决定从缓存中刷新哪些块的组织方式。有几种可能的实现来解决这个问题，但最常见的是一个从最近使用过 (MRU) 的块到最少使用过 (LRU) 的块排序的双向链表。以这种方式排序的双向链表通常被称为 LRU 列表（其头部是 MRU 端，尾部是 LRU 端）。哈希表和 LRU 列表紧密地交织在一起，对它们的访问需要仔细协调。

我们讨论的缓存管理侧重于哈希表和 LRU 列表的这种双重结构。除了使用 LRU 列表来决定从缓存中丢弃哪个块之外，我们本可以使用其他算法，例如随机替换、工作集模型、基于时钟的算法或 LRU 列表的变体（例如最不常使用）。在设计 BFS 时，如果能对这些其他算法进行实验以确定哪种算法在典型工作负载下表现最佳，那将是很好的。不幸的是，时间限制要求缓存得到实现，而不是进行实验，因此对其他可能的算法的探索很少。

哈希表和 LRU 列表的基础是缓存管理的数据块。BeOS 设备缓存使用称为 cache_ent 的数据结构来管理数据块。cache_ent 结构维护一个指向数据块的指针、块号以及 LRU 列表的下一个/上一个链接。哈希表使用其自己的结构按块号进行索引，以检索指向关联 cache_ent 结构的指针。

在图 8-1 中，我们说明了哈希表和双向链表的相互关系。为清晰起见，我们省略了从 cache_ent 结构到数据块的指针。

缓存读取 (Cache Reads)

首先，我们将考虑缓存为空且更高级别的代码从缓存请求一个块的情况。哈希表查找确定该块不存在。然后，缓存代码必须从磁盘读取该块并将其插入哈希表。将块插入哈希表后，缓存会将该块插入 LRU 列表的 MRU 端。随着从磁盘读取更多块，第一个被读取的块将随着其他块插入其前面而向列表的 LRU 端迁移。

如果我们最初的块再次被请求，哈希表的探测将会找到它，并且该块将被移动到 LRU 列表的 MRU 端，因为它现在是最近使用过的块（参见图 8-2）。这是缓存提供最大益处的地方：经常使用的数据将以哈希表查找和 memcpy() 的速度被找到和检索，而不是磁盘寻道和磁盘读取的成本，后者要慢几个数量级。

缓存不能无限增长，因此在某个时候，缓存管理的块数将达到最大值。当缓存已满并且请求不在缓存中的新块时，必须决定将哪个块踢出缓存。LRU 列表使这个决定变得容易。只需取出列表 LRU 端的块，我们就可以丢弃其内容并重用该块来读入新请求的块（参见图 8-3）。丢弃最近最少使用的块本质上是有道理的：如果该块很长时间没有被使用，那么它再次被需要的可能性就不大。删除 LRU 块不仅涉及将其从 LRU 列表中删除，还涉及从哈希表中删除该块号。回收 LRU 块后，新块被读入内存并放在 LRU 列表的 MRU 端。

缓存写入 (Cache Writes)

缓存写入有两种情况。第一种情况是正在写入的块已经在缓存中。在这种情况下，缓存可以将新写入的数据 memcpy() 覆盖它已经为特定磁盘块拥有的数据。缓存还必须将该块移动到 LRU 列表的 MRU 端（即，它成为最近使用过的数据块）。如果向一个磁盘块写入数据，并且该磁盘块不在缓存中，那么缓存必须为新的磁盘块腾出空间。为不在缓存中的新写入磁盘块在缓存中腾出空间与前面描述的缓存读取未命中时的情况相同。一旦有了新磁盘块的空间，数据就被复制到该块的缓存缓冲区中，并且 cache_ent 被添加到 LRU 列表的头部。如果出于数据完整性的原因，缓存必须执行写通 (write-through)，则缓存还必须将该块写入其对应的磁盘位置。

第二种也是更常见的情况是，该块仅被标记为脏 (dirty)，然后写入完成。稍后，当该块从缓存中刷新时，由于它已被标记为脏，它将被写入磁盘。如果系统在缓存中存在脏数据时崩溃或发生故障，磁盘上的数据将与内存中的数据不一致。

刷新缓存时，缓存中的脏块需要更多的工作。在前面描述的情况下，缓存中只有干净的块，刷新它们仅仅意味着重用它们的数据块来保存新数据。当存在脏块时，缓存必须首先将脏数据写入磁盘，然后才允许重用关联的数据块。正确处理脏块非常重要。如果由于任何原因，脏块在被丢弃之前没有刷新到磁盘，缓存将丢失对磁盘所做的更改，从而有效地损坏磁盘。

8.3 缓存优化 (Cache Optimizations)

当存在脏块时刷新缓存提供了一个有趣的机会。如果缓存总是每次只刷新一个块，那么它在写入磁盘方面的性能不会比每次写入都直接写穿 (write directly through) 更好。然而，通过等到缓存已满，缓存可以做两件能极大提升性能的事情。首先，缓存可以将多个更改批量处理。也就是说，与其每次只刷新一个块，不如同时刷新多个块更明智。一次刷新多个块可以将刷新操作的成本分摊到几个块上，更重要的是，它促成了第二种优化。当刷新多个块时，就有可能对磁盘写入进行重新排序，并在一次磁盘写入中写入连续的磁盘块。例如，如果更高级别的代码写入以下块序列：

971 245 972 246 973 247

在刷新缓存时，序列可以重组为：

245 246 247 971 972 973

这使得缓存可以执行两次磁盘写入（每次写入三个连续的块）和一次寻道，而不是六次磁盘写入和五次寻道。这一点的重要性怎么强调都不为过。将 I/O 模式重组为高效的顺序可以显著减少磁盘必须进行的寻道次数，从而提高到磁盘的整体带宽。大型连续写入的性能比顺序单块写入高出 5-10 倍，这使得这种优化极其重要。至少，缓存应该对要刷新的块列表进行排序，并且如果可能，它应该合并对连续磁盘位置的写入。

以类似的方式，当发生缓存未命中并且必须读取磁盘块时，如果缓存每次只读取一个块，它的性能也不会很好。无论读取的大小如何，进行磁盘读取都有一个固定的成本。相对于传输一个或两个磁盘块所需的时间，这个固定成本非常高。因此，最好将进行磁盘读取的成本分摊到许多块上。BeOS 缓存会在缓存未命中时读取 32K。与读取单个磁盘块的成本相比，读取额外数据的成本微不足道。这种方案的另一个好处是它为文件系统执行了预读 (read-ahead)。如果文件系统擅长连续分配文件，那么读取的额外数据很可能就是很快会需要的数据。执行 32K 的预读也增加了文件系统看到的有效磁盘带宽，因为它比执行 32 次单独的 1K 读取快得多。

在缓存级别执行预读的一个缺点是它本质上是不完美的。缓存不知道读取的额外数据是否有用。可以在缓存 API 中引入特殊参数来控制预读，但这会使 API 复杂化，并且不清楚它是否会带来显著的好处。如果文件系统能够很好地连续分配文件，它将与这种简单的缓存策略很好地交互。实际上，BFS 与隐式预读配合得非常好。

无论是读取还是写入，如果数据引用的是连续的磁盘块地址，则还有另一种可能的优化。如果缓存系统可以访问分散/聚集 (scatter/gather) I/O 原语，它就可以构建一个分散/聚集表，以将 I/O 直接导向内存中的每个块。分散/聚集表是指针和长度对的表。分散/聚集 I/O 原语接收此表，并直接对表中描述的每个内存块执行 I/O。这很重要，因为即使缓存要对其执行 I/O 的数据块引用的是连续的磁盘块，它们在内存中也不太可能是连续的。使用分散/聚集原语，缓存可以避免必须通过连续的临时缓冲区复制数据。

BeOS 缓存提供的另一个特性是允许直接在缓存中修改数据。缓存 API 允许文件系统请求一个磁盘块，并获取指向该块中数据的指针。缓存将磁盘块读入其内部缓冲区，并返回指向该缓冲区的指针。一旦以这种方式请求了一个块，该块就会被锁定在缓存中，直到被释放。BFS 主要将此特性用于 i-node，它直接操作 i-node，而不是将它们复制到另一个位置（这将需要两倍的空间）。当这样的块被修改时，会有一个缓存调用将该块标记为脏，以便在释放时将其正确写回磁盘。对缓存 API 的这个小调整使得 BFS 能够更有效地使用内存。

8.4 I/O 和缓存 (I/O and the Cache)

缓存设计中的一个重要考虑因素是它在执行 I/O 时不应保持锁定状态。在执行 I/O 时不锁定缓存允许其他线程进入缓存并读取或写入已在缓存中的数据。这种方法被称为“未命中时命中”(hit-under-miss)，在像 BeOS 这样的多线程系统中非常重要。

实现“未命中时命中”会引出几个问题。在执行 I/O 之前解锁缓存允许其他线程进入缓存并对数据块进行读/写操作。这也意味着在 I/O 发生时，其他线程将操作缓存数据结构。这有可能造成巨大的混乱。为了防止出现混乱情况，在释放缓存锁之前，任何相关的数据结构都必须标记为“忙碌”(busy)，以便任何其他进入缓存的线程不会删除它们或以其他方式使它们无效。标记为忙碌的数据结构在忙碌位清除之前不得修改。在 BeOS 缓存系统中，一个 cache_ent（缓存条目）可以被标记为忙碌。如果另一个线程希望访问该 cache_ent 所代表的块，那么它必须释放缓存锁，休眠一小段时间，然后重新获取缓存锁，再次查找该块，并检查忙碌位的状态。虽然该算法听起来很简单，但它有一个严重的 implications。解锁-休眠-重试的方法并不能保证向前进展。虽然不太可能，但如果足够多的其他线程也希望访问同一个块，等待该块的线程可能会遇到“饿死”(starvation) 的情况。BeOS 中此循环的实现包含检测是否有大量时间花在等待块变为可用的代码。在我们的测试场景中，我们曾见过在分页压力较大时，一个线程花费了大量时间等待一个块，但从未长到导致线程饿死。尽管在实践中似乎没有发生任何不好的事情，但这正是那种每次在屏幕上滚动过时都会让你感到不安的代码片段之一。

回到最初的情况，当 I/O 完成时，必须重新获取缓存锁，并且任何存储的指针（除了所讨论的 cache_ent 的指针外）都需要重新赋值，因为它们可能在此期间发生了变化。一旦正确的状态被重新建立，缓存代码就可以完成其对 cache_ent 的操作。在未完成的缓存未命中期间处理缓存命中的能力非常重要。

调整缓存大小 (Sizing the Cache)

调整缓存大小是一个难题。通常，缓存越大，其效果越好（当然，是在合理的范围内）。由于缓存使用主机内存来保存驻留在磁盘上的数据副本，因此让缓存过大会减少可用于运行用户程序的内存量。没有足够的内存来运行用户程序可能会迫使这些程序不必要地进行交换 (swap)，从而产生更多的磁盘开销。这是一个难以维持的平衡。

理想的情况，也是大多数现代 Unix 版本所提供的情况，是允许缓存随着用户程序内存需求的变化而动态增长和缩小。像这样的动态缓存通常与虚拟内存 (VM) 系统紧密集成，并使用空闲内存来保存来自磁盘的数据块。当 VM 系统需要更多内存时，它会使用最近最少使用的缓存数据块来满足程序的内存请求。当内存被释放时，VM 系统允许缓存使用该内存来保存来自磁盘的额外数据块。这种安排提供了对内存的最佳利用。如果有一个正在运行的程序不使用太多内存，但确实引用了大量基于磁盘的数据，它将能够在内存中缓存更多数据。同样，如果有一个正在运行的程序需要的内存多于其需要的磁盘缓存，则缓存将减小大小，而内存将分配给程序数据。

遗憾的是，BeOS 没有集成的 VM 和磁盘缓冲缓存。BeOS 磁盘缓存的大小是固定的，在启动时根据系统中的内存量确定。这种安排的效果尚可，但我们计划将来修改系统的这个区域。BeOS 为每 16MB 的系统内存分配 2MB 的缓存。当然，这样做的明显缺点是，无论用户程序执行多少磁盘 I/O，内核都会将八分之一的内存用于磁盘缓存。

日志记录和缓存 (Journaling and the Cache)

BFS 的日志系统对缓存提出了两个额外的要求。首先是日志系统必须能够锁定缓存中的磁盘块，以防止它们被刷新。第二个要求是日志系统必须知道磁盘块何时被刷新到磁盘。没有这些特性，日志系统在管理作为事务一部分而被修改的块时会面临严重的困难。

当一个块作为事务的一部分被修改时，日志记录代码必须确保在该事务完成并且日志被写入磁盘之前，该块不会被刷新到磁盘。该块必须被标记为脏 (dirty) 并被锁定 (locked)。当搜索要刷新的块时，缓存必须跳过锁定的块。这对于日志的正确操作至关重要。锁定缓存中的块与在对块执行 I/O 时将其标记为忙碌是不同的。其他线程仍然可以访问锁定的块；而忙碌的块在忙碌位清除之前不能被访问。

当日志将事务写入磁盘上的日志时，缓存中的块可以被解锁。然而，为了完成一个事务，日志需要知道每个块何时从缓存中刷新。在 BeOS 中，这是通过一个回调函数 (callback function) 实现的。当一个事务在内存中完成时，日志会写入日志条目，并为事务中的每个块设置一个回调。当这些块中的每一个被缓存刷新到磁盘时，日志回调函数就会被调用，并记录该块已被刷新。当回调函数发现事务的最后一个块已被刷新到磁盘时，该事务才真正完成，其在日志中的空间才能被回收。这种回调机制对于缓存来说并不常见，但对于日志的正常运行是必需的。

BeOS 缓存支持获取指向缓存数据块的指针，BFS 利用这一点直接引用 i-node 数据。这一事实，再加上日志记录的要求，带来了一个有趣的问题。如果对 i-node 进行了修改，i-node 数据会被写入日志（这会锁定缓存中相应的磁盘块）。当事务完成时，日志记录代码会解锁该块，并请求在该块被刷新到磁盘时进行回调。然而，BFS 的其余部分已经有一个指向该块的指针（因为它是一个 i-node），因此在该文件系统的其余部分放弃对该块的访问之前，该块实际上并不能自由地被刷新到磁盘。但这还不是问题所在。

问题在于日志期望将块的当前版本写入磁盘，但是因为系统的其他部分仍然拥有指向该数据块的指针，它有可能在被刷新到磁盘之前再次被修改。为了确保日志记录的完整性，当缓存为一个块设置回调时，缓存会克隆 (clone) 该块的当前状态。块的克隆副本才是缓存有机会时将刷新的内容。如果该块已经有一个克隆，则在克隆当前块之前，会将现有的克隆写入磁盘。克隆缓存块是必要的，因为系统的其余部分直接拥有指向缓存数据的指针。如果 i-node 数据在日志处理完它之后但在它被写入磁盘之前被修改，文件系统可能会处于不一致的状态。

何时不使用缓存 (When Not to Use the Cache)

尽管缓存有诸多好处，但在某些情况下不使用它反而更合理。例如，如果用户复制一个非常大的文件，缓存会充满相同数据的两个副本；如果文件足够大，缓存也无法容纳所有数据。另一个例子是当一个程序向磁盘流式传输大量数据（如视频或音频数据）时。在这种情况下，数据在写入后不太可能再次被读取，并且由于正在写入的数据量大于缓存的大小，它无论如何都必须被刷新。在这些情况下，缓存最终只会导致一次额外的从用户缓冲区到缓存的 memcpy() 操作，并且缓存的有效性为零。这不是最优的。在这种情况下，最好完全绕过缓存并直接执行 I/O。

BeOS 磁盘缓存以隐式方式支持绕过缓存。任何大小为 64KB 或更大的 I/O 都会绕过缓存。这使得程序可以轻松跳过缓存并直接对其底层设备执行 I/O。在实践中，这种方式效果很好。操作大量数据的程序可以通过指定较大的 I/O 缓冲区大小来轻松绕过缓存。那些不关心此问题的程序可能会使用默认的 stdio 缓冲区大小 4KB，因此以完全缓冲的方式运行。

这里有两个需要注意的地方。缓存不能简单地将大型 I/O 事务直接传递过去，而不首先检查正在写入的磁盘块是否已在缓存中。如果一个块是通过大型 I/O 写入的，并且该块已在缓存中，那么该块的缓存版本也必须用新写入的数据进行更新。同样，在读取时，如果一个块已在缓存中，则用户缓冲区必须用内存中该块的版本进行修补，因为它可能比磁盘上的版本更新。这两个注意点虽小，但对于缓存的一致操作非常重要。

在某些情况下，此特性会导致比必要更多的磁盘流量。如果一个程序重复读取同一数据块，但该块大于 64KB，则磁盘请求每次都会被传递过去；程序将以磁盘的速度而不是 memcpy() 的速度运行。虽然罕见，但这可能发生。如果性能是一个问题，很容易将这样的程序重新编码为以较小的、可缓存的块请求数据。

这种缓存绕过策略的一个结果是，设备可以将数据直接从用户缓冲区传输到磁盘，而无需通过缓存执行 memcpy()（即，它使用 DMA 传输数据）。当以这种方式绕过缓存时，BeOS 能够为应用程序提供原始磁盘带宽的 90-95%（有时甚至更高）。这一点意义重大，因为它几乎不需要程序员付出任何努力，也不需要额外的调整、特殊选项或专门分配的缓冲区。例如，一个视频捕获程序的简单实现（捕获一个 320x240、16 位视频场并将其写入磁盘）仅通过执行大块写入就达到了每秒 30 场的带宽而没有掉帧。缓存绕过是 BeOS 的一个重要特性。

8.5 总结 (Summary)

磁盘缓存可以极大地提高文件系统的性能。通过缓存常用的数据，缓存显著减少了对底层磁盘的访问次数。缓存有两种访问模式。第一种访问方法是根据磁盘块号查找磁盘块；另一种方法是根据有助于确定在缓存已满且必须放入新数据时应丢弃哪些块的标准对磁盘块进行排序。在 BeOS 缓存中，这是通过一个哈希表和一个从最近使用过 (MRU) 到最少使用过 (LRU) 排序的双向链表来管理的。这两个数据结构紧密地交织在一起，并且必须始终保持自洽。

缓存可以进行许多优化。在最简单的情况下，当将数据刷新到磁盘时，缓存可以重新排序写入操作，以最大限度地减少所需的磁盘寻道次数。还可以合并对连续磁盘块的写入，以便用一次大的写入替换许多小的写入。在缓存读取时如果数据不在缓存中，缓存可以执行预读以获取更多可能很快需要的数据。如果文件系统能够很好地连续布局数据，预读将消除未来的读取操作。这些优化可以显著提高磁盘的有效吞吐量，因为它们利用了磁盘擅长批量数据传输这一事实。

当缓存确实执行 I/O 时，重要的是在 I/O 发生期间缓存不被锁定。保持缓存未锁定状态允许其他线程读取已在缓存中的数据。这被称为“未命中时命中”(hit-under-miss)，在像 BeOS 这样的多线程系统中非常重要。

日志记录对缓存施加了几个约束。为了适应 BFS 中日志记录的实现，BeOS 磁盘缓存必须提供两个主要特性。第一个特性是日志记录代码必须能够在块作为事务的一部分被修改时锁定缓存中的这些块。第二个特性是日志系统需要被告知磁盘块何时被刷新。BeOS 缓存支持一种回调机制，日志记录代码利用该机制来了解事务何时完成。由于 BFS 直接使用指向缓存数据的指针，因此当日志记录代码释放块时，缓存必须克隆这些块。克隆块可确保写入磁盘的数据将是事务期间修改块的完全相同的副本。

本章的最后一小节讨论了何时不适合使用缓存。通常在复制大文件或向磁盘流式传输数据时，缓存效率不高。如果使用缓存，它会在有效吞吐量方面造成相当大的损失。当 I/O 大小为 64KB 或更大时，BeOS 缓存直接从用户缓冲区执行 I/O。这种隐式缓存绕过对于程序员来说很容易利用，并且通常不会干扰大多数使用较小 I/O 缓冲区的普通程序。