[译]分布式系统中的一致性模型

是的，我们想要直观的正确性。那就做正确的事吧！但什么是正确的事？我们如何描述它？在这篇文章里，我们会见到一些“强”一致性模型，并且看到他们是如何互相适应的。

其实有很多种描述一个算法抽象行为的方式——但为了统一，我们说一个系统是由状态和一些导致状态转移的操作组成的。在系统运行期间，它将随着操作的演进从一个状态转移到另一个状态。

uniprocessor history

举个例子，我们的状态可以是个变量，操作可以是对这个变量的读和写。在这个简单的 Ruby 程序里，我们会对一个变量进行几次读写，以输出的方式表示写。

假设有一个用 Node.js 或 Erlang 写的并发程序。现有多个逻辑线程，我们称之为“多进程”。如果我们用 2 个进程运行这个并发程序，每个进程都对同一个寄存器进行访问（读和写），那么我们之前认为的寄存器系统的不变性（指顺序不变性）就会被改写。

multiprocessor history

两个工作进程分别称为“top”和“bottom”。Top 进程尝试执行写 a
，读
，读
。Bottom 进程同时尝试执行读
，写 b
，读
。因为程序是并发的，所以两个进程之间互相交错的操作将导致多个执行顺序——而在单核场景下，执行顺序总是程序里指定的那一个逻辑顺序。图例中，top 写入a
，bottom 读a
，top 读a
，bottom 写b
，top 读b
，bottom 读b
。

但是并发会让一切表现的不同。我们可以默认地认为每个并发的程序——一旦执行，操作能以任意顺序发生。一个线程，或者说是一个逻辑进程，在执行记录层面的做了一个约束：属于同一个线程的操作一定会按顺序发生。逻辑线程对允许操作集合中的操作强加了部分顺序保证。（一个逻辑线程即一个执行实体，即使编译器重排了指令，单个线程中的同步 workflow 顺序是不会颠倒的。但是不同线程之间的事件顺序无法保证。）

即使有了以上的保证，从独立进程的角度来看，我们的寄存器不变性也被破坏了。Top 写入a
，读到a
，接着读到b
——这不再是它写入的值。我们必须使一致性模型更宽松来有效描述并发。现在，进程可以从其他任意进程读到最近写入的值。寄存器变成了两个进程之间的协调地：它们共享了状态。

读写不再是一个瞬时的过程，而是一个类似光传播->反射面->反向传播的过程。

light cone history

concurrent read

不同地点之间传送消息的延迟会在操作记录中造成歧义。消息传播的快慢会导致预期外的事件顺序发生。上图中，Bottom 发起一个读请求的时候，值为a
，但在读请求的传播过程中，top 将值写为b
——写操作偶然地比读请求先到达寄存器。Bottom 最终读到了b
而不是a
。

这一记录破坏了我们的寄存器并发一致性模型。Bottom 并没有读到它在发起读请求时的值。有人会考虑使用完成时间
而不是调用时间
作为操作的真实时间
，但反过来想想，这同样行不通：当读请求比写操作先到达时，进程会在当前值为b
时读到a
。

在分布式系统中，操作的耗时被放大了，我们必须使一致性模型更宽松：允许这些有歧义的顺序发生。

我们该如何确定宽松的程度？我们必须允许所有可能的顺序吗？或许我们还是应该强加一些合理性约束？

finite concurrency bounds

linearizability complete visibility

“全局单点状态”并不一定是一个单独的节点，同样的，操作也并不一定全是原子的，状态也可以被分片成横跨多台机器，或者分多步完成——只要从进程的角度看来，外部记录的表现与一个原子的单点状态等效。通常一个可线性化的系统由一些更小的协调进程组成，这些进程本身就是线性的，并且这些进程又是由更细粒度的协调进程组成，直到硬件提供可线性化的操作。

