《分布式系统：为了乐趣和利益》是一本广受欢迎的资源，用于理解和学习分布式系统。该书由作者 Mikito Takada 撰写，介绍了构建分布式系统的基本概念、原则和挑战。

这本书涵盖了与分布式系统相关的广泛主题，包括网络、容错性、一致性模型、分布式算法、可扩展性等等。它旨在以清晰易懂的方式解释复杂的概念，适合初学者和有经验的分布式系统从业者阅读。

在整本书中，作者提供了各种实际案例和案例研究，以说明分布式系统的实际应用和实践方面。它还强调了构建分布式系统涉及的权衡和设计考虑，帮助读者全面理解这个主题。

《分布式系统：为了乐趣和利益》作为开源资源，可以免费在线获取，非常适合任何对学习分布式系统感兴趣的人。

原文链接：Distributed systems: for fun and profit

5. 复制：弱一致性模型协议

现在，我们已经研究了一些可以在越来越现实的故障情况下实施单副本一致性的协议，让我们转向当我们放弃单副本一致性的要求时所打开的选择世界。

总的来说，很难找到一个单一的维度来定义或描述允许副本发散的协议。大多数这样的协议都具有高可用性，关键问题更多地在于最终用户是否发现这些保证、抽象和 API 对他们的目的有用，尽管在节点和/或网络故障发生时副本可能发散。

为什么弱一致性系统没有更受欢迎呢？

正如我在介绍中所述，我认为分布式编程很大程度上涉及处理分布的两个结果所带来的影响：

1. 信息以光速传播；
2. 独立的事物独立地发生故障。

由于信息传输速度受限，节点以不同且独特的方式体验世界。在单个节点上进行计算很容易，因为一切都按照可预测的全局总序发生。在分布式系统上进行计算很困难，因为没有全局总序。

长期以来（例如几十年的研究时间），我们通过引入全局总序来解决这个问题。我已经讨论了许多实现强一致性的方法，通过在没有自然总序的情况下以容错方式创建顺序的方法。

当然，问题在于强制执行顺序是昂贵的。这在大规模的互联网系统中特别突出，因为系统需要保持可用性。强一致性的系统不像分布式系统那样运行，而是像单个系统，这对于分区期间的可用性是不利的。

此外，对于每个操作，通常需要联系大多数节点，而且通常不止一次（正如您在关于 2PC 的讨论中所看到的）。这在需要在地理上分布以为全球用户提供足够性能的系统中尤其困难。

因此，默认情况下像单个系统一样运行可能并不理想。

也许我们希望拥有一种可以编写不使用昂贵协调的代码，但仍返回一个“可用”值的系统。我们将允许不同的副本彼此发散-既为了保持效率，也为了容忍分区-然后尝试以某种方式处理这种发散。

最终一致性表达了这个想法：节点在一段时间内可以相互发散，但最终它们将达成一致的值。

在提供最终一致性的系统集合中，有两种类型的系统设计：

带有概率保证的最终一致性。这种类型的系统可以在以后的某个时间点检测到冲突的写操作，但不能保证结果与某个正确的顺序执行等效。换句话说，冲突的更新有时会导致将较新的值覆盖为较旧的值，并且在正常操作（或分区）期间可能会出现一些异常情况。

近年来，最有影响力的提供单副本一致性的系统设计是亚马逊的 Dynamo，我将以它作为提供带有概率保证的最终一致性系统示例进行讨论。

带有强保证的最终一致性。这种类型的系统保证最终结果会收敛到一个共同的值，该值等同于某个正确的顺序执行。换句话说，这样的系统不会产生任何异常结果；在没有任何协调的情况下，您可以构建相同服务的副本，并且这些副本可以以任何模式进行通信并以任何顺序接收更新，只要它们都看到相同的信息，它们最终会就最终结果达成一致。

CRDT（收敛复制数据类型）是一种数据类型，它保证在网络延迟、分区和消息重排序的情况下收敛到相同的值。它们可以被证明是收敛的，但可以实现为 CRDT 的数据类型是有限的。

CALM（一致性作为逻辑单调性）猜想是相同原则的另一种表达方式：它将逻辑单调性与收敛等同起来。如果我们可以得出某个东西在逻辑上是单调的，那么在没有协调的情况下运行它也是安全的。收敛分析-特别是在 Bloom 编程语言中的应用-可用于指导程序员在何时何地使用强一致性系统的协调技术以及在何时可以安全地执行无需协调的操作。

协调不同的操作指令

不强制执行单副本一致性的系统是什么样子呢？让我们通过几个例子来更具体地了解。

也许最明显的非强制执行单副本一致性系统的特征是它们允许副本彼此发散。这意味着没有严格定义的通信模式：副本可以相互分离，但仍然保持可用并接受写操作。

