看看 Pat 的
关于分布式系统的零散想法

pathelland.substack.com

逃离奇点

  下载本文的 PDF 版本 PDF

逃离奇点

别陷入“概念”游戏中

一致性、收敛性和合流性并非同一事物！最终一致性和最终收敛性也与合流性不同。

Pat Helland，Salesforce

和许多其他人一样，我也曾深受使用最终一致性这一短语之害。这是一个流行的短语，尽管其含义模糊不清。计算机科学中的不同社群以不同的方式使用一致性一词。即使在这些不同的社群内部，人们对一致性的使用也前后矛盾。这种模糊性使我们许多人陷入了误解之中。

事实证明，还有其他术语，收敛性和合流性，它们具有更清晰的定义，并且比一致性更容易理解。

 

Dont Get Stuck in the Con Game

一致性是什么意思？最终一致性又是什么？

当数据库人员提到一致性时，他们通常指的是 ACID（原子性、一致性、隔离性、持久性）事务一致性（大致与可串行化相同）。我的挚友 Andreas Reuter 在 1983 年的 《面向事务的数据库恢复原则》中创造了术语 ACID。最近，当我问他 C 代表什么时，他说，“应用程序可以控制数据库何时尝试提交。”

换句话说，不要提交事务更新的真子集。不要过早提交。这与隔离性相结合，意味着应用程序可以控制其自身的数据一致性。这与大多数数据库人员理解一致性的方式不太一样。（参见 ACID：我个人的“C”变化。）数据库人员（包括我）甚至对自己一致性的含义感到困惑。

分布式系统人员有时以不同的方式使用这个词。当询问他们一致性是什么意思时，历史上的答案一直是，“对象 X 的每个副本值都具有相同的值。” 对象之间没有工作的概念，只有单个对象及其值。今天，这更常被称为收敛性。当我的朋友 Doug Terry 在 1995 年的 Bayou 论文中创造了最终一致性这个短语时，他的意思是对于对象集合中的每个对象，该对象的所有副本最终都将具有相同的值。

多年后，当我问及此事时，他说，“是的，我应该称之为最终收敛性。” 分布式系统人员也对他们自己对一致性的解释感到困惑。

查看 Seth Gilbert 和 Nancy Lynch（2002 年）在 《Brewer 的猜想和一致性、可用性、分区容错 Web 服务的可行性》中对 CAP 定理的证明，显示了对一致性的另一种含义。当然，该证明与我找到的其他 CAP 描述具有不同的定义。

当分布式系统人员和数据库人员讨论他们自己的社群中最终一致性的含义时，他们会感到困惑；当他们与另一个社群的人员交谈时，情况会变得更糟。

 

收敛性和最终收敛性

让我们考虑收敛性的定义。我的朋友 Peter Alvaro 在他在加州大学伯克利分校 2015 年的博士论文 《面向分布式系统的数据中心编程》（第 76 页）中探讨了收敛性

 

如果一个系统是收敛的或“最终一致的”，那么当所有消息都已传递时，所有副本都对存储值的集合达成一致。

 

这与 Marc Shapiro 等人在 2011 年关于 CRDT 的论文（无冲突复制数据类型）中看到的本质上相同，尽管 Alvaro 关注的是具有一组最终收敛值的系统，而 Shapiro 等人关注的是单个对象。Shapiro 等人说

 

强收敛性：已传递相同更新的正确副本具有等效状态。

 

请注意，这也是 Doug Terry 在与我聊天时使用收敛性和最终收敛性的方式。收敛性是单个对象及其合并函数的属性。

最终收敛性是一个“过多冗余”的短语。收敛性意味着收敛，最终与否。尽管如此，最终收敛性听起来很酷，所以我还是用它吧。

 

线性一致性

线性一致性与收敛性不同。

每个分布式系统极客都应该学习 Maurice Herlihy 和 Jeannette Wing（1990 年）的 《线性一致性：并发对象的正确性条件》。我直到最近才认真研究它。它是分布式系统中某些对象的正确性标准的惊人清晰且简洁的定义。阅读本文后，我可以轻松清晰地解释线性一致性。

