ACM通信

实践

没有现在

作者:Justin Sheehy
ACM通信，2015年5月，第58卷第5期，第36-41页
10.1145 / 2733108
评论

“现在。”

从我写这个词到你们读到它至少有几周的时间。我们认为这种延迟是理所当然的，甚至不会在书面媒体中考虑。

“现在。”

如果我们在同一个房间里，而不是我大声说话，你可能会有更强的即时性。你可能会直觉地觉得，你听到这个词的时间和我说这个词的时间是完全一样的。这种直觉可能是错误的。如果你不相信你的直觉，而是思考声音的物理原理，你就会知道，从我说话到你听到一定经过了一段时间。空气的运动，带着我的话，需要时间从我的嘴到你的耳朵。

“现在。”

即使我举起一个写着那个词的牌子，我们都看着它，我们对那个图像的感知也不会在同一时刻发生，因为传递标牌信息的光到达我们每个人需要不同的时间。

虽然计算机的某些东西是“虚拟的”，但它们仍然必须在物理世界中运行，不能忽视物理世界的挑战。海军少将格蕾丝·霍珀(Grace Hopper)(该领域最重要的先驱之一，她的成就包括创造了第一个编译器)曾给她的每个学生一根11.8英寸长的电线来说明这一点，这是电在一纳秒内可以传播的最大距离。这种对信息、时间和距离之间关系的物理表示可以用来解释为什么信号(比如我这里的隐喻符号)总是不可避免地需要时间才能到达目的地。考虑到这些延迟，很难解释“现在”在计算机系统中的确切含义。

不过，如果我们事先仔细计划，理论上没有什么能阻止我们对“现在”的共同想法达成一致。(相对论在这里不是问题，尽管它很容易分散注意力。人类目前所有的计算系统都共享一个足够接近的参照系，使得时间知觉上的相对论差异变得无关紧要。)网络时间协议(NTP)，¹⁴用于同步互联网系统之间的时钟，部分工作原理是计算消息在主机之间传递的时间。然后，一旦知道了旅行时间，主机就可以在调整时钟以匹配更权威的源时考虑到它。通过在该网络中提供一些非常精确的源(基于连续测量原子辐射的时钟)，我们能够使用NTP将计算机的时钟同步到一个很小的误差范围内。组成全球全球定位系统的每颗卫星都包含多个原子钟(因此，一个原子钟失灵并不会使一颗卫星变得毫无价值)，而全球定位系统协议允许任何拥有接收器的人，只要他们能看到足够多的卫星，就能解出所有变量，不仅能确定接收器自身的位置，还能非常精确地确定时间。

我们已经理解这些协议几十年了，所以很容易相信我们已经克服了这类问题，我们应该能够构建假设我们的时钟是同步的系统。原子钟、NTP和GPS卫星提供了计算信息传播所需时间的知识和设备。因此，任何地方的系统都应该能够就“现在”达成一致，并共享一个共同的、单一的时间进程观点。这样，网络和计算领域的所有难题都将变得容易得多。如果您所关心的所有系统都具有完全相同的时间感知，那么即使在涉及的一些主机出现故障时，许多这些问题也会变得容易解决。然而，这些问题仍然存在，处理它们不仅是一个持续活跃的研究领域，而且是构建实际分布式系统时的一个主要关注点。

您可能会看到用于理解时间的成熟机制，并认为研究人员和系统构建人员正在做大量不必要的工作。当我们知道如何同步时，为什么要假设时钟可能不同来解决问题呢?为什么不直接使用时间源和协议的正确组合来使时钟一致，然后继续解决这些问题呢?有一件事使这种说法不可信，使这些问题不仅重要，而且必须直面:一切都会崩溃。

真正的问题不是理论上的信息需要时间从一个地方转移到另一个地方。真正的问题是，在计算系统所在的物理世界中，组件经常会发生故障。在商用机器和网络上构建系统——尤其是但不仅仅是分布式计算系统——最常见的错误之一是假设逃避基本的物理现实。

