没有“now”-分布式系统中的同时性问题

没有“now”-分布式系统中的同时性问题

There is No Now

Problems with simultaneity in distributed systems

-Justin Sheehy

“Now.” 从我写这个单词到你读到它，时间已经过去了至少几个星期，这种延迟我们认为是理所当然的，甚至在我们读到任何文章的时候都不会想到这个问题。 “Now.” 如果我们在同一个房间内，我大声这么说，你可能会有更强的直观性。你可能会直觉的觉得，就像我在说这个词的同时你就听到了一样。这种直觉是错误的，如果你不相信你的直觉，而是思考声音的物理原理，你就会知道从我说话到你的听觉之间一定经过了一段时间。空气的传播，带着我的话，会花费时间从我的嘴传递到你的耳朵。 “Now.” 即使我举起一个写着哪个字的牌子，我们都看着它，我们对哪个形象的感觉也不会同时发生，因为携带着这个牌子信息的光传到我们每个不同的人需要不同的时间。 虽然计算机的某些特性是虚拟的，但是他们仍然碧玺在现实世界中运行，不能忽视现实世界的挑战。海军少将Grace Hopper （我们这一领域最重要的先驱之一，他的成就包括创造了第一个编译器）用给每个学生一根11.8英寸长的电线来说明这一点，则是电在1 ns内可以传输的最大距离。这种信息，时间和距离之间的关系的物理表征可以作为一种工具来解释为什么信号（就像我们上面的比喻符号）必须总是而且不可避免地要花费时间才能到达目的地。考虑到这些延迟，很难解释“now”在计算机系统中的确切含义。 不过，如果我们提前详细计划，理论上没有什么能组织我们对“now”达成共识。（相对论在这里不是问题，尽管它很容易让人分心。人类目前所有的计算系统都有一个足够严谨的参照系，使得人们对于时间的感知存在着非物质的相对论性差异。）NTP协议用于在互联网上同步系统之间的时钟，部分工作原理是计算信息在主机之间传输的时间。一旦知道了这个传输时间，主机就可以根据这个时间来调整时钟，以匹配更权威的消息来源。通过在网络中提供一些非常精确的源，基于连续测量原子辐射的时钟。我们能够使用NTP将计算机的时钟同步到一个很小的误差范围内。在GPS中每个卫星都包含多个原子钟，这样一个时钟失败不会使卫星不可用。GPS协议允许任何人使用，只需要他们能够收到足够多的卫星信号就能解出所有的变量。不仅可以确定接收装置自己的位置，而且可以非常精确的确定时间。 我们已经理解这些协议几十年了，因此，我们很容易相信我们已经克服了这类问题，我们们应该能够建立一个假设我们的时钟是同步的系统。原子钟，NTP和GPS卫星提供了信息传播所需的时间的知识和设备。因此我，任何地方的系统都应该能够就“now”达成一致，并共享对时间进程的共同、单一的看法。然后，网络和计算中的所有困难问题都将变得容易得多。如果你所关系的所有系统对时间的感知都是完全相同的，那么即使再一些涉及主机出现故障时，许多这些问题也可以解决，但是在构建实际的分布式系统中，这些问题任然存在，并且处理它们不仅是一个持续活跃的研究领域，而且也是一个主要的关注点。 你可能会看到用于理解时间的成熟机制，并相信研究人员和系统构建者正在做大量不必要的工作。既然我们制定如何同步，为什么还要试图解决时钟可能不同的问题呢？为什么不适用时钟源和协议的正确组合来让时钟一致，继续前进，客服这些问题？有一件事情让这种说法难以置信，也让这些问题不仅重要，而且必须直面:一切都会崩溃。 真正的问题不是信息需要时间从一个地方转移到另外一个地方的理论概念。真正的问题是在计算系统所有的物理世界中，组件经常会失败。在构建系统，尤其是在商用机器和网络上的分布式计算系统时，最常见的错误之一就是假定脱离了基本的物理现实。光速就是这样一种现实，但是另外一种更有害但是同样普遍的现实也是这样，我们无法制造出永远有不坏的完美机器，正是这些现实，异步性和部分失败的结合，使得构建分布式系统变得困难。如果我们不计划考虑单个组件的故障，我们可以保证组合系统的故障。 分布式系统理论中最重要的结果之一不是可能的结果，它显示了在可能发生故障的世界中构建系统的能力的局限性。这通常被称为FLP结果，以其作者Fischer, Lynch, 和 Paterson命名。它们的工作以分布式计算领域最具影响力的论文获得了2001年的Dijkstra奖。最终证明了一些计算问题在同步模型中是可能实现的，在同步模型中，主机拥有相同或者共享的时钟，这样的不可能结果非常重要，因为它们可以引导你在涉及自己的系统的时候避免走入死胡同。它们还可以提供一个snake-oil探测器。所以你有理由怀疑哪些声称产品做了你认为不可能的事情的人。 一个相关的结果是CAP定理，用于一致性、可用性和分区耐受性。现在的开放人员相对FLP更加熟悉它。首先由Eric Brewer非正式的提出，后来由Seth Gilbert 和 Nancy Lynch证明了它。从分布式理论系统角度来看，CAP定理没有FLP有趣，一个反例击败了CAP的正式版本，它假设了一个比FLP更弱，更具有对抗性的世界模型，并要求在该模型中实现更多。虽然一个问题并不是另一个问题的子问题，但是FLP是一个更强大、更有趣、或许也更令人惊讶的结果，一个已经熟悉的FLP的研究人员可能会觉得CAP的想法有点无聊。 然而，认为CAP的价值更容易被哪些不精通分布式系统文献的人所理解是合理的。这将是值得称赞的，但是过去几年中显示（通过对过去数十篇文章和博客分析，其中许多由严重误解了其基本思想），非常遗憾的是，CAP的理论并不是一种适应分布式的、在不完美世界中编程的容易方式。无论从CAP、FLP还是其他的角度来看，现实都是这样一个世界，这个世界中，你必须假设你用 作构建的模块的组件存在缺陷。（在任何理论上的不可能的结果，如CAP或者FLP，都与它的系统模型有着内在联系。这就是结果所依赖的世界理论模型。任何这样的结果都不是说某些目标，如共识，在一般情况下是不可能的，而是说再特定的模型中是不可能的。这对于从业者来说非常有用，他们可以通过直觉来判断那条路可能是死胡同，但是如果你只知道结果而不了解结果所适用的上下文，这也可能对结果产生误导。） 真正的问题是这些东西是错误的，这里提到的文献如FLP，都是关于处理组件可能会出现故障的系统的。如果这就是问题所在，那么为什么我们不使用用不坏的东西，或者是我们认为是精装的组件来构建更好的系统呢？ 在过去几年内，谷歌的 Spanner 系统通常被引用作为做出这种假设的理由。该系统使用前面提到的技术NTP、GPS和原子钟来协调组成Spanner主机的时钟，并最小化和测量（不是消除）这些时钟之间的差异的不确定性。Spanner和系统文档通常用于支持这样的说法，即拥有一个时间视图的分布式系统是可能的。 尽管人们呼吁将矛头指向google，并使用更加权威的论点，但是每个人都是错误的。事实上，任何引用Spanner系统作为同步被解决的证据的人，要么是再说谎，要么实际上没有读过这篇论文。反对这一观点最简单，最清楚的证据就是Spanner论文本身。Spanner的TrueTime组件每一提供一个简单同一的共享时间轴。相反，它非常清楚的提供了一个API，直接暴露了系统时钟之间感知和时间差异的不确定性。如果你问它当前的时间，他不会给你一个单一的值，但是一堆描述围绕“now”的一系列可能性的值–也就是说，TrueTime并没有解决这个基本问题。他需要勇敢和迷人的选择，直接面对它，明确不确定性，而不是假装“now”的一个绝对值再一个工作的分布式系统中是有意义的。 再Spanner的生产环境中，时钟延迟在任何时刻通常为1-7ms。这是google在包括GPS校正效果，原子钟，清除最严重延迟的时钟以及未来最小化偏移而做的最好的事情。X86类型的时钟的速度取决于各种不可预测的环境因素，如负载、热量和功率。即使是同一机架的顶部和底部之间的差异也会导致倾斜的差异。如果在google这样机器昂贵的环境中，我们能做的最好的事情就是生活在几毫秒的不确定中，那么我我们大多数人应该认为我们自己的时钟差得远不止这些。 另外一个经常在分布式系统中设计中为假装它很好的方法辩护的说法是，足够高质量的设备不会担心失败，或者至少很少会失败，以至于你不需要担心它。这种说法来自这些设备制造商是可以理解的，尽管不是正确的名单上通常这些设备的用户，比如分布式数据库软件的设计者，才会做出这样的说法。（GPS的设计者，Spanner 和其他的依赖系统则不会同意这种说法。GPS大约有30颗卫星，你只需要收到其中4颗卫星就可以让系统正常工作，每一颗卫星都有多个冗余的原子钟，因此当其中一个原子钟损坏时，它仍能够继续工作）。 这种说法最常见的变体之一就是网络是可靠的，在数据中心的本地网络环境中。当网络表现不佳时，许多系统都有未定义的，最有可能的灾难性行为。哪些想把这些系统卖给你的人解释说，这种失败是极其罕见的，一次来证明他们忽略现实的选择是合理的。这样做，他们给顾客带来了双重伤害。首先，即使这样的事件很少发生，难道你不希望理解它们发生的时候系统的行为，以便未这些事件对你的业务造成的影响做好准备吗？其次，更糟糕的是，这种说法简直就是一个谎言，如此赤裸裸的谎言，事实上，它是分布式计算八大谬误中的第一个。这样的失败的现实已经在之前的ACM队列的一篇文章中说明。证据是如此的清晰，以至于任何声称网络是可靠的来证明燃尽设计选择的人都不应该被信任的去构建任何计算机系统。诚然，某些系统和网络肯为那个没有以特定观察者能够注意到的方式发生故障。单是将系统的安全性建立在它永远不会发生故障的假设之上是愚蠢的。 这种物理问题的壁咚相反的方法是假设几乎没有什么是可以依赖的，并且只使用一个非常敌对的世界模型来设计。FLP所证明的异步模型并不是构建一个工作系统的最敌对的模型，但是它肯定是一个比大多数开发人员认为它们的系统允许时环境更加敌对的世界。它们的想法时，如果你建立模型的世界比你允许的世界更糟糕，那么你在模型中成功的事情在现实世界中应该是可能的。注意，分布式系统理论家有一些更难成功的模型，蔽日哪些包含拜占庭式的故障可能性模型，即系统的某些部分可能比崩溃或者延迟更糟糕的方式出现故障。对于真正的对抗性网络和系统的模型，例如，你可以看到密码协议理论家使用的符号模型和计算模型，在这种情况下，系统构建者确实认为你自己id网络会对你不利。 正是在这种背景下，假设这个世界比我们想象的实际情况要糟糕一些，才设计出了著名的共识和协调协议，如Paxos。对于这种分布式系统的基本构建块，知道它们可以提供最重要的保证式很有用的，即使在任意丢失消息、主机崩溃等于设计人员敌对的情况下。例如，对于Paxos和相关协议，最强调的属性是安全性，保证不同彩玉的主机永远不会做出冲突的决策。另外一个这样的工作领域是逻辑时间，表现为矢量时钟，版本矢量和其他对事件排序进行抽象的方法，这一观点普遍承认人们无法界定时钟是同步的，并未一个时钟完全不可靠的世界构建有序的概念。 当然，你应该始终努力使一切包括网络尽可能的可靠，把一个恒定的目标何一个可实现的完美状态混为一谈是愚蠢的。同样愚蠢的是一种纯粹的观点，认为只有最基础的和完全理解的理论模型才是构建系统的合理起点。许多有效的分布式系统是建立在有价值的元素上的，这些元素不能完美的映射到最常见的分布式计算模型中。典型的此类构建是TCP。这个几乎无处不在的协议提供了一些非常有用的属性。但是这些属性的精确集合不能精确地映射到开发理论结果如FLP所使用的任何典型的网络模型。这给系统构建者带来了一个困境，在设计时不假定TCP之类的东西是愚蠢的，但是在某些情况下，如果这一回使它们处于脆弱的位置。 ZAB协议是流行的Apahce ZooKeeper协调软件的最基本的部分，它是尝试走这条中间道路的一个有趣的例子。Zookeeper的作者了解Paxos等现有的共识协议。但是它们决定要在自己的协议上加上一些额外的特性，比如一次性处理多个请求的能力，而不是等待每个协议提交完成之后再开始下一个请求。 它们意识到，如果它们构建在TCp之上，它们就有了一个底层系统的优势，该系统提供了一些它们可以在协议中假定的有价值的属性。例如在单个来凝结的TCP中，产生消息A和消息B的发送方式可以安全的假定，如果接收方读取了B那么接收方之前已经读取了A，prefix属性非常有用，在异步模型中不存在，从该领域的研究和实现可用的具体技术来看，这是可用优势的一个具体的例子。 然而，当你视图实现时，你必须小心，不要让使用主义称为它自己草率工作的借口。在zookeeper中实现的zab协议，事实上的参考实现，从来都不是zab协议设计的准确实现。你可能称自己未实用主义者，并注意到大多数其他软件也不符合正式的规范。因此，你可能会说，这里没有什么不寻常的担心。你可能错了 ，原因有二。首先zookeeper等软件的作用与其他软件不同，它的存在的正是为了提高基本的安全性特性，从而形成一个基础，在此基础上，系统的其余不麻烦可以做出强有力的假设。其次，如果协议的安全性属性存在这样的问题，那么这些问题的出现可能回造成危害。 所有这些都不是针对zookeeper的，事实上，zookeeper是同类软件中质量最高的软件之一。有许多优秀的工程师在不断的改进它。根据最近的分析，他在压力下的表现远远好于任何竞争对手。我已经之处zookeeper知识作为一个例子，在理论和实际方面采取中间道路的必要性和陷阱。将理论映射到实践是极具挑战性的。 这条中间道路的另外一个例子就是混合逻辑时钟。他集成了逻辑时间的一般技术和来自物理时钟的时间戳。者允许用户基于对整个系统的物理时钟的视图（不完美，但是仍然有用）的一些有趣的技术。与Spanner非常相似的是，这并没有假装创建一个统一的时间轴，而是允许系统设计者在集群中感知和交流最佳的可用时间知识的基础上构建。 所有这些不同的协调系统，包括paxos，viewStamped Replication,Zab/Zookeeper和raft都提供了跨分布式系统定义事件顺序的方法，即使物理时间不能安全的用于此目的。但是，这些协议绝对可以用于这些目的：提高了跨系统的统一时间线，你可以将协调看作视为“now”提供逻辑的代理，然而，当以这种方式使用时，这些协议都有一个代价，其结果是它们都有一个基本共同点，持续通信。例如，如果你协调分布式系统中发生的所有事件的顺序，那么你最多能够提供不小于该系统内部的往返时间（两个连续的消息之间）的响应延迟。 根据你的协调系统的细节，吞吐量也可能有类似的界限，具有强烈性能要求的系统的设计者可能有希望做正确的事情，但是发现持续协调的成本令人望而却步。当主机或者网络预计经常出现故障时，尤其如此。因为许多协调系统只能提供最终活动。并且只有故障在最小的时候次啊能取得进展。然而，即使在一切都很完美的极少的情况下，持续协调的沟通成本也可能太高了。 放弃严格的协调以换取性能是计算的血多领域中的一个众所周知的折衷，包括CPu架构，多线程编程和DBMS设计，通常这已经百年城了一种游戏。即摘除究竟需要多少协调才能向用户提供不那么奇怪的行为。虽然设计师的一些本地并发系统已经开发出相当足够的协调管理技巧的集合，如RDBMS领域历史悠久有趣的技巧，通常结果是ACID比你想象中的要少得多。通过分布式系统这类技术的探索才刚刚开始。 这是一个令人兴奋的时刻，因为如何在分布式系统中设计做出这些权衡的课题现在才开始被认真研究，这个话题值得关注的一个地方是加州大学伯克利分校的BOOM团队，在哪里，多个研究人员正采取不同但相关的方法来理解如何进行有纪律的权衡。他们正在开辟新的领域，知道何时以及如何可以安全地决定不关心“now”，从而不支付协调的成本。这一的工作可能很快就会让我们清除的认识到，为了完成我们的工作，我们到底需要多少同步时间。如果分布式系统能够在不太协调的情况下构建，那么他们可能回更快，更有弹性。更易于扩展。 避免担心时间或协调的另外一个重要的研究领域涉及CRDTS，这些数据结构的更新永远不需要排序，因此可以安全地使用，而不需要试图解决时间问题。他们提供了一种安全，有时被称为最终一致性：系统中所有接收到相同更新集的主机，无论顺序如何，都具有相同的状态。我们早久知道，如果你做的所有功能都具有某些性质，比如交换律，结合律和幂等。这是可以实现的。CRDTS令人兴奋的地方在于，该领域的研究人员正在扩充我们的理解，在至俄国范围内，我们可以如何表达自己，以及提供丰富的数据类型的同时，我们可以多么节约成本的进行这样的工作。 说明这些主题的开发刚刚开始的一种方法是流行的分布式系统的存在，这些系统更喜欢使用特殊的方法来处理一致性，协调或者共识等问题，而不是使用最知名的方法。其中一个例子是任何使用最后写优先的策略解决写冲突的分布式数据库。既然我们以及知道最后本身是一个毫无意义的术语，就像“now”不是整个系统的一个简单值一样。这实际上是一个许多写入，不可预测的选择，将回丢失的策略，但是这不会卖出那么多数据库，不是吗？即使技术水平仍在迅速提高，任何人都应该能够做得更好。 另外一个例子就是，选择通过特别的协调代码来管理集群，而不是使用正在建立并经过充分分析的共识协议，这与大多数写错的数据库策略一样糟糕。如果你确实需要一些除了众所周知的一致性协议之外的东西来解决他们所解决的相同问题，那么你至少应该做zookeeper/zab实现人员所需要的事情，并清除地记录你的目标和假设。这并不能把你从灾难中拯救出来，但至少可以帮助考古学家，他们稍后会来检查你的遗骸。 对于分布式系统的构建者来说，这是一个非常激动人心的时刻，许多变化还在后头，然而，有些事实可能会继续存在，把now作为一个简单的值，在距离上具有意义，这种想法总是有问题的，我们将继续需要更多的研究和更多的实践经验来改进我们的工具，以适应现实，我们可以做得更好，我们现在就可以这么做。

