Download PDF version of this article PDF

五年法则：20 年后以及闪存如何改变规则

旧规则持续演变，而闪存增加了两条新规则。

Goetz Graefe，惠普实验室

1987 年，Jim Gray 和 Gianfranco Putzolu 发表了他们现在著名的五年法则1，用于权衡内存和 I/O 容量。他们的计算比较了将记录（或页面）永久保存在内存中的成本，与每次访问记录（或页面）时执行磁盘 I/O 的成本，使用了 RAM 芯片和磁盘驱动器价格的适当比例。他们规则的名称指的是访问之间的盈亏平衡间隔。如果更频繁地访问记录（或页面），则应将其保存在内存中；否则，它应保留在磁盘上并在需要时读取。

基于当时 Tandem 设备的现行价格和性能特征，Gray 和 Putzolu 发现，保存 1 KB 记录的 RAM 价格大约等于访问此类记录每 400 秒所需的磁盘驱动器（部分）价格，他们将其四舍五入为五分钟。盈亏平衡间隔与记录大小成反比。Gray 和 Putzolu 给出了 100 字节记录一小时，4 KB 页面两分钟。

五年法则在 10 年后的 1997 年进行了回顾和更新。2 许多价格和性能参数都发生了变化（例如，RAM 的价格从每兆字节 5,000 美元降至 15 美元）。尽管如此，4 KB 页面的盈亏平衡间隔仍然约为五分钟。本文的第一个目的是在又过了 10 年后回顾五年法则。

当然，之前的两篇论文都承认，在任何时间点，不同技术和设备之间的价格和性能都存在差异（例如，大型机与小型机的 RAM，SCSI 与 IDE 磁盘等）。因此，邀请感兴趣的读者为他们的环境和设备重新评估适当的公式。此处使用的值（表 1 中）旨在代表 2007 年的典型技术，而不是普遍准确的。

除了价格和性能的量化变化外，正在进行的质变将影响服务器的软硬件架构，特别是数据库系统。随着新技术的出现，数据库软件将发生根本性变化：具有硬件和软件支持的虚拟化，以及物理机器的更高利用率目标；多核处理器和事务内存，在编程环境和硬件中都得到支持；3 部署在容纳数千个处理器和数 TB 数据的容器中；4 以及填补传统 RAM 和传统旋转磁盘之间空白的闪存。

就购置成本、访问延迟、传输带宽、空间密度、功耗和散热成本而言，闪存介于传统 RAM 和基于旋转磁盘的持久性海量存储之间。5 表 1 和表 2 中的一些派生指标说明了这一点。

鉴于磁盘 I/O 所需时间内可能执行的 CPU 指令数量稳步增加，因此存储层次结构中需要中间内存。闪存似乎是一个非常可能的候选者，这一点现在已经被多次观察到。

许多架构细节仍有待完善。例如，在硬件架构中，闪存将通过 DIMM 插槽、SATA（串行 ATA）磁盘接口还是另一种硬件接口访问？鉴于定义新硬件接口的努力和延迟，现有接口的调整是可能的。

一个主要问题是闪存被认为是主内存的特殊部分还是持久性存储的特殊部分。换句话说：如果系统包含 1 GB 传统 RAM、8 GB 闪存和 250 GB 传统磁盘，那么软件会将其视为 250 GB 的持久性存储和 9 GB 的缓冲区池，还是 258 GB 的持久性存储和 1 GB 的缓冲区池？本文的第二个目的是回答这个问题，事实上，要为文件系统和数据库系统论证不同的答案。

许多设计决策取决于这个问题的答案。例如，如果闪存是缓冲区池的一部分，则当页面内容与持久性存储中的等效页面不同时，页面必须被视为“脏页”。同步文件系统或检查点数据库必须在这些情况下强制执行磁盘写入。如果闪存是持久性存储的一部分，则不需要这些写入操作。

操作系统和文件系统的设计者希望使用闪存作为扩展缓冲区池（扩展 RAM），而数据库系统将受益于闪存作为扩展磁盘（扩展持久性存储）。文件系统和数据库系统的多个方面始终如一地支持这两种设计。

此外，闪存的特性表明 B 树页面的管理及其分配存在一些实质性差异。除了优化页面大小外，B 树可以对闪存和磁盘使用不同的 I/O 单元。本文的第三个目的是阐述这种设计的情况。

假设

前瞻性研究始终依赖于许多假设。本节列出了导致本文提出的结论的假设。有些假设相当基本，而另一些则更具推测性。

一个假设是文件系统和数据库系统将闪存分配到 RAM 和磁盘驱动器之间的级别。这两种软件系统都倾向于在未来有一定概率被访问的页面，但概率不足以保证将其保存在 RAM 中。此类概率的估计和管理遵循常用方法（例如，LRU 或最近最少使用）。

我们假设此类信息的管理使用 RAM 中的数据结构，即使对于内容已从 RAM 移动到闪存的页面也是如此。例如，文件系统缓冲区池中的 LRU 链可能同时覆盖 RAM 和闪存，或者可能存在两个单独的 LRU 链。当应用程序需要页面时，将其加载到 RAM 中并插入到第一个链的头部。当它到达第一个链的尾部时，该页面被移动到闪存，其描述符被移动到第二个 LRU 链的头部。当它到达第二个链的尾部时，该页面被移动到磁盘并从 LRU 链中删除。其他替换算法将相应地工作。