光速就是这样一个现实，但另一个更有害、同样普遍的现实也是如此:我们不可能制造出永不坏的完美机器。正是这些异步和局部故障的现实结合在一起，使得构建分布式系统成为一个困难的追求。如果我们不计划和解释单个组件的故障，我们几乎保证了组合系统的故障。

分布式系统理论中最重要的结果之一是一个不可能的结果，它显示了在一个事物可能失败的世界中构建能够工作的系统的能力的限制之一。这通常被称为FLP结果，以其作者费舍尔、林奇和帕特森的名字命名。⁸他们的工作获得了2001年分布式计算领域最具影响力的Dijkstra奖，最终表明，在主机拥有相同或共享时钟的“同步”模型中可以实现的一些计算问题，在较弱的异步系统模型中是不可能实现的。这样的不可能结果非常重要，因为它们可以引导你在设计自己的系统时避免陷入死胡同。他们还可以提供一个“蛇油探测器”，这样你就有理由怀疑那些声称某款产品做了你知道不可能做的事情的人。

一个相关的结果是CAP定理(关于一致性、可用性和分区容限)，它比今天的开发人员更了解FLP。这是埃里克·布鲁尔首次非正式提出的⁵后来，赛斯·吉尔伯特和南希·林奇证实了它的正式版本。⁹从分布式系统理论的角度来看，CAP定理没有FLP那么有趣:一个反例“击败”CAP的正式版本假设了一个比FLP更弱、更对抗性的世界模型，并且要求在该模型中实现更多的目标。虽然其中一个不是另一个的子问题，但FLP是一个更强大、更有趣、甚至可能更令人惊讶的结果。熟悉FLP的研究人员可能会觉得CAP的想法有点无聊。

尽管如此，我们还是有理由认为CAP存在的价值在于更容易接近，更容易被那些不熟悉分布式系统的人所理解。这将是值得称赞和值得称道的，但过去几年已经表明(通过数十篇文章和博客文章，其中许多严重误解了基本思想)，遗憾的是，对于今天的开发人员来说，在分布式和不完美的世界中编程的现实并不是一种简单的方法。无论从CAP、FLP还是其他任何角度来看，现实都是这样的:在这个世界中，你必须从作为构建块的组件中假设不完美。(任何理论上的“不可能结果”，如CAP或FLP，都与它的系统模型天生相关。这就是这个结果所依赖的世界理论模型。任何这样的结果并不是说某些目标，例如共识，在一般情况下是不可能的，而是说在特定的模型中是不可能的。这对于从业者建立关于哪条路径可能是死胡同的直觉是非常有用的，但如果您只了解结果而不了解结果所适用的上下文，它也可能会产生误导。)

真正的问题是东西会坏。这里提到的文献，例如FLP，都是关于处理组件可能会出现故障的系统的。如果这就是问题所在，那么为什么我们不使用那些不会损坏的东西，然后用我们可以假设是健壮的组件来构建更好的系统呢?

在过去的几年里，经常引用谷歌中的Spanner系统作为做出这类假设的理由。⁶该系统完全使用前面提到的技术(NTP、GPS和原子钟)来协助协调组成Spanner的主机的时钟，并最小化和测量(但不是消除)关于这些时钟之间差异的不确定性。Spanner论文及其所记录的系统经常被用来支持这样的主张:有可能拥有一个具有单一时间视图的分布式系统。

尽管指向谷歌并使用权威的这种论点很有吸引力，但所有做出这种主张的人都是错误的。事实上，任何引用Spanner作为同步被“解决”的证据的人要么是在撒谎，要么就是没有真正读过论文。反对这种说法的最简单、最明确的证据就是Spanner论文本身。Spanner的TrueTime组件不提供简单统一的共享时间线。相反，它非常清楚地提供了一个API，直接暴露了系统时钟之间感知时间差异的不确定性。如果你问它当前时间，它不会给你一个单独的值，而是两个值，描述了“现在”周围的一系列可能性，也就是说，TrueTime做了与解决这个基本问题相反的事情。它需要勇敢和迷人的选择，直接面对它，明确不确定性，而不是假装“现在”的单个绝对值在整个工作分布式系统中是有意义的。