线性化是强大的武器。一旦一个操作完成，它或它之后的某一状态将对所有参与者可见。因为每个操作一定发生在它的完成时间
之前，且任何之后被调用的操作一定发生在调用时间
之后，也就是在原操作本身之后。一旦我们成功写入b
，每个之后调用的读请求都可以读到b
，如果有更多的写操作发生的话，也可以是b
之后的某个值。

我们可以利用线性一致性的原子性约束来安全地修改状态。我们定义一个类似CAS（compare-and-set）
的操作，当且仅当寄存器持有某个值的时候，我们可以往它写入新值。 CAS
操作可以作为互斥量，信号量，通道，计数器，列表，集合，映射，树等等的实现基础，使得这些共享数据结构变得可用。线性一致性保证了变更的安全交错。

此外，线性一致性的时间界限保证了操作完成后，所有变更都对其他参与者可见。于是线性一致性禁止了过时的读。每次读都会读到某一介于调用时间
与完成时间
的状态，但永远不会读到读请求调用之前的状态。线性一致性同样禁止了非单调的读，比如一个读请求先读到了一个新值，后读到一个旧值。

由于这些强约束条件的存在，可线性化的系统变得更容易推理，这也是很多并发编程模型构建的时候选择它作为基础的原因。Javascript 中的所有变量都是（独立地）可线性化的，其他的还有 Java 中的 volatile 变量，Clojure 中的 atoms，Erlang 中独立的 process。大多数编程语言都实现了互斥量和信号量，它们也是可线性化的。强约束的假设通常会产生强约束的保证。

但如果我们无法满足这些假设会怎么办？

（线性一致性模型提供了这样的保证：1.对于观察者来说，所有的读和写都在一个单调递增的时间线上串行地向前推进。2.所有的读总能返回最近的写操作的值。）

sequencial history

如果我们允许进程在时间维度发生偏移，从而它们的操作可能会在调用之前或是完成之后生效，但仍然保证一个约束——任意进程中的操作必须按照进程中定义的顺序（即编程的定义的逻辑顺序）发生。这样我们就得到了一个稍弱的一致性模型：顺序一致性。

顺序一致性允许比线性一致性产生更多的记录，但它仍然是一个很有用的模型：我们每天都在使用它。举个例子，当一个用户上传一段视频到 Youtube，Youtube 把视频放入一个处理队列，并立刻返回一个此视频的网页。我们并不能立刻看到视频，上传的视频会在被充分处理后的几分钟内生效。队列会以入队的顺序同步地（取决于队列的具体实现）删除队列中的项。

很多缓存的行为和顺序一致性系统一致。如果我在 Twitter 上写了一条推文，或是在 Facebook 发布了一篇帖子，都会耗费一定的时间渗透进一层层的缓存系统。不同的用户将在不同的时间看到我的信息，但每个用户都以同一个顺序看到我的操作。一旦看到，这篇帖子便不会消失。如果我写了多条评论，其他人也会按顺序的看见，而非乱序。

（顺序一致性放松了对一致性的要求：1. 不要求操作按照真实的时间序发生。2. 不同进程间的操作执行先后顺序也没有强制要求，但必须是原子的。3. 单个进程内的操作顺序必须和编码时的顺序一致。）

我们不必对一个进程中的每个操作都施加顺序约束。只有因果相关的操作必须按顺序发生。同样拿帖子举例子：一篇帖子下的所有评论必须以同样的顺序展示给所有人，并且只有帖子可见后，帖子下的回复才可见（也就是说帖子和帖子下的评论有因果关系）。如果我们将这些因果关系编码成类似“我依赖于操作 X”的形式，作为每个操作明确的一部分，数据库就可以将这些操作延迟直到它们的依赖都就绪后才可见。

serializable history

x = 1
x = x + 1
puts x

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

这段程序只有一种输出可能。它并不按我们编写的顺序输出，但x
会从nil
开始变化：nil -> 1 -> 2 -> 3
，最终输出3
。

