关于分布式:图解一致性模型

引言：本文应用大量的图例，同时没有难懂的公式，用意解释分明一致性模型要解决什么问题，以及三种一致性模型：程序一致性、线性一致性、因果一致性。

概述

解决什么问题？

分布式系统要保证系统的可用性，就须要对数据提供肯定的冗余度：一份数据，要存储在多个服务器上，能力认为保留胜利，至于这里要保留的冗余数，有 Majority 和 Quorum之 说，能够参考之前的文章：周刊（第 17 期）：Read-Write Quorum System 及在 Raft 中的实际。

同一份数据保留在多个机器上提供冗余度，也被称为 正本 (replica) 策略，这个做法带来上面的益处：

• 容错性：即使分布式系统中几台机器不能工作，零碎还能照常对外提供服务。
• 晋升吞吐量：既然同一份数据存储在多个机器上，对该数据的申请（至多是读申请）可能分担到多个正本上，这样整个零碎能够线性扩容减少更多的机器以应酬申请量的减少。

同时，正本策略也有本人须要解决的问题，其中最重要的问题就是一致性问题：在零碎中的一个机器写入的数据，是否在零碎中其余机器看来也是一样的？

很显然，即使在所有都失常工作的条件下，在零碎中的一个机器胜利写入了数据，因为播送这个批改到零碎中的其余机器还须要工夫，那么零碎的其余机器看到这个批改的后果也还是须要工夫的。换言之，两头的这个 时间差 可能呈现短暂的数据不统一的状况。

能够看到，因为这个 时间差 的客观存在，并不存在一个 相对 意义上的数据一致性。换言之，数据一致性 有其实现的严格范畴，越严格的数据统一，要付出的老本、代价就越大。

为了解决一致性问题，须要首先定义一致性模型，在维基的页面上，一致性模型（Consistency model）的定义如下：

In computer science, a consistency model specifies a contract between the programmer and a system, wherein the system guarantees that if the programmer follows the rules for operations on memory, memory will be consistent and the results of reading, writing, or updating memory will be predictable.

咱们举一个日常生活中常见的问题来解释 一致性模型：

在上图中：

• 无妨把 朋友圈 当成一个大型的 分布式系统：

  • 这个分布式系统，对外提供了写入（发朋友圈）和读取（读朋友圈）的性能。
  • 存储这些朋友圈数据的，必定不止一台机器，因而这些机器在一起形成了这个大型的分布式系统。
  • 不同的用户，发朋友圈的时候，也不肯定都写入雷同的一台机器。反之也是，在读朋友圈时也不肯定会到同一台机器上读取数据。
• 朋友圈 这个分布式系统，有两种客户端：发朋友圈 的客户端负责写入数据，读朋友圈 的客户端负责读取数据，当然很多时候同一个客户端既能读也能写。

接下来的问题是：

• 这些看朋友圈的人，是否能看到全局统一的数据？即所有人看到的朋友圈都是同一个顺序排列的？

显然，有很多时候，即使是在看同一个朋友圈下的评论回复，不同的人看到也不尽然都是同一个程序的，所以以上的答案是否定的。那么就引入了下一个问题：

• 如果不同的人看到的朋友圈（包含评论）程序各有不同，这些程序又该恪守怎么的规定才是正当的？

答复怎么的 程序规定 才是正当的，这就是 一致性模型 要解答的问题。

一致性模型图例

本文意在应用各种图例来解释一致性模型，所以在持续往下解说之前，有必要首先交待一下图例中的各种元素，以下图为例：

在上图中，有以下几个元素：

• 最右边是分布式系统中的过程编号 P1、P2​。
• 横轴是时间轴，从左往右工夫递增，然而这里并没有严格的工夫刻度。

• 过程中产生的事件，事件的命名规定为 过程编号_过程中的事件编号，比方 P1_1，除此以外：

  • 事件有其开始、完结工夫，应用一个矩形来示意一个事件的执行，这样矩形的宽度能够认为在时间轴上的宽度，即事件的执行时长。
  • 事件与事件之间，在执行工夫上可能产生重叠，如图中的 P1_1 和 P2_1，这种有重叠的事件，被称为并发事件（concurrent event），在程序上，并发事件之间能够认为谁先谁后都能够，前面会专门聊这部分。
  • 应用不同的色彩来辨别不同过程上产生的事件。

  • 每个事件关联一个操作，为了简化问题目前只有读和写操作：

    • w(x) = A：向变量 x 写入 A。
    • r(x) = A：从变量 x 读出 A。

