强一致性模型

网络分区是会发生的。交换机、网卡、主机硬件、操作系统、磁盘、虚拟化层和语言运行时，更不用说程序语义本身，都在密谋延迟、放弃、重复或重新排列我们的信息。在一个不确定的世界里，我们希望我们的软件能够保持某种意义上的直觉正确性。

很明显，我们想要直观的正确性。做正确的事（TM）! 但到底什么是正确的事情？我们可以如何描述它？在这篇文章中，我们将参观一些 "强 "一致性模型，并看看它们是如何结合在一起的。

正确性

例如，我们的状态可能是一个变量，对状态的操作可能是对该变量的写入和读出。在这个简单的Ruby程序中，我们多次写和读一个变量，并把它打印到屏幕上以说明读的情况。

x = "a"; puts x; puts x
x = "b"; puts x
x = "c"
x = "d"; puts x

我们对这个程序的正确性已经有了一个直观的模型：它应该打印 "aabd"。为什么呢？因为每个语句都是按顺序发生的。首先是我们write the value a，然后是read the value a，然后是read the value a，然后是write the value b，依此类推。

一旦我们将一个变量设置为某个值，比如a，读取它应该返回a，直到我们再次改变这个值。读取一个变量会返回最近写入的值。我们称这种系统为单一值的变量--寄存器。

从我们开始写程序的第一天起，我们就把这种模式灌输到我们的头脑中，所以感觉就像第二天一样，但这并不是变量工作的唯一方式。变量可以返回任何读取的值：A或D。如果发生这种情况，我们就会说这个系统是不正确的，因为这些操作不符合我们关于变量应该如何工作的模型。

这暗示了系统正确性的定义：给定一些与操作和状态相关的规则，系统中的操作历史应该始终遵循这些规则。我们把这些规则称为一致性模型。

正式地说，我们说一致性模型是所有允许的操作历史的集合。如果我们运行一个程序，它经历了允许集合中的操作序列，那么这个特定的执行是一致的。如果程序偶尔搞砸了，经历了一个不在一致性模型中的历史，我们就说这个历史是不一致的。如果每个可能的执行都落入允许的集合，那么系统就满足了模型。我们希望真实的系统能够满足 "直观正确 "的一致性模型，这样我们就可以编写可预测的程序。

并发历史

现在想象一个并发的程序，比如用Node.js或Erlang编写的程序。有多个逻辑上的控制线程，我们称之为 "进程"。如果我们运行一个有两个进程的并发程序，每个进程都用同一个寄存器工作，我们之前的寄存器不变性就可能被违反。

在这种情况下，并发的概念就有了不同的形态。我们可以把每个程序想象成默认的并发--当执行时，操作可以以任何顺序发生。一个线程，一个进程--无论如何，在逻辑意义上--是对历史的约束：属于同一线程的操作必须按顺序发生。逻辑线程对允许的操作施加了一个部分顺序。

即使有这个顺序，我们的寄存器不变性--从单个进程的角度来看--也不再成立。上面的进程写了a，读了a，然后读了b--这并不是它写的值。我们必须放松我们的一致性模型，以便有效地描述并发性。现在，一个进程被允许从任何进程中读取最近写入的值，而不仅仅是自己。寄存器成为两个进程之间的协调场所；它们共享状态。

V

这意味着我们的操作不再是瞬时的。有些操作可能快到可以忽略不计，但总体而言，操作需要时间。我们调用一个变量的写操作；这个写操作被传送到内存，或另一台计算机，或月球；内存改变了状态；一个确认被传送回来；然后我们知道操作发生了。

这段历史违反了我们的并发寄存器一致性模型。底层进程在调用读的时候并没有读到当前的值。我们可以尝试使用完成时间，而不是调用时间，作为操作的 "真实时间"，但是这在对称性上也是失败的；如果读在写之前到达，那么当当前值是b时，进程会收到a。

在一个分布式系统中--一个需要时间来进行操作的系统--我们必须再次放松我们的一致性模型；允许这些模糊的顺序发生。

我们必须走多远？我们必须允许所有的顺序吗？或者我们仍然可以对世界施加一些理智的东西？

可线性化