因为串行一致性允许对操作顺序执行任意的重排（只要操作顺序是原子序的）， 它在实际的场景中并不是十分有用。大多数宣称提供了串行一致性的数据库实际上提供的是强串行一致性
，它有着和线性一致性一样的时间边界。让事情更复杂的是，大多数 SQL 数据库宣称的串行一致性等级比实际的更弱，比如可重复读，游标稳定性，或是快照隔离性。

（关于线性一致性和串行一致性，看似十分相似，其实不然。串行一致性是数据库领域的概念，是针对事务而言的，描述对一组事务的执行效果等同于某种串行的执行，没有 ordering 的概念，而线性一致性来自并行计算领域，描述了针对某种数据结构的操作所表现出的顺序特征。串行一致性是对多操作，多对象的保证，对总体的操作顺序无要求；线性一致性是对单操作，单对象的保证，所有操作遵循真实时间序。详见 Linearizability vs Serializability。）

之前说了“弱”一致性模型比“强”一致性模型允许更多的操作记录发生（这里的强与弱是相对的）。比如线性一致性保证操作在调用时间与完成时间之间发生。不管怎样，需要协调来达成对顺序的强制约束。不严格地说，执行越多的记录，系统中的参与者就必须越谨慎且通信频繁。

也许你听说过 CAP 理论，CAP 理论声明给定一致性（Consistency），可用性（Availability）和分区容错性（Partition tolerance），任何系统至多能保证以上三项中的两项而不可能满足全部三项。这是 Eric Brewer 的 CAP 猜想的非正式说法，以下是准确的定义：

• 一致性（Consistency）意味着线性化，具体说，可以是一个可线性化的寄存器。寄存器可以等效为集合，列表，映射，关系型数据库等等，因此该理论可以被拓展到各种可线性化的系统。

• 可用性（Availability）意味着向非故障节点发出的每个请求都将成功完成。因为网络分区可以持续任意长的时间，因此节点不能简单地把响应推迟到分区结束。

• 分区容错性（Partition tolerance）意味着分区很可能发生。当网络可靠的时候，提供一致性和可用性将变得十分简单，但当网络不可靠时，同时提供一致性和可用性将变得几乎不可能。然而网络总不是完美可靠的，所以我们不能选择 CA。所有实际可用的商用分布式系统至多能提供 AP 或 CP 的保证。

family tree

也许你会说：“等等！线性化并不是一致性模型的终极解决方案！我能围绕着 CAP 理论提供顺序一致性，串行一致性或是快照隔离性！”

没错，CAP 理论只声称我们不能构建一个完全可用的线性化系统。但问题是我们又有了其他证据表明我们同样不能利用顺序化，串行化，可重复读，快照隔离，游标稳定或是其它任意一个比这些强的约束来构建完全可用的系统。在 Peter Bailis 的 Highly Available Transactions 这篇论文中，红色阴影标注的模型就不能是完全可用的。

如果我们放松对可用性的定义，只要求 client 节点能够一直与同一 server 保持通信，某种一致性就被达成了。我们能以此为基础提供因果一致性，PRAM（pipelined random access memory）一致性和“读你所写”一致性。

如果我们要求完全可用，那就能提供单调读，单调写，读的提交，单调且原子的视角等等。这些一致性模型是由如 Riak 和 Cassandra 这样的分布式存储系统，低隔离性设置的 ANSI SQL 数据库提供的。这些一致性模型并没有保证线性顺序，而是在批处理任务或网络场景下提供部分顺序保证。只能保证部分顺序是因为它们准许更丰富的记录。

weak not unsafe

一些算法依赖于线性化提供安全性。例如当我们想构建分布式锁的服务时，我们就需要线性化，如果没有硬性的时间边界的话，我们就可以持有一把将来的锁或是过去的锁。而另一方面，很多算法根本不需要线性化。即使仅提供“弱”一致性模型，比如有最终一致性保证的集合，列表，树，映射等结构也能被安全地表示为 CRDTs（Commutative Replicated Data Types）

