在之前的文章中，我们解释了什么是一致性，“强一致性”和“最终一致性”之间的区别，以及为什么这种区别对于现代应用程序开发人员越来越重要。 我们还介绍了“一致性税”的概念：如果开发团队选择仅具有最终一致性或有限一致性保证的系统，则需要投入额外的时间和精力。
几个现代数据库使用最先进的算法来消除一致性和性能之间的权衡。 当然，我们不希望你在没有适当解释的情况下就相信我们的话。 因此，在这最后一篇文章中，我们将深入探讨这些数据库背后的技术细节。 通常，这些技术细节的唯一信息来源是研究论文，因此本文的目的是用更简单的术语解释这些系统。 因为这些系统在现实中要复杂得多，所以我们会在文本中提供链接，如果你想了解更多信息并喜欢阅读研究论文，可以点击这些链接。
介绍
在本系列文章的第 1 部分和第 2 部分中，我们解释了分布式数据库如何使用不同的副本来分散负载和/或为不同地区的用户提供服务。 为了总结一下，对于新读者来说，副本只是数据的复制。 这种复制可以位于同一个位置以实现冗余，也可以位于另一个位置以向这些位置的用户提供更低的延迟。 拥有可以处理读写操作的多个副本有一个很大的优势，因为数据库变得可扩展，并且可以为所有用户提供更低的延迟，无论他们在哪里。 但是，您不希望每个副本都对数据有自己的解释。 您希望数据的解释是唯一的，而不是每个副本之间存在微小的数据差异，这通常被称为单一事实来源。 为了实现这一点，您需要对数据更改达成某种协议。 我们需要达成共识。
等待共识
每个旨在保持一致的分布式数据库都有多个副本，这些副本必须就事务的结果达成一致。 如果发生冲突的数据更新，这些副本必须就哪个更新通过，哪个更新不通过达成一致。 这称为“共识”。
让我们回到我们的游戏，以举例说明为什么我们需要共识。 想象一下，我们的游戏玩家只剩下 3 枚金币，但试图同时从两家不同的商店购买两件不同的物品，总预算超过了剩余的 3 枚金币。 这涉及两个事务，每个事务对应一个物品/商店，我们将其表示为 t1 和 t2。 让我们假设商店的老板彼此相隔地球，所以交易发生在两个不同的副本上。 如果两个事务都被接受，用户将能够购买超出其负担能力的物品。 我们如何阻止用户超支？
我们知道这些副本需要通信以就两个事务的最终结果达成一致。 我们不知道的是它们需要多少通信。 副本 1 和副本 2 之间需要来回传递多少消息才能就哪个事务具有优先级以及哪个事务被取消达成一致？
由于分布式数据库中的副本旨在以低延迟为来自世界不同地区的用户提供服务，因此它们本质上相距甚远。 通过将数据的副本放置在更靠近最终用户的附近，这些用户可以以更低的延迟读取数据。 但是，当发生写入操作时，副本需要互相发送消息以一致地更新所有复制的数据 - 这些消息可能需要数十毫秒才能完成，因为它们在全球范围内传播时受光速的限制。 很明显，我们需要尽可能减少跨数据中心消息的数量，以便最终用户不会因等待这些分布在全球各地的副本达成共识而浪费时间。
长期以来，人们一直认为这是不可能的或不切实际的。 但今天，已经存在多种技术可以将往返次数保持在较低水平并将延迟控制在正常范围内。
纽约和巴黎之间的距离是 5,839 公里。 光从纽约传播到巴黎然后再返回需要 40 毫秒。
— 理论速度与现实世界速度
剩下的最重要的问题是：“我们需要执行多少次往返才能执行事务？” 这个问题的答案在很大程度上取决于所使用的算法。
如何达成一致？
看来，为了就某件事达成共识，您至少需要四跳（或两轮通信）：一轮是让每个副本都知道您即将执行某项操作，然后是第二轮是在每个人都同意可以执行此操作后实际执行操作。 这被称为分布式 两阶段提交 ，它几乎被所有分布式数据库使用。 让我们来看一个比喻。 想象一下，您必须与一群人就一个好的聚会日期达成一致。 它可能像这样
首先，Polly 询问每个人是否可以在星期一参加聚会； 现在她知道每个人都能参加聚会。 接下来，她需要让每个人都知道聚会确实会在星期一举行，并且人们承认他们会参加。
这些与两阶段提交中的两个阶段非常相似。 当然，数据库不会参加聚会，所以这些阶段有不同的功能。 在分布式系统的情况下，这些阶段被称为：
- 准备或请求提交：确保每个人都知道事务。 在此阶段，分布式数据库中的副本将查询存储在磁盘上的某种待办事项列表（事务日志）中，以确保在服务器出现故障时它们仍然知道该怎么做。
- 提交：实际计算结果并存储结果
当然，一如既往，事情永远不会那么简单。 存在许多此类算法的变体。 例如，存在对两阶段提交的改进，称为 Paxos 和 Raft，甚至存在这些算法的许多变体（multi paxos/fast paxos/…）。 这些替代方案旨在改进可用性或性能问题。 为了理解可用性问题，只需想象一下 Polly 生病了或者 Amber 的手机没电了。 在前一种情况下，她将无法继续担任聚会协调员的工作，而在后一种情况下，Polly 将暂时无法知道 Amber 是否同意聚会日期。 Raft 和 Paxos 通过仅要求大多数人回答和/或在领导者或协调者出现故障时自动选择新的协调者来改进这一点。 一个很好的动画展示了 Raft 的工作原理，可以在这里找到 这里。
就什么达成一致？
我们可以得出结论，每个分布式数据库都需要 2 次往返来写入/读取数据吗？ 不，现实比这更复杂。 一方面，存在许多可能的优化，另一方面，我们可能需要就多件事情达成一致。
- 就事务时间达成一致
- 就是否可以执行读取操作达成一致
可能存在多个两阶段提交轮次的简单示例可能是 Cassandra 的轻量级事务。 它们首先需要就读取达成共识协议，然后就写入达成共识协议。 如果每条消息需要 40 毫秒才能完成传播，这意味着整个事务需要 320 毫秒或更长时间 - 这取决于所需的“锁”，我们将在后面解释。
这很容易理解，但由于 Cassandra 从未设计为强一致的，因此存在一些 问题。 这是否意味着强一致性数据库更慢？ 根本不是！ 现代分布式数据库使用各种有趣的功能来实现更好的性能。
等待锁
我们不仅需要等待消息达成一致，几乎所有分布式数据库也会使用“锁”。锁保证了即将被事务修改的数据不会被另一个事务同时修改。当数据被锁定后，其他事务就不能再修改它，这意味着这些事务必须等待。因此，这种锁的持续时间对性能有很大影响。同样，这种性能影响取决于数据库实现的算法和优化。有些数据库会比其他数据库保持更长时间的锁，而有些数据库根本不使用锁。
现在我们已经了解了足够的基础知识，让我们深入研究算法。
现代共识算法
我们现在知道，共识和锁是我们需要优化的主要瓶颈。所以让我们回到这篇文章的主要问题：“新技术如何将这些延迟降低到可接受的范围内？”让我们从第一个现代算法开始，它为数据库世界的其他部分带来了有趣的思路。
2010 – Percolator
Percolator 是建立在 BigTable 之上的内部系统（Google 早期构建的 NoSQL 数据库之一），Google 使用它来对搜索索引的页面抓取速度进行增量更新。第一篇关于 Percolator 的 论文 于 2010 年发布，它启发了第一个受其启发的分布式数据库：FoundationDB，于 2013 年发布。FoundationDB 随后被苹果收购，并于 2019 年最终发布了一个稳定版本，同时发布了一篇 FoundationDB 论文。
尽管 Percolator 允许 Google 显着加快页面抓取速度，但它最初并不是作为通用数据库构建的。它更像是为了成为一个快速且可扩展的增量处理引擎，以支持 Google 的搜索索引。由于搜索索引必须可扩展，因此许多计算必须在许多机器上同时进行，这需要分布式数据库。正如我们在之前的文章中了解到的那样，针对存储数据的分布式系统进行编程非常复杂，传统上要求开发人员为绕过不可预测的数据库行为而付出“一致性代价”。为了避免付出如此高昂的一致性代价，Google 在构建 Percolator 时采用了强一致性模型。
Percolator 的一致性模型离不开两个关键要素：版本控制和时间戳预言机。
要素 1：版本控制
正如我们在之前的文章中提到的，强一致性要求我们对事务达成全局顺序。版本控制是许多这些算法中必不可少的元素之一，因为它可用于故障恢复，以帮助复制数据，并支持称为“快照隔离”的一致性模型。
当节点发生故障或断开连接时，版本控制有助于故障恢复。当节点重新上线时，由于版本的存在，它可以通过从它能够保存的最后一个快照开始，然后根据另一个节点中的版本重播事务来轻松恢复其状态。它只需要询问另一个节点：“嘿，自从我离开后发生了什么变化？”如果没有版本控制，它将不得不复制所有数据，这将给系统带来巨大的压力。
故障恢复很棒，但最强大的优势在于，这种版本控制系统可用于实现强一致性模型。如果版本控制系统为每次数据更改保留版本，我们实际上可以回到过去，并针对我们数据的早期版本执行查询。
一些聪明的人发现，这种历史查询功能可用于提供称为“快照一致性”的一致性模型。快照一致性的思想是在查询开始时选择数据的某个版本，在查询的其余部分使用该版本的 data，然后在查询结束时写入一个新的版本。
这里可能存在一个陷阱：在执行此类查询期间，另一个查询可能会写入与第一个查询冲突的数据。例如，如果两个写入查询都以具有相同快照的银行帐户（帐户中有 1000 美元）开始，则它们都可能花费这笔钱，因为它们没有看到另一个查询的写入。为了防止这种情况发生，将执行额外的交易以查看快照的值是否在任一查询写入结果之前发生了更改。如果确实发生了与快照值冲突的更改，则该事务将回滚并必须重新启动。
然而，Percolator 仍然需要解决一个问题。不同机器上的时钟很容易出现数百毫秒的偏差。如果某个查询的数据分散在多台机器上，就像我们最初的示例一样，您不能简单地要求两台机器在某个时间戳提供数据，因为它们对当前时间的理解略有不同。这只是几毫秒的问题，但在必须处理大量事务时，几毫秒足以将正确的数据变为错误的数据。
时间同步为我们带来了 Percolator 的第二个要素。
要素 2：时间戳预言机
Percolator 解决时间同步问题的方案称为时间戳预言机。Percolator 并没有让每个节点自己决定时间（这不够准确），而是使用一个中心系统来公开一个 API，该 API 为您提供时间戳。该系统所在的节点是时间戳预言机。当我们保留数据的多个版本时，每个查询至少需要两个时间戳。首先，我们需要一个时间戳来查询快照，我们将使用它来读取数据。然后，当我们准备写入时，在事务结束时，我们需要第二个时间戳来标记新的数据版本。因此，Percolator 的缺点是它至少需要两次调用时间戳预言机，如果预言机与发出调用的节点位于不同的区域，这会引入更多的延迟。当 Google 想出他们的分布式数据库 Spanner 时，他们解决了这个问题。
2012 – Spanner
Spanner 是第一个提供强一致性的全球分布式数据库，这基本上意味着您可以获得低延迟读取，而无需再担心潜在的数据库错误。开发人员不再需要投入额外的工作来规避由最终一致性引起的潜在错误。这篇论文于 2012 年发布，并于 2017 年作为 Spanner Cloud 发布给公众。
要素 1：版本控制
Google 在使用 Percolator 的经验基础上构建了 Spanner。由于 Percolator 的版本控制系统被证明是有效的，因此他们在 Spanner 的设计中保留了它。该版本控制系统提供了执行非常快速读取（快照读取）的功能，前提是您愿意放弃一致性。在这种情况下，您可以运行查询并为 Spanner 提供结果的最大年龄。例如：“请尽快返回我当前的库存，但数据只能是 15 秒前的”。基本上，您现在可以选择每个查询的适合您的用例的一致性级别，而不是放弃一致性。
要素 2：TrueTime
为了消除机器之间同步时间带来的额外开销，Spanner 放弃了时间戳预言机，转而使用称为 TrueTime 的新概念。TrueTime 并没有使用一个中心系统来提供时间的一致视图，而是试图减少机器本身的时钟漂移。Google 的工程师通过实现一个基于 GPS 和原子钟的时间同步协议来限制本地时钟漂移。这种同步算法允许他们将时钟漂移限制在 7 毫秒以内，但需要由 GPS 和原子钟技术组合而成的特定硬件。
当然，仍然存在 7 毫秒的潜在时钟漂移，这意味着两台服务器可能仍然会将时间戳解释为两个不同的快照。这是通过 Spanner 的第三个要素解决的：提交等待。
成分 3：提交等待
事实上，TrueTime API 并不返回一个时间戳，而是返回一个区间 n，它确定当前时间戳应该位于该区间内。一旦它准备好提交，它将等待几毫秒来应对可能发生的漂移，这被称为“提交等待”。这确保分配给写入操作的时间戳是在所有节点上都已过去的时间戳。这也是在通用硬件上运行 Spanner 无法提供相同保证的原因，因为等待时间需要几百毫秒。
2012 – Calvin
第一个关于 Calvin 算法的论文发布于 2012 年，来自耶鲁大学的研究。与之前的方案一样，Calvin 包含几个成分。虽然版本控制也是其中的一部分，但其余方案从根本上不同，需要一些额外的成分才能起作用：确定性计算，以及将排序与锁定分离。这些通常不是传统架构数据库中所具有的成分。通过改变架构并接受查询必须是确定性的，Calvin 可以将跨数据中心消息的最坏情况数量减少到**两个**。这将全局事务的最坏情况延迟大幅降低，使其低于 200 毫秒，理论上甚至低于 100 毫秒。当然，为了相信这是可能的，您可能想知道它是如何工作的，所以让我们看一下该算法。
要素 1：版本控制
与 Percolator 和 Spanner 相似，Calvin 依赖于版本化数据。Calvin 中的这些快照主要用于确保容错性。每个节点存储不同的快照，可以将其视为检查点。断开连接的节点重新联机后，只需获取其见证的最后一个检查点的时间戳，然后要求另一个节点通知它该检查点之后的所有事务。
成分 2：确定性计算
许多前端开发人员可能听说过Elm 前端框架，它实现了类似于React Redux 的工作流程。Elm 比类似的基于 JavaScript 的框架学习曲线更陡峭，因为它要求您学习一门新语言。但是，由于该语言是**函数式**的（没有副作用），Elm 允许一些令人印象深刻的优化。关键是 Elm 中的函数放弃了破坏性操作以成为确定性的。您可以用相同的输入两次运行相同的函数，它将始终产生相同的结果。由于它们是确定性的，Elm 查询现在可以更有效地决定如何更新视图。
与 Elm 相似，Calvin 也放弃了一些东西来加快计算速度。在 Calvin 的情况下，我们可以基本地说，事务的结果将是相同的，无论是在机器 A 上执行还是在机器 B 上执行。这可能看起来很明显，但通常数据库不会保证这一点。请记住，SQL 允许您使用当前时间或允许称为交互式事务的操作，其中用户输入可以在事务中间插入，这两者都可能违反 Calvin 提供的保证。
为了实现确定性计算，Calvin (1) 需要取出诸如当前时间之类的计算并对其进行预先计算，以及 (2) 不允许交互式事务。交互式事务是指用户启动事务、读取一些数据、在中间提供一些额外的用户输入，然后最终进行一些额外的计算以及可能的一些写入。由于用户是不可预测的，因此这种事务不是确定性的。本质上，Calvin 用一种小便利（交互式事务）换取了高性能。
成分 3：将排序问题分开。
数据库花费大量时间协商锁，以使系统看起来像是在特定的顺序下执行。如果您只需要一个顺序，也许我们可以将锁定的问题与排序的问题分开。这意味着您的事务必须是纯粹的。
— Kyle Kingsbury
在数据库领域，将排序事务的关注点与实际执行分离已经考虑过很多次，但没有取得太大成功。但是，当您的事务是确定性的时，将排序与计算分离实际上变得可行。事实上，确定性计算与将排序与算法其余部分分离相结合具有强大的力量，因为它有助于减少锁定时间并极大地减少了远程节点之间的较慢通信（跨数据中心通信）。
更短的锁定时间
每当对数据块进行锁定时，这意味着使用该数据的其他查询必须等待。因此，更短的锁定时间意味着更好的性能。以下是 Calvin 中锁定过程概述的图片，以及传统分布式数据库如何执行此操作的对比。大多数数据库会对数据保持锁定，直到至少对写入内容达成共识，而 Calvin 仅会保持锁定，直到所有节点都对顺序达成一致。由于计算是确定性的，并且它们都对顺序达成一致，因此每个节点将分别计算并得出相同的结果。
远程节点之间的通信减少
除了锁定时间上的优势外，将排序与算法其余部分分离还需要更少的通信。如 Cassandra 示例所述，分布式数据库通常在其算法的许多阶段都需要跨数据中心的通信。在 Calvin 的情况下，我们唯一需要达成一致的时刻是在确定顺序的时刻。使用 Raft 协议，这可以在两跳内完成，这使得读取写入查询的延迟低于 100 毫秒成为可能。
再加上减少的锁定时间，这也带来了极高的吞吐量。最初的 Calvin论文也进行了实验，表明这种方法在高争用工作负载下明显优于传统的分布式数据库设计。它们在一组通用机器上每秒 50 万笔事务的结果与目前在更高端硬件上获得的世界纪录结果相媲美。
在任何硬件上运行
除此之外，Calvin 还有一个优势：它不再需要特定硬件才能获得此类结果。由于 Calvin 可以在通用机器上运行，因此它可以在任何云提供商上运行。
2014 – FaunaDB 风格的共识
要素 1：版本控制
FaunaDB 拥有自己的分布式事务协议，与 Calvin 有一些相似之处。与之前的方案一样，FaunaDB 的数据也是版本化的。由于版本控制不仅对一致性模型有用，而且还可以具有业务价值，因此 FaunaDB 已将此机制升级为一等公民，可供最终用户使用。此功能本质上允许时间旅行查询。最终用户可以在历史数据上执行查询来回答以下问题：“20 天前此查询的结果是什么？”。这对于恢复意外覆盖的数据、审核数据更改或简单地在应用程序的功能中加入时间旅行很有用。
成分 2 和 3：确定性计算和分离
与 Calvin 类似，FaunaDB 也拥有确定性计算，并将排序问题与算法的其余部分分离。虽然存在相似之处，但 FaunaDB 中的交易计算发生在与 Calvin 不同的阶段。Calvin 利用确定性本质在确定顺序后多次执行相同的交易，而 FaunaDB 仅在交易顺序达成共识之前计算一次。这将我们引向第四个成分。
成分 4：乐观计算
FaunaDB 添加了第四个成分，当我们讨论快照隔离时已经看到过：**乐观计算**而不是锁定。
FaunaDB 不会锁定，而是会乐观地计算接收交易的节点中交易结果**一次**，然后将结果和原始输入值添加到日志中。Calvin 会将需要在交易日志中执行的查询保存下来，FaunaDB 会将计算结果和原始输入值都保存在日志中。一旦就结果应用顺序达成共识，FaunaDB 会验证该计算的输入数据是否发生更改（由于版本控制）。如果输入值已更改，则中止交易并重新启动；如果输入值保持不变，则将结果应用于所有节点，无需任何额外计算。
FaunaDB 的算法具有与 Calvin 相似的优势，但减少了集群中所需的计算量。
结论
在本系列文章中，我们解释了强一致性如何帮助您更有效地构建无错误应用程序。在本文中，我们进一步解释了革命性的思想如何推动新一代分布式数据库的发展，这些数据库既一致又高效。前面文章的结论是：“一致性很重要”。在本文中，结论概括如下
在不久的将来，如果您看到类似这样的短语：
“许多 NoSQL 数据库不提供对多个文档的原子写入，作为回报，它们提供了更好的性能。虽然一致性是 SQL 数据库的另一个重要功能，但它阻碍了数据库跨多个节点扩展的能力，因此许多 NoSQL 数据库放弃了一致性。” – 迁移到 NoSQL 的最大挑战
请认识到，现代算法使数据库能够在没有集中化的情况下提供一致性。在本文中，我们看到了一些执行此操作的算法和数据库的示例。建立在这些算法之上的数据库是下一代数据库，不再可以用简单的类别来描述，例如 NoSQL、SQL 甚至 NewSQL。
借助基于 Percolator、Spanner、Calvin 和 FaunaDB 交易协议的分布式云数据库，您可以拥有提供更强大一致性模型的高性能分布式数据库。这意味着您可以构建提供低延迟的数据密集型应用程序，而无需担心数据错误、性能或服务配置。在这些系统中，一致性是透明的，作为开发人员，您无需考虑它。下次选择数据库时，请选择默认情况下提供一致性的数据库。