我们把这种一致性模型称为线性化；因为尽管操作是并发的，并且需要时间，但是有一些地方--或者说有一个地方的出现--每一个操作都是以一个漂亮的线性顺序发生的。

可线性化具有强大的后果。一旦一个操作完成，每个人都必须看到它--或者某个后来的状态。我们知道这是真的，因为每个操作都必须在其完成时间之前发生，任何随后被调用的操作都必须在调用之后发生--并延伸到原始操作本身之后。一旦我们成功地写入b，每一个随后调用的读必须看到b--或者某个更晚的值，如果发生更多的写入。

我们可以使用线性化的原子约束来安全地改变状态。我们可以定义一个类似于比较和设置的操作，在这个操作中，我们将一个寄存器的值设置为一个新的值，当且仅当该寄存器当前有一些其他的值。我们可以使用比较和设置作为互斥、信号、通道、计数器、列表、集合、地图、树的基础，所有类型的共享数据结构都可以使用。线性化保证了我们可以安全地交织变化。

此外，线性化的时间界限保证了这些变化在操作完成后会被其他参与者看到。因此，线性化禁止陈旧的读取。每次读取都会看到调用和完成之间的一些当前状态；但不会看到读取之前的状态。它还禁止非单调性的读取--即先读取一个新值，然后再读取一个旧值。

由于这些强有力的约束，可线性化系统更容易推理，这就是为什么它们被选为许多并发编程结构的基础。Javascript中的所有变量都是（独立的）可线性化的；Java中的易失性变量、Clojure中的原子或Erlang中的单个进程也是如此。大多数语言都有互斥和信号，这些也是可线性化的。强大的假设产生强大的保证。

但如果我们不能满足这些假设，会发生什么？

顺序的一致性

顺序一致性比线性化允许更多的历史，但它仍然是一个有用的模型：我们每天都在使用。例如，当一个用户向YouTube上传视频时，YouTube将该视频放入一个队列进行处理，然后立即返回该视频的网页。在这一点上，我们实际上不能观看视频；视频上传在几分钟后才生效，这时它已经被完全处理了。队列消除了同步行为，同时（取决于队列）保留了顺序。

许多缓存也表现得像顺序一致的系统。如果我在Twitter上写了一条推文，或者在Facebook上发了一个帖子，它需要时间来渗透到各层缓存系统中。不同的用户会在不同的时间看到我的信息--但每个用户都会按顺序看到我的操作。一旦被看到，一个帖子就不应该消失。如果我写了多条评论，它们会按顺序变得可见，而不是不按顺序。

因果一致性

我们不必强制执行一个过程中每个操作的顺序。也许，只有因果关系的操作必须按顺序发生。例如，我们可以说，一篇博客文章的所有评论对每个人来说都必须以相同的顺序出现，并坚持任何回复只有在它所回复的文章可见之后才会对进程可见。如果我们把 "我依赖于操作X "这样的因果关系编码为每个操作的显式部分，数据库就可以推迟使操作可见，直到它拥有所有操作的依赖关系。

这比对来自同一进程的每个操作进行排序要弱--来自同一进程的具有独立因果链的操作可以以任何相对顺序执行--但可以防止许多不直观的行为。

可序列化的一致性

序列性是弱的，因为它对时间和顺序没有限制，所以它允许许多类型的历史。在右图中，就好像信息可以被任意地发送到过去或未来，因果线被允许交叉。在一个可序列化的数据库中，像读x这样的事务总是被允许在时间0执行，那时x还没有被初始化。或者它可能会被无限地延迟到未来! 向x写2的事务可以现在就执行，也可以延迟到时间的尽头，永远不会出现。

例如，在一个可序列化的系统中：

x = 1
x = x + 1
puts x

程序允许打印nil、1或2；因为这些操作可以按任何顺序进行。这是一个令人惊讶的弱约束! 在这里，我们假设每一行代表一个操作，并且所有的操作都能成功。

另一方面，可序列化是很强的，在这个意义上，它禁止大类的历史，因为它要求有一个线性顺序。该程序只能以一种方式排序。它不会按照我们写的顺序发生，但它会可靠地将x从nil->1->2->3，最后打印3。

