[譯]強一致性模型

網路分區會出現。交換機、網卡、主機硬體、操作系統、磁碟、虛擬層和語言運行時（更不用說程序語義本身）都存在延遲、丟包、複製或者重新排序我們的消息。在不確定的世界中，我們希望我們的軟體保持在直覺上的正確性。

顯然我們需要直觀的正確性。做正確的事！但究竟什麼是正確的？我們如何描述它？在這篇文章中，我們會介紹一些「強」一致性模型，並看一下如何將他們組合在一起。

正確性

有很多方法可以表示演算法的抽象行為 —— 但現在我們假設一個系統由一個狀態和轉換該狀態的一些操作組成。隨著系統的運行，通過某種操作調度[注1]從一個狀態轉換到另一個狀態。

例如，狀態可能是一個變數，對狀態的操作可能是對變數的寫入和讀取。在這個簡單的 Ruby 程序中，可以寫入和讀取幾次，然後列印到屏幕來顯示讀取的內容。

x = "a"; puts x; puts xx = "b"; puts xx = "c"x = "d"; puts x

對這個程序的正確性，我們已經有了一個直觀的模型：應該輸出"aabd"。為什麼？因為每個語句都是按順序執行的。首先，寫入值 a，然後讀取值 a，讀取值 a，寫入值 b，等等。

一旦我們將一個變數設置為某個值，例如 a，讀取時就會返回 a，直到我們再次對值做了變更。讀取一個變數返回最近寫入的值。我們稱這種系統為有單一值的變數 —— 一個寄存器。

從我們開始編寫程序的第一天起，這種模式已經深入到了我們的大腦中，所以感覺就像第二天性，但這不是變數得以工作的唯一方式。一個變數在一次讀取時可能返回任意值：a、d 或者月球。如果這種情況發生，我們會說系統是不正確的，因為這些操作跟我們期望變數工作的方式不一樣。

這暗示了系統正確性的定義：給出一些與操作和狀態相關的規則，系統中的操作調度應該總是遵循這些規則。我們稱這些規則為一致性模型。

我們把關於寄存器的規則用簡單的英語描述出來，但是他們可能是任意的複雜數學結構。「讀取返回兩次寫入前的值，加上三，除非值為四，在這種情況下讀取可能返回貓或狗」也是一個一致性模型。就像「每次讀取都返回零」。我們甚至可以說「沒有任何規則；所有的操作都是允許的」。這是可以滿足的最容易的一致性模型；一般意義上說，每個系統都遵循這個模型。

更正式地說，我們說的一致性模型是所有允許操作的調度的集合。如果我們運行一個程序，然後執行在允許集合中的一系列操作，對於特定的執行操作是一致的。如果程序偶爾出現故障，經過了不在一致性模型中的一個調度，我們說調度是不一致的。如果每個可能的執行都在允許的集合中，則系統滿足一致性模型。我們希望真實的系統滿足「直觀正確」的一致性模型，以便我們可以編寫可預期的程序。

並發調度

現在我們假設有一個並發的程序，如用 Node.js 或 Erlang 寫的程序。有多個邏輯的控制線程，我們用術語「過程」來定義。如果我們用兩個過程來運行一個並發的程序，每一個都有相同的寄存器，我們前面提到的寄存器變數模型就被違反了。

這裡有兩個過程同時工作：稱之為"頂部"和"底部"。頂部的過程嘗試寫入 a、讀取、讀取。與此同時，底部的過程嘗試讀取、寫入 b、讀取。因為程序是並發的，從這兩個過程發出的操作可能會以多種不同的順序交錯，只要單個過程的操作按照指定的順序發生即可。在如上圖所示的這種特殊情況下，頂部過程寫入 a，底部過程讀取 a，頂部過程讀取 a，底部過程寫入 b，頂部過程讀取 b 和底部過程讀取 b。

有鑒於此，並發的概念呈現出不同的形態。我們假設每個程序執行的時候默認都是並發的，操作可能會以任意順序發生。一個線程、一個邏輯意義上的過程，無論如何，都是對調度的限制：屬於同一個線程的操作必須按順序進行。邏輯線程對允許的操作施加了部分順序的要求。

即使是這樣的順序，我們的寄存器變數 —— 從單個流程的角度來看，也不再成立。頂部過程寫入 a，讀取 a，然後讀取 b，並不是它寫入的值。我們必須放鬆一致性模型，來描述並發模型使其有用。現在，一個過程被允許讀取在任何過程最近寫入的值，而不僅僅是自己寫入的值。寄存器成為了兩個過程之間的協調點：他們共享狀態。