让我们想象一个由三个副本组成的系统，每个副本彼此分离。例如，这些副本可能位于不同的数据中心，并因某种原因无法通信。在分离期间，每个副本仍然可用，可以接受一些客户端的读写操作：

1
2
3
4
5
6
7
8
9

[Clients]   - > [A]

--- Partition ---

[Clients]   - > [B]

--- Partition ---

[Clients]   - > [C]

一段时间后，分区会修复并且副本服务器会交换信息。他们从不同的客户那里收到了不同的更新，并且彼此存在分歧，因此需要进行某种协调。我们希望所有的副本都收敛到相同的结果。

1
2
3
4
5

[A] \
    --> [merge]
[B] /     |
          |
[C] ----[merge]---> result

考虑具有弱一致性保证的系统的另一种方法是想象一组客户端按某种顺序向两个副本发送消息。由于没有强制执行单一总顺序的协调协议，因此消息可以在两个副本上以不同的顺序传递：

1
2

[Clients]  --> [A]  1, 2, 3
[Clients]  --> [B]  2, 3, 1

从本质上讲，这就是我们需要协调协议的原因。例如，假设我们尝试连接一个字符串，消息 1、2 和 3 中的操作为：

1
2
3

1: { operation: concat('Hello ') }
2: { operation: concat('World') }
3: { operation: concat('!') }

然后，如果没有协调，A 将产生“Hello World!”，B 将产生“World!Hello”。

1
2

A: concat(concat(concat('', 'Hello '), 'World'), '!') = 'Hello World!'
B: concat(concat(concat('', 'World'), '!'), 'Hello ') = 'World!Hello '

这当然是不正确的。同样，我们希望副本收敛到相同的结果。

记住这两个例子，让我们首先看看亚马逊的 Dynamo 来建立基线，然后讨论一些构建具有弱一致性保证的系统的新方法，例如 CRDT 和 CALM 定理。

Amazon’s Dynamo

亚马逊的 Dynamo 系统设计（2007 年）可能是最著名的提供弱一致性保证但高可用性的系统。它是许多其他实际系统的基础，包括 LinkedIn 的 Voldemort、Facebook 的 Cassandra 和 Basho 的 Riak。

Dynamo 是一个最终一致性且高可用的键值存储系统。键值存储类似于一个大的哈希表：客户端可以使用 set(key, value)设置值，并通过键使用 get(key)检索值。Dynamo 集群由 N 个对等节点组成；每个节点负责存储一组键。

Dynamo 优先保证可用性而不是一致性；它不保证单副本一致性。相反，当写入值时，副本可能会发散；当读取一个键时，在将值返回给客户端之前，会有一个读取协调阶段，尝试解决副本之间的差异。

对于亚马逊的许多功能而言，避免停机比确保数据完全一致更为重要，因为停机可能导致业务损失和信誉损失。此外，如果数据并不是特别重要，那么弱一致性系统可以以比传统关系型数据库更低的成本提供更好的性能和更高的可用性。

由于 Dynamo 是一个完整的系统设计，除了核心复制任务之外，还有许多不同的部分需要考虑。下面的图示了一些任务，特别是写入如何路由到节点并写入多个副本。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

[ Client ]
    |
( Mapping keys to nodes )
    |
    V
[ Node A ]
    |     \
( Synchronous replication task: minimum durability )
    |        \
[ Node B]  [ Node C ]
    A
    |
( Conflict detection; asynchronous replication task:
  ensuring that partitioned / recovered nodes recover )
    |
    V
[ Node D]

在了解最初如何接受写入之后，我们将了解如何检测冲突以及异步副本同步任务。由于高可用性设计，节点可能暂时不可用（宕机或分区），因此需要执行此任务。副本同步任务确保节点即使在发生故障后也能相当快地赶上。

一致的散列

无论我们是读还是写，首先需要做的就是找到数据在系统上的位置。这需要某种类型的键到节点映射。

在 Dynamo 中，键使用称为一致性哈希的哈希技术（我不会详细讨论）映射到节点。主要思想是，通过客户端上的简单计算，可以将密钥映射到负责它的一组节点。这意味着客户端可以定位密钥，而无需向系统查询每个密钥的位置；这可以节省系统资源，因为散列通常比执行远程过程调用更快。

部分法定人数

一旦我们知道密钥应该存储在哪里，我们就需要做一些工作来保存该值。这是一个同步任务；我们立即将值写入多个节点的原因是为了提供更高级别的持久性（例如，防止节点立即发生故障）。

就像 Paxos 或 Raft 一样，Dynamo 使用仲裁进行复制。然而，Dynamo 的法定人数是草率（部分）法定人数，而不是严格（多数）法定人数。

