2018-11-29

彻底厘清真实世界中的分布式系统

为了厘清分布式系统的设计，很重要的一点是明确立论的指导原则或者说是定理，其中最基础的一个可能是「两将军问题」，首先由 Akkoyunlu 等人在论文「网络通信设计中的一些约束和权衡」中提出，而在 1975 年版和 1978 年版的《数据库操作系统注记》（http://research.microsoft.com/en-us/um/people/gray/papers/DBOS.pdf）中， Jim Gray 对两将军问题的讨论，使得这个问题开始被人们所熟知。两将军问题表明：通过不可靠网络通信的两个进程不可能达成一致的决定。两将军问题非常接近于必须保证下列条件成立的二元共识问题（“攻击”或者“不攻击”）：

终止（Termination）：所有正确的进程都会决定某个取值（活性/liveness）；

合法性（Validity）：所有正确的进程，如果它决定的取值是 v ，那么这个 v 必然是由某个正确的进程提议的（非平凡/non-triviality）；

诚实性（Integrity）：所有正确的进程，最多只决定一个取值 v ，并且这个 v 是正确的取值（安全性/safety）；

一致性（Agreement）：所有正确的进程决定的取值是相同的（安全性/safety）。

很显然，任何有用的分布式算法都涉及活性和安全性属性。如果再考虑到网络是异步的、存在崩溃失效，问题就更复杂了：

异步：消息有可能被无限延迟，但是最终会被投递；

崩溃失效：进程有可能无限停机。

对上述情境的思考，引导我们去了解据称是最重要的分布式系统理论结果之一： FLP 不可能性，由 Fischer, Lynch 和 Patterson 在 1985 年论文「只要存在一个可能失效的进程就不可能达成共识」中首次提出。这个结果表明两将军问题是不可能解决的。在崩溃-失效模型中，如果进程完成工作且给出响应的耗时没有上限，我们就不可能区分下面两种情况：进程已经崩溃或者只是响应的耗时比较长。 FLP 结果还表明，在异步环境中，只要至少有一个进程有可能失效，就不存在能够确定解决共识问题的算法。也就是说，存在崩溃-失效的异步环境中，不可能存在完美的失效检测器。

译者注：把 failure 翻译为「失效」，意味着系统已经完全不能工作；把 fault 翻译为「故障」，意思是系统组件有问题，不能按照原先设计目的正常地工作。

讨论故障容忍（fault-tolerant）系统时，很重要的一点是把拜占庭故障（实质上就是任意的故障）考虑在内。此类故障包括但不限于：试图破坏系统的攻击。例如，一次安全攻击可能会生成或者伪造消息。拜占庭将军问题是两将军问题的泛化版，它描述的就是拜占庭故障。拜占庭故障容忍是指检测出或者屏蔽掉大量的拜占庭故障，保护系统免受威胁。

我们为什么如此重视共识？因为它是解决分布式系统设计中很多重要问题的关键。领导人选举（leader election）要实现共识，这样才能动态选出一个协调者，避免单点失效。分布式数据库要实现共识，这样才能保证不同节点的数据是一致的。消息队列要实现共识，这样才能支持消息投递事务或保证消息投递的顺序。分布式初始化（init）系统要实现共识，这样才能协调不同的进程。共识根本就是分布式程序设计的一个重要问题。

人们一次又一次的证明，无论是局域网还是广域网，它们经常是不可靠的，总体上也是异步的。这给分布式系统的设计带来真切而巨大的挑战。

这些不可能性结果不单单有学术意义，受此启发，大量分布式系统及设计开始涌现，这些系统在网络失效时提供了不同的保证。

L. Peter Deutsch 写的「有关分布式计算的几个谬论」是研究分布式系统理论的绝佳起点。文中列举了很多新手会误以为真的假设，其中第一条就是“网络是可靠的”。这些实际上不成立的假设包括：

网络是可靠的。

延迟为零。

带宽是无限的。

网络是安全的。

拓扑不会改变。

肯定有一个管理员。

传输的代价为零。

网络是同质的。

