引言：本文使用大量的圖例，同時沒有難懂的公式，意圖解釋清楚一致性模型要解決什么問題，以及三種一致性模型：順序一致性、線性一致性、因果一致性。

概述

解決什么問題？

分布式系統(tǒng)要保證系統(tǒng)的可用性，就需要對數(shù)據(jù)提供一定的冗余度：一份數(shù)據(jù)，要存儲在多個服務(wù)器上，才能認為保存成功，至于這里要保存的冗余數(shù)，有?Majority?和?Quorum?之說，可以參考之前的文章：周刊（第17期）：Read-Write Quorum System 及在 Raft 中的實踐。

同一份數(shù)據(jù)保存在多個機器上提供冗余度，也被稱為副本(replica)策略，這個做法帶來下面的好處：

• 容錯性：即便分布式系統(tǒng)中幾臺機器不能工作，系統(tǒng)還能照常對外提供服務(wù)。

• 提升吞吐量：既然同一份數(shù)據(jù)存儲在多個機器上，對該數(shù)據(jù)的請求（至少是讀請求）能夠分擔到多個副本上，這樣整個系統(tǒng)可以線性擴容增加更多的機器以應(yīng)付請求量的增加。

同時，副本策略也有自己需要解決的問題，其中最重要的問題就是一致性問題：在系統(tǒng)中的一個機器寫入的數(shù)據(jù)，是否在系統(tǒng)中其他機器看來也是一樣的？

很顯然，即便在一切都正常工作的條件下，在系統(tǒng)中的一個機器成功寫入了數(shù)據(jù)，因為廣播這個修改到系統(tǒng)中的其他機器還需要時間，那么系統(tǒng)的其他機器看到這個修改的結(jié)果也還是需要時間的。換言之，中間的這個時間差可能出現(xiàn)短暫的數(shù)據(jù)不一致的情況。

可以看到，由于這個時間差的客觀存在，并不存在一個絕對意義上的數(shù)據(jù)一致性。換言之，數(shù)據(jù)一致性有其實現(xiàn)的嚴格范圍，越嚴格的數(shù)據(jù)一致，要付出的成本、代價就越大。

為了解決一致性問題，需要首先定義一致性模型，在維基的頁面上，一致性模型（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.

我們舉一個日常生活中常見的問題來解釋一致性模型：

在上圖中：

• 不妨把朋友圈當成一個大型的分布式系統(tǒng)：

• 這個分布式系統(tǒng)，對外提供了寫入（發(fā)朋友圈）和讀?。?讀朋友圈）的功能。

• 存儲這些朋友圈數(shù)據(jù)的，肯定不止一臺機器，因此這些機器在一起構(gòu)成了這個大型的分布式系統(tǒng)。

• 不同的用戶，發(fā)朋友圈的時候，也不一定都寫入相同的一臺機器。反之也是，在讀朋友圈時也不一定會到同一臺機器上讀取數(shù)據(jù)。

• 朋友圈這個分布式系統(tǒng)，有兩種客戶端：發(fā)朋友圈的客戶端負責寫入數(shù)據(jù)，讀朋友圈的客戶端負責讀取數(shù)據(jù)，當然很多時候同一個客戶端既能讀也能寫。

接下來的問題是：

• 這些看朋友圈的人，是否能看到全局一致的數(shù)據(jù)？即所有人看到的朋友圈都是同一個順序排列的？

顯然，有很多時候，即便是在看同一個朋友圈下的評論回復，不同的人看到也不盡然都是同一個順序的，所以以上的答案是否定的。那么就引入了下一個問題：

• 如果不同的人看到的朋友圈（包括評論）順序各有不同，這些順序又該遵守怎樣的規(guī)則才是合理的？

回答怎樣的順序規(guī)則才是合理的，這就是一致性模型要解答的問題。

一致性模型圖例

本文意在使用各種圖例來解釋一致性模型，所以在繼續(xù)往下講解之前，有必要首先交待一下圖例中的各種元素，以下圖為例：

在上圖中，有以下幾個元素：

• 最左邊是分布式系統(tǒng)中的進程編號 P1、P2。

• 橫軸是時間軸，從左往右時間遞增，但是這里并沒有嚴格的時間刻度。

• 進程中發(fā)生的事件，事件的命名規(guī)則為進程編號_進程中的事件編號，比如 P1_1，除此以外：

• w(x) = A：向變量 x 寫入 A。