引用 Peter Bailis 在他著名的博客文章 《线性一致性与可串行化》 中的话

 

线性一致性是对单个对象上的单个操作的保证。它为单个对象（例如，分布式寄存器或数据项）上的一组单个操作（通常是读取和写入）的行为提供实时（即，挂钟时间）保证。

 

正如我从 Herlihy 和 Wing 的论文中学到的

 

在线性一致性下，操作应从对象的角度来看似乎是瞬时的。 操作一次发生一个（对象所见），并且每个操作都作用于从其本地历史记录派生的对象状态。

 

客户端看到线性一致对象上的操作调用，随后看到对这些操作的响应。从客户端的角度来看，操作发生在对象上，时间介于调用和响应之间。

 

线性一致性定义了对象上的操作的部分顺序（或历史记录）与每个客户端看到的操作的部分顺序（或历史记录）之间的关系。虽然挂钟时间提供了一个绝妙的直观描述，但对象及其客户端的历史记录之间的真实关系是“先发生”关系（由 Leslie Lamport 在 1978 年的 《时间、时钟和分布式系统中事件的排序》中定义）。

线性一致性并不意味着读取/写入操作，尽管这些操作是可能的。线性一致对象可以提供任何操作集，并且这些操作中的每一个都似乎一次发生一个，在对象的历史记录中。这些操作似乎发生在每个客户端，时间介于客户端的调用和客户端收到响应之间。

很多时候，一致性一词用于描述一组对象上的线性一致读取/写入操作。读取被定义为返回在对对象的写入中看到的最新值。如果客户端 A 执行写入，然后对线性一致对象执行读取，则返回给读取调用的值必须是先前由客户端 A 写入的值，或者是另一个客户端 B 的写入值，该写入值在客户端 A 的写入之后和客户端 A 的后续读取之前由对象处理。读取操作与对象历史记录（在读取时）的交互对分区提出了挑战。

同样，线性一致性定义了对象的部分顺序（或历史记录）与每个客户端的部分顺序（或历史记录）之间的关系。它支持可以在对单个对象的单个请求中调用的任何操作。

 

收敛性与线性一致性

收敛性说明了当您停止折磨同一对象的多个不相交的副本并将副本聚集在一起时会发生什么。具体来说，如果您有对象的多个副本，并且每个副本接收不同子集的更新，则收敛对象将与其副本合并并产生相同的对象。这与更新应用于各个副本的顺序无关。

线性一致性是单个对象历史记录的属性，以及该历史记录与向该单个对象发送操作的客户端的历史记录的关系。线性一致对象的清晰历史记录必须看起来像它位于一个位置，一次执行一个操作。

线性一致性和收敛性非常相似，因为它们都指的是单个对象（无论这意味着什么）。它们的本质区别在于收敛性假设多个副本，而线性一致性必须看起来像是一个具有线性历史记录的副本。下面，我指出通过约束执行的操作类型，可以欺骗一个具有线性历史记录的副本的外观。

 

一致性的更多含义：CAP 定理中的“C”

CAP 最初是由 Eric Brewer 在 2000 年于 PODC（分布式计算原则）研讨会上以他的主题演讲 《迈向健壮的分布式系统》 中提出的猜想。它后来在 《Brewer 的猜想和一致性、可用性、分区容错 Web 服务的可行性》 中得到证明，现在被称为 CAP 定理。猜想和定理的名称源于“一致性读取、可用性和分区容错”。

根据 Brewer 在 《CAP 十二年后：规则如何改变》（2012 年）中的说法，一致性定义为 “一致性 (C) 等同于拥有数据的单个最新副本。” 他进一步指出

 

一致性 (C)。在 ACID 中，C 表示事务保留所有数据库规则，例如唯一键。相比之下，CAP 中的 C 仅指单副本一致性，它是 ACID 一致性的严格子集。ACID 一致性也无法跨分区维护。分区恢复将需要恢复 ACID 一致性。更一般而言，在分区期间维护不变量可能是不可能的，因此需要仔细考虑禁止哪些操作以及如何在恢复期间恢复不变量。

 

然后，我们看到

 

CAP 定理的各个方面经常被误解，尤其是可用性和一致性的范围，这可能导致不良结果。

 