最近， CAP 定理被认真审视，人们争论这个定理的作用是否被夸大了。尽管如此， CAP 定理仍然是一个有用的工具，它能帮助我们建立分布式系统的基本权衡因素，认清厂商玩的花招。 Gilbert 和 Lynch 合写的「对 CAP 定理的看法」 明确了易出故障（fault-prone）系统固有的安全性（safety）与活性（liveness）之间的权衡，而 Fox 和 Brewer 合写的「完备度、完成概率和可扩展的容忍系统」从更实用角度描述了 CAP 定理的特征。我将一直毫不含糊地说， CAP 定理在分布式系统领域的地位非常重要，对分布式系统设计者和实践者来说，它具有重大的意义。

重燃希望

根据前面这些理论结果，很多分布式算法，包括实现线性化操作、序列化事务和领导人选举的算法，都没什么用。果真如此吗？当然不是。只要精心设计，分布式系统不用靠撞大运就能保持正确性。

首先需要指出， FLP 定理并没有说共识是无法达成的，而是说在有限时间内不一定能达成。其次， FLP 定理讨论的是不受控制的系统。在同步系统中，进程间消息投递的耗时有一个上限；在异步系统中则没有固定的限制。实际的系统一般表现为部分同步（partial synchrony）， Dwork 和 Lynch 在「部分同步系统的共识」一文中描述了部分同步的两个模型。在第一个模型中，上限是固定的但是预先不知道；在第二个模型中，上限是已知的，但只是从某个未知的时间点 T 开始才保证这个上限成立。Dwork 和 Lynch 针对这两种模型（搭配不同的故障模型），分别给出相应的能够容忍故障的共识协议。

Chandra 和 Toueg 在「可靠分布式系统中的不可靠失效检测器」介绍了不可靠失效检测器的概念。每一个进程都有一个本地、外部的失效检测器，这个检测器有可能出错。失效检测器监控系统中的部分进程，维护一个它怀疑已经崩溃进程的列表。检测失效的方法很简单：检测器定期向某个进程发送打招呼消息，如果超过某个耗时上限（2×消息来回的最大可能耗时），仍然没有收到该进程的响应，就把它列入怀疑名单。检测器有可能犯错，把正确的进程列入怀疑名单中。不过，如果检测器在后续时段又收到进程的响应，会自动纠错，把这个进程从怀疑名单去掉。在一个条件稍微放松的系统模型中，只要有失效检测器，即使它是不可靠的，也能解决共识问题。

共识保证了不同的进程就某个取值达成一致，而原子化广播（atomic broadcast）保证了每一个进程按照相同的顺序投递同一个消息。在上面那篇论文中，作者证明了共识和原子化广播彼此是等价的。因此， FLP 等不可能性结果同样适用于原子化广播。有些协调服务，如 Apache ZooKeeper ，就用到原子化广播。

在《可靠且安全的分布式程序设计导论》一书中，Cachin, Guerraoui 和 Rodrigues 指出很多实践系统可以被认为是部分同步的：

分布式系统通常表现为一个同步系统。更准确地说，我们所知的大部分系统，在大部分时间内，投递消息的耗时有一个上限。当然，在有的时段，系统又是异步的。例如，网络过载，或者某个进程因为内存不够而运行得缓慢。更典型的例子，进程收发消息的缓冲区有可能发生溢出，导致消息丢失，此时投递消息的耗时肯定超过通常的上限。消息重传有助于保证通信链接的可靠性，同时又引入不可预测的延迟。从这个意义上，实际的系统是部分同步的。

我们注意到，部分同步只是说最终保证消息投递的耗时有一个固定的限制，但最终是指什么时候，没有明确指出。类似地，我们称这样的系统是最终同步的。这里的最终同步，并不是说过了一段时间后系统就永远是同步的，也不是说系统开始是异步的，一段时间之后变成同步的。相反，最终同步是指系统有时是异步的，此时消息投递的耗时有可能是无限长，但是也存在系统同步的时段，足够一个算法做有用的工作或者运行完。关键是要记住，异步系统不提供任何定时保证。

最后，在「分布式共识所需的最少同步」一文中， Dolev, Dwork 和 Stockmeyer 描述了一种分布式共识协议叫做 t-复原（t-resilient），它能在最多 t 个进程失效时保证系统仍然正常地工作。本文给出几个关键的系统参数和同步条件，描述不同的参数和条件对算法的影响。可以证明，在某些模型中共识是可达的，在另外一些模型中则不行。

依靠法定多数（quorum），能够实现容忍故障的共识。直觉上，如果大多数进程能就每一个决定达成一致，即使出现故障，也至少有一个进程了解完整的历史。

