ACM通信
实践
站在巨人的分布式肩膀上
图片来源:Alicia Kubista / Andrij Borys Associates
如果你仔细观察，你会发现分布式计算的许多挑战与伟大的物理学家所做的工作相似。该死，那些家伙真聪明!
在这里，我将分析一些最重要的物理学突破，并将其与计算机世界中的现象进行一些异想天开的类比……只是为了好玩。
牛顿以为他知道时间
艾萨克·牛顿(16421727)是一位杰出的物理学家，他定义了经典力学、运动定律和万有引力的基础。他还建造了第一台折射望远镜，发展了色彩理论，等等。他是个坏家伙。
牛顿认为时间的概念在整个宇宙中是恒定不变的。此外，他假定重力与距离无关，是瞬时作用的。宇宙中的每一个物体在任何时候都在施加引力。
这非常类似于我们在单个计算机或紧密耦合的计算机集群中看到的情况，这些计算机在共享事务中执行一致的工作。事务有一个明确定义的本地时间概念。每个事务都将其工作视为清晰地遵循一组事务。时间在不受距离干扰的情况下前进。
当我学习计算机科学的时候(尼克松是总统)，我们只考虑一台计算机。除了把终端连接到一台计算机之外，几乎没有任何网络。有时，从另一台计算机送来的磁带，我们必须弄清楚如何理解其中的数据。我们从来没有考虑过计算机间的时间。过了几年，我们才意识到自己的视角太狭隘了。
爱因斯坦有很多手表
1905年，阿尔伯特·爱因斯坦(18791955)基于两个原理提出了狭义相对论。首先，物理定律，包括时间，对所有观察者来说似乎都是一样的。第二，光速是不变的。
这一理论的一个含义是不存在同时性的概念。同时性的概念是相对于观察者而言的，时间的行进也是相对于观察者而言的。每一个参照系都被相对于它们在空间中的速度的光速分开。
这个概念产生了一些有趣的结果。太阳可能在五分钟前就爆炸了，接下来的三分钟会很美好。当事情发生在很远的地方，需要时间去发现……可能要很长一段时间。
在计算机领域，你不可能知道“那边”发生了什么。与另一个系统交互总是需要时间。您可以启动一条消息，但您总是必须等待回答回来才能知道结果。延迟越来越多地成为系统的主要设计要点。
分布式系统中知识传播的时间范围是不可预测的。这甚至比以爱因斯坦为基础的物理宇宙还要糟糕。至少以我们的太阳和光速，我们知道我们可以看到太阳在8分钟前发生了什么。在分布式系统中，我们对我们的知识如何传播有一个统计上的理解，但我们根本无法确定地知道。另一个服务器，在它自己的时间域内，可能会被隔离很长一段时间。
此外，在任何分布式交互中，消息可能在有限的时间内交付，也可能不交付。高级应用程序永远不知道协议是否完成。图1显示了如何不保证最后的消息传递，发送方永远不知道接收方知道什么。在任何分布式协议中，最后一条消息的发送方无法知道它是否到达。那需要另一条消息。
另一个问题是服务器和消息生活在它们自己的时间空间中。跨多个服务器发送和接收的消息可能会有令人惊讶的重新排序。每个服务器和每个消息都存在于自己的时间内，它们可能是相对的，但可能会带来意外，因为它们不协调。有些显得比较慢，有些显得比较快。这是令人讨厌的。
在图2，由于工作流在服务器和消息中跨越不同的时间，时间是断开的，可能比预期的慢或快。在这种情况下，A发送的第二条信息可能是由第一条信息通过c传递而导致的，它可能会在你下班后到达。这些问题会让你的头感到疼痛，就像当你想到双胞胎时一样，一个以接近光速的速度旅行，时间似乎变慢了，而另一个留在家里老化。
你不能在有限的时间内达成分布式协议。迷失的消息。你可以重试，他们可能会通过。然而，在一段固定的时间内，他们有很小(也许非常小)的机会不会到达。对于任何固定的时间段，都有可能运行合作伙伴服务器sloooooow再也回不去了。
两阶段提交不能保证在有限时间内达成一致。同样,Paxos,7木筏,8而其他酷的协议协议不能保证在有限的时间内达成一致。这些协议是很有可能很快达成协议，但不能保证。4每个人都生活在自己相对的世界里，不知道那里发生了什么……至少现在还没有。
根据CAP定理1，5(即一致性、可用性、分区容错)，如果您容忍计算机和/或网络的故障，您可以拥有经典的数据库一致性或数据库可用性。为了避免应用程序挑战，大多数系统选择一致性而不是可用性。
两阶段提交是反可用性协议。
在我看来，爱因斯坦说得很有道理。我不知道你对他是什么感觉。
哈勃越来越远了
埃德温·哈勃(18891953)是一位天文学家，他发现一个物体离我们越远，它离我们越快。反过来，这意味着宇宙正在膨胀。基本上，所有东西都离其他东西越来越远。
在计算中，我们看到了不断增长的计算量、带宽和内存大小。看起来这种情况还会持续一段时间。延迟并没有减少太多，并且受到光速的限制。目前还没有明显的迹象表明，光速在短期内将不再是一个制约因素。由于等待某样东西被取走而失去的教学机会的数量正在不可避免地增加。
计算就像哈勃的宇宙…所有东西都离其他东西越来越远。
共享只读数据并不是最大的问题。有了足够的缓存，就可以把需要的东西拉到共享系统中。分享可写的东西是一场灾难。在从队列的缓存中取出最新副本的缓存线时，您经常会陷入停顿。在等待的过程中，会失去越来越多的教学机会。随着时间的推移，情况只会变得更糟!
共享内存很棒…只要你不去分享内存。
要么我们想办法解决那烦人的光速问题，要么我们就得在异步和并发方面下更大的功夫。
海森堡不确定
维尔纳·海森堡(19011976)定义了不确定原理，即你对一个粒子的位置知道得越多，你对它的运动就知道得越少。基本上，你不可能什么都知道。
在分布式系统中，您有一群服务器，其中每个服务器处于不同的健康、死亡或垃圾收集状态。大多数情况下，您可以与服务器聊天，并得到一个清晰而及时的结果。其他时候，你得不到及时的答复，很难知道你是应该放弃这个懒惰的人，还是耐心等待。此外，您不知道服务器是否收到了请求，是否完成了工作，是否只是没有响应。当请求进入单个系统时，您不知道请求何时会被延迟。2，6
在一些分布式系统中，为在线用户提供极其一致和快速的响应时间是至关重要的。要实现这一点，必须发出多个请求，并且完成请求的一个子集就被视为幸福。在分布式系统中，您可以知道在哪里工作完成了，或者你可以知道当工作完成了，但你不能两者都知道．
要知道当如果请求是在统计SLA(服务水平协议)范围内完成的，您需要接受您不知道的情况在哪里这项工作将会完成。请求的重试通常是获得及时答复的唯一选择。因此，请求最好是等幂的。
薛定谔的
欧文Schrödinger(18871961)是20世纪初的一位杰出物理学家th世纪。虽然他对场量子理论做出了许多实质性的贡献，但他最被人记住的是一个旨在展示量子物理学挑战的思想实验。
在量子物理学中，理论、数学和实验观察表明，几乎所有东西都保持在多个状态，直到它与外部世界相互作用或被外部世界观察到。这就是所谓的态叠加，当你仔细观察时会坍塌。
为了表明这似乎很愚蠢，Schrödinger提出这种量子级的不确定性可以映射到宏观级的不确定性。首先，把少量铀、一个盖革计数器、一小瓶氰化物和一只猫放进一个钢盒子里。在盖革计数器上安装一个锤子，如果有一个铀原子衰变了，就可以敲碎氰化物瓶。由于铀衰变的量子物理表明，在你观察到这种状态之前，它既衰变又不衰变，很明显，这只猫同时是死的和活的。事实证明，许多当代物理学家认为这并不愚蠢……猫会同时处于两种状态。去图!
新的分布式系统，如Dynamo3.将数据存储在不可预测的位置。这允许put的提示和一致的延迟，以及自管理和自平衡服务器。通常，客户机向三个服务器中的每个服务器发送一个PUT，当集群自动重新平衡时，目标服务器可能会到处移动数据。用作目的地的服务器集可能很不稳定。后续的GET可能需要尝试许多服务器来跟踪新值。如果客户端在PUT期间死亡，则可能没有服务器接收到新值，或者只有单个服务器接收到它。在共享消息之前，单个服务器可能会死亡，也可能不会。单个服务器可能会死亡，无法响应读取，然后突然复活丢失的PUT。
因此，后续的GET可能找到PUT，也可能找不到。它可能隐藏的地方的数量实际上是没有限制的。新值出现所花费的时间没有上限。如果它确实出现了，它将被重新复制以使其保持不变。
虽然还没有观察到，但PUT实际上并不存在……它可能存在，但你不能确定。只有在GET看到它之后，PUT才会真正存在．
此外，无法观察并不意味着PUT确实缺失。它可能潜伏在死机或无响应的机器中。如果您看到PUT并强制将其复制到多个服务器，那么它仍然以非常高的保真度存在。看不到它只能告诉你它很可能不存在。
结论
哇!有很多杰出的物理学家，他们中的许多人在这里没有提到。他们的许多工作向我们展示了世界运行的非常违反直觉的方式。年复一年，有新的认识，也有很多惊喜。
在分布式系统这一新兴学科中，明智的做法是意识到在我们所做的事情中存在着微妙、惊喜和奇怪的不确定性。理解、限制和管理这些系统中固有的权衡将是未来几年的一个巨大挑战。我认为这很有趣!
相关文章
在queue.acm.org
像谷仓那么大?
斯坦Kelly-Bootle
http://queue.acm.org/detail.cfm?id=1229919
公寓和云
帕特Helland
http://queue.acm.org/detail.cfm?id=2398392
可测试的系统管理
马克·伯吉斯
http://queue.acm.org/detail.cfm?id=1937179
参考文献
1.迈向健壮的分布式系统。在19年会议纪要thACM分布式计算原理年会(2000)。
2.迪安，J.，巴罗佐，洛杉矶2013年。尾巴呈比例。Commun。ACM 56， 2(2013年2月)，7480。
3.DeCandia, G.， Hastorun, D.， Jampani, M.， Kakulapati, G.， Lakshman, A.， Pilchin, A.， Sivasubramanian, S.， Vosshall, P.， Vogels, W. Dynamo:亚马逊的高可用键值商店。在21世纪会议纪要圣ACM操作系统原理研讨会(2007), 205220。
4.Fischer, M.， Lynch, N.， Paterson, M.:一个错误过程的分布式共识的不可能性。JACM 32， 2(1985年4月)。
5.Gilbert, S.， Lynch, N. Brewer的猜想和一致的，可用的，分区容忍的web服务的可行性。ACM SIGACT新闻332(2002)。
6.海森伯格(P. Heisenberg)走上了写作的道路。在七项会议的议事程序th两年一次的创新数据系统研究会议(2015)。
7.兼职议会。ACM反式。计算机系统16， 2(1998年5月)。
8.Ongaro, D.， Ousterhout, J.寻找一种可以理解的共识算法。在Usenix年度技术会议论文集(2014);https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro．
数字图书馆是由计算机协会出版的。版权所有©2016 ACM股份有限公司
评论
韦恩·洛布
我不认为这些事情是为了好玩。我认为它们就是我们的现实。我看到了分布式计算的两个基本挑战:1)我对你的状态的内部表示是正确的吗?2)我和你的交易成功了吗?最终，我们永远不可能完全了解这两种情况。我们只能防范和正确处理异步带来的超时和不确定性。基于纯逻辑的形式方法(TLA+， Rodin, SPIN, Alloy, Verum Dezyne，许多其他)帮助我们有条不紊地、彻底地应对这些挑战。任何其他类型的方法都是临时的，将会失败。谷歌“amazon tla”或“nasa火星代码acm”(都没有引号)引人注目的讨论。韦恩·洛布
帕特里克Helland
嘿,韦恩!
伟大的评论!我确实理解这些问题是我们的现实，我写这篇文章的目的是让这些问题更容易理解。用一种“有趣”的方式来组织讨论有时可以拓宽理解。我们系统的成功越来越依赖于思考与过去截然不同的分销方式。
尽管我没有讨论它们，但我相信正式方法在确保正确性方面有巨大的希望，尤其是当问题变得更大、更复杂的时候。
显示所有2评论