随后是

 

一致性的范围反映了这样的想法，即在某些边界内，状态是一致的，但在该边界之外，一切都无法保证。例如，在主分区内，可以确保完全一致性和可用性，而在分区之外，服务不可用。

 

感到困惑，我深入挖掘。在 2012 年的文章中，Brewer 指出 CAP 猜想最初是在 1999 年在 Armando Fox 和 Brewer 的 《收获、产量和可扩展容错系统》 中讨论的。他们在该论文中如何定义一致性？

 

在此讨论中，强一致性意味着单副本 ACID 一致性；通过假设，强一致性系统提供执行更新的能力，否则讨论一致性是无关紧要的。

 

那么在 Brewer 于 2000 年在 PODC 上的主题演讲中呢？这里，C 作为强一致性的定义属于 ACID 事务的范畴，而弱一致性属于 BASE（基本可用、软状态、最终一致）的范畴。

最后，我查看了 《Brewer 的猜想和一致性、可用性、分区容错 Web 服务的可行性》 中定理的证明。在这里，我找到了对一致性的简洁定义，即使它与我在 CAP 探索中发现的任何其他定义都不同

 

形式化一致性服务概念的最自然方法是将其视为原子数据对象。原子或线性一致性是当今大多数 Web 服务期望的条件。在这种一致性保证下，所有操作必须存在一个总顺序，使得每个操作看起来都像是在一个瞬间完成的。这相当于要求分布式共享内存的请求表现得好像它们是在单个节点上执行一样，一次响应一个操作。这种一致性保证通常为用户提供了最容易理解的模型，并且对于那些试图设计使用分布式服务的客户端应用程序的人来说最方便。”

 

好的，酷！这正是 Herlihy 和 Wing 简洁描述的针对单个对象的操作的线性一致性。继续阅读，我找到了他们证明的定理。

 

定理 1。 在异步网络模型中，不可能实现保证以下属性的读/写数据对象

• 可用性

• 原子一致性

在所有公平执行中（包括消息丢失的情况）。

 

研究这篇论文，除非还限制操作为读取和写入，否则我不相信他们已经证明了原子或线性一致性的 CAP。因此，他们的证明不适用于他们在同一篇论文中引用的 一致性模型！

这是一个有趣的证明，但它仅适用于一致性读取与原子或线性一致性相结合。这是更广泛的原子或线性一致性的子集。

CAP 真的是 CrAP！

一致性读取、可用性和分区容错：三者选其二！

猜想中一致性的确切含义尚不清楚。定理中仅证明了一致性读取！

数据库社区和分布式系统社区似乎都没有一致的一致性概念。我完全可以肯定地说，只有当您愿意牺牲可用性或分区容错性时，才能实现一致性读取。CAP 猜想和证明的这种澄清对我来说是有效的！

 

合流性：处理组件的输入和输出

感觉自己被概念游戏欺骗了，我决定研究合流性，它是组件输入和输出的属性。

Alvaro 的论文将合流性定义如下

 

如果一个数据流组件对于其输入的所有排序都产生相同的输出集，我们就称其为合流组件。在任何时候，合流组件（以及该组件的任何冗余副本）的输出都是唯一“最终”输出的子集。

 

Alvaro 继续对比收敛性和合流性

 

收敛性是关于组件状态的局部保证；相比之下，合流性提供了关于组件输出的保证，组件输出（因为它们可以成为下游组件的输入）组合成关于数据流的全局保证。

 

总结

• 收敛性是基于最终状态的定义。

• 合流性是基于行为和程序输出的定义。

因此，给定合流组件的一组输入，您将从该组件获得一组输出。无论您看到输入的哪个合法子集，您都永远不会撤回任何发出的输出。

Alvaro 的论文和 Alvaro 和 Joe Hellerstein 最近的一篇论文都写到了合流性：《保持冷静：何时分布式一致性变得容易》。在那篇论文中，他们说

 

与传统的内存一致性属性（如线性一致性）不同，合流性对新近性的概念（例如，不保证读取返回最新发出的写入请求的结果）或操作的排序（例如，不保证写入在所有副本中都以相同的顺序应用）没有要求或承诺。

 