这种细粒度的单个页面 LRU 替换与将整个文件、目录、表或数据库分配给不同的存储单元形成对比。页面替换似乎是缓冲区池中合适的粒度。此外，存在成熟的方法可以完全自动地加载和替换缓冲区池内容，无需调整工具的辅助，也无需用户或管理员的指令。当闪存用作扩展磁盘时，扩展缓冲区池中的闪存应利用与传统缓冲区池相同的方法。为了真正具有可比性和竞争力的性能和管理成本，当闪存用作扩展磁盘时，类似的方法似乎是明智的。

文件系统

本文的研究假设了一个相当传统的文件系统。许多文件系统以一种或另一种方式与此模型不同，但大多数文件系统仍然普遍遵循它。

每个文件都是一个大型字节流。文件通常被完整读取，其内容在内存中操作，如果文件被更新，则替换整个文件。归档、版本保留、分层存储管理、使用可移动介质的数据移动等似乎也遵循此模型。

基于此模型，磁盘上的空间分配尝试为每个文件使用连续的磁盘块。元数据仅限于目录、一些标准标签（例如创建时间）以及用于空间管理的数据结构。

这些磁盘数据结构的一致性是通过仔细的写入顺序、相当快速的写回更新数据块以及在任何不完美的关机或介质移除后进行昂贵的文件系统检查来实现的。换句话说，我们假设至少对于文件内容而言，不存在事务性保证和事务日志记录。如果对于文件内容（例如页面内的单个页面或记录）支持基于日志的恢复，则此处提出的许多论点需要重新审视。

数据库系统

我们假设相当传统的数据库系统，其中 B 树索引是主力存储结构。类似的树结构不仅捕获了传统的聚集和非聚集索引，还捕获了位图索引、列式存储、内容索引、XML 索引、目录（元数据）和分配数据结构。

关于事务性保证，我们假设对内容更改（例如插入或删除记录）和结构更改（例如拆分 B 树节点）进行传统的预写日志记录。检查点通过强制将缓冲区池中的脏数据写入持久性存储，从而实现故障后高效的基于日志的恢复。

其他假设包括诸如“第二次机会”或模糊检查点之类的变体。此外，对于某些操作（例如索引创建），允许非日志记录（仅分配日志记录）执行。这些操作需要适当的写入顺序和“强制”缓冲区池策略。6

闪存

我们假设硬件和设备驱动程序隐藏了许多实现细节，例如闪存的特定硬件接口。例如，闪存可以安装在计算机的主板、DIMM 插槽、PCI 板或标准磁盘外壳内。在所有情况下，都假设 RAM 和闪存之间存在 DMA（直接内存访问）传输（或更好的方式）。此外，假设闪存和磁盘之间存在高效的 DMA 数据传输，或者 RAM 中存在传输缓冲区。在第一近似值中，此类传输缓冲区的大小应大约等于传输带宽和磁盘延迟的乘积。如果希望磁盘写入永远不会延迟磁盘读取，则必须将增加的后写延迟包括在计算中。

另一个假设是闪存和磁盘的传输带宽相当。虽然闪存写入带宽落后于读取带宽，但一些产品声称差异小于两倍（例如，表 1 中三星的基于闪存的固态磁盘）。如有必要，可以通过使用阵列排列来增加传输带宽，这在磁盘驱动器中是众所周知的。7 甚至在某些情况下，闪存的冗余排列也可能被证明是有利的。8

由于当前的 NAND 闪存在 10 万到 100 万次擦除和写入循环后可靠性会降低，因此我们假设提供了一些“磨损均衡”机制。这些机制确保所有页面或页面块以大致相同的频率写入。重要的是要认识到磨损均衡算法和日志结构文件系统9,10之间的相似性，尽管前者也会移动稳定的、未更改的数据，以便它们的位置可以吸收一些擦除和写入循环。

还要注意，传统的磁盘驱动器也不支持更多的写入操作，尽管原因不同。例如，以每秒 100 MB 的速度连续和持续写入六年，覆盖整个 250 GB 磁盘的次数少于 80,000 次。换句话说，假设日志结构文件系统适用于 RAID-5 或 RAID-6 阵列，则当前 NAND 闪存的可靠性似乎相当。同样，以每秒 30 MB 的速度覆盖 32 GB 闪存磁盘 100,000 次大约需要 3 年半的时间。

除了磨损均衡之外，我们还假设存在一个异步代理，将相当陈旧的数据从闪存移动到磁盘，并立即擦除闪存中释放的空间，以便为写入操作做好准备，而不会进一步延迟。此活动也与日志结构文件系统具有直接的等效性——即清理活动，该活动为未来的日志写入准备空间。不同之处在于，磁盘内容只需移动，而闪存内容还必须在在该位置进行下一次写入操作之前擦除。