在Spanner的生产环境中，任何时刻的时钟漂移通常在1到7毫秒之间。这是谷歌在考虑了GPS、原子钟、最坏漂移时钟的去除等因素后所能做到的最好结果。典型的x86时钟根据各种不可预测的环境因素(如负载、热和功率)来改变其速度。即使是同一架的顶部和底部之间的差异也会导致倾斜的差异。如果在像谷歌这样非常昂贵的环境中所能做的最好的事情是在几毫秒的不确定性中生活，那么我们大多数人应该假设我们自己的时钟误差比这要大得多。

在为分布式系统设计中“假装一切正常”的方法辩护时，经常提出的另一个主张是，足够高质量的设备不会发生故障，或者至少故障非常罕见，以至于您不需要担心它。这种说法是可以理解的，尽管是不正确的，但通常是这种设备的用户，如分布式数据库软件的设计者，会听到这样的说法。(Spanner和其他人所依赖的GPS的设计者当然不认同这种说法。全球定位系统大约有30颗卫星，你只需要看到其中的4颗，系统就能正常工作。每颗卫星都有多个多余的原子钟，所以当其中一个原子钟坏掉时，它可以继续工作。)

---

在构建分布式系统时最常见的错误之一是假设我们可以逃避基本的物理现实。

---

这种说法最常见的变体之一是，在本地数据中心网络的上下文中，“网络是可靠的”。当网络表现不佳时，许多系统都有未定义的和最有可能的灾难性行为。那些想把这些系统卖给你的人解释说这种失败是极其罕见的，以此为他们无视现实的选择辩护。通过这样做，他们给客户带来了双重的伤害。首先，即使这样的事件很少发生，您难道不想了解当它们发生时系统的行为方式，以便为这些事件对业务的影响做好准备吗?第二，更糟糕的是，这种说法完全是一个谎言——一个赤裸裸的谎言，事实上，它是分布式计算的八个经典谬误中的第一个。^7，15这种失败的现实在以前的ACM中有很好的记录队列文章中,^3.证据是如此清晰可见，任何用“网络是可靠的”来为软件设计选择辩护的人都不应该被信任去构建任何计算系统。虽然某些系统和网络可能不会以特定观察者所能注意到的方式发生故障，但把系统的安全建立在它永远不会发生故障的假设上是愚蠢的。

与此相反的避开物理问题的方法是假设几乎没有任何东西可以指望，并且只使用一个非常敌对的世界的正式模型进行设计。FLP所使用的“异步”模型并不是构建工作系统的最具竞争性的模型，但它确实是一个比大多数开发人员所认为的更具有敌意的世界。这种想法是这样的:如果您建模的世界比您运行的世界更糟糕，那么您在模型中能够成功的事情应该在实际实现世界中是可能的。(注意，分布式系统理论家有一些更难成功的模型，比如那些包含“拜占庭式”失败可能性的模型，在这种模型中，系统的某些部分可能以比崩溃或延迟更糟糕的方式失败。对于一个真正的对抗网络/系统模型，您可以看到，例如，密码协议理论家使用的符号或计算模型。在那个世界里，系统构建者确实认为你自己的网络是为了对付你。)

正是在这样的背景下，假设这个世界比我们想象的要糟糕一点，最著名的共识和协调协议，比如Paxos，¹²设计。对于分布式系统的这些基本构建块，知道它们可以提供最重要的保证是很有用的，即使在一个任意丢失消息、主机崩溃等不利于设计人员的环境中也是如此。(例如，对于Paxos和相关协议，最强调的属性是“安全性”，即保证不同参与的主机永远不会做出冲突的决定。)另一个这样的工作领域是逻辑时间，表现为向量时钟、版本向量和其他抽象事件顺序的方法。这个想法通常承认无法假设同步时钟，并为一个时钟完全不可靠的世界建立了排序的概念。

