复制：弱一致性模型协议

现在我们已经看过可以在越来越现实的故障情况下强制单副本一致性的协议，让我们关注一下在放弃单副本一致性要求后所打开的选项世界。

总体而言，很难提出一个单一的维度来定义或表征允许副本分歧的协议。大多数此类协议具有高度可用性，关键问题在于最终用户是否发现这些保证、抽象和API对他们的目的有用，尽管在节点和/或网络故障发生时副本可能会分歧。

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

正如我在引言中所述，我认为分布式编程的很大一部分是处理分布的两个后果的影响：

信息以光速传播
独立的事物独立故障

信息传播速度的限制所带来的含义是，节点以不同的、独特的方式体验世界。在单个节点上的计算是简单的，因为所有事情都以可预测的全局总顺序发生。在分布式系统上的计算是困难的，因为没有全局总顺序。

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

当然，强制执行顺序是昂贵的。这在大规模互联网系统中尤其明显，因为系统需要保持可用性。强一致性系统的行为不像分布式系统：它表现得像一个单一系统，这在分区期间对可用性是不利的。

此外，对于每个操作，通常必须联系大多数节点——而且往往不仅一次，而是两次（正如你在2PC的讨论中看到的）。这在需要地理分布以为全球用户群提供足够性能的系统中尤其痛苦。

因此，默认情况下表现得像一个单一系统可能并不理想。

也许我们想要的是一个系统，在这个系统中，我们可以编写不使用昂贵协调的代码，并且仍然返回一个“可用”的值。我们将允许不同的副本彼此分歧——既为了保持效率，也为了容忍分区——然后尝试以某种方式处理这种分歧。

最终一致性表达了这个想法：节点可以在一段时间内彼此分歧，但最终它们将就值达成一致。

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

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

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

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

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

CALM（逻辑单调性的一致性）猜想是同一原则的另一种表达：它将逻辑单调性与收敛等同。如果我们可以得出某事是逻辑单调的，那么在没有协调的情况下运行也是安全的。合流分析——特别是应用于Bloom编程语言的合流分析——可以用来指导程序员决定何时以及在哪里使用强一致性系统的协调技术，以及何时可以安全地在没有协调的情况下执行。

Reconciling different operation orders

不强制单副本一致性的系统是什么样的？让我们通过查看几个例子来使这一点更加具体。

不强制单副本一致性的系统最明显的特征是它们允许副本彼此分歧。这意味着没有严格定义的通信模式：副本可以彼此隔离，但仍然保持可用并接受写入。

让我们想象一个由三个副本组成的系统，每个副本与其他副本隔离。例如，这些副本可能位于不同的数据中心，并因某种原因无法进行通信。在分区期间，每个副本仍然可用，接受来自某些客户端的读取和写入：

[Clients]   - > [A]

--- Partition ---

[Clients]   - > [B]

--- Partition ---

[Clients]   - > [C]

经过一段时间，分区恢复，副本服务器交换信息。它们从不同的客户端接收了不同的更新，彼此之间发生了分歧，因此需要进行某种形式的调和。我们希望发生的情况是，所有副本都收敛到相同的结果。

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

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

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

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

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

那么，在没有协调的情况下，A将生成“Hello World！”，而B将生成“World!Hello ”。

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

这当然是错误的。我们希望发生的情况是，副本收敛到相同的结果。

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

亚马逊的Dynamo

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

Dynamo是一个最终一致的、高可用的键值存储。键值存储就像一个大型哈希表：客户端可以通过set(key, value)设置值，并使用get(key)按键检索它们。Dynamo集群由N个对等节点组成；每个节点负责存储一组键。

Dynamo优先考虑可用性而非一致性；它不保证单副本一致性。相反，当写入值时，副本可能会彼此分歧；当读取一个键时，会有一个读取调和阶段，试图在将值返回给客户端之前调和副本之间的差异。

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

由于Dynamo是一个完整的系统设计，除了核心复制任务之外，还有许多不同的部分可以查看。下面的图表说明了一些任务；特别是，写入如何路由到节点并写入多个副本。