在文件系统或数据库系统中，我们都假设用于页面跟踪和页面替换的独立机制。例如，传统的缓冲区池同时提供这两者，但它为此目的使用了两个不同的数据结构。标准设计依赖于用于页面替换的 LRU 列表和用于跟踪页面的哈希表（即，哪些页面存在于缓冲区池中以及在哪个缓冲区帧中）。替代算法和数据结构也分离了页面跟踪和替换管理。

替换算法的数据结构被假定为小巧且高流量，因此保存在 RAM 中。我们还假设页面跟踪必须与数据一样持久；因此，缓冲区池的哈希表在系统重启期间重新初始化，但持久性存储（例如磁盘）上的页面的跟踪信息必须与数据一起存储。

如前所述，我们假设按需页面替换。也可能存在用于预取、预读和后写的自动策略和机制。

基于这些考虑，我们假设闪存的内容几乎相同，无论闪存是扩展缓冲区池还是磁盘。因此，中心问题不是缓存中保留什么，而是如何管理闪存内容及其生命周期。

在数据库系统中，闪存也可以用于恢复日志，因为其短的访问时间允许非常快速的事务提交。然而，写入带宽的限制阻碍了这种使用。也许具有双日志的系统可以将低延迟和高带宽结合起来，一个日志在传统磁盘上，另一个日志在闪存芯片阵列上。

其他硬件

在所有情况下，RAM 都被假定为相当大的尺寸，尽管可能小于闪存或磁盘。相对大小应受五年法则11的约束。请注意，尽管传输带宽相似，但闪存相对于磁盘的短访问延迟导致数据在 RAM 中的保留时间令人惊讶。

最后，我们假设现代多核处理器提供了足够的处理带宽。此外，我们相信即将到来的事务内存（在硬件和软件运行时系统中）允许高度并发地维护复杂的数据结构。例如，页面替换启发式方法可能使用优先级队列而不是位图或链表。同样，高级锁管理可能会受益于更复杂的数据结构。尽管如此，我们不假设或要求数据结构比页面替换和位置跟踪中已常用的数据结构更复杂。

五年法则

如果引入闪存作为内存层次结构中的中间层，则内存级别的相对大小调整需要重新考虑。调整可以基于购买成本、总拥有成本、功耗、平均故障间隔时间、平均数据丢失时间或指标的组合。按照 Gray 和 Putzolu12的说法，本文重点关注购买成本。其他指标和确定相对大小的适当公式可以类似地导出（例如，通过用缓存和移动数据的能量使用量替换美元成本）。

Gray 和 Putzolu 引入了以下公式：13,14

秒为单位的盈亏平衡间隔 = (每 MB RAM 的页数 /
每个磁盘每秒的访问次数) × (每个磁盘驱动器的价格 /
每 MB RAM 的价格)

它是使用以下公式推导出来的：RAM 将页面保存在缓冲区池中的成本，以及（部分）磁盘每次需要页面时执行 I/O 的成本，使这两个成本相等，并求解访问间隔的方程。

假设现代 RAM、使用 4 KB 页面的磁盘驱动器以及表 1 和表 2 中的值，这会产生

(256 / 83) × ($80 / $0.047) = 5,248 秒 = 90 分钟 = 1½ 小时

（“=”符号表示本文中的四舍五入。）这与 20 年前（4 KB 页面）的两分钟相比。

如果此更改中有任何令人惊讶之处，那就是盈亏平衡间隔的增长幅度小于两个数量级。回想一下，1987 年 RAM 的估计价格约为每兆字节 5,000 美元，而 2007 年的成本约为每兆字节 0.05 美元，相差五个数量级。另一方面，磁盘价格也大幅下降（1987 年每个磁盘 15,000 美元），并且磁盘延迟和带宽也大大提高（从每秒 15 次访问到 SATA 上约 100 次，高性能 SCSI 磁盘上约 200 次）。

对于 32 GB 的 RAM 和闪存磁盘，盈亏平衡间隔为

(256 / 6,200) × ($999 / $0.047) = 876 秒 = 15 分钟

如果 2007 年闪存磁盘的价格包含“新奇溢价”，并且降至更接近原始闪存内存的价格——比如 400 美元（Gray 和 Fitzgerald15也预测了这一价格），那么盈亏平衡间隔为 351 秒 = 6 分钟。

一个重要的结果是，在使用经济考虑因素调整的系统中，如果闪存内存而不是传统磁盘是存储层次结构中的下一层，则 RAM 的周转速度快大约 15 倍（90 分钟 / 6 分钟）。所需的 RAM 少得多，从而降低了购买、功耗和散热成本。

也许最有趣的是，将相同的公式应用于闪存和磁盘会导致以下结果

(256 / 83) × ($80 / $0.03) = 8,070 秒 = 2¼ 小时

因此，所有活动数据都将保留在 RAM 和闪存中。

毫无疑问，两小时比任何常见的检查点间隔都长，这意味着闪存中的脏页面不是通过页面替换而是通过检查点强制写入磁盘的。频繁更新的页面必须比基于 Gray 和 Putzolu 公式的最佳频率更频繁地写入（由于检查点）。

1987 年，Gray 和 Putzolu 推测了未来 20 年的情况，并预测了 RAM 和磁盘的“五小时法则”。对于 1 KB 记录，2007 年的典型价格和规格表明为 20,978 秒，或略低于六小时。他们的预测非常准确。

