圖解一致性模型
引言
本文使用大量的圖例,同時沒有難懂的公式,意圖解釋清楚一致性模型要解決什麼問題,以及三種一致性模型:順序一致性、線性一致性、因果一致性。
概述
解決什麼問題?
分佈式系統要保證系統的可用性,就需要對數據提供一定的冗餘度:一份數據,要存儲在多個服務器上,才能認爲保存成功,至於這裏要保存的冗餘數,有 Majority 和 Quorum 之說,可以參考之前的文章:週刊(第 17 期):Read-Write Quorum System 及在 Raft 中的實踐 [1]。
同一份數據保存在多個機器上提供冗餘度,也被稱爲副本(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,除此以外:
-
w(x) = A:向變量 x 寫入 A。
-
r(x) = A:從變量 x 讀出 A。
-
事件有其開始、結束時間,使用一個矩形來表示一個事件的執行,這樣矩形的寬度可以認爲在時間軸上的寬度,即事件的執行時長。
-
事件與事件之間,在執行時間上可能發生重疊,如圖中的 P1_1和P2_1 ,這種有重疊的事件,被稱爲併發事件(concurrent event),在順序上,併發事件之間可以認爲誰先誰後都可以,後面會專門聊這部分。
-
使用不同的顏色來區分不同進程上發生的事件。
-
每個事件關聯一個操作,爲了簡化問題目前只有讀和寫操作:
單進程下的事件排列
我們繼續回到朋友圈的話題上來,一條朋友圈下面有多個人發表評論,可以認爲這是一個二維的數據:
-
進程(也就是發表評論的人)是一個維度。
-
時間又是另一個維度,即這些評論出現的先後順序。
但是在閱讀這些評論的讀者看來,需要將這一份二維的數據,去除掉不同進程這個維度,壓平到只有本進程時間線這一個單一維度上面來,以上面圖例來說就是這樣的:
在上圖中,在讀進程 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 還不足以滿足順序一致性,於是還有條件 2:
- 條件 2:對變量的讀寫要表現得像 FIFO 一樣先入先出,即每次讀到的都是最近寫入的數據。
我們來舉一個例子說明:
上圖中,有三個進程對變量 x 進行讀寫操作:
-
事件 P2_1 和 P1_2 都在事件 P1_1 之後,這個順序需要得到保持。
-
而事件 P3_1 在事件 P2_1 和 P1_2 之後,這個順序也需要得到保持。
-
如果保持了前面兩個順序,那麼 P3_1 執行的時候,必然讀不出來 A,而應該是 B 或者 C(即 P2_1 或者 P1_2 的執行結果)。
注意:在上圖中,事件 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)=B,r(x)=C,這違反了條件 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)=C,r(x)=B 以及 w(x)=B,r(x)=C:違反了條件 2。
-
P3_3先於 P3_2執行,違反了條件 1。
-
將事件對應的操作解讀出來,那麼執行順序爲:{w(x)=A,r(x)=A,w(x)=C,r(x)=B,w(x)=B,r(x)=C}。
-
這一次選擇了先執行 P2_1,可以看到:
以上就是順序一致性的解釋,它要求兩個條件:
-
不能打亂單進程的程序順序,同一個進程裏的事件先後順序要得到保留。
-
每次讀出來的都是最新的值,而且一旦形成了一個排列,要求系統中所有進程都是同樣的一個排列。
這裏需要特別說明的是,只要滿足這兩個條件,並沒有對事件的先後順序其他硬性的規定,所以即便是某些事件在排列之後看起來違反了事件發生的先後順序也是可以的。其實這在上圖中已經有體現了:
- 事件 P3_1 明明比事件P2_1 和P2_1 發生得更晚,但是隻要在重排之後它是緊跟着 P1_1的第一個讀事件,就沒有違反順序一致性。在這個大前提下,事件P3_1 甚至能出現在P2_1 和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[2] 關係即可:
引入符號 ->做爲表示事件之間 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 之前,不符合同一進程的事件之間的先後順序。
-
總結
-
在分佈式系統中,多個進程組合在一起協調工作,產生多個事件,事件之間可以有多種排列的可能性。
-
一致性模型本質上要回答這個問題:按照該一致性模型定義,怎樣的事件排列才符合要求?
-
順序一致性和線性一致性都意圖讓系統中所有進程看起來有統一的全局事件順序,但是兩者的要求不同,順序一致性:
只要滿足這兩個條件,順序一致性對事件之間的先後順序並沒有硬性要求,而線性一致性在此基礎上多了條件 3:
-
條件 3:不同進程的事件,如果在時間上不重疊,即不是併發事件,那麼要求這個先後順序在重排之後保持一致。
-
條件 1:每個進程的執行順序要和該進程的程序執行順序保持一致。
-
條件 2:對變量的讀寫要表現得像 FIFO 一樣先入先出,即每次讀到的都是最近寫入的數據。
-
因果一致性是更弱的一致性,只要滿足 happen-before 關係即可。由於 happen-before 關係實際上是由 Lamport 時鐘定義的,這是一種邏輯時鐘,所以不同的讀者看到的先後順序可能會有點反直覺,但是隻要滿足 happen-before 關係就是正確的。
參考資料
[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] 分佈式系統一致性的發展歷史 (一):
https://danielw.cn/history-of-distributed-systems-1
[6] 條分縷析分佈式:淺析強弱一致性 - 鐵蕾的個人博客:
http://zhangtielei.com/posts/blog-distributed-strong-weak-consistency.html
關於 Databend
Databend 是一款開源、彈性、低成本,基於對象存儲也可以做實時分析的新式數倉。期待您的關注,一起探索雲原生數倉解決方案,打造新一代開源 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
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/6G9ggjNxOoWIYgpB77lALg