[ 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（例如，每个值总共有三个副本）；这意味着用户可以选择：

 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 和 W = N/2 + 1：对两者都有利

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

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

Basho 的 Riak（N = 3，R = 2，W = 2 默认）
Linkedin 的 Voldemort（N = 2 或 3，R = 1，W = 1 默认）
Apache 的 Cassandra（N = 3，R = 1，W = 1 默认）

还有另一个细节：在发送读取或写入请求时，是否要求所有 N 个节点响应（Riak），还是仅要求满足最小数量的节点（例如 R 或 W；Voldemort）。”发送到所有”的方法更快且对延迟的敏感性较低（因为它只等待 N 中最快的 R 或 W 节点），但效率较低，而”发送到最小”的方法对延迟更敏感（因为与单个节点通信的延迟会延迟操作），但效率更高（总体消息/连接更少）。

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

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

不。

这并不是完全错误：一个满足R + W > N的系统可以检测读/写冲突，因为任何读取法定人数和任何写入法定人数都有一个共同的成员。例如，至少有一个节点在两个法定人数中：

   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变体。

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

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

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

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

此外，实际向量时钟系统的一个关键组成部分是时钟不能无限增长——因此需要有一个程序来定期以安全的方式进行时钟的垃圾回收，以平衡容错性和存储要求。

副本同步：八卦和Merkle树

鉴于Dynamo系统设计能够容忍节点故障和网络分区，它需要一种方法来处理节点在被分区后重新加入集群，或者在故障节点被替换或部分恢复时。

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

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

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

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

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

Dynamo在实践中：概率性有界过时性（PBS）

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

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

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

PBS通过使用有关反熵（八卦）速率、网络延迟和本地处理延迟的信息来估计不一致的程度，以估计读取的一致性水平。它已在Cassandra中实现，其中时间信息附加在其他消息上，并根据蒙特卡洛模拟中的此信息样本计算估计值。

根据论文，在正常操作期间，最终一致的数据存储通常更快，并且可以在数十或数百毫秒内读取一致状态。下表说明了在LinkedIn（SSD和15k RPM磁盘）和Yammer的经验时间数据中，给定不同R和W设置时，99.9%概率一致读取所需的时间：

例如，在Yammer的情况下，从R=1，W=1到R=2，W=1将不一致窗口从1352毫秒减少到202毫秒——同时保持读取延迟低于最快的严格法定人数（R=3，W=1；219.27毫秒）。

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

无序编程

让我们回顾一下我们希望解决的情况的例子。第一个场景由三个不同的服务器组成，处于分区状态；在分区恢复后，我们希望服务器收敛到相同的值。亚马逊的Dynamo使这成为可能，通过从R个N节点读取并执行读取调和。

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

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

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

使用具有read和write操作的寄存器，以及
使用具有本地debit和credit操作的整数数据类型

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

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

然而，写入一个固定值不能以任何顺序进行：如果写入被重新排序，其中一个写入将会覆盖另一个写入：

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

让我们以本章开头的例子为基础，但是使用一个不同的操作。在这个场景中，客户端向两个节点发送消息，这两个节点看到的操作顺序不同：

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

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

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

然后，在没有协调的情况下，A和B都将收敛到7，例如：

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

在这两种情况下，两个副本以不同的顺序看到更新，但我们能够以一种方式合并结果，使得尽管顺序不同，结果仍然相同。由于我们使用的合并程序（max），结果在两种情况下都收敛到相同的答案。

很可能不可能编写一个适用于所有数据类型的合并程序。在Dynamo中，一个值是一个二进制大对象，所以最好的做法是暴露它，并要求应用程序处理每个冲突。

然而，如果我们知道数据是更具体的类型，处理这些类型的冲突就变得可能。CRDT（Conflict-free Replicated Data Types，无冲突复制数据类型）是设计用来提供数据类型的，只要它们看到相同的操作集（以任何顺序），就总是会收敛。

CRDTs：收敛的复制数据类型

CRDTs（收敛的复制数据类型）利用了关于特定数据类型上特定操作的交换律和结合律的知识。

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

结合的（a+(b+c)=(a+b)+c），这样分组就不重要了
交换的（a+b=b+a），这样应用的顺序就不重要了
幂等的（a+a=a），这样重复就不重要了

事实证明，这些结构在数学中已经为人所知；它们被称为并集或交集半格。

格是一个具有明确顶部（最小上界）和明确底部（最大下界）的部分有序集。半格就像一个格，但它只有一个明确的顶部或底部。并集半格是具有明确顶部（最小上界）的半格，交集半格是具有明确底部（最大下界）的半格。

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

例如，这里有两个格：一个是为集合绘制的，合并操作符是union(items)；另一个是为严格递增的整数计数器绘制的，合并操作符是max(values)：

   { 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(values)；有效载荷 = 单个整数）
- 正负计数器（由两个增长计数器组成，一个用于递增，另一个用于递减）
寄存器
- 最后写入胜利寄存器（时间戳或版本号；合并 = max(ts)；有效载荷 = blob）
- 多值寄存器（向量时钟；合并 = 两者都取）
集合
- 仅增长集合（合并 = union(items)；有效载荷 = 集合；无删除）
- 两阶段集合（由两个集合组成，一个用于添加，另一个用于删除；元素可以添加一次并删除一次）
- 唯一集合（两阶段集合的优化版本）
- 最后写入胜利集合（合并 = max(ts)；有效载荷 = 集合）
- 正负集合（由每个集合项一个PN计数器组成）
- 观察到的删除集合
图和文本序列（见论文）

为了确保无异常操作，你需要为你的特定应用找到正确的数据类型——例如，如果你知道你只会删除一次项目，那么两阶段集合就有效；如果你只会向集合添加项目而从不删除它们，那么仅增长集合就有效。

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

有趣的是，寄存器实现直接对应于键值存储使用的实现：最后写入胜利寄存器使用时间戳或某种等效物，并简单地收敛到最大时间戳值；多值寄存器对应于Dynamo策略，保留、暴露和调和并发更改。有关详细信息，我建议你查看本章进一步阅读部分的论文。

CALM定理

CRDT数据结构基于一个认识：可以用半格表示的数据结构是收敛的。但是编程不仅仅是状态的演变，除非你只是在实现一个数据存储。

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

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

同样，在SQL中，人们指定了查询，但没有指定如何执行查询。查询只是任务的声明性描述，查询优化器的任务是找出执行查询的有效方法（跨多个机器、数据库和表）。

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

然而，从这两个例子中应该清楚，有许多类型的数据处理任务适合用声明性语言表达，在这种语言中执行的顺序并没有明确指定。编程模型表达了期望的结果，同时让优化器决定语句的确切执行顺序，这些模型的语义通常是顺序无关的。这意味着这样的程序可能可以在没有协调的情况下执行，因为它们依赖于它们接收的输入，但不一定依赖于接收输入的具体顺序。

关键点是，这样的程序_可能_在没有协调的情况下安全执行。没有一个明确的规则来表征什么可以在没有协调的情况下安全执行，什么不可以，我们就不能在确保结果正确的情况下实现程序。

这就是CALM定理的内容。CALM定理基于逻辑单调性和有用形式的最终一致性（例如，汇合/收敛）之间的联系的认识。它指出，逻辑上单调的程序保证最终是一致的。

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

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

单调性 > 如果句子φ是一组前提Γ的结果，那么它也可以从任何扩展了Γ的前提集Δ中推断出来。

大多数标准逻辑框架都是单调的：一旦在一组框架内（如一阶逻辑）做出的推理是演绎有效的，就不能被新信息推翻。非单调逻辑是一个系统，在该系统中不持有该属性——换句话说，如果一些结论可以通过学习新知识而被推翻。

在人工智能领域，非单调逻辑与可反驳推理相关联——推理，在这种推理中，利用部分信息做出的断言可以通过新知识被推翻。例如，如果我们得知Tweety是一只鸟，我们会假设Tweety可以飞；但如果我们后来得知Tweety是一只企鹅，那么我们就不得不修正我们的结论。

单调性关注前提（或关于世界的事实）和结论（或关于世界的断言）之间的关系。在单调逻辑中，我们知道我们的结果是无需撤回的：单调计算不需要重新计算或协调；答案随着时间的推移会变得更加准确。一旦我们知道Tweety是一只鸟（并且我们使用单调逻辑进行推理），我们可以安全地得出结论Tweety可以飞，而且我们学到的任何知识都不能推翻这个结论。

虽然任何产生面向人类结果的计算都可以被解释为关于世界的断言（例如，”foo”的值是”bar”），但很难确定基于冯·诺伊曼机器的编程模型中的计算是否是单调的，因为事实与断言之间的关系以及这些关系是否是单调的并不完全清楚。

然而，对于一些编程模型来说，确定单调性是可能的。特别是，关系代数（例如，SQL的理论基础）和Datalog提供了表达能力很强的语言，这些语言有很好理解的解释。

基本的Datalog和关系代数（即使带有递归）被认为是单调的。更具体地说，使用一组特定的基本操作符表达的计算被认为是单调的（选择、投影、自然连接、交叉乘积、联合和没有否定的递归Datalog），而非单调性是通过使用更高级的操作符（否定、集合差、除法、全称量化、聚合）引入的。

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

重要的是要认识到非单调性和在分布式系统中执行起来代价高昂的操作之间的联系。具体来说，[分布式聚合]和[协调协议]都可以被视为一种否定。正如Joe Hellerstein所写：

要在分布式环境中确定一个否定谓词的真实性，评估策略必须从”计数到0”开始以确定空性，并等待分布式计数过程明确终止。聚合是这个想法的概括。

并且：

这个想法也可以从另一个方向看到。协调协议本身就是聚合，因为它们涉及投票：两阶段提交需要一致同意，Paxos共识需要多数票，拜占庭协议需要2/3多数票。等待需要计数。

如果我们能够以一种可以测试单调性的方式表达我们的计算，那么我们可以执行全程序静态分析，检测程序的哪些部分是最终一致的并且可以在没有协调的情况下安全运行（单调部分）——以及哪些部分不是（非单调部分）。

请注意，这需要一种不同的语言，因为这些推论对于传统编程语言来说是很难做出的，在传统编程语言中，序列、选择和迭代是核心。这就是为什么设计了Bloom语言。

非单调性有什么用？

单调性和非单调性之间的区别很有趣。例如，加两个数是单调的，但是计算包含数字的两个节点上的聚合就不是。区别在哪里？其中一个是一个计算（加两个数），而另一个是一个断言（计算聚合）。

计算和断言有什么区别？让我们考虑查询“披萨是蔬菜吗？”。要回答这个问题，我们需要深入了解：何时可以接受推断某事是（或不是）真的？

有几个可接受的答案，每个答案都对应于关于我们所拥有的信息以及我们应该如何行动的不同假设集——我们在不同的上下文中接受了不同的答案。

在日常推理中，我们做出所谓的开放世界假设：我们假设我们不知道一切，因此不能从缺乏知识中得出结论。也就是说，任何句子都可能是真的、假的或未知的。

                                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)

当我们做出开放世界假设时，我们只能安全地断言我们可以从已知信息中推导出的内容。我们关于世界的信息被假定为不完整的。

让我们首先看看我们知道我们的推理是单调的情况。在这种情况下，我们所拥有的任何（可能不完整的）知识都不能因为学习新知识而被推翻。因此，如果我们能够基于某些推导推断出一个句子是真的，比如“含有两汤匙番茄酱的东西是蔬菜”和“披萨含有两汤匙番茄酱”，那么我们可以得出结论“披萨是蔬菜”。同样的推理也适用于如果我们能推断出一个句子是假的。

然而，如果我们无法推导出任何内容——例如，我们所拥有的知识集包含了客户信息，但关于披萨或蔬菜的信息却一无所知——那么在开放世界假设下我们必须说我们无法得出任何结论。

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

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

例如，在CWA下，如果我们的数据库中没有从旧金山到赫尔辛基的航班条目，那么我们可以安全地得出结论，没有这样的航班存在。

为了能够做出明确的断言，我们还需要一样东西：逻辑限定。限定是一种形式化的猜想规则。领域限定猜想已知实体就是所有的实体。我们需要能够假设已知实体就是所有的实体，以便得出明确的结论。

                                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语言

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

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

访问Bloom网站和tutorials以了解更多关于Bloom的信息。