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

最近看到的一篇超棒的关于分布式系统中强一致性模型的blog，实在没有不分享的道理。最近比较闲，所以干脆把它翻译了，一是为了精读，二是为了更友好地分享。其中会插入一些乱七八糟的个人补充，评论区的精彩讨论也会有选择性的翻译。原文在这：https://aphyr.com/posts/313-st ... odels

网络分区是大概率会发生的。交换机，网络接口控制器（NIC，Network Interface Controller），主机硬件，操作系统，硬盘，虚拟机，语言运行时，更不用说程序语义本身，所有的这些将导致我们的消息可能会延迟，被丢弃，重复或被重新排序。在一个充满不确定的世界里，我们希望程序保持一种直观的正确性。

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

正确性（Correctness）

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

uniprocessor history

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

x = "a"; puts x; puts x

x = "b"; puts x

x = "c"

x = "d"; puts x

我们对程序的正确性已经有了一个直观的概念：以上这段程序应该输出“aabd”。为什么呢？因为它们是有序发生的。首先我们写入值a，然后读到值a，接着读到值a，写入值b，如此进行。

一旦我们把变量写为某个值，比如a，那么读操作就应该返回a，直到我们再次改变变量。读到的值应该总是返回最近写入的值。我们把这种系统称为——单值变量——单一寄存器（并不单指硬件层次的寄存器，而是 act like a register）。

从编程的第一天开始，我们就把这种模型奉为圭臬，像习惯一样自然——但这并不是变量运作的唯一方式。一个变量可能被读到任何值：a，d，甚至是the moon。这样的话，我们说系统是不正确的，因为这些操作没有与我们模型期望的运作方式对应上。

这引出了对系统正确性的定义：给定一些涉及操作与状态的规则，随着操作的演进，系统将一直遵循这些规则。我们把这样的规则称为一致性模型。

我们把对寄存器的规则用简单的英语来陈述，但它们也可以是任意复杂的数学结构。“读取两次写入之前的值，对值加三，如果结果为4，读操作可能返回cat或dog”，这也可以是一种一致性模型（作者只是为了表名一致性模型的阐述原则，后同）。也可以是“每次读操作都会返回0”。我们甚至可以说“根本没有什么规则，所有操作都是允许的”。这就是最简单的一致性模型，任何系统都能轻易满足。

更加正式地说，一致性模型是所有被允许的操作记录的集合。当我们运行一个程序，经过一系列集合中允许的操作，特定的执行结果总是一致的。如果程序意外地执行了非集合中的操作，我们就称执行记录是非一致的。如果任意可能的执行操作都在这个被允许的操作集合内，那么系统就满足一致性模型。我们希望实际的系统是满足这样“直观正确”的一致性模型的，这样我们才能写出可预测的程序。

并发记录（Concurrent histories）

假设有一个用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 cones）

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


light cone history

现实往往没有那么理想化：在几乎每个实际的系统中，进程之间都有一定的距离。一个没有被缓存的值（指没有被CPU的local cache缓存），通常在距离CPU30厘米的DIMM内存条上。光需要整整一个纳秒来传播这么长的距离，实际的内存访问会比光速慢得多。位于不同数据中心某台计算机上的值可以相距几千公里——意味着需要几百毫秒的传播时间。我们没有更快传播数据的方法，否则就违反了物理定律。（物理定律都违反了，就更别谈什么现代计算机体系了。）

这意味着我们的操作不再是瞬时的。某些操作也许快到可以被近乎认为是瞬时的，但是通常来说，操作是耗时的。我们调用对一个变量的写操作；写操作传播到内存，或其他计算机，或月球；内存改变状态；一个确认信息回传；这样我们才知道这个操作真实的发生了。

concurrent read

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

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

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

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

线性一致性（Linearizability）

finite concurrency bounds

通过仔细的检查，我们发现事件的顺序是有边界的。在时间维度上，消息不能被逆向发送，因此最先到达的消息会即刻接触到数据源。一个操作不能在它被调用之前生效。

同样的，通知完成的消息也不能回传，这意味着一个操作不能在它完成之后生效。

如果我们假设有一个全局的状态与每个进程通信；继续假设与这个全局状态交互的操作都是原子的；那我们可以排除很多可能发生的记录。每个操作会在它调用和完成之间的某个时间点原子地生效。

我们把这样的一致性模型称为线性一致性模型。尽管操作都是并发且耗时的，但每一个操作都会在某地以严格的线性顺序发生。

linearizability complete visibility

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

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

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

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

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

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

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

顺序一致性（Sequential consistency）

sequencial history

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

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

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

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

因果一致性（Casual consistency）

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

因果一致性比同一进程下对每个操作严格排序的一致性（即顺序一致性）来的更宽松——属于同一进程但不同因果关系链的操作能以相对的顺序执行（也就是说按因果关系隔离，无因果关系的操作可以并发执行），这能防止许多不直观的行为发生。

串行一致性（Serializable consistency）

serializable history

如果我们说操作记录的发生等效于某些单一的原子序，但和调用时间与完成时间无关，那么我们就得到了名为串行一致性的一致性模型。这一模型比你想象的更强大同时也更脆弱。

串行一致性是弱约束的，因为它能允许多种类型的记录发生，且对时间或顺序不设边界。在上面的示意图中，消息看似可以被任意地发送至过去和未来，因果关系也可以交错。在一个串行数据库中，即使在0时刻，x还没被初始化，一个类似read x的读事务也是允许执行的。 或者它也会被延迟到无限远的未来执行。类似write 2 to x的写事务可以立即执行，也可能永远都不会执行。

举个例子，在一个串行系统中，有这么一段程序：

x = 1

x = x + 1

puts x

这段程序可以输出nil，1或2，因为操作能以任意顺序发生。 这是十分弱的约束！这里可以把每一行代码看作是单个操作，所有操作都成功执行了。

另一方面，串行一致性也是强约束的，当它要求一个线性顺序时，它能拦截很大一部分操作记录。看以下程序：

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的概念，而线性一致性来自并行计算领域，描述了针对某种数据结构的操作所表现出的顺序特征。串行一致性是对多操作，多对象的保证，对总体的操作顺序无要求；线性一致性是对单操作，单对象的保证，所有操作遵循真实时间序。详见：http://www.bailis.org/blog/lin ... lity/）

一致性的代价（Consistency comes with costs）

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

也许你听说过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数据库提供的。这些一致性模型并没有保证线性顺序，而是在批处理任务或网络场景下提供部分顺序保证。只能保证部分顺序是因为它们准许更丰富的记录。

一种混合方法（A hybrid approach）

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（作者）：请参考：https://projects.ics.forth.gr/ ... s.pdf，获得为什么因果一致性比PRAM更强的详细解释。具体地说，有因果关系的操作可以在中间节点之间传递，但是PRAM并没有对因果一致性的传递性作任何定义。

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

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

......欲知更多请见原文：https://aphyr.com/posts/313-st ... odels

译文链接：https://zhuanlan.zhihu.com/p/48782892