Skip to main content

第 3 章 人人都应了解的技术（Techniques Everyone Should Know）

原文：Readings in Database Systems, Fifth Edition (2015)，Chapter 3: Techniques Everyone Should Know，Introduced by Peter Bailis。原书文本采用 CC BY-NC-SA 4.0 许可；本译文按同一许可发布。

导读：Peter Bailis

选读论文​

  • Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. “Access path selection in a relational database management system.” SIGMOD, 1979.
  • C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz. “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging.” ACM Transactions on Database Systems, 17(1), 1992, 94-162.
  • Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger. “Granularity of Locks and Degrees of Consistency in a Shared Data Base.” IBM, September, 1975.
  • Rakesh Agrawal, Michael J. Carey, Miron Livny. “Concurrency Control Performance Modeling: Alternatives and Implications.” ACM Transactions on Database Systems, 12(4), 1987, 609-654.
  • C. Mohan, Bruce G. Lindsay, Ron Obermarck. “Transaction Management in the R* Distributed Database Management System.” ACM Transactions on Database Systems, 11(4), 1986, 378-396.

在本章中，我们呈现若干数据库系统设计中最重要核心概念的一手或接近一手资料：查询规划、并发控制、数据库恢复和分布式。这些思想对现代数据库系统如此基础，以至于几乎每个成熟的数据库系统实现都包含它们。本章中的三篇论文，远远称得上是各自主题上的经典参考。此外，与上一章不同，本章关注的是广泛适用的技术和算法，而不是完整系统。

查询优化​

查询优化在关系数据库架构中很重要，因为它是实现数据无关查询处理的核心。Selinger 等人关于 System R 的奠基性论文，把实际可用的查询优化问题分解为三个不同的子问题：代价估计、定义搜索空间的关系等价式，以及基于代价的搜索。

优化器会估计执行查询每个组成部分的代价，度量单位是 I/O 和 CPU 成本。为此，优化器既依赖每个关系内容的预计算统计信息，也就是存储在系统目录中的信息，也依赖一组启发式规则来判断查询输出的基数，也就是大小，例如基于谓词选择率估计。作为练习，可以仔细思考这些启发式规则：它们在什么时候合理？在哪些输入上会失败？又可以如何改进？

使用这些代价估计，优化器通过动态规划算法为查询构造执行计划。优化器定义一组物理算子，用来实现给定逻辑算子，例如使用完整 “segment” 扫描查找元组，或使用索引查找。基于这组算子，优化器迭代构造一个由算子组成的 left-deep 树，并利用代价启发式来最小化运行这些算子所需的估计总工作量，同时考虑上游消费者所需的 “interesting orders”。这种方式避免考虑所有可能的算子排列，但相对于计划大小仍然是指数级的；正如我们在第 7 章讨论的，现代查询优化器仍然会在大型计划，例如多路连接上遇到困难。此外，Selinger 等人的优化器会提前编译，而其他早期系统，例如 Ingres [150]，则解释查询计划；实际上，是逐元组解释执行。

像几乎所有查询优化器一样，Selinger 等人的优化器实际上并不是“最优”的，也就是说，无法保证优化器选择的计划就是最快或最便宜的。关系优化器在精神上更接近现代语言编译器中的代码优化例程，也就是执行尽力而为的搜索，而不是数学优化例程，也就是找到最佳解。不过，今天许多关系引擎都采用了这篇论文中的基本方法，包括使用二元算子和代价估计。

并发控制​

我们收录的第一篇事务论文来自 Gray 等人，它引入了两个经典思想：多粒度锁和多种锁模式。事实上，这篇论文读起来像是两篇独立论文。

首先，这篇论文提出了多粒度锁的概念。这里的问题很简单：给定一个具有层次结构的数据库，应该如何执行互斥？什么时候应该以粗粒度加锁，例如锁住整个数据库，什么时候应该以更细粒度加锁，例如锁住单条记录？又如何同时支持对层次结构不同部分的并发访问？虽然 Gray 等人的层次布局，由数据库、区域、文件、索引和记录组成，与现代数据库系统略有不同，但除了最初级的数据库加锁系统之外，今天几乎所有系统都吸收了他们的方案。

其次，这篇论文发展了多种隔离程度的概念。正如 Gray 等人提醒我们的，并发控制的目标之一，是维护“consistent”的数据，也就是遵守某些逻辑断言的数据。经典上，数据库系统使用可串行化事务作为强制一致性的手段：如果每个单独事务都会让数据库处于“consistent”状态，那么一个可串行化执行，也就是等价于这些事务某个串行执行的执行，就能保证所有事务都观察到数据库的“consistent”状态 [57]。Gray 等人的 “Degree 3” 协议描述了经典的严格 two-phase locking（2PL），它保证可串行化执行，是事务处理中的一个重要概念。

不过，强制可串行化通常被认为代价太高。为了提高性能，数据库系统往往改用不可串行化隔离来执行事务。在这里这篇论文中，持有锁是昂贵的：发生冲突时等待锁需要时间；如果发生死锁，则可能永远等待，或者导致中止。因此，早在 1973 年，IMS 和 System R 等数据库系统就开始实验不可串行化策略。在基于锁的并发控制系统中，这些策略通过缩短持锁时间来实现。这允许更高并发，可能减少死锁和系统引发的中止；在分布式环境中，还可能允许更高的操作可用性。