非正式地，严格法定人数系统是指具有法定人数系统中任意两个法定人数（集合）重叠的属性的法定人数系统。在接受更新之前要求多数投票支持更新可以保证只接受单个历史记录，因为每个多数仲裁必须在至少一个节点中重叠。例如，这就是 Paxos 所依赖的属性。

部分法定人数不具备该属性；这意味着不需要多数，并且法定人数的不同子集可能包含相同数据的不同版本。用户可以选择要写入和读取的节点数量：

• 用户可以选择写入成功所需的 W-of-N 节点数量；和
• 用户可以指定读取期间要联系的节点数 (R-of-N)。

W 和 R 指定写入或读取需要涉及的节点数。写入更多节点会使写入速度稍慢，但会增加值不丢失的概率；从更多节点读取会增加读取的值是最新的概率。

通常的建议是 R + W > N ，因为这意味着读取和写入仲裁在一个节点中重叠 - 使得返回过时值的可能性较小。典型的配置是 N = 3 （例如每个值总共三个副本）；这意味着用户可以选择：

1
2
3

 R = 1, W = 3;
 R = 2, W = 2 or
 R = 3, W = 1

更一般地说，再次假设 R + W > N ：

• R = 1, W = N: 读取快，写入慢
• R = N, W = 1: 写入速度快，读取速度慢
• R = N/2 and W = N/2 + 1: 对两者都有利

N 很少超过 3，因为保留大量数据的许多副本会变得昂贵！

正如我之前提到的，Dynamo 纸启发了许多其他类似的设计。它们都使用相同的基于部分仲裁的复制方法，但 N、W 和 R 的默认值不同：

• Basho’s Riak (N = 3, R = 2, W = 2 default)
• Linkedin’s Voldemort (N = 2 or 3, R = 1, W = 1 default)
• Apache’s Cassandra (N = 3, R = 1, W = 1 default)

还有一个细节：发送读或写请求时，是要求所有 N 个节点响应（Riak），还是仅要求满足最小值的多个节点（例如 R 或 W；Voldemort）。

“send-to-all”方法速度更快，对延迟不太敏感（因为它只等待 N 中最快的 R 或 W 节点），但效率也较低，而“send-tominimum”方法对延迟更敏感。延迟（因为与单个节点通信的延迟会延迟操作），而且效率更高（总体上消息/连接更少）。

当读取和写入仲裁重叠时会发生什么，例如（ R + W > N ）？具体来说，人们经常声称这会导致“强一致性”。

R + W > N 等同于“强一致性”吗？

No

这并不是完全错误的： R + W > N 可以检测读/写冲突的系统，因为任何读仲裁和任何写仲裁共享一个成员。例如。两个仲裁中至少有一个节点：

1
2

   1     2   N/2+1     N/2+2    N
  [...] [R]  [R + W]   [W]    [...]

这确保了先前的写操作将被后续的读取操作看到。然而，这仅在 N 中的节点永不改变的情况下成立。因此，Dynamo 并不符合这个要求，因为在 Dynamo 中，如果节点失败，集群成员资格可能会发生变化。

Dynamo 被设计为始终可写。它具有处理节点故障的机制，即在原始服务器宕机时，将一个不相关的服务器添加到负责某些键的节点集合中。这意味着法定人数不再保证始终重叠。即使 R = W = N 也不符合条件，因为尽管法定人数的大小等于 N，但在故障期间，这些法定人数中的节点可以发生变化。具体而言，在分区期间，如果无法达到足够数量的节点，Dynamo 将从不相关但可访问的节点中添加新节点到法定人数中。

此外，Dynamo 不以强一致性模型所强制的方式处理分区：即在分区的两侧都允许写操作，这意味着系统在某些时间内不作为单一副本运行。因此，将 R + W > N 称为"强一致性"是具有误导性的；这个保证仅仅是概率性的，而不是强一致性所指的意思。

冲突检测和读取修复

为了解决允许副本发散的系统必须有一种方法来最终协调两个不同的值，通常会通过补充一些元数据来跟踪数据的因果历史。当客户端从系统中读取数据时，必须保留元数据信息，并在写入数据库时返回相应的元数据值。

我们已经介绍了一种用于实现这一目的的方法：向量时钟可以用于表示值的历史。实际上，这就是原始的 Dynamo 设计用于检测冲突的方法。

然而，使用向量时钟并不是唯一的选择。通过查看系统跟踪的元数据，您可以推断出许多实际系统设计的工作方式。

没有元数据。当系统不跟踪元数据，仅返回值（例如通过客户端 API）时，它实际上无法对并发写入执行任何特殊操作。一个常见的规则是最后写入者获胜：换句话说，如果两个写入者同时写入，只有最慢的写入者的值被保留。