当然，您应该始终努力使一切(包括网络)尽可能可靠。将固定的目标与可实现的完美最终状态混淆是愚蠢的。同样愚蠢的是一种纯粹主义的观点，认为只有最充分的基础和完全理解的理论模型才是构建系统的明智起点。许多最有效的分布式系统都是建立在有价值的元素之上的，而这些元素并不能完美地映射到最常见的分布式计算模型。这种构建块的一个例子是TCP。这个几乎无处不在的协议提供了一些非常有用的属性，这些属性的确切集合并不完全映射到开发理论结果(如FLP)所使用的任何典型网络模型。这为系统构建者创造了一个困境:在设计时不假设像TCP这样的东西的现实是愚蠢的，但在某些情况下，如果他们试图理解分布式系统理论如何准确地应用于他们的工作，这将使他们处于一个脆弱的位置。

Zab协议是流行的Apache ZooKeeper协调软件中最基本的部分，它是尝试走这条中间道路的一个迷人的例子。¹⁰ZooKeeper的作者了解现有的共识协议，如Paxos，但他们决定自己的协议需要一些额外的功能，比如一次处理多个请求的能力，而不是等待每个提议完成后才开始下一个。他们意识到，如果建立在TCP之上，他们就可以利用底层系统的优势，该系统提供了一些他们可以在协议中假定的有价值的属性。例如，在一个连接的TCP套接字中，发送方产生消息a和消息B，可以有把握地假定，如果接收方读取了B，则接收方之前已经读取了a。“prefix”属性非常有用，而这在异步模型中是不存在的。这是一个具体的例子，通过观察该领域的研究和实际可用的具体技术，而不是忽略其中任何一个，可以获得的优势。

然而，当你试图变得务实时，你必须小心，不要让这种实用主义变成一种奇怪的纯粹，成为马虎工作的借口。Zab协议在ZooKeeper内部实现，事实上的参考实现，从来都不是Zab协议设计的准确实现。¹³您可能称自己为“实用主义者”，并注意到大多数其他软件也不符合正式的规范;因此，你可能会说没有什么不寻常的事情值得担心。你可能错了，原因有二。首先，ZooKeeper和类似软件所使用的作用不像其他软件;它的存在恰恰是为了提供基本的安全特性，从而形成一个系统的其余部分可以在此基础上做出强有力的假设。其次，如果像这样的协议的安全属性存在问题，这些问题的出现(虽然可能非常危险)可能是微妙的，很容易被忽略的，如果没有强烈的信念，实现反映了所分析的协议，那么用户信任一个系统是不合理的。如果普通用户无法评估系统的正确性，那么系统的“足够好的正确性”是由它的流行程度来证明的这种说法就是无稽之谈。

所有这些并不是要批评ZooKeeper。事实上，它是同类中质量最高的开源软件之一，有许多优秀的工程师在不断地改进它。根据最近的分析，它在胁迫下的表现要比它的竞争对手好得多。¹我以ZooKeeper为例，只是为了说明在理论和实用性方面采取中间路线的必要性和缺陷。将理论与实践相结合是极具挑战性的。

这条中间道路的另一个例子是混合逻辑时钟¹¹它将逻辑时间的一般技术与物理时钟的时间戳集成在一起。这允许用户基于整个系统的物理时钟视图(虽然不完善，但仍然有用)应用一些有趣的技术。与Spanner非常类似，它并不假装创建一个统一的时间轴，而是允许系统设计人员基于跨集群感知和通信的最佳可用时间知识进行构建。

所有这些不同的协调系统，包括Paxos、视图戳复制(View-stamped Replication)、Zab/Zookeeper和raft都提供了在分布式系统中定义事件顺序的方法，尽管物理时间无法安全用于此目的。但是，这些协议绝对可以用于这个目的:提供跨系统的统一时间轴。您可以将协调看作是为“现在”提供一个逻辑替代。然而，当以这种方式使用时，这些协议会有成本，这是由于它们基本上都有一个共同点:不断的通信。例如，如果您协调分布式系统中发生的所有事情的排序，那么您最多能够提供不少于该系统内的往返时间(两次连续消息传递)的响应延迟。

根据协调系统的具体情况，吞吐量也可能有类似的限制。具有积极性能要求的系统的设计师可能希望正确地做事情，但发现持续协调的成本令人望而却步。当预期主机或网络经常发生故障时，这种情况尤其严重，因为许多协调系统只提供“最终的活性”，只能在出现最小故障时取得进展。然而，即使在那些所有工作都很完美的罕见时刻，持续协调的沟通成本可能也太大了。