光椎[注2]

但是，這並不是全部情況：在真實的現實系統中，過程相互遠離。一個在內存中未緩存的值，例如距離 CPU 30cm 的 DIMM 上。需要整個納秒的光速距離 —— 真正內存訪問速度要慢得多。在不同數據中心的計算機中的一個值可能有幾千公里 —— 幾百毫秒的光速距離。我們不能以更快的速度發送信息；到目前為止，物理學還不允許。

這意味著我們的操作不再是瞬時的。其中一些可能很快，甚至可以忽略不計，但一般而言，操作需要時間。我們調用一個變數的寫入；寫入經過內存，或者一個計算機，或者經過月球；內存狀態發生改變；確認消息返回；然後我們才知道操作生效了。

將消息從一個地方發送到到另一個地方的延遲意味著操作調度的歧義。如果消息發送快了或者慢了，那就會有無法預期的順序。這裡，當值是 a 的時候，底部過程調用一次讀取。當讀取在進行中時，頂部過程寫入了 b，偶爾寫入會在讀取之前完成。底部的過程最後讀取到 b 而不是 a。

這個調度違反了我們的並發寄存器一致性模型，底部過程不能讀取到當前調用讀取時的值。我們可能會嘗試使用完成時間，而不是調用時間作為操作的真實時間，但是由於對稱性，同樣會失敗；如果讀取在寫入之前到達，過程會收到 a，而此時當前值是 b。

在分散式系統中，由於需要時間來完成一個操作，所以我們必須再次放鬆一致性模型，允許這些有歧義的順序發生。

我們必須走多遠？ 我們必須允許所有的順序嗎？ 還是我們仍然可以對現實世界加以理性分析？

線性化

通過仔細的檢查，事件順序有一些界限。我們不能逆時間發送消息，所以最早的消息能夠到達真實的來源，這是即時的。操作在調用之前無法生效。

同樣，通知一個過程其操作已經完成也不能逆時間，這意味著沒有任何操作可以在其完成之後生效。

如果我們假設有一個單一的全局狀態，每個過程都對其訪問；如果我們假設對這個狀態的操作時原子的，不會出現一個踩一個腳趾的情況；那麼確實我們可以排除很多調度。我們知道每個操作都會在調用和完成之間的某個點原子性生效。

我們稱這個一致性模型為線性化；雖然操作是並發的，並且需要時間，還是有一些地方 —— 或者是在一個地方出現，這裡每個操作按照很好的線性順序進行。

「單一全局狀態」不一定在一個節點上；也不一定操作必須是原子的。狀態可以被分割到多個機器上，或者在多個步驟中完成——只要外部的調度，從過程的角度來看，等同於原子的單一狀態即可。

通常，線性化系統由較小的協調過程組成，每個過程本身是線性化的；這些過程由仔細協調的較小的過程組成，直至由硬體提供線性化操作。

線性化有很強的結果，一旦操作完成，每個人必須看到當前狀態，或者後面的狀態。我們知道這是真的，因為每個操作必須在完成時間之前生效，任何後續調用操作必須在調用之後生效 —— 作為擴展，在原始操作之後。一旦我們成功寫入 b，每個後續的讀取調用必須看到 b，或者後面多次寫入之後的值。

我們可以使用線性化的原子約束來安全地改變狀態。我們可以定義像比較並設置（CAS）這樣的操作，當且僅當寄存器當前具有其他值時，我們設置寄存器中的值為新值。我們可以使用 CAS 作為互斥量、信號量、通道、計數器、列表、集合、映射、樹的基礎 —— 各種類型共享數據結構都可以用。線性化保證我們可以安全地交換變更。

此外，線性化的時間界限保證了這些變更在操作完成之後對其他參與者可見。因此，線性化禁止讀取舊值，每次讀取都會看到調用和完成之間的一些狀態；但是不是讀之前的狀態。它還禁止非單調讀入 —— 一個讀取新值一個讀取到舊值。

由於這些強約束，線性化系統更容易推理 —— 這就是為什麼它們被選為許多並發編程結構的基礎。Javascript 中的所有變數都是（獨立）線性化的；正如 Java 中的 volatile 變數，Clojure 中的原子或者 Erlang 中的單個進程一樣。大多數語言都有互斥鎖和信號量；這些也可以線性化。強的假設產生強的保證。

但是如果我們不能滿足這些假設會發生什麼？

順序一致性