时间戳。通常，具有较高时间戳值的值获胜。然而，如果时间没有被精确同步，许多奇怪的事情可能发生，其中来自具有故障或快速时钟的系统的旧数据覆盖了较新的值。Facebook 的 Cassandra 是 Dynamo 的一个变种，它使用时间戳而不是向量时钟。

版本号。版本号可以避免使用时间戳时的一些问题。需要注意的是，当存在多个可能的历史时，可以准确跟踪因果关系的最小机制是向量时钟，而不是版本号。

向量时钟。使用向量时钟，可以检测并发和过时的更新。然后可以执行读修复操作，尽管在某些情况下（并发更改），我们需要要求客户端选择一个值。这是因为如果更改是并发的，并且我们对数据没有更多了解（就像简单的键值存储一样），那么询问比任意丢弃数据更好。

在读取值时，客户端联系 N 个节点中的 R 个节点，并请求它们为某个键提供最新的值。它接收所有的响应，丢弃严格较旧的值（使用向量时钟值来检测）。如果只有一个唯一的向量时钟+值对，则返回该值。如果有多个并发编辑的向量时钟+值对（例如不可比较），则返回所有这些值。

显然，从上述内容可以看出，读修复可能会返回多个值。这意味着客户端/应用程序开发人员必须根据特定用例的标准偶尔处理这些情况，并选择一个值。

此外，实际向量时钟系统的一个关键组成部分是不能让时钟无限增长-因此需要定期以安全的方式回收时钟，以在容错性和存储需求之间保持平衡。

副本同步：gossip 和 Merkle 树

在 Dynamo 系统设计中，考虑到节点故障和网络分区的容错性，需要一种处理节点重新加入集群的方式，无论是在被分区后还是在替换或部分恢复失败的节点之后。

副本同步用于在故障后使节点保持最新状态，并定期使副本之间同步。

八卦（Gossip）是一种用于同步副本的概率性技术。通信模式（例如哪个节点与哪个节点联系）不是预先确定的。相反，节点具有尝试相互同步的概率 p。每隔 t 秒，每个节点选择一个节点进行通信。这提供了除同步任务（例如部分法定人数写入）之外的另一种机制，使副本保持最新。

八卦具有可扩展性，没有单点故障，但只能提供概率性的保证。

为了使副本同步过程中的信息交换更高效，Dynamo 使用一种称为 Merkle 树的技术，我将不详细介绍。关键思想是数据存储可以在多个不同的粒度级别上进行哈希：表示整个内容的哈希，一半的键，四分之一的键等等。

通过保持这种相当细粒度的哈希，节点可以比朴素技术更高效地比较其数据存储内容。一旦节点确定了哪些键具有不同的值，它们会交换必要的信息以使副本保持最新。

Dynamo 实践：概率有界陈旧性 (PBS)

这基本上涵盖了 Dynamo 系统的设计：

• 一致性哈希用于确定键的存放位置
• 部分法定人数用于读取和写入
• 通过向量时钟进行冲突检测和读修复
• 通过八卦进行副本同步

我们如何描述这样一个系统的行为？Bailis 等人（2012 年）的一篇相对较新的论文描述了一种称为 PBS（概率有界陈旧度）的方法，该方法使用模拟和从真实系统收集的数据来描述这样一个系统的预期行为。

PBS 通过使用反熵（gossip）速率、网络延迟和本地处理延迟的信息来估计不一致程度，从而估计读取的一致性水平的预期值。它已经在 Cassandra 中实现，在其他消息上附加了计时信息，并基于此信息的样本在蒙特卡洛模拟中计算出一个估计值。

根据该论文，在正常运行期间，最终一致性的数据存储通常更快，并且可以在几十到几百毫秒内读取一致的状态。下表描述了从 LinkedIn（SSD 和 15k RPM 磁盘）和 Yammer 的实证计时数据中，以不同的 R 和 W 设置下，以 99.9%的一致性读取概率所需的时间：

例如，在 Yammer 案例中，从 R=1 、 W=1 到 R=2 、 W=1 将不一致窗口从 1352 毫秒减少到 202 毫秒- 同时保持读取延迟（32.6 毫秒）低于最快的严格仲裁（ R=3 、 W=1 ；219.27 毫秒）。

有关更多详细信息，请查看 PBS 网站和相关论文。

无序编程

让我们回顾一下我们希望解决的情况的示例。第一个场景包括三个不同的服务器在分区后，当分区恢复时，我们希望这些服务器收敛到相同的值。亚马逊的 Dynamo 通过从 N 个节点中读取 R 个节点，然后执行读取协调操作来实现这一点。

在第二个示例中，我们考虑了一个更具体的操作：字符串连接。事实证明，没有已知的技术可以使字符串连接的结果达到相同的值，而不需要对操作进行排序（例如，不需要昂贵的协调）。然而，有些操作可以以任何顺序安全地应用，而简单的寄存器则无法做到这一点。正如 Pat Helland 所写：

