保持冷静：当分布式一致性很容易实现时
作者：Joseph M.Hellerstein，Peter Alvaro Communications of the ACM，2020年9月，第63卷第9期，第72-81页，10.1145/3369736评论，分布式系统很棘手。多台不可靠的机器并行运行，在任意延迟的网络链路上相互发送消息。尽管混乱不堪，我们怎么能相信这些系统能做我们想做的事呢？
这个问题应该引起我们的关注，因为我们今天使用的几乎所有软件都是分布式系统的一部分。您手机上的应用程序与云中的托管服务一起参与；它们共同构成一个分布式系统。托管服务本身是大规模分布式系统，通常在遍布全球的机器上运行。大数据系统和大型数据库分布在许多机器上。大多数科学计算和机器学习系统在多个处理器上并行工作。即使是传统的桌面操作系统和应用程序(如电子表格和文字处理器)也与分布式后端服务紧密集成。
构建正确的分布式系统的挑战日益紧迫，但这并不新鲜。一种传统的解决方案是通过内存一致性保证(保证以受控方式访问内存(堆变量、数据库键等))来降低这种复杂性。然而，用于实施这些保证的机制-协调协议-经常被批评为阻碍分布式系统高性能、可伸缩性和可用性的障碍。
高昂的协调成本。协调协议使自治的、松散耦合的机器能够共同决定如何控制基本行为，包括访问共享内存的顺序。这些协议是分布式计算中最聪明和被广泛引用的想法之一。一些众所周知的技术包括Paxos 33和两阶段提交(2PC)25、34协议，以及批量同步并行计算等计算模型底层的全局障碍。40岁。
不幸的是，协调协议的费用可能会使它们成为程序员的禁果。亚马逊网络服务公司的詹姆斯·汉密尔顿(James Hamilton)有力地阐述了这一点，他使用了一致性机制这一短语，其中我们使用了协调：
成功的可伸缩性的第一个原则是将一致性机制降低到最低限度，将它们移出关键路径，将它们隐藏在系统中一个很少访问的角落，然后使应用程序开发人员尽可能难以获得使用它们的许可。
问题不是协调很难实现，尽管这是真的。主要的问题是协调会极大地减慢计算速度，甚至完全停止计算。一些现代的全球规模的系统使用协调协议；Google Spanner事务数据库18是同时使用Paxos和2PC的一个著名示例。然而，这些协议存在10ms-100ms量级的高延迟。依赖于这些协议的全球范围的系统不应该在应用程序的快速路径中使用。协调延迟问题也会转化到微尺度上。最近的研究表明，最先进的多处理器键值存储可以花费90%的时间等待协调；一个名为Anna的无协调实现通过消除这种协调实现了超过两个数量级的加速。43我们能像汉密尔顿建议的那样，更普遍地避免协调吗？什么时候?。
更大的图景：程序一致性。关于何时需要协调以实现一致性的一般性问题直到最近才得到解决。关于一致性的传统工作集中在诸如可线性化30和冲突可串行化20之类的属性上，这些属性通过约束冲突存储器访问的顺序来确保存储器一致性。这一传统掩盖了一个基本的问题，即是否需要协调来保持特定计划的结果的一致性。要从整体上解决问题，我们需要向上移动堆栈，将低级别细节放在一边，以支持程序语义。
交通交叉口提供了一个来自现实世界的有用的类比。为了避免在繁忙的十字路口发生事故，我们经常安装停车灯来协调两条交叉道路的交通。然而，在这种情况下，协调并不是必要的坏事：我们还可以通过为其中一条道路修建天桥或隧道来防止事故发生。交通交叉口问题就是一个无协调解决方案的例子。重要的是，解决方案不是通过巧妙地控制通往地图上道路重叠的关键路段的顺序来找到的。解决方案包括对道路进行工程设计，以完全避免协调的需要。
对于交通交叉口问题，原来有一种完全避免协调的解决方案。并不是所有的问题都有这样的解决方案。对于任何给定的计算问题，我们如何知道它是否有无协调的解，或者是否需要协调以保持一致性？为了加深我们的直觉，我们考虑了分布式系统规范中的两个几乎相同的问题。两者都涉及图的可达性，但一个是无协调的，另一个不是。
分布式死锁检测。分布式数据库识别分布式图中的循环，以便检测和修复死锁。在传统的数据库系统中，事务T1可能正在等待由另一个事务Tj持有的锁，该事务Tj又可能在等待由T1持有的第二个锁。死锁检测器通过分析有向图来识别这样的等待循环，其中节点表示事务，边表示锁队列上等待另一个事务。死锁是一个稳定的属性：等待周期上的事务不能取得进展，因此周期上的所有边缘都会无限期地存在。
在分布式数据库中，等待图的本地(单机)视图仅包含全局等待图中的边的子集。在此场景中，本地死锁检测器如何协同工作来识别全局死锁？
图1显示了一个跨越多台机器的等待周期。为了识别这种分布式死锁，每台机器都会与其他机器交换其边的副本，以积累有关全局图的更多信息。只要机器观察到它到目前为止收到的信息中的一个周期，它就可以在该周期上的事务之间声明死锁。
图1.具有复制节点和分区边的分布式等待图。有一个跨越机器1和机器2({T1，T3})的周期。
在这种分布式计算中，我们可能会担心由于延迟或重新排序的消息而导致的瞬时错误。本地检测器是否必须与其他机器协调才能确保它们观察到的死锁？在这种情况下，不需要协调。要了解这一点，请注意，一旦我们知道图中存在循环，了解一条新边永远不会使循环消失。例如，一旦机器1和机器2共同识别T1和T3之间的死锁，来自机器3的新信息将不会改变这一事实。附加事实只能导致检测到附加周期：每台机器的输出随输入单调增长。最后，如果所有机器最终共享所有边，机器将基于完整的图形就结果达成一致。
分布式垃圾收集。分布式系统中的垃圾收集器必须在内存引用的分布式图中标识无法到达的对象。垃圾收集的工作方式是标识与系统运行时的根目录断开连接的图形组件。作为垃圾的属性也是稳定的：一旦图形组件与根的连接被删除，该组件中的对象将不会被重新引用。
在分布式系统中，对对象的引用可以跨计算机。参考图的局部视图仅包含全局图中的边的子集。多个本地垃圾收集器如何协同工作来识别真正无法到达的对象？
请注意，机器可能有一个本地对象，但不知道该对象是否连接到根；图2中的机器3和对象O4就是一个示例。然而，可能仍然存在从根部到该对象的路径，该路径由分布在其他机器上的边组成。因此，每台机器都与其他机器交换边的副本，以积累有关该图的更多信息。
图2.带有远程引用的分布式对象引用图(虚线箭头)。对象O3可以从Root到达这一事实可以在没有来自机器3的任何信息的情况下建立。对象O5和O6是垃圾，只有在知道整个图的情况下才能建立。
与以前一样，我们可能会担心由于消息延迟或重新排序而导致的错误。当地收集者可以自主申报和重新分配垃圾吗？在这里，答案是不同的：确实需要协调！要看到这一点，请注意，基于不完全信息的决策-例如，机器3在图2中判定对象O4是不可达的-可能会因随后到达的演示可达性的新信息(例如，边根→O 1、O 1→O 3、O 3→O 4)而无效。输出不会随着输入单调增长：临时答案可能需要收回。为了避免这种情况，机器在声明对象不可访问之前，必须确保它已经听到了所有要听到的内容。要知道它听到了一切，唯一的方法是与所有其他机器协调-即使是没有要报告的参考边缘的机器-以确定这一事实。正如我们将讨论的，协调的一个标志是即使在没有数据依赖的情况下也要进行通信的这一要求。
一致性的症结在于：单调性。这些示例将我们带回了我们的基本问题，该问题适用于任何并发计算框架。
问：如果存在一个分布式实现(即，解决问题的程序)，并且在不使用协调的情况下计算一致的输出，则我们称计算问题是无协调的。什么是无协调问题的家庭，这个家庭之外有什么问题？
附带使用协调和协调的内在需要之间存在差异：前者是实现选择的结果；后者是计算问题的属性。因此，我们的问题是可计算性，就像P与NP或可决断性。它问一个聪明的程序员可能实现什么。
请注意，该问题假设一致性的某些定义。在传统工作狭隘地关注内存一致性(即，读取和写入产生商定的值)的情况下，我们希望关注程序一致性：实现是否会产生我们预期的结果(例如，检测到死锁、垃圾回收)，而不考虑可能出现的跨消息和计算的任何争用条件？
我们的例子为回答我们的问题提供了线索。这两个示例都累积了一组有向边E，并依赖于可达性谓词-即，测试传递闭包E*中的节点对。但他们在一个关键方面有所不同。如果E*中存在到节点自身的路径：{n|∃(n，n)∈E*}，则节点参与死锁。如果不存在从根到n的路径，则节点n是垃圾节点：{n|∃(root，n)∈E*}。
逻辑谓词澄清了示例之间的区别。对于死锁检测的存在谓词，在接收到的信息中，存在的满足路径集是单调的：
定义1.问题P是单调的，如果对任何输入集S，T，其中S⊆T，P(S)⊆P(T)。
相比之下，垃圾收集示例中不存在的令人满意的路径集是非单调的：基于关于E的部分信息得出的结论可能不成立，因为反例似乎推翻了关于以前不存在的东西的先前信念。
单调性是需要协调以建立一致性的关键属性，正如平静定理中所描述的那样：
定理1。作为逻辑单调性的一致性(CAME)。当且仅当问题是单调的时，它才具有一致的、无协调的分布式实现。
直观地说，面对缺失的信息，单调的问题是安全的，并且可以在没有协调的情况下继续进行。相比之下，非单调问题必须关注的是，面对新的信息，财产的真相可能会发生变化。因此，在他们知道所有信息都已经到达之前，他们不能继续进行，这需要他们进行协调。
此外，因为他们改变了主意，非单调问题是顺序敏感的：他们接收信息的顺序决定了他们如何来回切换状态，这反过来又可以决定他们的最终状态(就像我们将在购物车的例子中看到的那样)。相比之下，单调的问题只是积累信念；它们的输出只取决于它们输入的内容，而不是它到达的顺序。
到目前为止，我们的讨论还停留在直觉的层面上。下一节提供了平静定理证明的草图，包括进一步讨论一致性和协调性的定义。该证明使用了数据库理论中的逻辑形式主义，并演示了将数据库理论(ACM POD)和分布式系统(ACM PODC)更紧密地结合在一起的好处。问题可以定义为跨多台机器运行的关系(记录集)上的一系列声明性查询。正如在我们的示例中一样，这些查询的单调性通常可以通过它们的语法进行静态检查：例如，∃(n，n)∈E*是单调的，但是∃(根，n)∈E*是非单调的，正如使用被否定的存在量词∃("；NOT EXISTS"；)所证明的那样。寻找完整证据的读者可参考阿梅鲁特等人的论文。8、9。
将平静定理形式化的第一个挑战是以一种允许我们对程序结果进行推理的方式来定义程序一致性，而不是存储突变。做完这些之后，我们可以继续讨论在有和没有协调的情况下一致的可计算性。
程序一致性：汇流。分布式系统为我们的程序引入了重大的不确定性。不确定性的来源包括不同步的并行、不可靠的组件和延迟不可预测的网络。因此，分布式程序可以在给定输入上表现出很大的可能行为空间。
虽然我们可能无法控制分布式程序的所有行为，但我们真正关心的是它的可观察行为：程序结果。为此，我们希望评估分布式不确定性如何影响项目结果。一个实际的一致性问题是这样的：尽管运行时系统中存在不确定性，但我的程序是否会产生确定性的结果？
这是一个程序融合的问题。在不确定消息传递的上下文中，如果一台机器上的操作为一组输入请求的任何不确定排序和批处理产生相同的输出响应集，则该操作是合流的。按照这种思路，汇流的单机操作可以被视为从一个集合到另一个集合的确定性函数，抽象出其输入碰巧出现在分布式系统的特定运行中的不确定顺序。合流操作合成：如果一个合流操作的输出集被另一个合流操作使用，则结果复合操作是合流的。因此，合流可以应用于单个操作、数据流中的组件，甚至整个分布式程序。2如果我们通过组合合流操作来限制自己构建程序，那么我们的程序通过构造是合流的，尽管组件内和组件之间的消息或执行竞争是有序的。
与传统的存储器一致性属性(如可线性化)不同，Confluence对新近概念(例如，不保证读取返回发出的最新写入请求的结果)或操作顺序(例如，不保证在所有副本中以相同的顺序应用写入)没有要求或承诺。但是，如果应用程序是合流的，我们知道内存或存储级别的任何此类异常都不会影响应用程序结果。
对于分布式应用程序，合流是一个强大但允许的正确性标准。它排除了由于竞争和非确定性交付导致的应用程序级不一致，同时允许对低级别操作进行非确定性排序和计时，而这些操作在实践中可能代价高昂(有时不可能)。
汇合的购物车。为了说明合流推理的效用，我们考虑了一个更高级别的应用程序的示例。在他们关于Dynamo Key-Value商店的论文中，来自亚马逊的19名研究人员描述了一个购物车应用程序，该应用程序无需协调即可实现汇流。在他们的场景中，客户端Web浏览器请求在线购物车中添加和删除项目。出于可用性和性能的考虑，购物车的状态由一组分布式服务器副本跟踪，这些副本可能会以不同的顺序接收请求。在Amazon实现中，购物时不需要协调，但是所有服务器副本最终都同意购物车的最终状态。这是我们感兴趣的这类程序的一个最好的例子：最终是一致的，即使在不进行协调的非确定性分布式基板上实现时也是如此。
在这种情况下，程序一致性是可能的，因为在购物车上执行的基本操作(例如，添加)通勤，只要购物车的内容表示为一个集合，并且忽略其元素的内部排序。如果两个副本在一路上了解到它们对购物车的内容存在分歧，则只需发出一个返回其各自集合的并集的逻辑查询即可合并它们的不同视图。
不幸的是，如果除了添加之外还允许删除操作，则集合既不会单调增长，也不会缩小，这会导致一致性问题。如果添加项目I和删除项目I的指令以不同的顺序到达不同的机器，那么机器可能不同意我是否应该在购物车中。如前所述，这反映在节点上i的存在方式上。在一台机器上，I的存在可能以NOT-EXISTS状态开始，但是一系列消息<；add(I)；delete(I)&>将导致状态切换到EXISTS，然后切换到NOT-EXISTS；在另一台机器上，消息可能会以<；delete(I)；add(I)&>的顺序到达，从而导致I的状态从NOT-EXISTS转换到NOT-EXISTS到EXISTS。即使在两台机器各自收到所有信息后，它们对最终结果仍存在分歧。作为避免这种争用条件的传统方法，我们可以用全局协调将每个非单调的删除操作括起来，以商定在它之前的哪些添加请求。我们能做得更好吗？
作为单调性在应用程序级的创造性使用，一种常见的技术是通过两个单独的单调增长集(添加项和删除项)将删除与添加分开处理。19、39添加和删除的集合都是仅插入的，并且跨两个通勤插入。最终购物车内容可以通过合并跨节点的添加集，以及合并跨节点的删除集，并计算结果的集差来确定。这似乎解决了我们的问题：它消除了。
.
