圖解一致性模型

引言

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

概述

解決什麼問題?

分佈式系統要保證系統的可用性,就需要對數據提供一定的冗餘度:一份數據,要存儲在多個服務器上,才能認爲保存成功,至於這裏要保存的冗餘數,有 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.

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

在上圖中:

接下來的問題是:

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

回答怎樣的順序規則纔是合理的,這就是一致性模型要解答的問題。

一致性模型圖例

本文意在使用各種圖例來解釋一致性模型,所以在繼續往下講解之前,有必要首先交待一下圖例中的各種元素,以下圖爲例:

在上圖中,有以下幾個元素:

單進程下的事件排列

我們繼續回到朋友圈的話題上來,一條朋友圈下面有多個人發表評論,可以認爲這是一個二維的數據:

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

在上圖中,在讀進程 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 要求這樣被壓平之後的順序,每個進程的執行順序,和程序順序(program order)保持一致。

舉一個違反這個條件的反例,如下圖所示:

上圖中:

但是,僅靠條件 1 還不足以滿足順序一致性,於是還有條件 2:

我們來舉一個例子說明:

上圖中,有三個進程對變量 x 進行讀寫操作:

注意:在上圖中,事件 P1_2 和P2_1 有重疊,意味着這兩個事件是 “併發事件”,即哪個事件先發生、完成都是可以接受的。

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

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

這裏需要特別說明的是,只要滿足這兩個條件,並沒有對事件的先後順序其他硬性的規定,所以即便是某些事件在排列之後看起來違反了事件發生的先後順序也是可以的。其實這在上圖中已經有體現了:

再比如下圖:

在上圖中,故意將三個事件畫的分開一些,意味着三個事件並不重疊,即有明確的先後順序,但是在順序一致性模型看來:

可以看到,順序一致性在滿足了條件 1、2 之後,對事件之間的順序沒有硬性的要求,即便在感官直覺上某事件應該發生得更早,但是隻要沒有違反這兩個條件就可以認爲是滿足順序一致性模型的。

於是就出現了更嚴格的線性一致性,它基於順序一致性的條件,對事件的先後順序做了更嚴格的要求。

線性一致性

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

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

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

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

這是因爲:

順序一致性和線性一致性總結

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

除了滿足這些條件以外,這兩個一致性還有一個要求:系統中所有進程的順序是一致的,即如果系統中的進程 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。

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

以下圖爲例:

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

總結

參考資料

[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。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/6G9ggjNxOoWIYgpB77lALg