……操作中心的工作可以通过正确的操作和正确的语义变得可交换，而简单的读取/写入语义则不适合可交换性。

例如，考虑一个实现简单会计系统的系统，其中借记和贷记操作以两种不同的方式实现：

• 使用具有读取和写入操作的寄存器
• 使用具有本地借记和贷记操作的整数数据类型

后一种实现对数据类型的内部有更多了解，因此它可以在操作被重新排序的情况下保留操作的意图。借记或贷记可以以任何顺序应用，最终结果是相同的：

1
2

100 + credit(10) + credit(20) = 130 and
100 + credit(20) + credit(10) = 130

但是，写入固定值不能按任何顺序完成：如果重新排序写入，则其中一个写入将覆盖另一个：

1
2

100 + write(110) + write(130) = 130 but
100 + write(130) + write(110) = 110

让我们采用本章开头的示例，但使用不同的操作。在这种情况下，客户端将消息发送到两个节点，这两个节点以不同的顺序查看操作：

1
2

[Clients]  --> [A]  1, 2, 3
[Clients]  --> [B]  2, 3, 1

假设我们正在寻找一组整数的最大值（例如 MAX()），而不是字符串连接。消息 1、2 和 3 是：

1
2
3

1: { operation: max(previous, 3) }
2: { operation: max(previous, 5) }
3: { operation: max(previous, 7) }

那么，如果没有协调，A 和 B 都会收敛到 7，例如：

1
2

A: max(max(max(0, 3), 5), 7) = 7
B: max(max(max(0, 5), 7), 3) = 7

在这两种情况下，两个副本都会以不同的顺序看到更新，但是无论顺序如何，我们都能够以具有相同结果的方式合并结果。由于我们使用了合并过程 ( max )，两种情况下的结果都会收敛到相同的答案。

编写适用于所有数据类型的合并过程可能是不可能的。在 Dynamo 中，值是一个二进制 blob，因此最好的办法就是公开它并要求应用程序处理每个冲突。

但是，如果我们知道数据属于更具体的类型，则处理此类冲突就成为可能。 CRDT 是一种数据结构，旨在提供始终收敛的数据类型，只要它们看到相同的操作集（以任何顺序）。

CRDT：聚合复制数据类型

CRDT（收敛复制数据类型）利用有关特定数据类型上特定操作的交换性和关联性的知识。

为了在副本仅偶尔通信的环境中使一组操作收敛于相同的值，这些操作需要与顺序无关并且对（消息）复制/重新传递不敏感。因此，他们的操作需要是：

• 关联 ( a+(b+c)=(a+b)+c )，因此分组并不重要
• 可交换 ( a+b=b+a )，因此应用程序的顺序并不重要
• 幂等 ( a+a=a )，因此重复并不重要

原来这些结构在数学中已经被称为"join"或"meet"半格。

格是一个具有明确的顶部（最小上界）和明确的底部（最大下界）的偏序集合。半格类似于格，但只有一个明确的顶部或底部。“join"半格具有明确的顶部（最小上界），而"meet"半格具有明确的底部（最大下界）。

任何可以表示为半格的数据类型都可以实现为保证收敛的数据结构。例如，计算一组值的最大值(max())将始终返回相同的结果，无论接收值的顺序如何，只要所有值最终都被接收到，因为最大值(max())操作是可结合的、可交换的和幂等的。

例如，下面是两个格的示例：一个用于表示集合，其中合并操作符是 union(items)；另一个用于表示严格递增的整数计数器，其中合并操作符是 max(values)：

1
2
3
4
5

   { a, b, c }              7
  /      |    \            /  \
{a, b} {b,c} {a,c}        5    7
  |  \  /  | /           /   |  \
  {a} {b} {c}            3   5   7

使用可以表示为半格的数据类型，您可以让副本以任何模式进行通信并以任何顺序接收更新，只要它们都看到相同的信息，它们最终就会就最终结果达成一致。这是一个强大的属性，只要满足先决条件，就可以得到保证。

然而，将数据类型表示为半格通常需要一定程度的解释。许多数据类型的操作实际上与顺序无关。例如，将项目添加到集合中是关联的、可交换的和幂等的。但是，如果我们还允许从集合中删除项目，那么我们需要某种方法来解决冲突的操作，例如 add(A) 和 remove(A) 。如果本地副本从未添加过某个元素，那么删除该元素意味着什么？该分辨率必须以与顺序无关的方式指定，并且有几种不同的选择和不同的权衡。

这意味着一些熟悉的数据类型具有更专业的实现，例如 CRDT，它们会进行不同的权衡，以便以与顺序无关的方式解决冲突。与仅处理寄存器（例如，从系统角度来看是不透明 blob 的值）的键值存储不同，使用 CRDT 的人必须使用正确的数据类型以避免异常。