然而，如果应用程序是合流的，我们知道内存或存储级别的任何此类异常都不会影响应用程序的结果。

 

换句话说，合流性与内存读取和写入无关。

 

通过关注细节实现单调性

因此，合流性是函数输入和输出的属性。这意味着，对于给定的输入集，您将仅创建那些在获得新输入时永远不会撤回的输出。基本上，您永远不会改变对输出的想法。

单调性意味着您只向前移动，永不后退。换句话说，一旦您说出输出，就永远不需要撤回它。

CALM 代表一致性即逻辑单调性。这其中的逻辑部分意味着您可以关注输入和输出，以便您具有单调性。您是否可以省略足够的细节，以至于您无需撤回任何输出消息？

如果单调性意味着始终向前移动，那么您如何思考向前移动意味着什么？在某种程度上，它与从合流函数看到的输出的等价性（或可替代性）有关。如果您对操作有足够高的视角，并且可以将许多答案视为相同，则无需备份和撤回输出。

另一种说法是，两个合流副本可能会给出两个不同的答案，但当它们聚集在一起时，它们可以被视为一个答案。如果我负责为住一晚挑选一家合适的酒店，那么几乎任何酒店都可以。如果我的妻子选择酒店，则会有许多其他标准。当我的妻子的酒店选择函数不是合流的时，我的酒店选择函数有时会是合流的。相同输出的概念取决于相同的含义。

合流性讨论的是函数的输入和输出。这是从外部看到的。从内部来看，我们经常考虑副作用。在 《副作用，置于中心！》 中，我指出副作用是主观的。一个人的（或子系统的）副作用是另一个人的主流业务目的。因此，解释单调性似乎取决于观察者认为重要的内容。

 

合流流的密封

在他们的 CALM 论文中，Hellerstein 和 Alvaro 指出，合流函数可以回答诸如“这是否存在？”之类的问题，但很难回答诸如“这不存在？”之类的问题。这是因为合流函数可能仍然会获得稍后的知识，而新的知识可能会添加迄今为止不存在的事物。因此，在您知道您不会获得新事实作为新输入之前，最好不要说它不存在。

有一个称为合流流的密封的概念。密封是一种表示不会再有更多合流输入操作的方式。当您密封合流流时，您可以获得一个输出，该输出表示：“我可以证明这不存在。”（请参阅 Alvaro 的论文。）密封合流流很奇怪。根据定义，密封操作是有序的，因此，不是合流输入集的一部分（因为密封的顺序很重要）。

您可以有意义地密封合流函数的单个副本，并说该副本将不再有输入。如果您知道有界集合，跟踪它们并密封它们，则可以有意义地密封函数的有界副本集。如果您不确切知道副本集，则无法确保所有副本的输入都被密封。当发生这种情况时，您无法回答关于集合输出的“不存在”问题。

合流性允许任意组合合流函数集。如果您想考虑“不存在”问题，则最好能够控制此函数集的边界。

 

概念混淆：合流性和收敛性相同吗？

作为数据库人员，当人们将数据视为一切的最终目标时，我感到非常恼火。通常认为数据是仅支持读取和写入的东西。重点应该放在函数及其内部状态上定义的操作集合上。读取和写入只是两种类型的操作（尤其是非常糟糕的操作）。

合流性是关于函数的输入和输出。如果函数产生的输出在输入顺序更改时不会更改，则该函数是合流的。

收敛性是关于副本与其他副本合并时的状态。但是状态是什么意思？从我的角度来看，副本的状态由它在响应未来输入时将产生的输出定义。

收敛副本被允许四处游荡，接受输入并生成输出。当看到家庭的其他成员时，他们会进行瓦肯思维融合，融合成一个整体。输出集中的新输出取决于任何副本接收的输入和发出的输出。收敛对象的副本的输出集单调增长，而与任何副本中看到的输入顺序无关。您可以根据收敛性的定义推断出这一点。Shapiro 等人说

 

强收敛性：已传递相同更新的正确副本具有等效状态。

 