在某些系统模型中，不可能达成确定性共识，许多有用的算法也因此无法实现。但是，大部分实际系统对应的模型能够规避这一点。不管怎样，这都显示出分布式系统固有的复杂性，以及解决特定问题所需的严格性。

从理论转向实践

上述理论有什么实践意义呢？对于初学者而言，这意味着分布式系统没有表面看起来那么简单。不认识到这一点，人们就会在文档中不确切地描述权衡因素，还有很多因为认识不足而导致数据丢失和违反安全性的例子。我们需要重新考虑分布式系统的设计方式，把焦点从系统属性及保证转向行业规则和应用的不变量。

我最钟意的一篇论文是 Saltzer, Reed 和 Clark 写的「系统设计中的端到端原则」。这篇论文很好读，它提出了一个非常有说服力的设计原则，帮助人们搞清楚究竟应该在分布式系统的哪一层实现所需的功能。端到端原则是说在系统的底层实现功能有可能是多余的，或者与付出的代价相比，这样做的用处不大。很多时候，外部保证比内部保证更有意义，也就是说应该在应用层提供保证，而不是依靠子系统、中间件或者系统的底层提供保证。

我们以“设计周全的文件传输”为例说明端到端原则。某个文件保存在计算机 A 的硬盘的文件系统中， A 通过通信网络与计算机 B 相连。现在要求把这个文件从计算机 A 无损地传输到计算机 B ，在此过程中有可能出现各种失效。换言之，这是一个文件传输应用程序，依赖底层存储和网络的抽象。开发者考虑到下列问题有可能发生：

文件刚写到计算机 A 的磁盘时，数据是正确的。如果现在读这个文件，有可能因为磁盘存储系统的硬件故障而读到错误的数据。

无论是在计算机 A 还是 B 上，文件系统、文件传输程序或者数据通信系统在缓冲和复制文件数据时都可能出错。

计算机 A 或 B 的处理器或者内存在缓冲和复制时有可能暂时出错。

通信系统有可能丢掉或者改变网络包数据、丢包或者多次投递同一个网络包。

任何一个主机都有可能在文件传输过程中（已经完成了未知比例的数据传输）崩溃。

这些本质上都属于拜占庭问题。如果我们逐个考虑这些威胁，很显然，即使我们在底层实现了问题处理程序，高层的应用仍然必须检查问题是否存在。例如，通信系统依靠校验和、重试和网络包排序提供可靠的数据传输。这只是消除了上述第 4 个威胁。为了克服其余的威胁，文件传输应用程序仍然需要端到端校验和重试机制。

在底层构建可靠性，代价太大。不光需要不少的投入，这么做也纯属多余。实际上，这虽然减少应用层重试的频率，却在底层了增加不必要的负担，最终降低系统的性能。应该只靠端到端校验和重试保证正确性，底层的实现对此没什么帮助。通信系统的可靠性和正确性并非那么很重要，在通信层保证复原性并不能减少应用层的负担。实际上，仅仅依靠底层不可能保证正确性，因为消除第 2 个威胁要求编写正确的程序，但是并非所有的程序都是由文件传输应用开发者自己编写的。

根本上，在底层实现功能会引发两个问题。首先，底层不清楚应用的需求和语义，这就意味着在底层实现的功能往往是不充分的，在应用层仍然需要实现类似的功能，这就造成逻辑的重复，如前面例子所示。其次，其他依赖底层的应用，即使不需要这些功能，也得承担相应的代价。

Saltzer, Reed 和 Clark 把端到端原则视为系统设计的“奥坎姆剃刀”原则，他们认为，端到端原则有助于指导设计系统的层次组织和确定功能在哪一层实现。

因为经常是先确定通信子系统之后，才知道要运行的上层应用，所以设计者必须顶住诱惑，不要试图为用户提供超出需要的功能。了解端到端原则，有助于增强抵抗力。

需要特别指出的是，端到端原则不是万能药。它是一个指导原则，帮助设计者从端到端角度思考解决方案，确认应用的需求，考虑失效的模式。最后，它提供了一种理念：把功能往系统上层移，靠近用到这项功能的应用程序。当然，凡事都有例外。有时为了性能优化，选择在底层实现功能。总之，端到端原则主张底层应当避免承担任何超出需要的责任。在 Google Bigtable 论文的“教训”部分有类似的论述：