指定为 CRDT 的不同数据类型的一些示例包括：

• 计数器

  • 仅增长计数器（合并 = max(值)；有效负载 = 单个整数）
  • 正负计数器（由两个增长计数器组成，一个用于增量，另一个用于减量）

• 寄存器

  • 最后写入获胜 -register（时间戳或版本号；merge = max(ts)；payload = blob）
  • 多值寄存器（矢量时钟；合并=两者兼而有之）

• 集合

  • 仅增长集（合并 = union(items)；有效负载 = 设置；不删除）
  • 两相集合（由两个集合组成，一个用于添加，另一个用于删除；元素可以添加一次，删除一次）
  • 独特集（两相集的优化版本）
  • 最后一次写入获胜设置（合并 = max(ts)；有效负载 = 设置）
  • 正负组（每组项目包含一个 PN 计数器）
  • 观察-移除集

• 图形和文本序列（参见论文）

为了确保无异常操作，您需要为您的特定应用程序找到正确的数据类型 - 例如，如果您知道您只会删除一个项目一次，那么两阶段集就可以工作；如果您只将项目添加到集合中并且从不删除它们，那么仅增长集合就可以了。

并非所有数据结构都有 CRDT 的实现，但在 Shapiro 等人最近（2011 年）的调查论文中，有布尔值、计数器、集合、寄存器和图形的 CRDT 实现。

有趣的是，寄存器实现直接与键值存储使用的实现相对应：最后写入获胜寄存器使用时间戳或某些等效项，并且简单地收敛到最大时间戳值；多值寄存器对应于保留、公开和协调并发更改的 Dynamo 策略。有关详细信息，我建议您查看本章延伸阅读部分中的论文。

CALM 定理

您提到的 CRDT 数据结构是基于一种认识，即可表示为半格的数据结构是收敛的。但是，编程不仅仅涉及状态的演化，除非您只是在实现一个数据存储。

显然，无序性是任何收敛计算的重要属性：如果数据项接收的顺序影响计算的结果，那么没有办法在不保证顺序的情况下执行计算。

然而，在许多编程模型中，语句的顺序并不起重要作用。例如，在 MapReduce 模型中，Map 和 Reduce 任务都被指定为无状态的元组处理任务，需要在数据集上运行。关于如何以及以什么顺序将数据路由到任务的具体决策并没有明确指定，而是由批处理作业调度器负责将任务安排在集群上运行。

类似地，在 SQL 中，我们只指定查询，而不指定查询的执行方式。查询只是任务的声明性描述，查询优化器负责找出执行查询的高效方式（跨多个机器、数据库和表）。

当然，这些编程模型并不像通用编程语言那样自由。MapReduce 任务需要在无环数据流程序中表达为无状态任务；SQL 语句可以执行相当复杂的计算，但很多东西很难用它来表达。

然而，从这两个示例可以清楚地看出，有许多种数据处理任务可以在声明性语言中表达，而不需要明确指定执行顺序。表达所需结果的编程模型，同时将语句的确切顺序交给优化器决定，往往具有无序性的语义。这意味着这样的程序可能可以在没有协调的情况下执行，因为它们依赖于接收到的输入，而不一定依赖于输入的特定顺序。

关键点是这样的程序可能可以在没有协调的情况下安全地执行。如果没有明确的规则来描述什么可以在没有协调的情况下执行，什么不能，在保证结果正确的前提下，我们无法实现一个程序。

这就是 CALM 定理的内容。CALM 定理基于对逻辑单调性和有用的最终一致性形式（如收敛性）之间关系的认识。它声明逻辑上单调的程序保证最终一致。

因此，如果我们知道某个计算在逻辑上是单调的，那么我们知道它也可以在没有协调的情况下安全地执行。

为了更好地理解这一点，我们需要将单调逻辑（或单调计算）与非单调逻辑（或非单调计算）进行对比。

单调性 如果句子 φ 是一组前提 Γ 的结论，那么它也可以从任何扩展 Γ 的前提集 Δ 中推断出来。 大多数标准逻辑框架都是单调的：在诸如一阶逻辑的框架中进行的任何推理，一旦经过演绎验证，就不会被新信息无效。非单调逻辑是一种不具备这一属性的系统，换句话说，某些结论可能会被学习新知识所否定。

在人工智能领域，非单调逻辑与可废弃推理相关联，即利用部分信息进行的断言可以被学习新知识所否定。例如，如果我们得知 Tweety 是一只鸟，我们会认为 Tweety 可以飞；但是如果我们后来得知 Tweety 是一只企鹅，那么我们就我明白您提到的 CALM 定理和单调性的概念。CALM 定理指出，在逻辑上单调的计算最终将达到一致状态。单调性是一个重要的特性，它表示当我们获得更多的信息时，我们的结论不会被否定。

