在之前的文章中，我们解释了什么是一致性，“强一致性”和“最终一致性”之间的区别，以及为什么这种区别对于现代应用程序开发人员来说比以往任何时候都更加重要。我们还介绍了“一致性税”的概念：如果开发团队选择一个只有最终一致性或有限一致性保证的系统，他们需要投入的额外时间和精力。
一些现代数据库使用最先进的算法来消除一致性和性能之间的权衡。当然，我们不希望您在没有适当解释的情况下就相信我们的话。因此，在本文的最后一部分，我们将深入探讨其中一些数据库背后的技术细节。通常，这些技术细节的唯一信息来源是研究论文，因此本文的目的是用更简单的术语解释这些系统。由于这些系统在现实中要复杂得多，因此如果您想了解更多信息并喜欢阅读研究论文，我们将在文本中提供链接。
简介
在本系列文章的第一部分和第二部分中，我们解释了分布式数据库如何使用不同的副本分发负载和/或为不同区域的用户提供服务。为了在这里总结，对于新读者来说，副本只是数据的复制。并且此复制可以存在于同一位置以实现冗余，或者存在于另一个位置以向这些位置的用户提供更低的延迟。拥有可以处理读写操作的多个副本具有很大的优势，因为数据库变得可扩展并且可以为所有用户提供更低的延迟，无论他们身在何处。但是，您不希望每个副本对数据都有自己的解释。您希望数据有一个唯一的解释，而不是每个副本之间存在细微的数据差异，这通常被称为单一事实来源。为了实现这一点，您需要就数据更改达成某种协议。我们需要达成共识。
等待共识
每个旨在保持一致的分布式数据库都有多个副本，这些副本必须就事务的结果达成一致。如果发生冲突的数据更新，这些副本必须就哪个更新通过，哪个更新不通过达成一致。这称为“共识”。
让我们回到我们的游戏来举例说明为什么我们需要共识。假设游戏的玩家只剩下3个金币，但试图同时从两个不同的商店购买两个不同的物品，总预算超过剩余的3个金币。这涉及两个事务，每个物品/商店一个，我们将其表示为t1和t2。并且假设商店的店主彼此相隔千里，因此交易发生在两个不同的副本上。如果这两个事务都被接受，用户将能够购买超出其承受能力的物品。我们如何防止用户超支？
我们知道这些副本需要通信才能就这两个事务的最终结果达成一致。我们不知道的是他们需要多少通信。为了就哪个事务优先，哪个事务被取消达成一致，副本1和副本2之间需要来回发送多少消息？
由于分布式数据库中的副本旨在以低延迟为世界不同地区的用户提供服务，因此它们本质上相距甚远。通过将数据的副本放置在更靠近最终用户的位置，这些用户可以以更低的延迟读取数据。但是，当写入发生时，副本需要相互发送消息以统一更新所有复制的数据——而这些消息可能需要几十毫秒才能到达，因为它们在全球传播时受到光速的限制。很明显，我们需要尽可能减少跨数据中心消息的数量，以便最终用户不会一直等待这些分布在全球的副本达成共识。
长期以来，人们一直认为做到这一点是不可能或不切实际的。但如今，已经存在多种技术可以减少往返次数，并将延迟控制在正常范围内。
纽约和巴黎之间的距离为5839公里。光从纽约传播到巴黎，然后再返回需要40毫秒。
——理论速度与现实世界速度
剩下的最重要的问题是：“我们需要执行多少次往返才能执行事务？”这个问题的答案在很大程度上取决于所使用的算法。
如何达成一致？
看来，为了就某件事达成共识，您至少需要四跳（或两轮通信）：一轮让每个副本知道您将要执行某些操作，然后第二轮在每个人都同意可以执行此操作后实际执行该操作。这被称为分布式两阶段提交 ，几乎所有分布式数据库都使用它。让我们来看一个类比。假设您必须与一群人就聚会的合适日期达成一致。它可能会像这样
首先，Polly询问每个人是否可以在周一参加聚会；她现在知道每个人确实可以来参加聚会。接下来，她需要让每个人知道聚会确实将在周一举行，并且人们确认他们会去。
这些与两阶段提交中的两个阶段非常相似。当然，数据库不会举办派对，因此这些阶段具有不同的功能。在分布式系统的情况下，这些阶段称为：
- 准备或请求提交：确保每个人都知道该事务。在此阶段，分布式数据库中的副本将查询存储在磁盘上的某种待办事项列表（事务日志）中，以确保服务器宕机时它们仍然知道该做什么。
- 提交：实际计算结果并存储它们
当然，一如既往，事情永远不会那么简单。此类算法有很多种。例如，有两阶段提交的改进版本，称为Paxos和Raft，甚至还有这些算法的许多变体（多Paxos/快速Paxos/…）。这些替代方案旨在解决可用性或性能问题。要了解可用性问题，只需想象一下Polly生病了或Amber的手机没电了。在第一种情况下，她将无法继续担任聚会协调员的工作，而在第二种情况下，Polly将暂时无法知道Amber是否同意聚会日期。Raft和Paxos通过仅要求大多数人回复和/或在领导者或协调者宕机时自动选择新的协调者来改进这一点。一个展示Raft工作原理的很好的动画可以在这里找到这里。
就什么达成一致？
我们可以得出结论，每个分布式数据库都需要2次往返来写入/读取数据吗？不，现实比这更复杂。一方面，有很多可能的优化，另一方面，我们可能需要就多件事达成一致。
- 就事务的时间达成一致
- 就是否可以执行读取操作达成一致
具有多个两阶段提交轮次的简单示例可能是Cassandra的轻量级事务。它们首先需要就读取达成共识协议，然后就写入达成共识。如果每条消息需要40毫秒才能传播，则表示整个事务需要320毫秒或更长时间——具体取决于所需的“锁”，我们将在后面解释。
这很容易理解，但由于Cassandra从未设计为强一致的，因此在实现方面存在一些问题。这是否意味着强一致性数据库更慢？一点也不！现代分布式数据库使用各种有趣的特性来实现更好的性能。
等待锁
我们不仅需要等待消息达成一致，而且几乎每个分布式数据库也都会使用“锁”。锁保证了即将被事务修改的数据不会被另一个事务同时修改。当数据被锁定后，其他事务就无法修改它，这意味着这些事务必须等待。因此，这种锁的持续时间对性能有很大的影响。同样，这种性能影响取决于数据库实现的算法和优化。一些数据库持有锁的时间比其他数据库长，而一些数据库根本不使用锁。
现在我们已经了解了足够的基础知识，让我们深入了解一下算法。
现代共识算法
我们现在知道，共识和锁是我们需要优化的主要瓶颈。所以让我们回到本文的主要问题：“新技术如何在可接受的范围内降低这些延迟？”让我们从这些现代算法中的第一个开始，它引发了数据库世界其他领域的一些有趣的想法。
2010 – Percolator
Percolator 是一个构建在 BigTable （谷歌构建的早期 NoSQL 数据库之一）之上的内部系统，谷歌使用它来提高搜索索引页面抓取速度。关于 Percolator 的第一篇 论文 于 2010 年发布，启发了第一个受其启发的分布式数据库：2013 年的 FoundationDB。然后 FoundationDB 被苹果收购，并于 2019 年最终发布了稳定版本，以及 FoundationDB 论文。
虽然 Percolator 允许 Google 显着加快页面抓取速度，但它最初并非作为通用数据库构建。它更像是为了成为一个快速且可扩展的增量处理引擎，以支持 Google 的搜索索引。由于搜索索引必须具有可扩展性，因此许多计算必须在许多机器上同时进行，这需要一个分布式数据库。正如我们在之前的文章中了解到的，针对存储数据的分布式系统进行编程可能非常复杂，并且传统上要求开发人员为解决不可预测的数据库行为而支付“一致性税”。为了避免支付如此高的“一致性税”，Google 在构建 Percolator 时采用了强一致性模型。
Percolator 的一致性模型离不开两个关键要素：版本控制和时间戳预言机。
要素 1：版本控制
正如我们在之前的文章中提到的，强一致性要求我们对事务达成全局顺序。版本控制是许多算法的关键要素之一，因为它可以用于故障恢复、帮助复制数据以及支持称为“快照隔离”的一致性模型。
当节点发生故障或断开连接时，版本控制有助于故障恢复。当节点重新上线时，由于版本的存在，它可以通过从能够保存的最后一个快照开始，然后根据另一个节点中的版本重放事务来轻松恢复其状态。它所要做的就是询问另一个节点：“嘿，自从我不在以来，发生了什么变化？”如果没有版本控制，它将不得不复制**所有**数据，这会给系统带来巨大压力。
故障恢复很棒，但最大的优势在于这样一个版本控制系统可以用来实现强一致性模型。如果版本控制系统为每个数据更改保留版本，我们实际上可以回到过去并针对我们数据的早期版本执行查询。
一些聪明人发现，这种历史查询功能可以用来提供一种称为“快照一致性”的一致性模型。快照一致性的想法是在查询开始时选择数据的某个版本，在查询的其余部分使用该版本的数据，然后在查询结束时写入一个新版本。
这里有一个潜在的陷阱：在执行此类查询期间，另一个查询可能会写入与第一个查询冲突的数据。例如，如果两个写查询都以同一个银行账户的快照（账户上有 1000 美元）开始，它们都可能花费这笔钱，因为它们看不到另一个查询的写入。为了防止这种情况发生，将执行一个额外的交易以查看在任一查询写入结果之前快照的值是否发生了变化。如果确实有冲突导致快照的值发生变化，则该事务将回滚并必须重新启动。
然而，Percolator 仍然需要解决一个问题。不同机器上的时钟很容易出现几百毫秒的偏差。如果查询的数据分布在多台机器上（例如我们最初的示例），则不能简单地要求两台机器在特定时间戳为您提供数据，因为它们对当前时间的理解略有不同。这只是一毫秒的问题，但当必须处理许多事务时，几毫秒就足以导致从正确的数据变为错误的数据。
时间同步为我们带来了 Percolator 的第二个要素。
要素 2：时间戳预言机
Percolator 解决时间同步问题的方法称为时间戳预言机。Percolator 没有让每个节点自行决定时间（这不够准确），而是使用一个中央系统，该系统公开了一个 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 事务协议的分布式云数据库，您可以拥有提供更强一致性模型的高性能分布式数据库。这意味着您可以构建提供低延迟的数据密集型应用程序，而无需担心数据错误、性能或服务供应。在这样的系统中，一致性是透明的，作为开发人员，您无需考虑它。下次选择数据库时，请选择默认情况下提供一致性的数据库。