单过程下的事件排列

咱们持续回到 朋友圈 的话题上来，一条朋友圈上面有多集体发表评论，能够认为这是一个 二维 的数据：

• 过程（也就是发表评论的人）是一个维度。
• 工夫又是另一个维度，即这些评论呈现的先后顺序。

然而在浏览这些评论的读者看来，须要将这一份 二维 的数据，去除掉不同过程这个维度，压平 到只有本过程工夫线这一个繁多维度下面来，以下面图例来说就是这样的：

在上图中，在读过程 P3 的视角看来，两个写过程的事件，须要 压平 到本过程的工夫线上进行排列，能够看到这些事件在 压平 之后有多种排列的可能性。

将多个写过程的事件进行排列，放到单过程的工夫线上，这是一个排列组合问题，如果所有的写过程事件加起来一共有 n 个，那么这些事件的所有排列组合就是 n!。比方事件a、b、c，不同的排列一共有这些：

{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}

一致性模型 就是要答复：在所有的这些可能存在的事件排列组合中，依照要求的一致性严格水平，哪些是能够承受的，哪些不可能呈现？

前面的讲述将看到：越是宽松的一致性模型，能包容的事件排列可能性就越多；反之越严格则越少。

一致性模型

本文中将探讨以下三种一致性模型：线性一致性、程序一致性、因果一致性，下面是依照严格程序排行的，也就是说线性一致性最严格、因果一致性则最弱。须要阐明的是，还存在其它一致性模型，然而不在本文的探讨范畴内。

程序一致性

程序一致性的定义最后呈现在论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Progranm》中，原文中要求程序一致性模型满足两个要求：

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

（任何执行的后果都与所有处理器的操作按某种程序执行的状况雷同，每个独自的处理器的操作按其程序指定的程序呈现在这个序列中。）

它有两个条件：

Requirement Rl: Each processor issues memory requests in the order specified by its program.

Requirement R2: Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.

先来看条件 1：

• 条件 1：每个过程的执行程序要和该过程的程序执行程序保持一致。

后面提到过，当读过程读到多过程的多个事件时，相当于把这些不同工夫、过程维度的事件“压平”到本过程的同一个工夫维度里，条件 1 要求这样被 压平 之后的程序，每个过程收回的事件的执行程序，和程序程序（program order）保持一致。

举一个违反这个条件的反例，如下图所示：

上图中：

• 过程 P1 视角下：程序的执行程序是先执行 P1_1，再执行 P1_2。
• 然而到了 P3 视角下重排事件之后，P1_2 呈现在了事件 P1_1 后面，这是不容许呈现的，因为违反了原过程 P1 的程序程序了。

然而，仅靠条件 1 还不足以满足程序一致性，于是还有条件 2：

• 条件 2：对变量的读写要体现得像 FIFO 一样先入先出，即 每次读到的都是最近写入的数据。

咱们来举一个例子来残缺阐明程序一致性：

上图中，有三个过程对变量 x 进行读写操作：

• 过程 P1：事件 P1_1 批改 x 为 A，事件 P1_2 批改 x 为 B。
• 过程 P2：事件 P2_1 批改 x 为 C。
• 过程 P3：事件 P3_1 读出 x 为 A，事件 P3_2 读出 x 为 C，事件 P3_1 读出 x 为 B。

留神：在上图中，事件 P1_2 和 P2_1 有重叠，意味着这两个事件是“并发事件”，即哪个事件先产生、实现都是能够承受的。

图中下半局部给出了三种可能的事件排列：

• 第一种排列：

  • 将事件对应的操作解读进去，那么执行程序为：{w(x)=A,r(x)=A,w(x)=B,r(x)=B,w(x)=C,r(x)=C}。
  • 能够看到，下面这个程序，既没有违反条件 1（因为同过程的程序程序没有被打乱），也没有违反条件 2（读出的都是开始写入的数据）。