• r(x) = A：從變量 x 讀出 A。

• 事件有其開始、結(jié)束時間，使用一個矩形來表示一個事件的執(zhí)行，這樣矩形的寬度可以認為在時間軸上的寬度，即事件的執(zhí)行時長。

• 事件與事件之間，在執(zhí)行時間上可能發(fā)生重疊，如圖中的 P1_1 和 P2_1，這種有重疊的事件，被稱為并發(fā)事件（concurrent event），在順序上，并發(fā)事件之間可以認為誰先誰后都可以，后面會專門聊這部分。

• 使用不同的顏色來區(qū)分不同進程上發(fā)生的事件。

• 每個事件關(guān)聯(lián)一個操作，為了簡化問題目前只有讀和寫操作：

單進程下的事件排列

我們繼續(xù)回到朋友圈的話題上來，一條朋友圈下面有多個人發(fā)表評論，可以認為這是一個二維的數(shù)據(jù)：

• 進程（也就是發(fā)表評論的人）是一個維度。

• 時間又是另一個維度，即這些評論出現(xiàn)的先后順序。

但是在閱讀這些評論的讀者看來，需要將這一份二維的數(shù)據(jù)，去除掉不同進程這個維度，壓平到只有本進程時間線這一個單一維度上面來，以上面圖例來說就是這樣的：

在上圖中，在讀進程 P3 的視角看來，兩個寫進程的事件，需要壓平到本進程的時間線上進行排列，可以看到這些事件在壓平之后有多種排列的可能性。

將多個寫進程的事件進行排列，放到單進程的時間線上，這是一個排列組合問題，如果所有的寫進程事件加起來一共有n個，那么這些事件的所有排列組合就是 n!。比如事件a、b、c，不同的排列一共有這些：

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

一致性模型就是要回答：在所有的這些可能存在的事件排列組合中，按照要求的一致性嚴格程度，哪些是可以接受的，哪些不可能出現(xiàn)？

后面的講述將看到：越是寬松的一致性模型，能容納的事件排列可能性就越多；反之越嚴格則越少。

一致性模型

本文中將討論以下三種一致性模型：線性一致性、順序一致性、因果一致性，上面是按照嚴格順序排行的，也就是說線性一致性最嚴格、因果一致性則最弱。需要說明的是，還存在其它一致性模型，但是不在本文的討論范圍內(nèi)。

順序一致性

順序一致性的定義最初出現(xiàn)在論文《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.

（任何執(zhí)行的結(jié)果都與所有處理器的操作按某種順序執(zhí)行的情況相同，每個單獨的處理器的操作按其程序指定的順序出現(xiàn)在這個序列中。）

它有兩個條件：

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：每個進程的執(zhí)行順序要和該進程的程序執(zhí)行順序保持一致。

前面提到過，當讀進程讀到多進程的多個事件時，相當于把這些不同時間、進程維度的事件“壓平”到本進程的同一個時間維度里，條件 1 要求這樣被壓平之后的順序，每個進程發(fā)出的事件的執(zhí)行順序，和程序順序（program order）保持一致。

舉一個違反這個條件的反例，如下圖所示：

上圖中：

• 進程 P1 視角下：程序的執(zhí)行順序是先執(zhí)行?P1_1，再執(zhí)行?P1_2。

• 但是到了 P3 視角下重排事件之后，P1_2 出現(xiàn)在了事件 P1_1 前面，這是不允許出現(xiàn)的，因為違反了原進程 P1 的程序順序了。

但是，僅靠條件 1 還不足以滿足順序一致性，于是還有條件 2：

• 條件 2：對變量的讀寫要表現(xiàn)得像 FIFO 一樣先入先出，即每次讀到的都是最近寫入的數(shù)據(jù)。

我們來舉一個例子來完整說明順序一致性：

上圖中，有三個進程對變量 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 有重疊，意味著這兩個事件是“并發(fā)事件”，即哪個事件先發(fā)生、完成都是可以接受的。

圖中下半部分給出了三種可能的事件排列：

• 第一種排列：

• 將事件對應(yīng)的操作解讀出來，那么執(zhí)行順序為：{w(x)=A,r(x)=A,w(x)=B,r(x)=B,w(x)=C,r(x)=C}。

• 可以看到，上面這個順序，既沒有違反條件1（因為同進程的程序順序沒有被打亂），也沒有違反條件 2（讀出的都是開始寫入的數(shù)據(jù)）。

• 第二種排列：

