重新审视分布式系统：永远不会有完美的一致性方案……

​如今使用的几乎所有软件都是分布式系统的一部分，手机上的应用程序与托管在云中的服务一起工作，托管服务本身就是大规模的分布式系统，通常运行在遍布全球的机器上，大数据系统和大规模数据库分布在许多机器上，大多数科学计算和机器学习系统在多个处理器上并行工作，即使是传统的桌面操作系统以及诸如电子表格和文字处理器之类的应用程序也在与分布式后端服务紧密集成。分布式系统中，多台不可靠的机器并行运行，通过具有任意延迟的网络链路彼此发送消息。怎么能确信这些系统在混乱的情况下能够做到我们想要的呢？

构建正确的分布式系统并不新鲜，一个传统的解决办法是通过保证内存一致性来降低这种复杂性，即确保以受控的方式访问内存(堆变量、数据库等)。然而，用于实施这些机制的分布式协议却通常阻碍了分布式系统的高性能、可伸缩性和可用性。

一、分布式协议的相关问题

通过分布式协议，自治的且松耦合的机器能够共同决定如何控制基本行为，包括对共享内存的访问顺序。这些协议在分布式计算中被广泛引用，一些著名的技术包括paxos和两阶段提交(2PC)协议等等。

​1、高昂的协调成本

不幸的是，分布式协议的成本可能使它们难以最终落地实施。分布式系统高伸缩性的第一个原则可能就是将一致性机制降到最低，并移出关键路径，或者将其隐藏在系统很少访问的角落，然后让应用程序开发人员难以获得使用它们的许可。

实际上，问题不在于分布式协议难以实施，而是因为分布式协议可以减缓或停止分布式服务中的计算。这些协议的延迟很高，大约为10ms-100ms。依赖于这些协议的大规模系统并不意味着要在应用程序的快速路径中使用。另外，分布式协议的延迟问题也会转化为微观层面的问题，多服务器的键值存储可能在花费90% 的时间在等待协调。

2、程序一致性

传统的一致性研究主要集中在线性度和冲突序列化上，这些属性通过限制冲突的内存访问顺序来保证内存的一致性。这掩盖了一个根本问题，即是否需要协调来保持程序的一致性。从整体上解决这个问题，是否从程序的语义上支持呢？

在现实中，十字路口的红绿灯相对于分布式协议，但如果有了立交桥或者隧道就相当于无需分布式协议就实现了目标。其核心是，通过巧妙地控制进入地图上道路重叠的关键区域的顺序，并不能找到更好的解决方案。解决方案是设计道路以避免对协调的需要。然而，并非所有的问题都有这样的解决方案。对于任何给定的计算问题，如何知道它是否需要分布式协议以保持程序的一致性呢？

3、死锁检测

在传统的数据库系统中，死锁检测器通过分析一个有向图来识别这样的“等待”周期，在有向图中，节点表示事务，而边表示一个事务在锁队列上等待另一个事务。死锁是一个稳定的属性是：等待周期中的事务无法取得进展，因此所有的边都将无限期地持续下去。

在分布式数据库的有向图中，等待图的“本地”视图只包含全局等待图中边的一个子集。在这种情况下，本地死锁检测器如何协同工作来识别全局死锁呢？为了识别这种分布式死锁，每台计算机与其他计算机交换其边的副本，以积累有关全局有向图的更多信息。任何时候，一台机器在接收到的信息中观察到一个循环，它就可以在该循环上的事务中声明一个死锁。

在这种分布式计算中，可能会担心由于延迟或重新排序的消息而导致的暂时性错误。本地检测器是否必须与其他机器协调以确保观测到是死锁呢？额外的事实只能导致检测额外的周期: 每台机器的输出随着输入单调增长。最后，如果所有的边最终在所有机器之间共享，那么机器就会同意基于完整图形的结果。

4、垃圾收集

分布式系统中的垃圾收集器必须在分布式内存引用图中标识不可到达的对象。垃圾收集的工作方式是识别与系统运行时的“根”断开连接的组件。一旦图中组件与根的连接被删除，该组件中的对象将不会被重新引用。

在分布式系统中，对对象的引用可以跨越机器，参考图的局部视图只包含全局图中边的一个子集，多个本地垃圾收集器如何协同工作来识别真正不可访问的对象呢？机器可能有一个本地对象，但不知道该对象是否连接到根，同样，每台机器与其他机器交换图中边的副本，以积累关于图的更多信息。

本地收集器能够自主地判断并回收垃圾吗？在这里确实需要分布式协议来协调的！机器必须在声明一个对象不可访问之前，确保它已经听到了所有需要听到的内容。要知道它已经听到了所有的声音，唯一的方法是与所有其他机器协商，以确定这一事实。协商的一个标志是即使在没有数据依赖关系的情况下也需要进行通信。

二、一致性问题的核心抽象

如果存在一个分布式系统 ，程序不需要协商就可以计算出一致的输出，那么这个计算问题就是无协调的，无需使用分布式协议来实现一致性。那么，无需协调的边界是什么呢？

分布式协议的使用和内在需求之间是有区别的，前者是实现选择的结果，后者是计算问题的属性。因此，希望关注程序一致性： 尽管可能出现消息和计算之间的竞争条件，但实现是否产生期望的结果呢 ？

那么，一致性问题的核心可否是程序的逻辑单调性呢？简单的说，当且仅当一个问题具有逻辑单调性，才具有一致的、无协调的分布式实现。相比之下，非单调性问题是在所有的信息已经到达之前，不能继续运行，这时必须通过分布式协议实现一致性。或者说，具有逻辑单调性的问题，其输出只取决于输入的内容，而不取决于输入到达的顺序。

