Distributed systems for fun and profit翻译-5. Replication: weak consistency model protocols

原文地址：http://book.mixu.net/distsys/eventual.html

现在，我们已经研究了在一组越来越现实的受支持的故障情况下可以强制实现单拷贝一致性的协议，让我们把注意力转向一旦我们放弃单拷贝一致性的要求就会打开的选项世界。

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

为什么弱一致系统不更受欢迎？

正如我在导言中所说，我认为分布式编程的大部分内容都是关于处理分布式的两个后果的含义：

• 信息以光速传播
• 独立的事物独立地失败

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

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

当然，问题是执行命令的成本很高。这一点在大规模的互联网系统中尤为突出，因为系统需要保持可用。执行强一致性的系统的行为不像分布式系统：它的行为像单个系统，这对分区期间的可用性不利。

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

因此，在默认情况下表现得像一个单一的系统可能是不可取的。

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

最终一致性表达了这一观点：节点可以在一段时间内彼此分离，但最终它们将在值上达成一致。

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

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

近年来，提供单副本一致性的最有影响力的系统设计是Amazon的Dynamo，我将以他为例提供最终一致性和概率保证的系统进行讨论。

强力保证的最终一致性。这种类型的系统保证结果收敛到一个公共值，相当于一些正确的顺序执行。换言之，这样的系统不会产生任何异常结果；没有任何协调，您可以构建同一服务的副本，这些副本可以以任何模式进行通信，并以任何顺序接收更新，只要它们都看到相同的信息，它们最终将同意最终的结果。

CRDT（convergent replicated data types）是不管网络延迟、分区和消息重新排序如何都能保证收敛到相同值的数据类型。它们可以证明是收敛的，但是可以实现为CRDT的数据类型是有限的。

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

不同顺序操作的对账

不强制单副本一致性的系统是什么样子的？让我们看几个例子来试着使这更具体。
不强制实现单拷贝一致性的系统最明显的特征可能是它们允许副本彼此分离。这意味着没有严格定义的通信模式：副本可以彼此分离，但仍可以继续使用并接受写操作。

让我们设想一个由三个副本组成的系统，每个副本都被从其他副本中分割出来。例如，副本可能位于不同的数据中心，并且由于某种原因无法通信。在分区期间，每个副本都保持可用，接受来自某些客户端集的读写操作：

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

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

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

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

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

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

Amazon’s Dynamo

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

Dynamo是一个最终一致的、高度可用的K/V存储。键值存储类似于一个大型哈希表：客户机可以通过set（key，value）设置值，并使用get（key）按key检索值。Dynamo集群由N个对等节点组成，每个节点有一组密钥，负责存储这些密钥。

Dynamo优先考虑可用性而不是一致性；它不能保证单拷贝一致性。相反，在写入值时，副本可能会彼此分离；在读取密钥时，存在一个读取协调阶段，该阶段在将值返回给客户端之前尝试协调副本之间的差异。

对于Amazon上的许多功能来说，避免中断比确保数据完全一致更为重要，因为中断可能导致业务损失和信誉损失。此外，如果数据不是特别重要，那么弱一致性系统可以以比传统RDBMS更低的成本提供更好的性能和更高的可用性。

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

在研究了写操作最初是如何被接受的之后，我们将研究如何检测冲突，以及异步副本同步任务。此任务是必需的，因为高可用性设计中的节点可能暂时不可用（关闭或分区）。副本同步任务确保节点即使在失败后也能相当快地赶上。

一致性哈希

无论我们是在读还是在写，首先需要做的是我们需要找到数据应该在系统上的位置。这需要某种类型的K/V映射。

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

部分仲裁（Partial quorums）

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

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

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

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

• 用户可以选择写操作成功所需的节点数（W/N）
• 用户可以指定在读操作期间要联系的节点数（R/N）。

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

通常的建议是R+W>N，因为这意味着读和写队列在一个节点上重叠—这使得返回过时值的可能性降低。典型的配置是N=3（例如，每个值总共有三个副本）；这意味着用户可以在以下两个选项中进行选择：

更一般地，再次假设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’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）。“发送到所有”方法更快，对延迟的敏感度更低（因为它只有等待N中最快的R个或W个节点），但效率也更低。虽然“发送给最少”方法对延迟更敏感（因为与单个节点通信的延迟会延迟操作），但也更高效（总体上消息/连接更少）。