我们学习到的另外一个教训是，在搞清楚新特性将被如何使用之前，不要添加这个新特性。例如，刚开始时，我们计划提供支持通用事务的 API 。由于我们没有马上使用这些 API ，就没有实现它们。现在，我们有很多运行在 Bigtable 上的实际应用，我们能够检验这些应用的真实需求，结果发现大部分应用只需要单行事务。其他需要分布式事务的使用情景，最重要的一个是用分布式事务维护二级索引，我们计划添加特别的机制满足这一需求。这种新机制的通用性比不上分布式事务，但是更有效率（尤其是执行横跨几百行的更新操作时），也更适合我们采用的跨数据中心乐观复制的模式。

接下来的讨论中，我们把端到端原则视为一个常识。

到底由谁来保证

一般来说，我们要靠健壮的算法、事务管理器和协调服务来维护一致性和应用的正确性。这会引发两个问题：这些服务经常是不可靠的；还经常成为严重的系统性能瓶颈。

分布式协调算法很难做到万无一失。即使是像两阶段提交这样有效的协议，也容易受崩溃和网络分区的影响而无法正常工作。更能容忍故障的协议，像 Paxos 和 Raft ，它们的扩展性不佳，只能运行在比较小的集群内，也不能跨越广域网。像 ZooKeeper 这样的共识系统决定了整个系统的可用性，一旦它宕机了，你的麻烦就大了。出于性能的考虑，法定多数通常设得较小，这种情况并不少见。

于是乎，协调系统作为一种基础设施，变得既复杂又脆弱。这太讽刺了，因为本来是想利用协调系统降低整个系统的脆弱性。另外一方面，消息中间件很大程度上是依靠协调为开发者提供下列有关消息投递的保证：有且只有一次、顺序、事务等等。

从传输协议到企业消息代理，对投递保证的依赖都属于分布式系统设计中的反模式。很难正确地处理投递的语义。尤其是对分布式消息投递而言，你想要的往往不是你需要的。重要的是审视其中涉及的权衡因素，了解这些因素如何影响系统的设计（和用户体验！），权衡这些因素以便做出更好的设计决定。

由于各种失效模式的存在，提供强保证变得很难。实际上，根据前面我们讨论的两将军问题和 FLP 不可能性结果，有些保证，像有且只有一次的投递，甚至是不可能提供的。如果你想提供有且只有一次投递、有序投递的保证，往往属于超出需要的过度设计和实现。系统变得难以部署和维护、脆弱和运行慢。提供保证的服务，如果能完美地运行，开发者的开发工作肯定变得更轻松。现实情况是这些服务很多时候不能完美地运行。你会在凌晨一点收到警报，不得不查找问题的源头： 从监控服务看，RabbitMQ 明明一切正常，为什么整个系统却接连出现问题？

如果部署在生产环境的系统依赖此类保证，那你迟早会遇到一次（往往不止一次）上述的麻烦。最终，所谓的保证就不存在了，因此导致的后果可大可小。这种设计系统的方式不光危险，也不可取，尤其是当你运维一个大规模系统，特别看重系统的吞吐或者需要提供关键的服务等级约定时。

分布式事务显然会影响性能。协调的代价是昂贵的，因为进程不能单独继续运行，这会限制系统的吞吐、可用性和扩展性。 Peter Bailis 有一个非常棒的演讲「沉默是金：避免协调的系统设计」，他详细讨论了协调的代价以及如何避免协调。他提到一个特别的例子，其中分布式事务会导致系统的吞吐下降 400 倍。

如果不需要协调，系统可以无限横向扩展，从而极大提高系统的吞吐和可用性。但是有时协调是不可避免的。在《数据库系统中的协调避免》一书中， Bailis 等人回答了一个关键问题：为了保证正确性，在哪种情况下协调是不可避免的？他们提出一个属性叫不变量交汇点（invariant confluence, I-confluence），它是安全、无协调、可用及收敛的执行的充分必要条件。 I-confluence 的本质是在应用层定义和保持不变性，因为我们在这里可以用应用的语义而不是底层数据库操作来定义正确性。

不知道应用程序的正确性定义（例如， I-confluence 用到的那些不变性），在读写模型中，能够保证的最佳正确性是序列化。

给定事务集，以及统一分散状态的合并函数，就可以判定 I-confluence 是否成立。如果成立，就意味着存在一种保证不变性的无协调执行策略。如果不成立，意味着这样的策略不存在，协调就是必需的。由此可见， I-confluence 能够帮我们识别出何时需要协调，何时不需要。由于是在应用层定义和保持不变性，就不会存在超出需要的设计。