• w(x)=B,r(x)=C，這違反了條件 2。

• 將事件對應(yīng)的操作解讀出來，那么執(zhí)行順序為：{w(x)=A,r(x)=A,w(x)=B,r(x)=C,w(x)=C,r(x)=B}。

• 由于 p1_2 和 p2_1 是并發(fā)事件，可以任意排列兩者的順序，這里選擇先執(zhí)行 p1_2，可以看到：

• 第三種排列：

• w(x)=C,r(x)=B?以及?w(x)=B,r(x)=C：違反了條件 2。

• p3_3 先于 p3_2 執(zhí)行，違反了條件 1。

• 將事件對應(yīng)的操作解讀出來，那么執(zhí)行順序為：{w(x)=A,r(x)=A,w(x)=C,r(x)=B,w(x)=B,r(x)=C}。

• 這一次選擇了先執(zhí)行 p2_1，可以看到：

以上就是順序一致性的解釋，它要求兩個條件：

• 不能打亂單進程的程序順序，同一個進程里的事件先后順序要得到保留。

• 每次讀出來的都是最新的值，而且一旦形成了一個排列，要求系統(tǒng)中所有進程都是同樣的一個排列。

這里需要特別說明的是，只要滿足這兩個條件，并沒有對不同進程的事件先后順序其他硬性的規(guī)定，所以即便是某些事件在排列之后看起來違反了事件發(fā)生的先后順序也是可以的。其實這在上圖中已經(jīng)有體現(xiàn)了：

• 事件 p3_1 明明比事件 p1_2 和 p2_1 發(fā)生得更晚，但是只要在重排之后它是緊跟著 p1_1 的第一個讀事件，就沒有違反順序一致性。在這個大前提下，事件p3_1 甚至能出現(xiàn)在 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 之后，對不同進程的事件之間的順序沒有硬性的要求，即便在感官直覺上某事件應(yīng)該發(fā)生得更早，但是只要沒有違反這兩個條件就可以認為是滿足順序一致性模型的。

于是就出現(xiàn)了更嚴格的線性一致性，它基于順序一致性的條件，對事件的先后順序做了更嚴格的要求。

線性一致性

線性一致性要求首先滿足順序一致性的條件，同時還多了一個條件，不妨稱之為條件3：

• 條件 3：不同進程的事件，如果在時間上不重疊，即不是并發(fā)事件，那么要求這個先后順序在重排之后保持一致。

如果加上這個更強的條件，上面的圖中，就只有 {P1_1,P2_1,P3_1} 是滿足線性一致性的排列了。

再舉一個例子來說明線性一致性：

這還是最開始解釋順序一致性模型的圖，但是在線性一致性的條件下，找不到能夠滿足條件的排列了。

這是因為：

• 事件 P2_1 和 P1_2 都在事件 P1_1 之后，這個順序需要得到保持。

• 而事件 P3_1 在事件 P2_1 和 P1_2 之后，這個順序也需要得到保持。

• 如果保持了前面兩個順序，那么 P3_1 執(zhí)行的時候，必然讀不出來 A，而應(yīng)該是 B 或者 C（即 P2_1 或者 P1_2 的執(zhí)行結(jié)果）。

順序一致性和線性一致性總結(jié)

可以看到，如果滿足線性一致性，就一定滿足順序一致性，因為后者的條件是前者的真子集。

除了滿足這些條件以外，這兩個一致性還有一個要求：系統(tǒng)中所有進程的順序是一致的，即如果系統(tǒng)中的進程 A 按照要求使用了某一種排序，即便有其他排序的可能性存在，系統(tǒng)中的其他進程也必須使用這種排序，系統(tǒng)中只能用一種滿足要求的排序。

這個要求，使得滿足順序和線性一致性的系統(tǒng)，對外看起來“表現(xiàn)得像只有一個副本”一樣。

但因果一致性則與此不同：只要滿足因果一致性的條件，即便不同進程的事件排列不一致也沒有關(guān)系。

因果一致性

相較于順序和線性一致性，因果一致性就簡單一些，其實就只要滿足在 Lamport 時鐘中提到的happen-before關(guān)系即可：

• 引入符號→→做為表示事件之間happen-before的記號。

• 在同一個進程中，如果事件 a 在事件 b 之前發(fā)生，那么 a→b。（這是因為根據(jù)規(guī)則 1，進程每次發(fā)出事件之后都會將本地的 lamport 時鐘加一，于是可以在同一個進程內(nèi)定義事件的先后順序了）