当读写指令重叠时会发生什么情况，例如（R+W>N）？具体地说，人们常说这会导致“强一致性”。

R+W>N是否与“强一致性”相同？

不

它不是完全脱离基础的：一个R+W>N可以检测读/写冲突的系统，因为任何读仲裁和任何写仲裁共享一个成员。也就是说两个仲裁中至少有一个共同节点：

这保证了先前的写入将被随后的读取看到。但是，这只在N中的节点永远不变的情况下有效。因此，Dynamo不符合条件，因为在Dynamo中，如果节点失败，集群成员资格可能会改变。

Dynamo的设计总是可写的。它有一种机制，当原始服务器关闭时，通过向负责某些密钥的节点集中添加不同的、不相关的服务器来处理节点故障。这意味着，不再保证仲裁总是重叠的。即使R=W=N也不符合条件，因为当仲裁大小等于N时，这些仲裁中的节点可以在故障期间更改。具体地说，在分区期间，如果无法达到足够数量的节点，Dynamo将从不相关但可访问的节点向仲裁添加新节点。

此外，Dynamo处理分区的方式与执行强一致性模型的系统不同：也就是说，分区的两边都允许写操作，这意味着至少有一段时间系统不会充当单个副本。因此，称R+W>N为“强一致性”是误导性的；保证仅仅是概率性的——这不是强一致性所指的。

冲突检测和读取修复

允许复制副本分离的系统必须有办法最终协调两个不同的值。正如在部分仲裁方法中简要提到的，一种方法是在读取时检测冲突，然后应用一些冲突解决方法。但这是怎么做到的？
一般来说，这是通过跟踪一段数据的因果历史来完成的，方法是用一些元数据对其进行补充。客户端在从系统读取数据时必须保留元数据信息，在写入数据库时必须返回元数据值。

我们已经提过了一种方法：矢量时钟可以用来表示一个值的历史。事实上，这就是最初的Dynamo设计用来检测冲突的地方。

然而，使用矢量时钟并不是唯一的选择。如果您查看许多实际的系统设计，您可以通过查看它们跟踪的元数据来推断它们是如何工作的。

没有元数据。当系统不跟踪元数据，只返回值（例如，通过客户端API）时，它不能真正对并发写做任何特殊的事情。一个常见的规则是最后一个写操作获胜：换句话说，如果两个写操作同时写，那么只有最慢的写操作的值才会被保留下来。

时间戳。名义上，具有更高时间戳值的值获胜。然而，如果时间没有被仔细地同步，许多奇怪的事情可能会发生，从一个有故障或快时钟的系统的旧数据覆盖新的值。Facebook的Cassandra是一个Dynamo变体，它使用时间戳而不是矢量时钟。

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

矢量时钟。使用矢量时钟，可以检测到并发和过期的更新。然后执行读取修复就成为可能，尽管在某些情况下（并发更改），我们需要要求客户机选择一个值。这是因为如果更改是并发的，并且我们对数据一无所知（就像简单的keyvalue存储一样），那么请求比任意丢弃数据要好。

当读取一个值时，客户机联系N个节点中的R个，并要求它们提供密钥的最新值。它接受所有响应，丢弃严格意义上较旧的值（使用矢量时钟值来检测）。如果只有一个唯一的向量时钟+值对，则返回该值。如果同时编辑了多个矢量时钟+值对（例如不可比较），则返回所有这些值。

如上所述，读取修复可能返回多个值。这意味着客户机/应用程序开发人员偶尔必须通过基于某些特定于用例的标准选择一个值来处理这些情况。

此外，实用矢量时钟系统的一个关键组成部分是，时钟不能永远增长，因此需要有一个程序，偶尔以安全的方式对时钟进行垃圾收集，以平衡容错性和存储需求。

副本同步：gossip和Merkle树

考虑到Dynamo 的设计能够容忍节点故障和网络分区，因此需要一种方法来处理分区后或故障节点被替换或部分恢复时重新加入集群的节点。

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

gossip是一种同步副本的概率技术。通信模式（例如，哪个节点与哪个节点接触）不是预先确定的。相反，节点以p的概率尝试相互同步。每t秒，每个节点选择一个要与之通信的节点。这提供了同步任务（例如，部分仲裁写入）之外的附加机制，使副本保持最新。

gossip是可伸缩的，没有单一的失败点，但只能提供概率保证。

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