回想一下，分布式计算的同步性（synchrony）只是对时间做的假设，所以同步（synchronization）从根本上是两个或两个以上进程随着时间推移进行的协调。我们知道，无需协调的系统能提供最优的性能和可用性，因为每个进程完全独立运行。然而，根据 I-confluence 理论，这样的分布式系统没什么用或者说是不可能的。 Christopher Meiklejohn 在 Strange Loop 大会做的演讲「分布式、最终一致的计算」中，用汽车打比方来解释协调。驾驶汽车需要摩擦力，但是只能有非常少量的摩擦点。太多的摩擦点会出问题或者降低效率。如果把物理时间看做摩擦力，完全消除它是不可能的，因为这是问题的本质属性。但是我们可以尽量减少它在系统中的使用。通常，可以选用逻辑时间取代物理时间，例如，使用 Lamport 时钟或者其他冲突消除技术。有关这一思路的经典介绍，是 Lamport 写的书《分布式系统的时间、时钟和事件顺序》。

系统在执行延迟敏感操作时通常会完全放弃协调。这是非常自然的权衡选择，只不过要在文档中清楚地指出这一点。不幸的是，现实往往并非如此，这很不应该。 I-confluence 提供了一个有用的协调避免框架，我们还能从中学到更多：重新审视我们现在设计分布式系统的方式，看起来这些方式与端到端原则有些背道而驰。

在底层实现功能，意味着一开始我们就要付出代价——序列化事务、线性化读写和协调。这好像违反了端到端原则。应用程序并不关心原子性、隔离级别或者线性化，它关心的是两个用户共享同一个 ID 或者两个订单预定了同一个房间或者银行账户有负结余，数据库是不知道这些的。有时，诸如此类的规则甚至不需要任何代价昂贵的协调。

如果把应用规则和约束编码成基础设施层理解的语言，这会引发几个问题。首先，必须把应用语义无缝地转换成底层操作。以消息传送为例，应用程序并不关心投递送达的保证，它关心的是这个消息要干什么。其次，我们不能使用很多通用的解决方案，有时甚至要专门处理特别的情况。这种处理的实际扩展性如何是未知的。第三，降低了性能，这本来是可以避免的（I-confluence 已经揭示了这一点）。最后，一切都依赖基础设施，希望它能按照设计运行——往往并非如此。

身为消息平台团队的一员，我经历过无数次像下面这样的对话：

开发者：“我需要快速消息传递。”

我：“可以偶尔丢失消息吗？”

开发者：“什么？当然不行！我们要求可靠的消息传递。”

我：“好，那我们加上投递确认。不过，如果你的应用程序在处理消息之前崩溃了，会出现什么情况？”

开发者：“我们在消息处理后会确认。”

我：“那如果处理完了但是还没确认的时候程序崩溃了，怎么办？”

开发者：“重试呗。”

我：“也就是说允许重复发送？”

开发者：“这个，还是应该有且只有一次发送。”

我：“你不是想快速发送吗？”

开发者：“是啊。对了，还要保持消息的顺序。”

我：“你要求的就是 TCP 。”

相反，如果重新评估系统间交互和系统 API 及语义，把其中一些特性从基础设施移到应用层，我们就能构建更健壮、更容错和更高性能的系统。就消息传递而言，真的需要基础设施层保证先入先出顺序吗？系统存在失效情况下要保证分布式消息的顺序，同时还要提供高可用性，这太难了，代价高。如果消息是可交换的，就没必要保证消息的顺序。同样，投递事务需要又慢又脆弱的协调，还无法提供应用层的保证。如果消息是幂等的，就不需要事务，重试就行了。如果需要应用层的保证，那就在应用层构建，基础设施可保证不了。

我特别喜欢 Gregor Hohpe 写的「咖啡店不用两阶段提交」。这篇文章揭示了，如果我们仿效真实世界解决分布式系统问题，解决方案会非常简单。我有信心设计更好的系统，有时我们只需换个角度思考问题。事物的运作方式蕴含着一定的道理，这可没用到计算机或者复杂的算法。

不要试图用脆弱、笨重的抽象来掩盖复杂性，相反，在设计决策时识别问题，端到端思考，直面问题。追寻分布式系统之道的道路漫长而艰难，现在就开始吧。

本文翻译：柳泉波