• 在不同的進程中，如果事件 a 表示一個進程發(fā)出一個事件，事件 b 表示接收進程收到這個事件，那么也必然滿足 a→b。（這是因為根據(jù)規(guī)則 2，接收進程在收到事件之后會取本地時鐘和事件時鐘的最大值并且 +1，于是發(fā)出事件和接收事件盡管在不同的進程，但是也可以比較其 lamport 時鐘知道其先后順序了）

• 最后，happend-before關(guān)系是滿足傳遞性的，即：如果 a→b 且 b→c，那么也一定有 a→c。

以評論朋友圈這個行為來解釋因果一致性再合適不過：

• 評論另一個用戶的評論：相當于進程給另一個進程發(fā)消息，肯定要求滿足?happen-before?關(guān)系，即先有了評論，才能針對這個評論發(fā)表評論。

• 同一個用戶的評論：相當于同一個進程的事件，也是必須滿足?happen-before?關(guān)系才行。

以下圖為例：

?一共有 4 個朋友圈的讀者，它們看到的評論順序都各不一樣：

• 最上面的兩個讀者，讀到的順序都滿足因果一致性，因此即便是不一樣的順序也是正確的。

• 最下面的兩個讀者，順序都不滿足因果一致性：

• A 回復 B 這個事件出現(xiàn)在了 B 回復 A 之前，不符合多進程之間的?happen-before?關(guān)系。

• A 回復 C 這個事件在進程 A 中應(yīng)該在 A 回復 B 之前，不符合同一進程的事件之間的先后順序。

總結(jié)

• 在分布式系統(tǒng)中，多個進程組合在一起協(xié)調(diào)工作，產(chǎn)生多個事件，事件之間可以有多種排列的可能性。

• 一致性模型本質(zhì)上要回答這個問題：按照該一致性模型定義，怎樣的事件排列才符合要求？

• 順序一致性和線性一致性都意圖讓系統(tǒng)中所有進程看起來有統(tǒng)一的全局事件順序，但是兩者的要求不同，順序一致性：

  只要滿足這兩個條件，順序一致性對事件之間的先后順序并沒有硬性要求，而線性一致性在此基礎(chǔ)上多了條件 3：

• 條件 3：不同進程的事件，如果在時間上不重疊，即不是并發(fā)事件，那么要求這個先后順序在重排之后保持一致。

• 條件 1：每個進程的執(zhí)行順序要和該進程的程序執(zhí)行順序保持一致。

• 條件 2：對變量的讀寫要表現(xiàn)得像 FIFO 一樣先入先出，即每次讀到的都是最近寫入的數(shù)據(jù)。

• 因果一致性是更弱的一致性，只要滿足?happen-before?關(guān)系即可。由于?happen-before?關(guān)系實際上是由 Lamport 時鐘定義的，這是一種邏輯時鐘，所以不同的讀者看到的先后順序可能會有點反直覺，但是只要滿足?happen-before?關(guān)系就是正確的。

參考資料

[1]周刊（第17期）：Read-Write Quorum System 及在 Raft 中的實踐:?https://www.codedump.info/post/20220528-weekly-17/
[2]happen-before:?https://www.codedump.info/post/20220703-weekly-21/#happen-before%E5%85%B3%E7%B3%BB
[3]How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Progranm:?https://www.microsoft.com/en-us/research/uploads/prod/2016/12/How-to-Make-a-Multiprocessor-Computer-That-Correctly-Executes-Multiprocess-Programs.pdf
[4]Linearizability: A Correctness Condition for Concurrent Objects:https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
[5]分布式系統(tǒng)一致性的發(fā)展歷史 (一):https://danielw.cn/history-of-distributed-systems-1
[6]條分縷析分布式：淺析強弱一致性 - 鐵蕾的個人博客:http://zhangtielei.com/posts/blog-distributed-strong-weak-consistency.html關(guān)于

Databend

Databend 是一款開源、彈性、低成本，基于對象存儲也可以做實時分析的新式數(shù)倉。期待您的關(guān)注，一起探索云原生數(shù)倉解決方案，打造新一代開源 Data Cloud。

• Databend 文檔：https://databend.rs/

• Twitter：https://twitter.com/Datafuse_Labs

• Slack：https://datafusecloud.slack.com/

• Wechat：Databend

• GitHub ：https://github.com/datafuselabs/databend