对于更大的页面大小（例如，64 KB 甚至 256 KB），所有盈亏平衡间隔都不同。表 3 显示了盈亏平衡间隔，包括上面引用的间隔，适用于各种页面大小和存储技术组合。“$400”代表未来 32 GB NAND 闪存驱动器的价格为 400 美元，而不是 2007 年的 999 美元。

用于 RAM 和磁盘的旧五年法则现在适用于 64 KB（334 秒）的页面大小。五分钟是 1987 年16 1 KB 和 1997 年17 8 KB 的近似盈亏平衡间隔。这种趋势反映了磁盘访问延迟和传输带宽的不同改进速度。

对于 64 KB 及以上的页面大小（64 KB 为 365 秒，256 KB 为 339 秒），五年盈亏平衡间隔也适用于 RAM 和 2007 年昂贵的闪存内存。随着闪存内存的价格溢价降低，盈亏平衡间隔也会缩短（分别为 146 秒和 136 秒）。

此处承诺的两条新五年法则在表 3 中以粗斜体值表示。我们将在关于 B 树索引的最佳节点大小的讨论中回到此表和这些规则。

页面移动

除了与 RAM 的 I/O 之外，三级内存层次结构还需要闪存和磁盘存储之间的数据移动。移动页面的纯机制可以在硬件中实现（例如，通过 DMA 传输），或者可能需要通过 RAM 的间接传输。前一种情况承诺更好的性能，而后一种设计可以完全在软件中实现，而无需新颖的硬件。另一方面，混合磁盘制造商可能已经有可用的经济高效的硬件实现。

页面移动的策略由按需分页和 LRU 替换管理或派生。如已讨论的，文件系统和数据库系统中的替换策略可能依赖于 LRU，并且可以使用 RAM 中的适当数据结构来实现。与 RAM 中的缓冲区管理一样，预取、预读和后写可能会导致差异。在数据库系统中，这些可以由查询执行层的提示来指导，而文件系统必须在没有此类提示的情况下检测页面访问模式和有价值的预读操作。

如果闪存是持久性存储的一部分，则闪存和磁盘之间的页面移动类似于碎片整理期间的页面移动，无论是在文件系统还是在数据库系统中。最重要的区别是如何在这两种系统中跟踪页面移动和当前页面位置。

跟踪页面位置

文件系统和数据库系统中跟踪页面位置的机制截然不同。在文件系统中，指针页面跟踪数据页面或连续数据页面运行。移动单个页面可能需要中断运行。它始终需要更新然后写入指针页面。

在数据库系统中，大多数数据都存储在 B 树索引中，包括表上的聚集（主，非冗余）索引和非聚集（辅助，冗余）索引、物化视图和数据库目录。位图索引、列式存储和主从聚类可以轻松有效地在 B 树中表示。18 从 B 树派生的树结构也用于 blob（二进制大对象），并且类似于某些文件系统的存储结构。19,20

对于 B 树，移动单个页面可能非常昂贵或非常便宜。最有效的机制通常在碎片整理或重组实用程序中找到。成本或效率源于 B 树实现的两个方面：即，邻居指针的维护和恢复的日志记录。

首先，如果在每个 B 树页面中维护物理邻居指针，则移动单个页面除了父节点之外还需要更新两个邻居。如果邻居指针是使用围栏键的逻辑指针，则在页面移动期间只需要更新父页面。21 如果父页面在内存中，甚至可能固定在缓冲区池中，则记录新位置很像更新内存中的间接数组。父页面中的指针更改记录在恢复日志中，但无需立即强制日志写入稳定存储，因为此更改仅仅是结构性更改，而不是数据库内容更改。

其次，数据库系统记录物理数据库中的更改，在极端情况下，删除的页面图像和新创建的页面图像都会被记录。因此，每当单个数据页面从一个位置移动到另一个位置时，低效的实现都会填充两个日志页面。更高效的实现仅记录分配操作，并延迟旧页面图像的取消分配，直到新图像安全地写入其预定位置。22 换句话说，将页面从一个位置（例如，持久性闪存上）移动到另一个位置（例如，磁盘上）在数据库恢复日志中只需要几个字节。

文件系统和数据库系统之间的区别在于恢复日志启用的更新效率。在文件系统中，必须尽快通过写入指针页面的新映像来保存新页面位置。在数据库系统中，只需将单个日志记录或几个短日志记录添加到日志缓冲区即可。因此，文件系统中页面移动的开销是使用随机访问写入整个指针页面，而数据库系统向日志缓冲区添加几十字节的日志记录，这些日志记录最终将使用大型顺序写入操作写入。

如果文件系统使用闪存作为持久性存储，则在闪存位置和磁盘位置之间移动页面会增加大量开销。因此，大多数文件系统设计者可能会更喜欢将闪存内存作为缓冲区池的扩展而不是磁盘的扩展，从而避免这种开销。

然而，数据库系统具有内置机制，可以轻松跟踪页面移动。这些机制是“主力”数据结构 B 树索引固有的。与文件系统相比，这些机制允许高效的页面移动，每个页面移动仅需要顺序写入（在恢复日志中）的一小部分，而不是完整的随机写入。