print x if x = 3
x = 1 if x = nil
x = 2 if x = 1
x = 3 if x = 2

因为可序列化允许对操作进行任意的重新排序（只要顺序看起来是原子性的），所以它在实际应用中不是特别有用。大多数声称提供可序列化的数据库实际上提供的是强序列化，它的时间界限与可线性化相同。让事情变得更加复杂的是，大多数SQL数据库所称的可序列化的一致性水平实际上是指更弱的东西，比如可重复读取、游标稳定性或快照隔离。

一致性是有代价的

我们已经说过，"弱 "一致性模型比 "强 "一致性模型允许更多历史。例如，线性化（Linearizability）保证了操作发生在调用和完成时间之间。然而，强加秩序需要协调。松散地讲，我们排除的历史越多，系统中的参与者就必须更加小心和沟通。

你可能听说过CAP定理，该定理指出，鉴于一致性、可用性和分区容忍度，任何给定的系统最多可以保证其中的两个属性。虽然埃里克-布鲁尔的CAP猜想是用这些非正式的术语表述的，但CAP定理有非常精确的定义。

1. 一致性意味着可线性化，尤其是可线性化的寄存器。寄存器等同于其他系统，包括集合、列表、地图、关系数据库等等，所以该定理可以扩展到涵盖所有种类的可线性化系统。
2. 可用性意味着对非故障节点的每个请求必须成功完成。由于网络分区被允许持续任意长的时间，这意味着节点不能简单地推迟响应，直到分区愈合之后。
3. 分区容忍意味着分区可能发生。当网络是可靠的时候，提供一致性和可用性是容易的。当网络不可靠时，提供这两点是可以证明不可能的。如果你的网络不是完全可靠的--它不是的--你就不能选择CA。这意味着所有商品硬件上的实用分布式系统都能最大限度地保证AP或CP。

如果我们放宽可用性的概念，比如客户端节点必须始终与同一个服务器对话，那么某些类型的一致性就可以实现。我们可以提供因果一致性、PRAM和读你写的一致性。

如果我们要求完全的可用性，那么我们可以提供单调的读、单调的写、读承诺、单调的原子视图，等等。这些是Riak和Cassandra等分布式存储提供的一致性模型，或者是较低隔离度设置上的ANSI SQL数据库。这些一致性模型并不像我们之前画的图那样有线性顺序；相反，它们提供了部分顺序，这些顺序以拼凑或网络的方式组合在一起。这些命令是部分的，因为它们承认更广泛的历史类别。

一种混合方法

较强的一致性模型也倾向于需要更多的协调--更多的信息来回传递，以确保其操作以正确的顺序发生。它们不仅可用性较低，而且还会施加更高的延迟约束。这就是为什么现代CPU内存模型在默认情况下是不可线性化的--除非你明确说出来，否则现代CPU会相对于其他内核重新安排内存操作的顺序，甚至更糟。虽然更难推理，但其性能优势是惊人的。地理上的分布式系统，在数据中心之间有几百毫秒的延迟，通常会做出类似的权衡。

因此，在实践中，我们使用混合数据存储，混合具有不同一致性模型的数据库，以实现我们的冗余性、可用性、性能和安全目标。尽可能使用 "弱 "一致性模型，以提高可用性和性能。必要时采用 "强 "一致性模型，因为所表达的算法需要更严格的操作顺序。例如，你可以把大量的数据写到S3、Riak或Cassandra，然后把这些数据的指针以线性方式写到Postgres、Zookeeper或Etcd。一些数据库承认多种一致性模型，比如关系型数据库的可调整隔离级别，或者Cassandra和Riak的可线性化交易，这可以帮助减少系统的数量。不过，底线是：任何说自己的一致性模型是唯一正确选择的人，都可能是在试图推销什么。你不可能把你的蛋糕也吃了。

在对一致性模型有了更细致的了解之后，我想谈谈我们如何去验证一个可线性化系统的正确性。在下一篇Jepsen文章中，我们将讨论我为测试分布式系统而建立的线性化检查器。Knossos。

对于这些模型的更正式的定义，请尝试Dziuma、Fatourou和Kanellou的一致性条件调查综述。

本文译自：https://aphyr.com/posts/313-strong-consistency-models