通过维护这种相当细粒度的散列，节点可以比简单的技术更有效地比较其数据存储内容。一旦节点识别出哪些密钥具有不同的值，它们就交换必要的信息来更新副本。

实践中的Dynamo：概率有界陈旧性（PBS）

这几乎涵盖了Dynamo系统的设计：

• 一致性HASH来确定密钥位置，
• 读写冲突仲裁
• 通过向量时钟进行冲突检测和读取修复
• 使用gossip来进行副本同步

我们如何描述这样一个系统的行为？Bailis等人最近发表的一篇论文。（2012）描述了一种称为PBS（概率有界陈旧性）的方法，该方法使用从真实系统收集的仿真和数据来描述此类系统的预期行为。

PBS利用反熵（gossip）速率、网络延迟和本地处理延迟等信息来估计读取的预期一致性水平，从而估计不一致程度。它已经在Cassandra中实现了，在Cassandra中，时间信息被其他消息所承载，并且在Monte Carlo模拟中基于此信息的样本计算估计值。

基于这篇文章，在正常操作过程中，最终一致性数据存储通常更快，并且可以在几十毫秒或几百毫秒内读取一致性状态。下表显示了在LinkedIn（固态硬盘和15k RPM磁盘）和Yammer的经验计时数据上，给定不同的R和W设置，99.9%的一致读取概率所需的时间：

例如，在Yammer情况下从R=1，W=1变为R=2，W=1将不一致窗口从1352 ms减少到202 ms，同时保持读取延迟低于最快的严格仲裁（R=3，W=1；219.27 ms）。

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

无序程序设计

让我们回顾一下我们希望解决的各种情况的例子。第一个场景由分区后面的三个不同服务器组成；分区修复后，我们希望服务器收敛到相同的值。Amazon的Dynamo通过从N个节点中的R读取数据，然后执行读取协调来实现这一点。

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

以操作为中心的工作可以进行交换（使用正确的操作和正确的语义），而一个简单的读/写语义却不适合进行交换。

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

• 使用寄存器进行读写操作，
• 使用整数数据类型进行本机借方和贷方操作

后一个实现更了解数据类型的内部，因此它可以保留操作的意图，尽管操作被重新排序。借记或贷记可按任何顺序应用，且最终结果相同

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

让我们回到本章开始举的例子，但是使用不同的操作。在这种情况下，客户机向两个节点发送消息，这两个节点按不同的顺序查看操作：

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

然后，如果没有协调，A和B都会收敛到7，例如。

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

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

但是，如果我们知道数据属于更特定的类型，那么就有可能处理这些类型的冲突。CRDT是一种数据结构，设计用于提供总是收敛的数据类型，只要它们看到相同的操作集（以任何顺序）。

CRDTs：收敛复制数据类型

CRDTs（convergent replicated datatypes）利用有关特定数据类型上特定操作的交换性和关联性的知识。

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

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

这些结构在数学中已经是已知的；它们被称为join或meet semilattice。格是一个部分序集，具有不同的顶（最小上界）和不同的底（最大下界）。semilattice就像一个格，但只有一个独特的顶部或底部。join semilattice是具有不同顶部（最小上界）的半格，而meet semilattice是具有一个底部（最大下界）的半格。

任何表示为semilattice的数据类型都可以实现为保证收敛性的数据结构。例如，只要最终接收到所有值，计算一组值的max（）将始终返回相同的结果，而不管接收值的顺序如何，因为max（）操作是关联的、可交换的和等幂的。

例如，这里有两个格：一个为集合绘制，其中合并运算符是并集（项），另一个为严格递增的整数计数器绘制，其中合并运算符是max（值）：

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

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

这意味着几种常见的数据类型都有更为特殊的实现，如CRDT，为了以与顺序无关的方式解决冲突，CRDT会做出不同的权衡。与只处理寄存器的键值存储不同（例如，从系统的角度来看是不透明的blob值），使用CRDTs的人必须使用正确的数据类型来避免异常。

CRDT包含的数据类型的一些示例包括：