此外，数据库机制也是可靠的。如果在页面移动期间发生故障，数据库恢复由恢复日志驱动，而文件系统需要在重启期间检查整个卷。

检查点处理

为了确保系统故障后快速恢复，数据库系统采用检查点。它们的效果是，恢复需要考虑晚于最近检查点加上检查点信息中明确指示的某些有限活动的数据库活动。主要工作是将缓冲区池中的脏页面写入持久性存储。

如果闪存中的页面被视为缓冲区池的一部分，则必须在数据库检查点期间将脏页面写入磁盘。常见的检查点间隔以秒或分钟为单位。或者，如果检查点不是真正的点而是间隔，则可以合理地刷新页面并持续执行检查点活动，并在一个检查点完成后立即开始下一个检查点。因此，很快对闪存执行许多写入操作就需要写入磁盘，并且闪存作为内存层次结构中的中间层无法吸收写入活动。如果如上一节所述，由于闪存的存在而使 RAM 保持较小，则这种影响可能会加剧。

另一方面，如果闪存被视为持久性存储，则写入闪存就足够了。仅在页面替换时才需要写入磁盘（即，当页面的使用情况建议将其放置在磁盘而不是闪存中时）。因此，检查点不会产生将数据从闪存移动到磁盘的成本。

在具有闪存的系统中，检查点甚至可能更快，因为 RAM 中的脏页面只需要写入闪存，而不是磁盘。鉴于闪存相对于磁盘驱动器的非常快的随机访问速度，这种差异可能会显着加快检查点速度。

总而言之，如果将闪存视为系统持久性存储的一部分，则数据库系统将受益。相比之下，传统的文件系统没有系统范围的检查点来刷新恢复日志和缓冲区池中的任何脏数据。相反，由于缺乏保护文件内容的恢复日志，它们依赖于仔细写入修改后的文件系统页面。

页面大小

除了基于五年法则进行调整外，另一种基于访问性能的优化是 B 树节点的调整大小。最佳页面大小可最大限度地减少在从根到叶的搜索期间花费在 I/O 上的时间。它平衡了短访问时间（即，对小页面的需求）和剩余搜索空间的较大减少（即，对大页面的需求）。

假设在每个 B 树节点中进行二分搜索，则剩余搜索空间的减少是通过每个节点内记录数的对数来衡量的。在我们早期的工作中，此度量称为节点的效用。23 这种优化本质上等同于 B 树原始研究中描述的优化。24

表 4 说明了对 20 字节的记录（前缀和后缀截断25的典型记录）和填充率约为 70% 的节点的这种优化。毫不奇怪，现代高带宽磁盘上 B 树索引的最佳节点大小远大于传统数据库系统中使用的页面大小。对于这些磁盘，对于所有小页面大小，访问时间都占主导地位，因此额外的字节传输以及因此额外的效用几乎是免费的。

256 KB 的 B 树节点非常接近最佳状态。对于这些节点，表 3 指示 RAM 和磁盘的盈亏平衡时间为 88 秒。对于 400 美元的闪存磁盘和传统的旋转硬盘，表 3 指示为 337 秒或略超过五分钟。这是此处提出的两条新五年法则中的第一条。

表 5 说明了闪存上 B 树的相同计算。由于缺乏机械寻道和旋转，即使对于小页面，传输时间也占主导地位。闪存上 B 树的最佳页面大小为 2 KB，远小于传统磁盘驱动器。

在表 3 中，4 KB 页面的盈亏平衡间隔为 351 秒。这是第二条新五年法则。

两种不同的最佳页面大小的含义是，闪存和传统旋转硬盘上 B 树的任何统一节点大小都是次优的。优化两种介质的页面大小需要更改缓冲区管理、空间分配和一些 B 树逻辑。

幸运的是，马萨诸塞大学的 Patrick O'Neil 已经为 B 树设计了一种空间分配方案，其中相邻的叶节点通常驻留在同一页面的连续范围内。26 当节点拆分需要新页面时，将分配同一范围内的另一个页面。当范围溢出时，其一半页面将移动到新分配的范围。换句话说，B 树的“满时拆分一半”逻辑不仅应用于包含记录的页面，还应用于包含页面的连续磁盘范围。

使用 O'Neil 的 SB 树（S 表示顺序），256 KB 的范围可以是闪存和磁盘之间传输的单元，而 4 KB 的页面可以是 RAM 和闪存之间传输的单元。

自相似 B 树的类似概念也已针对内存层次结构中的更高级别提出（例如，以用于大型页面内间接向量的缓存行的 B 树形式）。27 鉴于现在至少有三级 B 树和三种节点大小（即，缓存行、闪存页面和磁盘页面），对缓存无关 B 树28的研究可能非常有前景。

查询处理

自相似设计既适用于 B 树等数据结构，也适用于算法。例如，排序算法已经以多种方式使用类似于传统外部归并排序的算法，不仅在磁盘上归并运行，而且在内存中归并运行，其中内存中的初始运行的大小被调整为将运行创建限制在 CPU 缓存中。29,30