在许多计算领域，放弃严格的协调以换取性能是众所周知的权衡，包括CPU体系结构、多线程编程和DBMS设计。这往往变成了一种游戏，即找出为用户提供不令人惊讶的行为所需的协调有多少。虽然一些并发但本地系统的设计人员已经开发了相当多的技巧来管理刚刚足够的协调(例如，RDBMS领域有很长一段有趣的性能hack历史，通常导致的ACID(即原子性、一致性、隔离性、持久性)远远低于您的猜测²)，对于通用分布式系统的这种技术的探索才刚刚开始。

这是一个令人兴奋的时刻，因为如何在分布式系统设计中进行这些权衡的主题现在才开始被认真地研究。这个话题值得关注的地方之一是加州大学伯克利分校的伯克利数量级(BOOM)团队，该团队的多个研究人员正在采取不同但相关的方法来理解如何进行有纪律的权衡。⁴他们在了解何时以及如何可以安全地决定不关心“现在”，从而无需支付协调成本方面开辟了新领域。这样的工作可能很快就会让我们更好地理解，为了完成工作，我们真正需要的同步时间到底有多少。如果分布式系统能够以更少的协调来构建，同时还能提供所需的所有安全属性，那么它们可能会更快、更有弹性、更能扩展。

避免担心时间或协调需求的另一个重要研究领域涉及无冲突复制数据类型(crdt)。这些数据结构的更新从来不需要排序，因此可以安全地使用，而不必试图解决时间问题。它们提供了一种安全，有时被称为强最终一致性:系统中接收到同一组更新的所有主机，无论顺序如何，都将具有相同的状态。人们早就知道，如果你所做的所有功都具有特定的性质，例如交换性、结合性和幂等性，那么这是可以实现的。让CRDTs激动人心的是该领域的研究人员¹⁶在为开发人员提供一组现成的丰富数据类型的同时，正在扩展我们对在这种限制下我们的表达能力的理解，以及我们做这些工作的成本有多低。

说明这些主题的发展才刚刚开始的一种方法是，流行的分布式系统的存在更喜欢临时的hack，而不是处理一致性、协调或共识等问题的最著名的选择。其中一个例子是任何具有“最后写入胜出”策略的分布式数据库，该策略用于解决写入冲突。因为我们已经知道，“最后”本身是一个没有意义的术语，同样的原因，“现在”不是一个横跨整个系统的简单值，这实际上是一个“许多写入，选择不可预测，将丢失”的策略——但这不会卖出那么多数据库，不是吗?即使技术水平仍在迅速提高，任何人都应该能够做得比这更好。

另一个例子，就像“大多数写丢失”的数据库策略一样糟糕，是选择通过特别的协调代码来解决集群管理，而不是使用正式建立和充分分析的共识协议。如果你真的需要其他的协议来解决他们解决的问题(提示:你不需要)，那么至少你应该像ZooKeeper/Zab实实者那样做，并清楚地记录你的目标和假设。这并不能把你从灾难中拯救出来，但至少可以帮助后来来检查你遗骸的考古学家。

对于分布式系统的构建者来说，这是一个非常令人兴奋的时代。许多变化还在后头。然而，有些事实很可能会保留下来。把“现在”作为一个简单的值，有跨越距离的意义，这种想法总是有问题的。我们将继续需要更多的研究和更多的实践经验来改进我们的工具，以适应这一现实。我们可以做得更好。我们现在就可以做。

回到顶部

致谢

感谢那些提供反馈的人，包括Peter Bailis, Christopher Meiklejohn, Steve Vinoski, Kyle Kingsbury和Terry Coatta。

相关文章
在queue.acm.org

如果你有太多的数据，那么“足够好”就是足够好了
帕特Helland
http://queue.acm.org/detail.cfm?id=1988603

这是无法回避的:你正在构建一个分布式系统
马克Cavage
http://queue.acm.org/detail.cfm?id=2482856

网络可靠
彼得·贝利斯和凯尔·金斯伯里
http://queue.acm.org/detail.cfm?id=2655736

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2015 ACM, Inc.

---

没有找到条目