在这篇论文的后半部分，Gray 等人对这些基于锁的策略的行为给出了初步形式化。今天，它们非常普遍；正如我们在第 6 章讨论的，不可串行化隔离是大多数商业和开源 RDBMS 的默认选项，有些 RDBMS 甚至完全不提供可串行化。Degree 2 现在通常称为 Repeatable Read 隔离，Degree 1 现在称为 Read Committed 隔离，而 Degree 0 很少使用 [27]。论文还讨论了 recoverability 这个重要概念：在某些策略下，一个事务可以被中止，或者说被“撤销”，而不影响其他事务。除 Degree 0 外，所有事务都满足这一属性。

在 Gray 等人关于基于锁的可串行化的开创性工作之后，出现了各种替代并发控制机制。随着硬件、应用需求和访问模式变化，并发控制子系统也随之变化。不过，并发控制有一个性质几乎可以确定：并发控制中不存在单方面“最佳”的机制。最优策略依赖工作负载。为了说明这一点，我们收录了 Agrawal、Carey 和 Livny 的一项研究。尽管这篇论文年代久远，它的方法论和总体结论仍然切中要害。它是一个很好的例子，展示了深思熟虑、与具体实现无关的性能分析工作如何能够随时间提供有价值的经验。

从方法论上说，执行所谓“信封背面”计算是一项有价值的技能：通过粗略算术快速估计感兴趣的指标，得到一个与正确值相差不超过一个数量级的答案，可能节省数小时，甚至数年的系统实现和性能分析时间。这在数据库系统中有着长期而有用的传统，从 “Five Minute Rule” [73] 到 Google 的 “Numbers Everyone Should Know” [48] 都是如此。虽然从这些估算中得出的一些经验是短暂的 [69, 66]，但结论往往能提供长期经验。

不过，对于并发控制这样的复杂系统分析，仿真可以成为介于信封背面估算和完整系统基准测试之间的有价值中间步骤。Agrawal 的研究就是这种方法的例子：作者使用精心设计的系统模型和用户模型，来模拟加锁、基于重启的并发控制，以及乐观并发控制。

这项评估中有几个方面特别有价值。第一，几乎每张图里都有一个 “crossover” 点：不存在明显赢家，因为表现最好的机制取决于工作负载和系统配置。相反，几乎每个没有交叉点的性能研究都可能并不有趣。如果某个方案“总是赢”，那么研究应包含分析性说明，理想情况下还应包含证明，说明为什么会这样。第二，作者考虑了广泛的系统配置；他们考察并讨论了模型中的几乎所有参数。第三，许多图表现出非单调性，也就是说，并不总是向右上方增长；这是颠簸和资源限制的产物。正如作者所说明的，假设资源无限会导致截然不同的结论。一个不够仔细的模型如果隐含了这个假设，就会有用得多。

最后，这项研究的结论是合理的。基于重启的方法的主要成本，是冲突发生时“浪费”的工作。当资源充足时，投机执行是有意义的：浪费的工作成本更低，而且在资源无限时，它是免费的。不过，当资源更受限制时，阻塞策略会消耗更少资源，并提供更好的整体性能。再次强调，不存在单方面最优的选择。不过，这篇论文的结论性评论已经证明很有预见性：计算资源仍然稀缺，而事实上，今天很少有商品系统采用完全基于重启的方法。不过，随着技术比率，也就是磁盘、网络、CPU 速度继续变化，重新审视这个权衡仍然有价值。

数据库恢复​

事务处理中的另一个主要问题是维持持久性：事务处理的效果应能在系统故障后继续存在。维持持久性的一项几乎无处不在的技术是日志记录：事务执行期间，事务操作会被存储在容错介质，例如硬盘或 SSD 上的日志中。每个从事数据系统工作的人都应该理解预写日志（write-ahead logging）如何工作，最好还要理解得比较详细。

实现 “No Force, Steal” WAL 恢复管理器的经典算法，是 IBM 的 ARIES 算法，也就是我们下一篇论文的主题。（资深数据库研究者可能会告诉你，非常相似的思想在同一时期也出现在 Tandem 和 Oracle 等地方。）在 ARIES 中，数据库不需要在提交时把脏页写入磁盘（“No Force”），并且数据库可以在任何时候把脏页刷到磁盘（“Steal”）[78]；这些策略允许高性能，几乎存在于所有商业 RDBMS 产品中，但也反过来增加了数据库复杂性。ARIES 的基本思想是分三个阶段执行崩溃恢复。第一，ARIES 通过向前重放日志执行分析阶段，以确定崩溃时哪些事务正在进行。第二，ARIES 执行 redo 阶段，再次重放日志，并且这次执行崩溃时正在进行的任何事务的效果。第三，ARIES 通过向后播放日志执行 undo 阶段，撤销未提交事务的效果。因此，ARIES 的关键思想是通过“重复历史”来执行恢复；事实上，undo 阶段可以执行正常操作中用于中止事务的同一套逻辑。