对我来说，等效状态意味着未来的输出将基于未来的输入。因此，收敛对象的合并副本将基于未来的输入发出可预测的输出，而与它们先前看到的输入的顺序无关。

合流性是描述一组收敛副本的外部视图输出的一种方式。收敛性说明了一组合流函数的预期行为。

当然，这只是以不同的方式谈论 Shapiro 等人定义的 CRDT。

• CvRDT（基于收敛的复制数据类型）是基于状态的。以任何顺序合并两个或多个副本都会产生等效状态。

• CmRDT（基于交换的复制数据类型）是基于操作的。任何看到相同输入集而与其顺序无关的副本都将是等效的。

由于每个收敛副本都看到了自己的一组输入，因此合并后的副本将看到合并前副本所看到的输入的并集。如果这是等效的，那么它们未来的输出将是相同的。CvRDT 等效于 CmRDT 的证明在 Shapiro 等人中提供。

 

线性一致性在观察者眼中

回想一下，线性一致性定义了对象上的操作的部分顺序（或历史记录）与每个客户端看到的操作的部分顺序（或历史记录）之间的关系。

对于某些操作，至少从客户端的角度来看，线性一致性似乎与合流性相同。如果后续响应（输出）不需要撤回，则对于具有合流行为的对象，响应（或输出）似乎是线性一致的。输出的顺序很好，无论其他客户端可能看到了什么。

为了使合流对象看起来是线性一致的，对象本身看到的“线性”顺序必须放宽。虽然此对象从外部看起来是线性一致的（由于合流操作），但其历史记录具有 DAG（有向无环图）。外部的客户端将无法分辨出事情是否没有以线性顺序发生。这是因为合流操作容忍重新排序。如果操作是合流的，则从外部看起来是线性的可能在内部是 DAG。

合流函数和收敛对象提供的行为对其客户端而言似乎是线性一致的。每个客户端发送一个输入，该输入反过来生成一个输出。客户端在执行输入请求后看到输出响应。

假设操作是合流的并且它们永远不需要撤回它们发出的任何输出，那么放宽对线性一致行为的解释可以为时间（例如，长时间运行的工作）和空间（例如，复制）提供必要的灵活性。在分布式计算和幸福的婚姻生活中，永远没有理由说对不起是一个极好的策略！

 

不一致和“一致”的一致性

一致性一词似乎至少有三种流行的用法

• 数据库一致性。 这是完整事务与某些未声明的规则的某些未声明的强制执行的混合。由于事务中的更新集必须由应用程序与数据库的上部勾结来限制，因此应用程序和上部数据库可以强制执行事务系统不理解的某些规则。我将其视为从事务的角度来看是完整的。

• 复制对象的最终一致性（收敛）。 当对象的所有副本合并时，它们都具有相同的值。

• 一致性作为线性一致的读取/写入操作。对分布式系统中每个对象的更新都必须看起来好像它们发生在对象看到的单个历史记录中，并且来自客户端的调用和响应必须在每个客户端形成明确定义的先发生历史记录。

这些流行的用法对我来说都没有任何意义。但是，我确实清楚地理解一致性（前面带有形容词）的用法

• 严格一致性。 这与 Gilbert 和 Lynch 在他们对 CAP 猜想的证明中使用的线性一致读取/写入操作完全相同。通常，它被解释为可能非合流操作（例如，读取和写入）的线性顺序。

• 顺序一致性。 Lamport 在 《如何制造一台能够正确执行多进程程序的多处理器计算机》（1979 年）中定义的顺序一致性比严格一致性弱。从编写者的角度来看，每个客户端对变量的写入都按顺序显示。客户端的读取不能保证其他客户端的并发写入的可见性。我理解这个定义。

• 因果一致性。 因果一致性是我最喜欢的一致性形式之一，它是顺序一致性的弱化形式。它根据操作的因果依赖性对操作进行分类。

假设我收到客户端 A 对对象 X 执行的操作 Y。因果一致性表示，在我收到客户端 A 执行的操作 Y 之前，我将首先收到客户端 A 请求操作 Y 时对其可见的对对象 X 执行的所有操作。