在编程中，特定的编程模型可能是单调的，这意味着我们可以在没有协调的情况下安全地执行这些模型中的计算。例如，关系代数和 Datalog 是两种具有单调性的编程模型。

在关系代数和 Datalog 中，使用一组基本操作符进行的计算被认为是单调的，例如选择、投影、自然连接、交叉乘积、并集和递归 Datalog（不包含否定）。而使用更高级的操作符（否定、集合差、除法、全称量化、聚合）会引入非单调性。

这意味着在这些系统中使用许多操作符（例如 map、filter、join、union、intersection）的计算在逻辑上是单调的，因此可以在没有协调的情况下安全运行。而使用否定和聚合的表达式则不适合在没有协调的情况下运行。

确定计算是否单调并不容易，特别是对于传统的编程语言，其中顺序、选择和迭代是核心。因此，为了能够测试单调性并进行静态分析，需要不同类型的编程语言，这就是为什么设计了 Bloom 语言的原因。

总而言之，单调性在分布式系统中的执行是重要的，因为它可以减少协调的需要，并提高系统的性能。通过使用单调性进行静态分析，我们可以确定哪些部分的计算是单调的，并可以在没有协调的情况下运行，从而实现更高效、更可扩展的计算模型。

非单一性有什么好处？

单调性和非单调性之间的区别很有趣。例如，将两个数字相加是单调的，但计算包含数字的两个节点的聚合不是单调的。它们之间的区别在于一个是计算（将两个数字相加），而另一个是断言（计算聚合）。

计算和断言在本质上有所不同。计算是指执行计算或进行操作以获得结果的过程，它是通过遵循特定的规则和算法来进行的。计算是确定性的，给定相同的输入和操作，它总是会产生相同的输出。例如，将两个数字相加所遵循的加法规则是确定的，因此计算的结果总是一致的。

相反，断言是关于陈述或命题真实性的主张。它表达了对某个事实或知识的主观断定。断言是基于可用证据或假设的，并且可以根据不同的上下文或视角而变化。例如，关于"披萨是蔬菜"的陈述是一个断言，根据所约定的"蔬菜"的定义，可以评估其真实性或虚假性。

当推理关于断言时，涉及到各种假设和上下文。对于这个问题"披萨是蔬菜吗？"，我们需要考虑何时可以推断某个命题的真实性或虚假性。

有几种合理的回答，每个回答对应着对我们拥有的信息和我们应该如何处理它的不同假设。在不同的上下文中，我们接受了不同的答案。

在日常推理中，我们使用所谓的"开放世界假设”：我们假设我们并不知道一切，因此不能根据缺乏知识来得出结论。也就是说，任何陈述都可能为真、为假或未知。根据开放世界假设，我们不会从缺乏知识中得出否定的结论，而是持开放的态度，接受陈述可能为未知的可能性。

1
2
3
4
5
6

                                OWA +             |  OWA +
                                Monotonic logic   |  Non-monotonic logic
Can derive P(true)      |   Can assert P(true)    |  Cannot assert P(true)
Can derive P(false)     |   Can assert P(false)   |  Cannot assert P(true)
Cannot derive P(true)   |   Unknown               |  Unknown
or P(false)

在进行开放世界假设时，我们只能安全地断言我们可以从已知信息中推导出的内容。我们假设对世界的信息是不完全的。

首先，让我们看看我们知道推理是单调的情况。在这种情况下，我们拥有的任何（可能不完整的）知识都不会因为学习新知识而失效。因此，如果我们可以基于某种推理（例如，“含有两汤匙番茄酱的物品是蔬菜”和“比萨含有两汤匙番茄酱”）推断某个陈述为真，那么我们可以得出“比萨是蔬菜”的结论。同样，如果我们可以推断某个陈述为假，也是一样的。

然而，如果我们无法推导出任何结论 - 例如，我们掌握的知识集合只包含顾客信息，而没有关于比萨或蔬菜的任何信息 - 那么根据开放世界假设，我们必须说我们无法得出任何结论。

对于非单调知识，我们现在所知道的任何内容都有可能被否定。因此，即使我们可以从当前所知的内容中推导出真或假，我们也不能安全地得出任何结论。

然而，在数据库上下文中，以及在许多计算机科学应用中，我们更倾向于得出更明确的结论。这意味着采用了所谓的封闭世界假设：即不能显示为真的任何内容都被认为是假的。这意味着不需要明确声明为假。换句话说，我们假设拥有的事实数据库是完整（最小的），因此可以假设其中没有的任何内容都是假的。

例如，在封闭世界假设下，如果我们的数据库中没有旧金山到赫尔辛基之间的航班信息，那么我们可以安全地得出结论说不存在这样的航班。