如果我們允許過程在時間上出現歪斜，以便他們的操作可以在調用之前或完成之後生效 —— 但保留來自任何給定過程的操作必須在該過程中的順序的約束，這樣我們就得到了一個較弱的一致性：順序一致性。

順序一致性比線性一致性允許更多的調度 —— 但是仍然很有用：我們每天都在使用。當一個用戶上傳視頻到 YouTube 時，YouTube 將視頻放入到一個處理隊列，然後立即返回視頻的網頁。在這時，我們不能看視頻；視頻上傳在幾分鐘之後完成處理後生效。隊列在保證順序的同時（依賴隊列）移除了同步行為。

許多緩存也有類似順序一致性系統的行為。如果我在 Twitter 上發送推文或者發布到 Facebook，會透過緩存系統的各個層。不同的用戶會在不同的時間看到我的消息 —— 但是每個用戶看到我的操作是順序的。一旦看到之後，發布的消息就不會消失。如果我寫了多條評論，也會順序可見，而不是無序的。

因果一致性

我們不必強制要求一個過程的每個操作都是順序的。也許只有因果相關的操作必須按順序進行。例如，我們可以說，博客文章上的所有評論都必須以每個人相同的順序出現，並堅持只有在恢復的帖子可見之後，任何回復才能在過程中顯示。如果我們將諸如「我依賴操作 X」的因果關係編碼為每個操作的顯式部分，那麼資料庫可以延遲操作直到它具有所有操作的依賴關係。

這比在同一個過程中排序每個操作要弱 —— 來自相同過程，具有獨立因果鏈的操作可以按任何相對順序執行，但是阻止了很多不直觀的行為。

串列化一致性

如果我們說操作的調度等同於以某種單一原子順序發生的調度 —— 但對調用和完成時間沒有說明，我們就獲得了稱為串列化的一致性模型。 這個模型比你想像的要強得多，比你期望的要弱得多。

串列化是弱的，從某種意義上說，它允許許多類型的調度，因為它沒有按時間或順序排列界限。在上圖中，似乎消息可以額任意發送到過去或者未來，因果線允許被穿過。在串列化資料庫中，一個事務如讀取x總是被允許在時間0執行，不管 x 是否被初始化。或者它可能被無線延遲到未來時間！事務寫入2到x可能立刻被執行，或者被延遲到時間結束，沒有出現過一樣。

例如，在串列化系統中，程序

x = 1x = x + 1puts x

允許輸出 nil，1，2；因為操作可能會以任意順序發生。這是非常弱的約束！這裡我們假設每條線代表單個操作，所有操作都會成功。

另一方面，串列化是強的，從某種意義上它禁止了大量的調度，因為需要線性的調度。程序

print x if x = 3x = 1 if x = nilx = 2 if x = 1x = 3 if x = 2

只能有一種排序方式。不是以我們寫的代碼的順序執行，但是但它會可靠地將x從 nil - > 1 - > 2 - > 3 做變更，最後列印3。

因為串列化允許對操作任意重新排序（只要順序是原子的），對實際應用不是很有用。多部分資料庫聲稱提供的串列化實際是強串列化，與線性化一樣有時間界限。大部分 SQL 資料庫所稱的串列化一致性級別實際上的含義更弱一些，如可重複讀、游標穩定或者快照隔離，將事情進一步複雜化了。[注3]

一致性有成本

我們說「弱」一致性模型比「強」一致性模型允許更多的調度。例如，線性化保證操作在調用和完成之間完成。但是，施加順序約束需要協調。鬆散地說，我們排除的調度越多，系統中的參與者系統參與者越要小心溝通。

你可能聽說過 CAP 定理，該定理指出，考慮一致性、可用性和分區容錯，任何給定的系統都至多保證其中的兩個屬性。雖然 Eric Brewer 的 CAP 猜想被這些非正式的術語表達，但是 CAP 定理卻有著非常精確的定義：

1. 一致性的含義是線性化，特別指的是線性化寄存器。寄存器和其它系統中的包括集合、列表、映射、關係資料庫和其它等等都是等價的，所以定理可以被擴展為所有類型的線性化系統。
2. 可用性意味著對無故障節點的每個請求都必須成功完成。 由於網路分區允許持續任意長時間，這意味著節點不能簡單地推遲響應，直到分區恢復。
3. 分區容錯的含義是網路分區會出現。當網路可靠時，一致性和可用性很容易滿足。當網路不可靠時，提供這兩種保證是不可能的。如果你的網路不是完全可靠，你不能選擇 CA。這意味著商用硬體上的所有實用分散式系統都可以最大限度地保證 AP 或 CP。