这可以通过仔细跟踪操作向客户端 A 的交付并在网络中喷射这些操作作为捕获客户端 A 看到的交付顺序的捆绑包来完成。当我准备接收对象 X 上的下一个操作时，将这些操作交付给我的管道首先确保我看到客户端 A 在请求操作 Y 之前收到的所有操作。

每个客户端看到的操作顺序显示了因果顺序。这在分布式系统中是易于实现的。它在偶尔连接的系统中也非常有用。

 

外部一致性

本文未深入探讨“外部一致性”一词。据我所知，这意味着您应该在分布式集群外部提供与在单个节点外部相同的行为。由于这与一致性一词的含义纠缠在一起，我也发现这令人困惑且不精确。“外部”部分看起来还可以。“一致性”部分经常以不一致的方式使用。

 

结论

本文是关于术语和如何谈论事物。我将在未来努力使我使用的词语更清晰、更简洁。

因此，除了严格一致性、顺序一致性或因果一致性之外，我将来将始终如一地避免使用一致一词。大多数时候。

 

开放性问题

• 设计者何时应选择以操作为中心的复制方法（例如，合流性）和以对象为中心的复制方法（例如，收敛性）？

• 何时、何地以及如何在任何系统设计中，因果一致性都是一份令人惊叹的礼物？

• 共识是一种允许对象就新值达成一致的机制。这仅仅是一个分布式写入操作吗？为什么我们将共识作为一种写入新值的形式来关注？这与强一致性相同吗？

• 当您的约会对象谈论最终一致性时，您在第一次约会时应该如何反应？这是否比谈论政治更难讨论？

• 线性一致性真的在观察者眼中吗？我们能否通过不关心被另一个系统隐藏的缺乏秩序来构建健壮的分布式系统？“无法分辨它是否是线性的”与“真正线性”相同吗？

 

Pat Helland 自 1978 年以来一直从事事务系统、数据库、应用程序平台、分布式系统、容错系统和消息传递系统的实现工作。为了消遣，他偶尔会撰写技术论文。他在 Salesforce 工作。他的博客位于 pathelland.substack.com。

版权所有 © 2021，所有者/作者持有。出版权已许可给 。

acmqueue

最初发表于 Queue vol. 19, no. 3—
在 数字图书馆 中评论本文




更多相关文章

Ethan Miller, Achilles Benetopoulos, George Neville-Neil, Pankaj Mehra, Daniel Bittman - 远内存中的指针
有效利用新兴的远端内存技术需要考虑在父进程上下文之外操作富连接数据。正在开发中的操作系统技术通过暴露诸如内存对象和全局不变指针等抽象概念来提供帮助，这些抽象概念可以被设备和新实例化的计算资源遍历。这些想法将使运行在未来具有分离内存节点的异构分布式系统上的应用程序能够利用近内存处理来获得更高的性能，并独立扩展其内存和计算资源以降低成本。


Simson Garfinkel, Jon Stewart - 磨砺你的工具
本文介绍了我们在最初发布十年后更新高性能数字取证工具 BE (bulk_extractor) 的经验。在 2018 年至 2022 年间，我们将程序从 C++98 更新到 C++17。我们还进行了完整的代码重构并采用了单元测试框架。DF 工具必须经常更新，以跟上其使用方式的变化。对 bulk_extractor 工具更新的描述可以作为可以并且应该做什么的示例。


Pat Helland - 自主计算
自主计算是一种业务工作模式，它使用协作来连接领地及其使节。这种基于纸质表格的模式已经使用了几个世纪。在这里，我们解释领地、协作和使节。我们研究使节如何在自主边界之外工作，以及如何在保持局外人身份的同时提供便利。并且我们研究如何在不同的领地之间发起、长期运行并最终完成工作。


Archie L. Cobbs - 持久性编程
几年前，我的团队正在为一个商业 Java 开发项目工作，该项目是为增强型 911 (E911) 紧急呼叫中心开发的。我们尝试使用传统的 Java over SQL 数据库模型来满足该项目的数据存储需求，但感到沮丧。在对项目的特定需求（和非需求）进行一些反思之后，我们深吸一口气，决定从头开始创建我们自己的自定义持久层。



© 保留所有权利。

© . All rights reserved.