ARIES 本应是一篇相当简单的论文，但它也许是本文集中最复杂的一篇。在研究生数据库课程中，这篇论文是一道成年礼。不过，这些材料是基础性的，因此理解它很重要。幸运的是，Ramakrishnan 和 Gehrke 的本科教材 [127]，以及 Michael Franklin 的一篇综述论文 [61]，都提供了更温和的处理方式。我们这里收录的完整 ARIES 论文，之所以明显复杂，是因为它沿途穿插讨论了替代设计决策的缺点。第一遍阅读时，我们鼓励读者忽略这些材料，只关注 ARIES 方法本身。替代方案的缺点很重要，但应该留到更仔细的第二遍或第三遍阅读时再看。除了组织结构之外，ARIES 协议的讨论还因为若干内容而进一步复杂化，例如管理索引等内部状态，也就是 nested top actions 和 logical undo logging，后者也用于 Escrow transactions [124] 等特殊方案，以及最小化恢复期间停机时间的技术。在实践中，让恢复时间看起来尽可能短很重要；这并不容易实现。

分布式​

本章最后一篇论文关注分布式环境中的事务执行。今天，这个主题尤其重要，因为越来越多数据库都是分布式的：要么是复制型，在不同服务器上有多份数据副本；要么是分区型，数据项存储在互不相交的服务器上；或者两者兼有。尽管分布式能在容量、持久性和可用性方面带来好处，但它也引入了一组新的关注点。服务器可能失败，网络链路可能不可靠。即使没有故障，网络通信也可能代价高昂。

我们聚焦于分布式事务处理中的一项核心技术：原子提交（atomic commitment，AC）。非常非正式地说，给定一个在多台服务器上执行的事务，无论这些服务器是多个副本、多个分区，还是二者兼有，AC 都确保该事务要么在所有服务器上提交，要么在所有服务器上中止。实现 AC 的经典算法可以追溯到 20 世纪 70 年代中期，称为 Two-Phase Commit（2PC；不要与前面的 2PL 混淆！）[67, 100]。除了很好地概述 2PC 以及提交协议与 WAL 之间的交互之外，这里这篇论文还包含两个改进 AC 性能的变体。Presumed Abort 变体允许进程避免强制把中止决策写入磁盘，或确认中止，从而减少磁盘使用和网络流量。Presumed Commit 优化与之类似，当更多事务提交时，它优化空间和网络流量。请注意 2PC 协议、本地存储和本地事务管理器之间交互的复杂性；细节很重要，正确实现这些协议可能很有挑战。

故障的可能性会显著复杂化 AC，也会复杂化分布式计算中的大多数问题。例如，在 2PC 中，如果所有参与者都已经发送投票，但协调者还没收到某个失败参与者的投票之前，协调者和该参与者都失败了，会发生什么？剩余参与者将不知道应该提交还是中止事务：失败的参与者投的是 YES 还是 NO？参与者无法安全继续。事实上，在不可靠网络上运行时，任何 AC 实现都可能阻塞，或者无法取得进展 [28]。如果再结合可串行化并发控制机制，阻塞 AC 意味着吞吐可能停滞。因此，一组相关 AC 算法在放宽假设的情况下研究 AC，这些假设既包括网络方面，例如假设同步网络 [145]，也包括服务器可获得的信息方面，例如使用能够判断节点何时失败的“故障检测器” [76]。

最后，许多读者可能熟悉一个密切相关的问题：共识（consensus），也可能听说过 Paxos 算法这样的共识实现。在共识中，只要所有进程最终会就某个提案达成一致，任何提案都可以被选中。（相比之下，在 AC 中，任何单个参与者都可以投 NO，之后所有参与者都必须中止。）这使得共识成为一个比 AC “更容易”的问题 [75]，但和 AC 一样，任何共识实现在某些场景下也可能阻塞 [60]。在现代分布式数据库中，共识常被用作复制的基础，以确保副本以相同顺序应用更新，这是状态机复制的一个实例（参见 Schneider 的教程 [141]）。AC 常被用来执行跨多个分区的事务。Lamport 的 Paxos [99] 是最早的共识实现之一，也最著名，部分原因是其呈现方式的复杂程度堪比 ARIES。不过，在实践中，Viewstamped Replication [102]、Raft [125]、ZAB [92] 和 Multi-Paxos [35] 算法可能更有帮助。这是因为这些算法实现的是分布式日志抽象，而不是原始 Paxos 论文中的“共识对象”。

不幸的是，数据库社区和分布式计算社区在某种程度上彼此分离。尽管双方都关注复制数据，但许多年来，两个领域之间的思想转移一直有限。在云和互联网规模数据管理时代，这个鸿沟已经缩小。例如，Gray 和 Lamport 在 2006 年合作提出了 Paxos Commit [71]，这是一个结合 AC 和 Lamport Paxos 的有趣算法。这个交叉领域仍然有许多工作要做，而这里“人人都应了解的技术”数量也已经增加。