• 计数器
• • 仅增长计数器（merge=max（values）；payload=single integer）
• • 正负计数器（由两个增长计数器组成，一个用于递增，另一个用于递减）
• 寄存器
• • 最后写入获胜-寄存器（时间戳或版本号；merge=max（ts）；payload=blob）
• • 多值寄存器（矢量时钟；merge=两个都要）
• 集合
• • 仅增长集合（merge=union（items）；payload=set；没有删除）
• • 两阶段集合（由两个集合组成，一个用于添加，另一个用于删除；元素可以添加一次，删除一次）
• • 唯一集合（Unique set）（两阶段集合的优化版本）
• -最后写入获胜集合（merge=max（ts）；payload=set）
• • 正负集（每个集合项包含一个PN计数器）
• • 观察-移除集合（Observed-remove set）
• 图和文本序列（见论文）

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

并不是所有的数据结构都被称为CRDTs，但是在Shapiro等人最近（2011年）的调查报告中，有针对布尔值、计数器、集合、寄存器和图的CRDT实现。

有趣的是，寄存器实现与键值存储使用的实现直接对应：最后一次写入获胜寄存器使用时间戳或一些等效的时间戳，并简单地收敛到最大的时间戳值；多值寄存器对应于保留、公开和协调并发更改的动态策略。关于细节，我建议你看一下本章进一步阅读部分的文章。

CALM定理

CRDT数据结构的基础是认识到可表示为semilattice的数据结构是收敛的。但是编程不仅仅是进化状态，除非你只是实现一个数据存储。

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

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

类似地，在SQL中，一个指定查询，而不是如何执行查询。查询只是对任务的声明性描述，查询优化器的工作是找出执行查询的有效方法（跨多台计算机、数据库和表）。
当然，这些编程模型并不像通用编程语言那样宽容。MapReduce任务需要在非循环数据流程序中表示为无状态任务；SQL语句可以执行相当复杂的计算，但许多东西很难在其中表示。

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

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

这就是CALM定理的意义所在。CALM定理是基于对逻辑单调性和最终一致性的有用形式（如合流/收敛）之间联系的认识。它指出逻辑单调的程序保证最终是一致的。

然后，如果我们知道某些计算在逻辑上是单调的，那么我们知道在没有协调的情况下执行也是安全的。为了更好地理解这一点，我们需要对比单调逻辑（或单调计算）和非单调逻辑（或非单调计算）。

单调

如果句子“φ”是一组前提“Γ”的结果，那么也可以从延伸“Γ”的任何一组前提“Γ”中推断出来

大多数标准逻辑框架都是单调的：在一阶逻辑等框架内作出的任何推论，一旦演绎有效，就不能被新的信息推翻。非单调逻辑是这样一个系统，在这个系统中，如果某些结论可以通过学习新知识而无效，那么这个属性就不成立。

在人工智能领域中，非单调逻辑与不可行的推理-推理联系在一起，其中利用部分信息做出的断言可以被新知识失效。例如，如果我们知道Tweety是一只鸟，我们会假设Tweety可以飞；但是如果我们后来知道Tweety是一只企鹅，那么我们就必须修改我们的结论。

单调性涉及前提（或关于世界的事实）和结论（或关于世界的断言）之间的关系。在单调逻辑中，我们知道我们的结果是无伸缩的：单调计算不需要重新计算或协调；随着时间的推移，答案会变得更加精确。一旦我们知道Tweety是一只鸟（我们正在使用单调逻辑进行推理），我们就可以安全地得出结论，Tweety可以飞，我们所学的任何东西都不能使这个结论失效。

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

然而，有许多编程模型可以确定单调性。特别是，关系代数（如SQL的理论基础）和数据日志提供了高度表达性的语言，这些语言有很好的解释。

基本数据日志和关系代数（即使是递归）都是单调的。更具体地说，使用某一组基本运算符表示的计算已知是单调的（选择、投影、自然连接、交叉积、并集和递归数据日志，不带否定（selection, projection, natural join, cross product,union and recursive Datalog without negation）），使用更高级的运算符（否定、集差、除、通用量化，聚合 (negation, set difference, division, universal
quantification, aggregation)）引入了非单调逻辑。

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

认识到在分布式系统中实现非单调性与代价昂贵的操作之间的联系是非常重要的。具体来说，分布式聚合和协调协议都可以看作是一种否定形式。正如Joe Hellerstein所写：

要在分布式环境中建立否定谓词的准确性，计算策略必须开始“计数为0”以确定空性，并等待分布式计数过程确定结束。聚合是这种思想的概括。
这个想法也可以从另一个角度看出来。协调协议本身就是聚合，因为它们需要投票：两阶段提交需要一致投票，Paxos共识需要多数票，拜占庭协议需要2/3多数票。等待需要计数。

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

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