相同的技术可以应用三次而不是两次：首先，内存大小的运行在内存中合并为闪存中内存大小的运行；其次，在非常大的排序操作中，闪存中内存大小的运行合并为磁盘上的运行；第三，磁盘上的运行合并以形成最终排序结果。预读、预测、后写和页面大小都值得在由缓存、RAM、闪存和传统磁盘驱动器组成的多级内存层次结构中重新审视。然后，这些页面大小可以告知页面保留与 I/O 之间的盈亏平衡计算，从而指导每个内存级别的最佳容量。

我们可以推测，这种排序算法的变体不仅速度快，而且节能。虽然能源效率一直对电池供电设备至关重要，但现在才开始研究服务器机器上的节能查询处理。31 例如，对于闪存和磁盘，能源最佳页面大小可能与性能最佳页面大小大相径庭。

外部归并排序的 I/O 模式与外部分区排序的 I/O 模式相似（尽管方向相反），也与哈希连接和哈希聚合期间的分区 I/O 模式相似。后一种算法也需要在三级内存层次结构中重新评估和重新设计，如果也考虑 CPU 缓存，则甚至需要在四级内存层次结构中重新评估和重新设计。32

具有非常快访问时间的闪存可能会重新激起人们对基于索引的查询执行的兴趣。33,34 最佳页面大小和周转时间是前面几节中得出的那些。

记录和对象缓存

多年来，数据库系统中的页面大小一直在增长，尽管没有磁盘传输带宽增长得那么快。另一方面，小页面为每次从根到叶的搜索所需的缓冲区池空间更少。例如，考虑一个包含 2000 万个条目的索引。对于 128 KB 和 4,500 条记录的索引页面，从根到叶的搜索需要两个节点，因此在缓冲区池中需要 256 KB，尽管其中一半（根节点）可能与其他事务共享。对于 8 KB 和每页 280 条记录的索引页面，从根到叶的搜索需要三个节点或缓冲区池中的 24 KB，或少一个数量级。

在传统数据库架构中，默认页面大小是在高效索引搜索（如先前讨论的，使用大型 B 树节点，并且已在原始 B 树论文35中提及）和每个索引搜索对适度缓冲池需求之间的一种折衷方案。尽管如此，这个例子仍然需要 24 KB 的缓冲池来查找可能只有 20 字节的记录，并且需要 8 KB 的缓冲池来将这 20 字节的数据保留在内存中。另一种替代设计是使用大型磁盘页和记录缓存来服务应用程序，因为记录缓存可以最大限度地减少内存需求，同时提供所需的数据保留。用作传统磁盘数据库前端的内存数据库代表了记录缓存的一种特定形式。

闪存的引入，凭借其快速的访问延迟和较小的最佳页面大小，可能会使记录缓存变得过时。通过在闪存中使用大型磁盘页，而在内存缓冲池中只使用小型页，无需两个独立的数据结构（即，事务性 B 树和一个单独的记录缓存）即可实现所需的折衷。

在面向对象的应用程序中，这些应用程序从关系数据库中的多个表和索引组装复杂的对象，问题可能会变得更好或更糟，具体取决于 B 树技术。如果使用传统索引，每个记录格式都有一个单独的 B 树，则在内存中组装一个复杂的对象需要多次从根到叶的搜索，因此，在缓冲池中需要许多 B 树节点。如果来自多个索引的记录可以基于其通用搜索键和排序顺序36,37（例如，对象标识符加上适当的附加键）在单个 B 树中交错，则可能只需极少甚至一次 B 树搜索就足够了。此外，整个复杂对象可以保留在缓冲池中的单个页面中。

未来工作的方向

未来的研究方向有几个值得关注。首先，本文提出的分析侧重于购买成本。也可以考虑其他成本，以捕捉总拥有成本。也许最有趣的是，关注能源消耗可能会导致不同的盈亏平衡点，甚至完全不同的结论。与 CPU 调度一样，内存层次结构中数据分级的算法，包括缓冲池替换和压缩，可能是对能源消耗影响最大的软件技术。

其次，五分钟规则适用于永久数据及其在缓冲池中的管理。对于临时数据（例如排序中的运行文件和哈希连接及哈希聚合中的溢出文件）的最佳保留时间可能有所不同。对于排序，就像 B 树搜索一样，目标应该是最大化每单位 I/O 时间或每单位 I/O 能源消耗的比较次数。有重点的研究可能会对多级内存层次结构中的查询处理产生新的见解。

第三，Gray 和 Putzolu 提出了进一步的经验法则，例如用于权衡内存和 CPU 性能的 10 字节规则。这些规则也值得针对成本和能源进行重新审视。与 1987 年相比，最根本的变化可能是 CPU 性能的衡量标准不应是指令数，而应是缓存行替换次数。在这种环境下，权衡空间和时间似乎是一个新问题。

第四，最佳数据移动策略是什么？一种极端情况是数据库管理员显式地在闪存和传统磁盘之间移动整个文件、表和索引。另一种极端情况是自动移动单个页面，由诸如 LRU 之类的替换策略控制。中间策略可能侧重于数据库中各个页面的角色或当前查询处理活动。例如，目录页面可以在模式更改后移动，以方便快速重新编译所有缓存的查询执行计划，并且可以在依赖于索引到索引导航的查询计划执行期间预取和缓存在 RAM 或闪存中的上层 B 树级别。