1、程序的一致性

分布式系统给程序带来了显著的非确定性，包括不同步的并行性、不可靠的组件和具有不可预知延迟的网络。因此，一个分布式程序可以在给定的输入上展示大量可能的行为。

在非确定性消息传递的场景中，如果单台机器上的一个操作对任何非确定性排序和一组输入请求产生相同的输出响应集，则该操作是具有程序一致性。程序一致性可以应用于单个操作、数据流中的组件，甚至是整个分布式程序。

与传统的内存一致性属性(如可线性化)不同，程序一致性对近因概念(例如，读并不保证返回最新发出的写请求的结果)或操作顺序(例如，写并不保证在所有副本上以相同的顺序应用)没有要求或承诺。如果应用具有程序一致性，则在内存或存储级别上的任何此类异常都不会影响应用程序的结果。

对于分布式系统来说，程序一致性是一个强大而宽松的正确性标准。它排除了由于竞争和不确定性而导致的应用级不一致性，同时允许在实践中防止代价高的不确定性排序操作的计时。例如，电商平台的购物车功能，客户通过 Web 浏览器请求在线购物车中添加和删除项，是一个逻辑单调性的过程，最终的购物车内容可以通过跨节点统一 Added 集、跨节点统一 Deleted 集并计算结果的集合差来确定。但是，付账的流程不具备程序一致性。

2、二分布式系统的可计算性模型

分布式计算中的每个机器都支持一些计算的本地模型，跨机器的数据分区，以及机器随时间进行通信的能力，大约可以抽象为一个转换器网络。简单地说，关系型转换器是一个事件驱动的服务器，内存是关系数据库，每个转换器运行一个顺序事件的循环。

• 提取并处理一批无序的请求，以在本地关系中插入和删除记录，而请求可能来自其他机器或特殊的输入关系。
• 查询本地关系来计算应该发送到某个地方，以便将处理的请求记录。
• 将查询结果作为要处理的请求发送到网络中的相关机器，在事件循环的下一个迭代中被消化，结果也可以“发送”到一个特殊的输出。

在这个计算模型中，每台机器上的状态通过记录集(即关系)来表示，而消息则通过插入或从接收机器上的关系中删除的记录来表示。每台计算机上的计算是通过事件循环每次迭代中对当前局部关系的逻辑查询来指定的。

3、逻辑单调性

经典的数据库查询语言包括关系演算和代数、 SQL、数据模型都是基于一阶逻辑的，大多数常见的表达式是单调的，而语法则揭示了潜在的非单调表达式。因此，具有逻辑单调性的程序是符合转化器的网络，其中每台机器的查询只使用单调语法。

有了一个计算模型 ，以及程序一致性和逻辑单调性的定义，在单调的关系转化器网络中，很容易表明任何机器最终将摄取并发送一组确定性的消息并生成确定性的输出。在执行期间的任何时候，任何机器输出的消息都构成最终输出的有效子集。

直观地看，数据流消息是那些组装其组件不在同一位置的数据的消息。为了隔离协调消息，在程序启动时将网络中的机器之间的数据进行分区。在程序的执行过程中，每一个起始点都会产生一个消息模式。如果一个程序需要在所有可能的分区下发送消息，那么它就包含协调。在每个分区中发送的消息与数据流无关; 它是一个协调消息。

单调性问题不仅是无需协调问题，而且是那些不需要网络成员知识的问题。

三、现实中的一致性实现

Brewer 的 CAP 理论非正式地指出，一个系统只能表现出以下三个属性中的两个: 一致性、可用性和分区容忍性。CAP 只有在我们假设有问题的系统需要执行程序时才有效，并没有指出是否有特定的程序可以同时具有这三个属性！

如果分布式系统满足程序一致性，对属于逻辑单调性的问题实际上可以同时满足 CAP 的三个性质，而非单调问题则不能。

传统编程语言将世界建模为一组命名变量，它们的值随时间而变化，赋值使最终程序状态依赖于输入的到达顺序。函数式编程长期以来一直提倡使用不可变变量，这些变量在计算过程中被限制只能取一个值。一个不可变变量是一个简单的单调模式，不可变变量泛化为不可变的数据结构，使得不可变树、列表和图的编程更加实用。基于单调逻辑的编程模式在分布式存储系统的设计中很常见。

CRDT为基于单调逻辑的编程模式提供了一个面向对象的框架，通常用于状态复制的场景。CRDT 是一种抽象的数据类型，其可能的内部状态构成一个网格，并根据网格的相关偏序单调地演化。CRDT以一种面向对象的视角，利用交换性实现了并发性下的确定性。这可以追溯到在 Linux 内核上的工作，crt 的一个问题是它们的保证只适用于单个对象。交换性的好处已经扩展到可组合的库和编程语言，局部的、以状态为中心的保证可以被验证并自动组成全局的、面向结果的、程序级的保证。

对于非单调逻辑的问题必然需要分布式系统中的各组件协调，需要通过分布式协议来实现，将分布式协议从关键路径转移到后台任务需要一定的编程能力和创造力。简而言之，基于单调逻辑性的编程不是构建高效分布式系统的唯一途径，但作为识别不确定性的分析框架很有用，这样我们就可以创造性地处理分布式系统的一致性问题。

CAP 定理确定了在一般分布式系统中不可能实现的事情。实际上，我们需要明确那些可以实现的东西，以及如何在最小化复杂性和成本的同时实现分布式系统的一致性。

如果一个问题是单调的，那么它就无需通过分布式协议的协商来保证一致性。任何非单调问题的程序都需要运行时强制协调以确保结果的一致性。​