「等等！」你可能會驚嘆。「線性化並不是最終所有的一致性模型！我可以通過提供順序一致性、串列化化或者快照隔離！」

這是真的；CAP 定理僅僅說明我們不能構建完全可用的線性化系統。問題是，我們有其它的證據告訴我們，你不能用順序、可序列化、可重複讀取、快照隔離或者游標穩定的一致性，或者比這些強的模型構建可用系統。來自 Peter Bailis 的高可用事務論文中上面的圖，紅色背景中的模型不能完全可用。

如果我們放鬆我們的可用性概念，例如客戶端節點必須總是與同一台伺服器通信，則可以實現某些類型的一致性。 我們可以提供因果一致性，PRAM [注4] 和讀寫一致性。

如果我們要求總是可用，那麼我們可以提供單調讀，單調寫入，讀已提交，單調原子視圖等等。這些是 Riak 和 Cassandra 等分散式存儲支持的一致性模型，或者是設置為較低隔離級別的 ANSI SQL 資料庫所支持的。這些一致性模型沒有像我們在前面的圖中畫的那樣的線性順序；相反，他們提供了部分順序，通過拼湊或者網頁的形式組合在一起。提供部分有序，有更廣的調度類別。

混合方法

一些演算法為了安全性需要依賴線性化。如果我們想構建一個分散式鎖服務，則需要線性化；沒有時間的界限，我們可能獲得一個來自未來時間或者過去時間的鎖。另一方面，許多演算法不需要線性化。最終一致的集合、列表、樹和映射，即使在「弱」一致性模型中，也可以用 CRDT 來表示。

強一致性模型需要更多的協調 —— 更多的來回消息，來保證正確的操作順序。不僅有更差的可用性，而且有更高的延遲約束。這就是為什麼現代的 CPU 內存模型默認不是線性化的原因（除非你顯式地這樣做），現代的 CPU 會對相對於其它核的內存操作重新排序，或者更糟。

雖然更難推理，但是性能優勢非常顯著。地理上分布的系統在數據中心之間有數百毫秒的延遲，通常會做出類似的權衡。

因此，在實踐中，我們使用混合數據存儲，將資料庫與各種一致性模型混合以實現冗餘、可用性、性能和安全的目標。儘可能提供「較弱」一致性模型，以確保可用性和性能。「更強」的一致性模型在必要時提供，例如演算法要求更嚴的操作順序。

你可以將大量數據寫入 S3，Riak 或 Cassandra，然後線性地將這些數據的指針直接寫入 Postgres、Zookeeper 或者 ETCD。一些資料庫承諾多種一致性模型，如關係資料庫的可調隔離級別，或者 Cassandra 和 Riak 的線性化事務，可以幫助減少系統的數量。但底線是：任何一個說他們的一致性模型是唯一正確選擇的人可能會推銷某些東西。魚和熊掌不能兼得[注5]。

為了對一致性模型有更細緻的理解，我想談談我們如何驗證線性化系統的正確性。在接下來的 Jepsen 的文章中，我們會討論我們為測試分散式系統而構建的線性化檢查器：Knossos。

有關這些模型的更正式的定義，請參考 Dziuma、Fatourou、Kanellou 關於一致性條件的調查報告。

譯者注

• 注1：原文中使用 歷史（history）來表示一系列的操作，其實也是我們更容易理解的 調度。參考《分散式系統原理（第3版）》第11章 分散式並發控制。
• 注2：在狹義相對論中，光錐（英語：Light cone）是閔可夫斯基時空下能夠與一個單一事件通過光速存在因果聯繫的所有點的集合，並且它具有洛倫茲不變性。 光錐也可以看作是閔可夫斯基時空下的一束光隨時間演化的軌跡。
• 注3：正確性原則：如果每個事務在隔離情況下執行（沒有任何其它事務與之同時執行），將把任何一致的狀態轉換到另一個一致的狀態。串列調度：一個事務的所有操作執行，然後另一個事務的所有操作執行，那麼這個調度是串列的。可串列化：如果存在一個串列調度 S，使得對於每個資料庫的狀態，調度 S 和調度 S 的效果相同，我們就說這個調度 S 是可串列化的。
• 注4：PRAM：Parallel random-access machine，在計算機科學中，PRAM 是一個共享內存抽象機器。
• 注5：You can』t have your cake and eat it too. 英語諺語。

原文：https://aphyr.com/posts/313-strong-consistency-models

作者：Aphyr

翻譯：王世德

推薦閱讀：