第五，将闪存引入数据库服务器的内存层次结构会产生哪些次要影响？例如，较短的访问时间允许较低的多程序设计级别，因为只需要通过异步 I/O 和上下文切换来“隐藏”短 I/O 操作。较低的多程序设计级别反过来可以减少排序和哈希操作以及锁（数据库内容的并发控制）和闩锁（内存数据结构的并发控制）的内存争用。如果这种影响被证明是显著的，则可以使用细粒度锁定的工作量和复杂性可能会降低。

第六，闪存将如何影响内存数据库系统？基于廉价地用闪存而不是 RAM 扩展的内存，它们会变得更具可扩展性、可负担性和普及性吗？由于非常快速的传统数据库系统使用闪存而不是（或除了）磁盘，它们会变得不那么受欢迎吗？在使用闪存代替传统磁盘的传统代码库中，在性能、总拥有成本、开发和维护成本、功能和版本的上市时间等方面，能否与专门的内存数据库系统竞争？

最后，类似于分代垃圾回收的技术可能有利于存储层次结构。选择性回收不仅适用于不可访问的内存对象，也适用于缓冲池页面和永久存储上的首选位置。此类研究也可能为日志结构文件系统、闪存的磨损均衡以及 RAID 存储上的写优化 B 树提供指导。

总结和结论

针对 RAM 和磁盘的 20 年五分钟规则仍然成立，但适用于更大的磁盘页面。此外，它应该通过两个新的五分钟规则来扩充：一个用于在 RAM 和闪存之间移动的小页面，另一个用于在闪存和传统磁盘之间移动的大页面。对于在 RAM 和磁盘之间移动的小页面，Gray 和 Putzolu 非常准确地预测了未来 20 年的五小时盈亏平衡点。

对闪存及其在系统架构中的地位进行研究是紧迫且重要的。在未来几年内，闪存将被用于填补许多操作系统、文件系统和数据库系统中传统 RAM 和传统磁盘驱动器之间的空白。

闪存可以用于扩展 RAM 或持久存储。这些模型在此处分别称为“扩展缓冲池”和“扩展磁盘”。这两种模型在操作系统、文件系统和数据库系统中都可能可行。然而，由于这些系统的特性，它们将采用不同的使用模型。

在这两种模型中，RAM 和闪存的内容都将受 LRU 类似的替换算法支配，这些算法试图将最有价值的页面保留在 RAM 中，而将价值最低的页面保留在传统磁盘上。用于实现闪存替换策略的链表或其他数据结构将在 RAM 中维护。

操作系统和文件系统将主要将闪存用作瞬态内存（例如，作为虚拟内存的快速备份存储和作为辅助文件系统缓存）。这两个应用程序都属于扩展缓冲池模型。在有序的系统关机期间，闪存内容可能会写入持久存储。然而，在系统崩溃期间，基于 RAM 的闪存内容描述将丢失，并且必须通过非常类似于传统文件系统检查的内容分析来重建。或者，闪存内容可以被清空并在需要时重新加载。

另一方面，数据库系统将采用闪存作为持久存储，使用扩展磁盘模型。当前内容将在持久数据结构（例如，B 树索引中的父页面）中描述。传统的持久性机制——特别是日志记录和检查点——确保系统崩溃后的数据一致性和高效恢复。有序的系统关机无需将闪存内容写入磁盘。

闪存的不同使用模型有两个原因。首先，数据库系统依赖于定期的检查点，在此期间，脏页从缓冲池刷新到持久存储。将脏页从 RAM 移动到闪存中的扩展缓冲池会在下一个检查点期间产生巨大的开销。必须在 RAM 中找到一个空闲缓冲区，必须将页面内容从闪存读取到 RAM 中，然后必须将页面写入磁盘。在具有频繁检查点的数据库系统中，向检查点添加此类开销是不可取的。另一方面，操作系统和文件系统不依赖于检查点，因此可以利用闪存作为扩展缓冲池。

其次，数据库的主要持久数据结构 B 树索引提供了精确的映射和位置跟踪机制，这些机制正是频繁的页面移动和替换所需的补充。因此，当数据页面在磁盘和闪存之间移动时，跟踪数据页面依赖于为高效数据库搜索而维护的相同数据结构。除了避免闪存中页面的缓冲描述符等之外，避免在定位页面时的间接寻址也使数据库搜索尽可能高效。

最后，由于闪存和磁盘的访问延迟和传输带宽的比率非常不同，因此不同的 B 树节点大小是最佳的。O'Neil 的 SB 树利用了多级存储层次结构中所需的两种节点大小。在闪存和磁盘之间移动单个页面所需的廉价机制与在闪存和磁盘之间移动页面所需的机制相同。Q

致谢

本文献给 Jim Gray，他提出了这项研究，并在许多方面多次帮助我和许多其他人。Barb Peters、Lily Jow、Harumi Kuno、Josè Blakeley、Mehul Shah 和 DaMoN 2007 审稿人在阅读本文的早期版本后提出了多项改进建议。