• 第二种排列：

  • 将事件对应的操作解读进去，那么执行程序为：{w(x)=A,r(x)=A,w(x)=B,r(x)=C,w(x)=C,r(x)=B}。

  • 因为 p1_2 和 p2_1 是并发事件，能够任意排列两者的程序，这里抉择先执行 p1_2，能够看到：

    • w(x)=B,r(x)=C，这违反了条件 2。

• 第三种排列：

  • 将事件对应的操作解读进去，那么执行程序为：{w(x)=A,r(x)=A,w(x)=C,r(x)=B,w(x)=B,r(x)=C}。

  • 这一次抉择了先执行 p2_1，能够看到：

    • w(x)=C,r(x)=B 以及 w(x)=B,r(x)=C：违反了条件 2。
    • p3_3 先于 p3_2 执行，违反了条件 1。

以上就是程序一致性的解释，它要求两个条件：

• 不能打乱单过程的程序程序，同一个过程里的事件先后顺序要失去保留。
• 每次读出来的都是最新的值，而且一旦造成了一个排列，要求零碎中所有过程都是同样的一个排列。

这里须要特地阐明的是，只有满足这两个条件，并没有对 不同过程的事件 先后顺序其余硬性的规定，所以即使是某些事件在排列之后看起来违反了事件产生的先后顺序也是能够的。其实这在上图中曾经有体现了：

• 事件 p3_1 明明比事件 p1_2 和 p2_1 产生得更晚，然而只有在重排之后它是紧跟着 p1_1 的第一个读事件，就没有违反程序一致性。在这个大前提下，事件 p3_1 甚至能呈现在 p1_2 和 p2_1 之前，这看起来就很 违反直觉 了。

再比方下图：

在上图中，成心将三个事件画的离开一些，意味着三个事件并不重叠，即有明确的先后顺序，然而在程序一致性模型看来：

• {p1_1,p2_1,p3_1 和 p1_1,p3_1,p2_1} 都是对的，因为这两者都没有违反条件 1 和 2。
• 只有最上面的 {p3_1,P2_1,P1_1} 才是错的，因为违反了条件 2。

能够看到，程序一致性在满足了条件 1、2 之后，对 不同过程的事件 之间的程序没有硬性的要求，即使在感官直觉上某事件应该产生得更早，然而只有没有违反这两个条件就能够认为是满足程序一致性模型的。

于是就呈现了更严格的线性一致性，它基于程序一致性的条件，对事件的先后顺序做了更严格的要求。

线性一致性

线性一致性要求首先满足程序一致性的条件，同时还多了一个条件，无妨称之为条件 3：

• 条件 3：不同过程的事件，如果在工夫上不重叠，即不是并发事件，那么要求这个先后顺序在重排之后保持一致。

如果加上这个更强的条件，下面的图中，就只有 {P1_1,P2_1,P3_1} 是满足线性一致性的排列了。

再举一个例子来阐明线性一致性：

这还是最开始解释程序一致性模型的图，然而在线性一致性的条件下，找不到可能满足条件的排列了。

这是因为：

• 事件 P2_1 和 P1_2 都在事件 P1_1 之后，这个程序须要失去放弃。
• 而事件 P3_1 在事件 P2_1 和 P1_2 之后，这个程序也须要失去放弃。
• 如果放弃了后面两个程序，那么 P3_1 执行的时候，必然读不进去 A，而应该是 B 或者 C（即 P2_1 或者 P1_2 的执行后果）。

程序一致性和线性一致性总结

能够看到，如果满足线性一致性，就肯定满足程序一致性，因为后者的条件是前者的真子集。

除了满足这些条件以外，这两个一致性还有一个要求：零碎中所有过程的程序是统一的，即如果零碎中的过程 A 依照要求应用了某一种排序，即使有其余排序的可能性存在，零碎中的其余过程也必须应用这种排序，零碎中只能用一种满足要求的排序。

这个要求，使得满足程序和线性一致性的零碎，对外看起来“体现得像只有一个正本”一样。

但因果一致性则与此不同：只有满足因果一致性的条件，即使不同过程的事件排列不统一也没有关系。