致谢

我要感谢所有提供反馈的人，包括Peter Bailis, Christopher Meiklejohn, Steve Vinoski, Kyle Kingsbury, 和 Terry Coatta.

参考

1. Aphyr. 2013. Call me maybe: ZooKeeper; http://aphyr.com/posts/291-call-me-maybe-zookeeper.
2. Bailis, P. 2013. When is “ACID” ACID? Rarely; http://www.bailis.org/blog/when-is-acid-acid-rarely/.
3. Bailis, P., Kingsbury, K. 2014. The network is reliable. ACM Queue 12(7); http://queue.acm.org/detail.cfm?id=2655736.
4. BOOM; http://boom.cs.berkeley.edu/papers.html.
5. Brewer, E. A. 2000. Towards robust distributed systems; http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf.
6. Corbett, J. C., et al. 2012. Spanner: Google’s globally distributed database. Published in Proceedings of the 10th Symposium on Operating System Design and Implementation; http://research.google.com/archive/spanner.html; http://static.googleusercontent.com/media/research.google.com/en/us/archive/spanner-osdi2012.pdf.
7. Deutsch, P. The eight fallacies of distributed computing; https://blogs.oracle.com/jag/resource/Fallacies.html.
8. Fischer, M. J., Lynch, N. A., Paterson, M. S. 1985. Impossibility of distributed consensus with one faulty process. Journal of the ACM 32(2): 374-382; http://macs.citadel.edu/rudolphg/csci604/ImpossibilityofConsensus.pdf.
9. Gilbert, S., Lynch, N. 2002. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant Web services. ACM SIGACT News 33 (2): 51-59; http://webpages.cs.luc.edu/~pld/353/gilbert_lynch_brewer_proof.pdf.
10. Junqueira, F. P., Reed, B. C., Serafini, M. 2011. Zab: high-performance broadcast for primary backup systems; http://web.stanford.edu/class/cs347/reading/zab.pdf.
11. Kulkarni, S., Demirbas, M., Madeppa, D., Bharadwaj, A., Leone, M. 2014. Logical physical clocks and consistent snapshots in globally distributed databases; http://www.cse.buffalo.edu/tech-reports/2014-04.pdf.
12. Lamport, L. 1998. The part-time parliament. ACM Transactions on Computer Systems 16(2): 133-169; http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#lamport-paxos.
13. Medeiros, A. 2012. ZooKeeper’s atomic broadcast protocol: theory and practice; http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf.
14. NTP; http://www.ntp.org.
15. Rotem-Gal-Oz, A. Fallacies of distributed computing explained; http://www.rgoarchitects.com/Files/fallacies.pdf.
16. SyncFree; https://syncfree.lip6.fr/index.php/publications.

feedback@queue.acm.org

Justin Sheehy is the site leader for VMware’s Cambridge MA R&D center, and also plays a strategic role as architect for the company’s Storage & Availability business. His three most recent positions before joining VMware were as CTO for Basho, Principal Scientist at MITRE, and Senior Architect at Akamai. Much of his career has focused on resilient distributed systems, both how to build them and how to apply them to solve business problems related to scalability and availability. Justin can be found on Twitter as @justinsheehy.

© 2015 ACM 1542-7730/14/0200 $10.00