参考文献

  1. Gray, J., Putzolu, G.R. 1987. The 5-minute rule for trading memory for disk accesses and the 10-byte rule for trading memory for CPU time. SIGMOD Record 16(3): 395-398.
  2. Gray, J., Graefe, G. 1997. The five-minute rule ten years later, and other computer storage rules of thumb. SIGMOD Record 26(4): 63-68.
  3. Larus, J.R., Rajwar, R. 2007. Transactional Memory. Synthesis Lectures on Computer Architecture. Morgan and Claypool.
  4. Hamilton, J. 2007. An architecture for modular data centers. CIDR (Conference on Innovative Data Systems Research).
  5. Gray, J., Fitzgerald, B. Flash Disk Opportunity for Server-Applications; http://research.micro-soft.com/~gray/papers/FlashDiskPublic.doc.
  6. Härder, T., Reuter, A. 1983. Principles of transaction-oriented database recovery. Computing Surveys 15(4): 287-317.
  7. Chen, P.M., Lee, E.L., Gibson, G.A., Katz, R.H., Patterson, D.A. 1994. RAID: High-performance, reliable secondary storage. Computing Surveys 26(2): 145-185.
  8. 参见参考文献 7。
  9. Ousterhout, J.K., Douglis, F. 1989. Beating the I/O bottleneck: A case for log-structured file systems. Operating Systems Review 23(1): 11-28.
  10. Woodhouse, D. 2001. JFFS: the Journaling Flash File System. Ottawa Linux Symposium. Red Hat Inc.
  11. 参见参考文献 1。
  12. 参见参考文献 1。
  13. 参见参考文献 2。
  14. 参见参考文献 1。
  15. 参见参考文献 5。
  16. 参见参考文献 1。
  17. 参见参考文献 2。
  18. Graefe, G. 2007. Master-detail clustering using merged indexes. Informatik – Forschung und Entwicklung 21 (3-4): 127-145.
  19. Carey, M.J., DeWitt, D.J., Richardson, J.E., Shekita, E.J. 1989. Storage management in EXODUS. Object-Oriented Concepts, Databases, and Applications: 341-369.
  20. Stonebraker, M. 1981. Operating system support for database management. Communications of the 24(7): 412-418 .
  21. Graefe, G. 2004. Write-optimized B-trees. VLDB: 672-683.
  22. 参见参考文献 21。
  23. 参见参考文献 2。
  24. Bayer, R., McCreight, E.M. 1970. Organization and maintenance of large ordered indexes. SIGFIDET Workshop: 107-141.
  25. Bayer, R., Unterauer, K. 1977. Prefix B-trees. Transactions on Database Systems 2(1): 11-26.
  26. O'Neil, P.E. 1992. The SB-Tree: An index-sequential structure for high-performance sequential access. Acta Informatica 29(3): 241-265.
  27. Lomet, D.B. 2001. The evolution of effective B-tree page organization and techniques: A personal account. SIGMOD Record 30(3): 64-69.
  28. Bender, M.A., Demaine, E.D., Farach-Colton, M. 2005. Cache-oblivious B-trees. SIAM Journal on Computing 35(2): 341-358.
  29. Graefe, G. 2006. Implementing sorting in database systems. Computing Surveys 38(3).
  30. Nyberg, C., Barclay, T., Cvetanovic, Z., Gray, J., Lomet, D.B. 1995. AlphaSort: A cache-sensitive parallel external sort. VLDB Journal 4(4): 603-627.
  31. Rivoire, S., Shah, M. Ranganathan, P., Kozyrakis, C. 2007. JouleSort: A balanced energy-efficiency benchmark. SIGMOD.
  32. Shatdal, A., Kant, C., Naughton, J.F. 1994. Cache-conscious algorithms for relational query processing. VLDB: 510-521.
  33. DeWitt, D.J., Naughton, J.F., Burger, J. 1993. Nested loops revisited. PDIS: 230-242.
  34. Graefe, G. 2003. Executing nested queries. BTW: 58-77.
  35. 参见参考文献 24。
  36. 参见参考文献 18。
  37. Härder, T. 1978. Implementing a generalized access path structure for a relational database system. Transactions on Database Systems 3(3): 285-298.

喜欢或讨厌？请告诉我们

[email protected]

GOETZ GRAEFE ([email protected]) 在 Hewlett-Packard 实验室工作，此前他在学术界担任研究员和教师七年，然后在微软担任产品架构师和开发人员 12 年，最近被任命为 HP Fellow。在数据库管理领域，他的工作桥接了编译时查询优化、运行时查询执行和索引技术。他的 Volcano 研究项目因在查询执行方面的工作而荣获 SIGMOD 2000 的 10 年时间考验奖，并因其在查询优化方面的工作而荣获 2005 年 IEEE 国际数据工程会议的首届有影响力论文奖。

本文最初发表于 2007 年 6 月 15 日在中国北京举行的第三届新型硬件数据管理国际研讨会 (DaMoN 2007) 会议论文集。

© 2008 1542-7730/ 09/0200 $5.00

acmqueue

最初发表于 Queue vol. 6, no. 4—
在 数字图书馆 中评论本文





© 保留所有权利。

© . All rights reserved.