因果一致性

相较于程序和线性一致性，因果一致性就简略一些，其实就只有满足在 Lamport 时钟中提到的 happen-before 关系即可：

• 引入符号→→做为示意事件之间 happen-before 的记号。

<!—->

• 在同一个过程中，如果事件 a 在事件 b 之前产生，那么 a→b。（这是因为依据规定 1，过程每次收回事件之后都会将本地的 lamport 时钟加一，于是能够在同一个过程内定义事件的先后顺序了）
• 在不同的过程中，如果事件 a 示意一个过程收回一个事件，事件 b 示意接管过程收到这个事件，那么也必然满足 a→b。（这是因为依据规定 2，接管过程在收到事件之后会取本地时钟和事件时钟的最大值并且 +1，于是收回事件和接管事件只管在不同的过程，然而也能够比拟其 lamport 时钟晓得其先后顺序了）
• 最初，happend-before 关系是满足传递性的，即：如果 a→b 且 b→c，那么也肯定有 a→c。

以 评论朋友圈 这个行为来解释因果一致性再适合不过：

• 评论另一个用户的评论：相当于过程给另一个过程发消息，必定要求满足 happen-before 关系，即先有了评论，能力针对这个评论发表评论。
• 同一个用户的评论：相当于同一个过程的事件，也是必须满足 happen-before 关系才行。

以下图为例：

一共有 4 个朋友圈的读者，它们看到的评论程序都各不一样：

• 最下面的两个读者，读到的程序都满足因果一致性，因而即使是不一样的程序也是正确的。

• 最上面的两个读者，程序都不满足因果一致性：

  • A 回复 B 这个事件呈现在了 B 回复 A 之前，不合乎多过程之间的 happen-before 关系。
  • A 回复 C 这个事件在过程 A 中应该在 A 回复 B 之前，不合乎同一过程的事件之间的先后顺序。

总结

• 在分布式系统中，多个过程组合在一起协调工作，产生多个事件，事件之间能够有多种排列的可能性。
• 一致性模型实质上要答复这个问题：依照该一致性模型定义，怎么的事件排列才符合要求？

• 程序一致性和线性一致性都用意让零碎中所有过程 看起来 有对立的全局事件程序，然而两者的要求不同，程序一致性：

  • 条件 1：每个过程的执行程序要和该过程的程序执行程序保持一致。
  • 条件 2：对变量的读写要体现得像 FIFO 一样先入先出，即每次读到的都是最近写入的数据。

  只有满足这两个条件，程序一致性对事件之间的先后顺序并没有硬性要求，而线性一致性在此基础上多了条件 3：

  • 条件 3：不同过程的事件，如果在工夫上不重叠，即不是并发事件，那么要求这个先后顺序在重排之后保持一致。
• 因果一致性是更弱的一致性，只有满足 happen-before 关系即可。因为 happen-before 关系实际上是由 Lamport 时钟定义的，这是一种逻辑时钟，所以不同的读者看到的先后顺序可能会有点 反直觉，然而只有满足 happen-before 关系就是正确的。

参考资料

[1]周刊（第 17 期）：Read-Write Quorum System 及在 Raft 中的实际: https://www.codedump.info/pos…
[2]happen-before: https://www.codedump.info/pos…
[3]How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Progranm: https://www.microsoft.com/en-…
[4]Linearizability: A Correctness Condition for Concurrent Objects:https://cs.brown.edu/~mph/Her…
[5]分布式系统一致性的倒退历史 (一):https://danielw.cn/history-of…
[6]条分缕析分布式：浅析强弱一致性 – 铁蕾的集体博客:http://zhangtielei.com/posts/… 对于

Databend

Databend 是一款开源、弹性、低成本，基于对象存储也能够做实时剖析的旧式数仓。期待您的关注，一起摸索云原生数仓解决方案，打造新一代开源 Data Cloud。

• Databend 文档：https://databend.rs/
• Twitter：https://twitter.com/Datafuse_…
• Slack：https://datafusecloud.slack.com/
• Wechat：Databend
• GitHub：https://github.com/datafusela…

文章首发于公众号：Databend