非单调性有什么好处？

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

计算与断言有何不同？让我们考虑一下“比萨是蔬菜吗？”。为了回答这个问题，我们需要从核心出发：什么时候可以推断出某件事是（或不是）真的？

有几个可以接受的答案，每一个都对应于一组关于我们所拥有的信息和我们应该如何处理这些信息的不同假设，并且我们已经在不同的上下文中接受了不同的答案。

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

当我们做出开放世界的假设时，我们只能安全地断言一些我们可以从已知事物中推断出来的东西。我们关于世界的信息被认为是不完整的。

让我们先看看我们知道我们的推理是单调的情况。在这种情况下，我们所拥有的任何（潜在的不完整）知识都不能通过学习新知识而失效。因此，如果我们能根据一些推论推断出一个句子是真的，比如“含有两汤匙番茄酱的东西是蔬菜”和“比萨含有两汤匙番茄酱”，那么我们就可以得出“比萨是蔬菜”的结论。如果我们能推断出一个句子是错误的，情况也是一样的。

然而，如果我们不能推断出任何东西——例如，我们拥有的知识集合包含客户信息，而没有关于比萨饼或蔬菜的信息——那么在开放世界的假设下，我们不得不说，我们不能得出任何结论。

有了非单调知识，我们现在所知道的一切都有可能失效。因此，我们不能安全地得出任何结论，即使我们能够从我们目前所知道的推断出真假。

然而，在数据库环境中，在许多计算机科学应用中，我们更愿意作出更明确的结论。这意味着假设所谓的封闭世界假设：任何不能被证明是真的东西都是假的。这意味着不需要明确的虚假声明。换言之，我们假设的事实数据库是完整的（最小的），因此它中没有的任何东西都可以假设是错误的。

例如，根据CWA，如果我们的数据库没有旧金山和赫尔辛基之间航班的条目，那么我们可以安全地得出结论，不存在这样的航班

我们还需要一件事才能做出明确的断言：逻辑限制（ logical circumscription.）。限制是一种形式化的猜想规则。域限定猜想已知的实体都存在。我们需要能够假设已知的实体都存在，以便得出明确的结论

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

这在实践中意味着什么？首先，单调逻辑只要能证明一个句子是真（或假）的，就可以得出明确的结论。第二，非单调逻辑需要一个额外的假设：已知的实体都存在。

那么为什么表面上的两个操作是等价的呢？为什么加两个数是单调的，但计算两个节点上的聚合不是单调的？因为聚合不仅计算一个和，而且还断言它看到了所有的值。保证这一点的唯一方法是跨节点协调，并确保执行计算的节点真正看到了系统中的所有值。

因此，为了处理非单调性，我们需要使用分布式协调来确保断言是在所有信息都知道之后才做出的，或者做出带有警告的断言，即结论可以在以后失效。

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

纯单调系统是罕见的。似乎大多数应用程序都是在封闭世界的假设下运行的，即使它们有不完整的数据，我们人类对此很满意。当一个数据库告诉你旧金山和赫尔辛基之间不存在直飞航班时，你可能会将其视为“根据这个数据库，没有直飞航班”，但你不排除在现实中这种航班仍然存在的可能性。

实际上，只有当复制副本可以分离时（例如，在分区期间或由于正常操作期间的延迟），这个问题才会变得有趣。然后需要更具体的考虑：答案是仅仅基于当前节点，还是基于整个系统。

此外，由于非单调性是由断言引起的，因此许多计算可能会持续很长时间，并且仅在将某些结果或断言传递给第三方系统或最终用户时应用协调似乎是合理的。当然，如果系统中的每个读写操作只是长时间运行计算的一部分，则在每一个读写操作时不必强制按总顺序执行。

Bloom语言

Bloom语言是一种利用CALM定理设计的语言。它是一个Ruby DSL，它的形式基础是一种叫做Dedalus的时态逻辑编程语言。

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

查看Bloom网站和教程以了解有关Bloom的更多信息

Further reading

---

The CALM theorem, confluence analysis and Bloom
Joe Hellerstein’s talk @RICON 2012 is a good introduction to the topic, as is Neil Conway’s
talk @Basho. For Bloom in particular, see Peter Alvaro’s talk@Microsoft.

---

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

---

Dynamo; PBS; optimistic replication