我们需要另外一件事才能够做出明确的断言：逻辑封装。封装是一种推测的形式化规则。域封装假设已知实体就是全部实体。为了得出明确的结论，我们需要假设所知的实体就是全部实体。

1
2
3
4
5
6
7

                                CWA +             |  CWA +
                                Circumscription + |  Circumscription +
                                Monotonic logic   |  Non-monotonic logic
Can derive P(true)      |   Can assert P(true)    |  Can assert P(true)
Can derive P(false)     |   Can assert P(false)   |  Can assert P(false)
Cannot derive P(true)   |   Can assert P(false)   |  Can assert P(false)
or P(false)

特别是，非单调推理需要这个假设。只有在我们假设拥有完整信息的情况下，我们才能做出自信的断言，因为额外的信息可能会否定我们的断言。

这在实践中意味着什么呢？首先，单调逻辑可以在能够推导出一个句子为真（或假）时得出确定的结论。其次，非单调逻辑需要额外的假设：已知实体就是全部实体。

那么为什么表面上等价的两个操作会有所不同呢？为什么加法是单调的，而在两个节点上进行聚合计算却不是？因为聚合计算不仅计算总和，还断言它已经看到了所有的值。而要保证这一点，需要在节点之间进行协调，确保执行计算的节点确实在系统中看到了所有的值。

因此，为了处理非单调性，需要使用分布式协调来确保只有在了解所有信息之后才进行断言，或者在断言中附带警告，即结论可能在以后被否定。

处理非单调性对于表达能力非常重要。这归结为能够表达非单调的事物；例如，能够说某一列的总和是 X 是很好的。系统必须检测到这种计算需要全局协调边界，以确保我们已经看到了所有的实体。

纯粹的单调系统很少见。似乎大多数应用程序在拥有不完整数据时也是基于封闭世界假设运行的，而我们人类对此也没有意见。当一个数据库告诉你旧金山和赫尔辛基之间没有直达航班时，你可能会把它理解为“根据这个数据库，不存在直达航班”，但你并不排除现实中可能仍然存在这样一种航班的可能性。

事实上，只有在复制品出现分歧时（例如在分区期间或由于正常操作期间的延迟），这个问题才变得有趣。那时就需要更具体的考虑：答案是基于当前节点还是基于整个系统。

此外，由于非单调性是通过做出断言来引起的，许多计算似乎可以进行很长时间，只有在将某个结果或断言传递给第三方系统或最终用户时才应用协调。当然，并不需要在系统内的每个读写操作都强制执行总序，如果这些读写操作只是长时间运行计算的一部分，那么这是没有必要的。

布隆语言

Bloom 语言是一种旨在利用 CALM 定理的语言。它是一种 Ruby DSL，其形式基础是一种称为 Dedalus 的时序逻辑编程语言。

在 Bloom 中，每个节点都有一个由集合和格组成的数据库。程序被表示为与集合（事实集）和格（CRDT）交互的无序语句集。默认情况下，语句是与顺序无关的，但也可以编写非单调函数。

请访问 Bloom 网站和教程，了解有关 Bloom 的更多信息。

进一步阅读

CALM 定理、汇合分析和 Bloom

Joe Hellerstein 的演讲@RICON 2012 很好地介绍了该主题，Neil Conway 的演讲@Basho 也是如此。特别是对于 Bloom，请参阅 Peter Alvaro 的 talk@Microsoft。

• The Declarative Imperative: Experiences and Conjectures in Distributed Logic - Hellerstein, 2010
• Consistency Analysis in Bloom: a CALM and Collected Approach - Alvaro et al., 2011
• Logic and Lattices for Distributed Programming - Conway et al., 2012
• Dedalus: Datalog in Time and Space - Alvaro et al., 2011

CRDTs CRDT

Marc Shapiro’s talk @ Microsoft is a good starting point for understanding CRDT’s.

• CRDTs: Consistency Without Concurrency Control - Letitia et al., 2009
• A comprehensive study of Convergent and Commutative Replicated Data Types, Shapiro et al., 2011
• An Optimized conflict-free Replicated Set - Bieniusa et al., 2012

Dynamo; PBS；乐观复制

• Dynamo: Amazon’s Highly Available Key-value Store - DeCandia et al., 2007
• PNUTS: Yahoo!’s Hosted Data Serving Platform - Cooper et al., 2008
• The Bayou Architecture: Support for Data Sharing among Mobile Users - Demers et al. 1994
• Probabilistically Bound Staleness for Practical Partial Quorums - Bailis et al., 2012
• Eventual Consistency Today: Limitations, Extensions, and Beyond - Bailis & Ghodsi, 2013
• Optimistic replication - Saito & Shapiro, 2005