更强约束的一致性模型需要更多的协调——需要更多的消息交互，确保操作在正确的顺序发生。这不仅意味着更低的可用性，还会被导致更高的延迟。这也是为什么现代 CPU 内存模型默认不是线性化的，除非显示指定。（x86-64 架构的 CPU 通常以 Sequential consistency 作为默认的 memory order），现代 CPU 会在核之间重排内存操作，甚至更糟糕。虽然（程序的行为）更难以推理，但带来的性能提升是惊人的。在地理位置上零落的分布式系统，数据中心通常有几百毫秒的延迟，通常和 CPU 的场景类似，代价也相似。

因此在实践中，通常会用混合数据存储，在数据库之间混用不同的一致性模型来权衡冗余度，可用性，性能和安全性等目标。可能的话就为了可用性和性能选择“弱”一致性模型。必要的话就选择“强”一致性模型，因为某些算法对操作顺序有严格要求。我们可以向 S3，Riak，Cassandra 等数据库写入大量数据，然后线性地向 Postgres，Zookeeper 或 Etcd 写入指向数据的指针。一些数据库准许多种一致性模型共存，比如关系数据库中的可调节隔离等级，Cassandra 和 Riak 中的线性化事务，减少了使用的系统数量。但底线是：任何人宣称它的一致性模型是最优解，那么他一定是个大猪蹄子。

Colin Scott：当你提到“属于同一进程但不同因果关系链的操作”的时候，是否对潜在的因果关系（happens before）作了更保守的假设？我在苦想一个 case，当来自同一台机器上的两个存在潜在因果关系（A 必须先于 B 发生）的操作并发时，会发生什么？

Aphyr（作者）：尽管来自同一个进程的操作在某一节点上按顺序发生，但它们并不需要在任何地方都按序发生。顺序一致性（Sequential consistency）作了这样的约束，但因果一致性（Casual consistency）并没有。只有显式的因果关系在因果一致性系统中才是顺序不变的，而隐式的因果关系在顺序一致性系统中作了保证。（因为都来自同一进程，通过 pid 区分）

Aurojit Panda：实际上你对Colin Scott
的回复和你在文章中的一致性层级示意图
是自相矛盾的。PRAM 一致性模型约定：所有节点都能按同一顺序从一个给定节点观测到它的写操作（Lipton, Sandberg 1988）。而你描述的因果一致性是某一比 PRAM 一致性更弱的一致性模型，并不是经典的因果一致性模型。并且你描述中出现的隐式因果关系也是 PRAM 一致性模型约束中的一部分。如果因果一致性比 PRAM 一致性更强，PRAM 一致性就应该用任何因果一致性系统来实现，利用因果一致性对单节点的写操作进行正确排序，使得其他节点的观测结果一致。

Aphyr（作者）：请参考 Survey on Consistency Conditions 获得为什么因果一致性比 PRAM 更强的详细解释。具体地说，有因果关系的操作可以在中间节点之间传递，但是 PRAM 并没有对因果一致性的传递性作任何定义。

Prakash：关于问题 - “在你串行一致性的示例中，各种if
假设是如何对顺序进行约束的？”

你的回答中提到 - “这些操作发生的顺序有且只有一种可能。”

而我的问题是，当我们考虑在并发环境下执行某种操作时，是怎么做到“串行有且只有一种可能”的？举个例子，我们有不同的线程，其中一个检查x
值是否为 3 并把它打印，另一个将x
的值设为 2。你能解释一下在这种场景中是如何维护顺序的？

Aphyr（作者）：串行的操作记录实际上会转化为单道线程下的操作记录，单道线程下的操作记录就是我们之前的讨论中发挥作用的状态转移方程。如果以恒等函数作为你的模型，操作记录中任何可能的路径都是有效的，它们并不会改变状态。为了让某些操作记录永远不可串行化（限制那些非法的可能造成状态转移的操作发生），不得不声明一些等效于单线程执行的操作无效，这就是条件语句（if
）强制部分操作有序的原因。

......欲知更多请见原文。