# 一致性與共識
LLMS 索引： [llms.txt](/tw/llms.txt)
---
> *古諺有云：“出海切勿帶兩隻航海鍾；要麼帶一隻，要麼帶三隻。”*
>
> 弗雷德裡克・P・布魯克斯，《人月神話：軟體工程隨筆》（1995）
正如[第 9 章](/tw/ch9#ch_distributed)所述，分散式系統裡可能出錯的事情很多。要讓服務在這些故障發生時仍能正確執行，就必須設法容忍故障。
*複製*（*replication*）是實現容錯最有力的工具之一。然而，正如[第 6 章](/tw/ch6#ch_replication)所示，把同一份資料複製到多個副本，也帶來了不一致的風險。讀請求可能由尚未追上進度的副本處理，返回陳舊結果；如果多個副本都能接受寫入，還必須解決不同副本上併發寫入的值之間的衝突。從總體上看，處理這類問題有兩種彼此競爭的思路：
最終一致性（eventual consistency）
: 這種思路把系統採用複製這一事實暴露給應用，由應用開發者處理隨之而來的不一致與衝突。採用[“多主複製”](/tw/ch6#sec_replication_multi_leader)和[“無主複製”](/tw/ch6#sec_replication_leaderless)的系統常常使用這種方式。
強一致性（strong consistency）
: 這種思路認為，應用不應操心複製的內部細節，系統應當表現得彷彿只有一個節點。它讓應用開發者的工作簡單得多，代價則是更強的一致性會損害效能，而且有些故障在最終一致系統中尚可容忍，卻會令強一致系統停擺。
一如既往，哪種方式更好取決於具體應用。如果應用允許使用者離線修改資料，那麼正如[“同步引擎與本地優先軟體”](/tw/ch6#sec_replication_offline_clients)所述，最終一致性不可避免。然而，應用要正確處理最終一致性也很困難。如果各副本位於通訊快速而可靠的資料中心，強一致性的成本通常可以接受，因而往往更合適。
本章將深入討論強一致性，重點考察三個方面：
1. “強一致性”這個說法相當含糊，因此我們先給出一個更精確的目標：*線性一致性*（*linearizability*）。
2. 接著討論 ID 和時間戳的生成。這個問題看似與一致性無關，實際上二者關係密切。
3. 最後探討分散式系統如何既實現線性一致性，又保持容錯能力；答案在於 *共識*（*consensus*）演算法。
在此過程中，我們會看到，分散式系統中什麼可以做到、什麼無法做到，受到一些根本限制。
本章討論的內容素以難以正確實現而著稱。一個系統在沒有故障時執行良好並不難，難的是它可能在某種設計者未曾考慮的不利故障組合下徹底崩潰。為幫助我們推理這些邊界情況，研究者發展出了大量理論；藉助這些理論，我們才能構建真正穩健的容錯系統。
本章只能淺嘗輒止：我們會採用非形式化的直觀解釋，避開演算法的繁瑣細節、形式化模型和證明。如果你打算認真從事共識系統或類似基礎設施的工作，就必須深入掌握相關理論，否則很難讓系統真正可靠。與往常一樣，本章參考文獻可以作為進一步學習的起點。
## 線性一致性 {#sec_consistency_linearizability}
要讓複製資料庫儘可能簡單易用，最好讓它表現得彷彿根本沒有複製。這樣，使用者就不必操心複製延遲、衝突和其他不一致問題：既能獲得容錯的好處，又不必承擔思考多個副本所帶來的複雜性。
這就是 *線性一致性*（*linearizability*）[^1]（也稱為 *原子一致性*，*atomic consistency* [^2]，*強一致性*，*strong consistency*，*即時一致性*，*immediate consistency*，或 *外部一致性*，*external consistency* [^3]）背後的思想。線性一致性的精確定義相當微妙，本節餘下部分會逐步展開；其基本思想，是讓系統看起來彷彿只有一份資料，所有操作都原子地作用於這份資料。有了這種保證，即使實際上存在多個副本，應用也無需關心它們。
在線性一致的系統中，只要一個客戶端成功完成寫入，此後所有客戶端從資料庫讀取時，都必須能看到剛寫入的值。要維持“只有一份資料”的假象，就必須保證讀到的是最近寫入的最新值，而不是來自陳舊快取或副本的舊值。換句話說，線性一致性是一種 *新鮮度保證*（*recency guarantee*）。下面用一個不滿足線性一致性的系統來說明這一點。
**圖 10-1.** 如果這個資料庫滿足線性一致性，那麼 Alice 的讀取應返回 1 而不是 0，或者 Bob 的讀取應返回 0 而不是 1。
[圖 10-1](/tw/ch10/#fig_consistency_linearizability_0)展示了一個不滿足線性一致性的體育網站 [^4]。Aaliyah 和 Bryce 坐在同一個房間裡，都在用手機關注自己喜愛球隊的比賽結果。終場比分剛剛公佈，Aaliyah 重新整理頁面，看到了獲勝方，便興奮地告訴 Bryce。Bryce 將信將疑地按下自己手機上的 *重新整理*，但請求被路由到一個落後的資料庫副本，於是頁面仍顯示比賽正在進行。
如果兩人同時重新整理，得到不同結果倒不那麼令人意外，因為誰也不知道伺服器究竟在什麼時刻處理了各自的請求。然而 Bryce 知道，自己是在聽見 Aaliyah 喊出終場比分 *之後* 才按下重新整理按鈕、發起查詢的，因此他有理由期待查詢結果至少不比 Aaliyah 看到的更舊。結果卻返回了陳舊資料，這就違反了線性一致性。
### 什麼使系統具有線性一致性？ {#sec_consistency_lin_definition}
為了更好地理解線性一致性，我們再看幾個例子。[圖 10-2](/tw/ch10/#fig_consistency_linearizability_1)展示了三個客戶端如何併發讀寫線性一致資料庫中的同一個物件 *x*。在分散式系統理論中，*x* 稱為 *暫存器*（*register*）；在實際系統裡，它可以是鍵值儲存中的一個鍵、關聯式資料庫中的一行，或文件資料庫中的一個文件。
**圖 10-2.** 如果讀請求與寫請求併發，則可能返回舊值，也可能返回新值。
為簡單起見，[圖 10-2](/tw/ch10/#fig_consistency_linearizability_1)只展示客戶端看到的請求，不涉及資料庫內部。每根橫條代表客戶端發出的一次請求：左端是請求發出的時刻，右端是客戶端收到響應的時刻。由於網路延遲變化不定，客戶端不知道資料庫究竟何時處理了請求，只知道處理一定發生在請求發出與響應到達之間。
在這個例子中，暫存器有兩種型別的操作：
* *read*(*x*) ⇒ *v* 表示客戶端請求讀取暫存器 *x*，資料庫返回值 *v*。
* *write*(*x*, *v*) ⇒ *r* 表示客戶端請求把暫存器 *x* 設為 *v*，資料庫返回響應 *r*（可以是 *ok* 或 *error*）。
在[圖 10-2](/tw/ch10/#fig_consistency_linearizability_1)中，*x* 的初始值為 0，客戶端 C 發出寫請求，要把它改為 1。在此期間，客戶端 A 和 B 不斷輪詢資料庫，讀取最新值。它們可能得到哪些響應？
* 客戶端 A 的第一次讀取在寫入開始前就已完成，因此必然返回舊值 0。
* 客戶端 A 的最後一次讀取在寫入完成後才開始，因此在線性一致的資料庫中必然返回新值 1，因為該讀取一定是在寫入之後處理的。
* 凡是時間上與寫操作重疊的讀取，都可能返回 0 或 1，因為我們不知道資料庫處理讀取時，寫入究竟是否已經生效。這些讀取與寫入是 *併發* 的。
但這還不足以完整描述線性一致性。如果與寫入併發的讀取可以任意返回舊值或新值，那麼在寫入期間，讀者可能看到值在新舊之間來回跳變。這不符合我們對“只有一份資料”的系統的預期。
要使系統滿足線性一致性，還需要增加一條約束，如[圖 10-3](/tw/ch10/#fig_consistency_linearizability_2)所示。
**圖 10-3.** 如果 Alice 和 Bob 擁有完美時鐘，線性一致性要求讀取返回 x \= 1，因為對 x 的讀取開始於 x \= 1 寫入完成之後。
在線性一致的系統中，可以設想在寫操作起止之間存在某個時刻，*x* 的值在那一刻原子地從 0 變為 1。因此，只要某個客戶端已經讀到新值 1，此後所有讀取也都必須返回 1，即使寫操作本身尚未結束。
[圖 10-3](/tw/ch10/#fig_consistency_linearizability_2)用箭頭標出了這種時序依賴。客戶端 A 最先讀到新值 1；A 的讀取剛一返回，B 就開始了新的讀取。由於 B 的讀取嚴格晚於 A 的讀取，它也必須返回 1，哪怕 C 的寫入仍在進行。（這與[圖 10-1](/tw/ch10/#fig_consistency_linearizability_0)中 Aaliyah 和 Bryce 的情形相同：Aaliyah 已經讀到新值之後，Bryce 也理應讀到新值。）
還可以進一步細化時序圖，把每個操作視為在某個時刻原子生效 [^5]，如[圖 10-4](/tw/ch10/#fig_consistency_linearizability_3)這個更複雜的例子所示。除了 *read* 和 *write*，圖中又加入了第三種操作：
* *cas*(*x*, *v* old, *v* new) ⇒ *r* 表示客戶端請求執行原子 *比較並設定*（*compare-and-set*）操作（參見[“條件寫入（比較並設定）”](/tw/ch8#sec_transactions_compare_and_set)）。如果暫存器 *x* 的當前值等於 *v* old，就原子地把它改為 *v* new；否則保持不變並返回錯誤。*r* 是資料庫的響應（*ok* 或 *error*）。
[圖 10-4](/tw/ch10/#fig_consistency_linearizability_3)在每次操作的橫條內畫了一根豎線，表示我們認為該操作實際生效的時刻。把這些標記依次連起來，必須得到暫存器的一條合法讀寫序列——每次讀取都應返回最近一次寫入所設定的值。
線性一致性要求，連線這些操作標記的線只能沿時間向前移動（從左向右），絕不能倒退。這項要求保證了前面所說的新鮮度：一旦新值已經被寫入或讀到，此後的讀取就都必須看到這個值，直至它再次被覆蓋。
**圖 10-4.** 對 x 的讀取與 x \= 1 的寫入併發。由於不知道操作的確切時序，讀取可以返回 0 或 1。
[圖 10-4](/tw/ch10/#fig_consistency_linearizability_3)中有幾個細節值得注意：
* 客戶端 B 先發出讀取 *x* 的請求，隨後 D 請求把 *x* 設為 0，A 又請求把 *x* 設為 1；但 B 最終讀到了 1，也就是 A 寫入的值。這沒有問題：它說明資料庫先處理 D 的寫入，再處理 A 的寫入，最後才處理 B 的讀取。這個順序雖然不同於請求發出的順序，卻仍然合法，因為三次請求彼此併發。也許 B 的讀請求在網路中耽擱了一會兒，直到兩次寫入之後才抵達資料庫。
* 客戶端 B 在 A 收到資料庫確認“寫入 1 成功”的響應之前，就已經讀到了 1。這也沒有問題，只說明資料庫發給 A 的 *ok* 響應在網路中有所延遲。
* 這個模型不作任何事務隔離假設，其他客戶端隨時都可能修改值。例如，C 先讀到 1，隨後又讀到 2，是因為兩次讀取之間 B 修改了該值。原子的比較並設定（*cas*）操作可以檢查某個值是否已被其他客戶端併發修改：B 和 C 的 *cas* 請求成功，而 D 的 *cas* 請求失敗，因為資料庫處理該請求時，*x* 已經不再等於 0。
* 客戶端 B 最後一次讀取（陰影橫條）不滿足線性一致性。該讀取與 C 的 *cas* 寫入併發，後者把 *x* 從 2 改為 4。若沒有其他請求，B 返回 2 原本是允許的；但在 B 開始讀取之前，客戶端 A 已經讀到了新值 4，因此 B 不能再讀到比 A 更舊的值。這仍然是[圖 10-1](/tw/ch10/#fig_consistency_linearizability_0)中 Aaliyah 與 Bryce 的同一種情形。
以上就是線性一致性的直觀含義，形式化定義 [^1] 對此有更精確的描述。可以記錄所有請求與響應的時序，再檢查它們能否排成一條合法的順序序列，以此檢驗系統行為是否滿足線性一致性；只是這種檢驗的計算成本很高 [^6] [^7]。
正如事務除了可序列化之外還有各種[“弱隔離級別”](/tw/ch8#sec_transactions_isolation_levels)，複製系統除了線性一致性之外，也有許多較弱的一致性模型 [^8]。我們在[“複製延遲的問題”](/tw/ch6#sec_replication_lag)中見過的 *寫後讀*、*單調讀* 和 *一致字首讀*，就是這類較弱保證。線性一致性不僅包含所有這些保證，還提供得更多。本章將集中討論線性一致性——實際系統中常用的最強一致性模型。
> [!TIP] 線性一致性與可序列化
>
> 線性一致性很容易與[“可序列化”](/tw/ch8#sec_transactions_serializability)混淆，因為兩個名稱看起來都像是在說“可以排成某種順序”。但二者是完全不同的保證，必須加以區分：
>
> 可序列化
> : 可序列化是事務的一項隔離屬性；每個事務可以讀寫 *多個物件*（行、文件或記錄）。它保證事務的行為等同於按 *某種* 序列順序執行：先完整執行一個事務，再完整執行下一個事務，彼此不交錯。這個序列順序可以不同於事務實際執行的順序 [^9]。
>
> 線性一致性
> : 線性一致性是對暫存器（即 *單個物件*）讀寫的保證。它不會把操作組合成事務，因此無法防止[“寫偏差與幻讀”](/tw/ch8#sec_transactions_write_skew)這類涉及多個物件的問題。但線性一致性是一項 *新鮮度* 保證：如果一個操作在另一個操作開始前已經結束，那麼後一個操作必須觀察到至少與前一個操作同樣新的狀態。可序列化沒有這項要求，例如它允許陳舊讀取 [^10]。
>
> （*順序一致性* 又是另外一回事 [^8]，但我們不會在這裡討論它。）
>
> 資料庫可以同時提供可序列化與線性一致性，這種組合稱為 *嚴格可序列化*（*strict serializability*）或 *強單副本可序列化*（*strong one-copy serializability*，*strong-1SR*）[^11] [^12]。單節點資料庫通常滿足線性一致性。對於採用[“可序列化快照隔離（SSI）”](/tw/ch8#sec_transactions_ssi)等樂觀方法的分散式資料庫，情況要複雜一些。例如，CockroachDB 提供可序列化以及一定的讀取新鮮度保證，卻不提供嚴格可序列化 [^13]，因為後者要求事務之間進行代價高昂的協調 [^14]。
>
> 也可以把較弱的隔離級別與線性一致性組合，或把較弱的一致性模型與可序列化組合。事實上，一致性模型與隔離級別在很大程度上可以獨立選擇 [^15] [^16]。
### 依賴線性一致性 {#sec_consistency_linearizability_usage}
線性一致性在什麼情況下有用？檢視體育比賽的終場比分也許只是個無關緊要的例子：結果陳舊幾秒，通常不會造成實際損失。然而在少數領域，線性一致性卻是系統正確工作的必要條件。
#### 鎖定與領導者選舉 {#locking-and-leader-election}
採用單主複製的系統必須確保領導者確實只有一個，而不是同時出現多個領導者（腦裂）。一種選舉辦法是使用租約：每個啟動的節點都嘗試獲取租約，成功者成為領導者 [^17]。無論底層機制如何實現，都必須滿足線性一致性，絕不能讓兩個不同節點同時獲得同一份租約。
Apache ZooKeeper [^18]、etcd 等協調服務經常用於實現分散式租約和領導者選舉。它們藉助共識演算法，以容錯方式提供線性一致的操作（本章稍後會討論這些演算法）。要正確實現租約和領導者選舉，還有許多微妙細節，例如[“分散式鎖和租約”](/tw/ch9#sec_distributed_lock_fencing)所述的柵欄問題。Apache Curator 等庫在 ZooKeeper 之上封裝了更高層的慣用方案，可以減輕這項工作；而所有這些協調任務的根基，仍是線性一致的儲存服務。
> [!NOTE]
> 嚴格來說，ZooKeeper 的寫入滿足線性一致性，但讀取可能陳舊，因為它不保證讀請求一定由當前領導者處理 [^18]。從版本 3 開始，etcd 預設提供線性一致的讀取。
一些分散式資料庫還會在細得多的粒度上使用分散式鎖，例如 Oracle Real Application Clusters（RAC）[^19]。RAC 為每個磁碟頁設定一把鎖，多個節點共享同一套磁碟儲存。由於這些線性一致的鎖位於事務執行的關鍵路徑上，RAC 部署通常會使用專用的叢集互連網路，讓資料庫節點彼此通訊。
#### 約束與唯一性保證 {#sec_consistency_uniqueness}
唯一性約束在資料庫中十分常見。例如，使用者名稱或電子郵件地址必須唯一標識一位使用者；檔案儲存服務也不能同時存在路徑和檔名完全相同的兩個檔案。如果要在寫入時強制執行這種約束——也就是說，兩個人併發建立同名使用者或檔案時，必須讓其中一人收到錯誤——就需要線性一致性。
這種情形其實與鎖很相似：使用者註冊服務時，可以看作在獲取所選使用者名稱的“鎖”。這個操作也很像原子的比較並設定：只要使用者名稱尚未被佔用，就把它設為認領該名稱的使用者 ID。
類似的問題還有很多：確保銀行賬戶餘額永不為負，商品銷量不超過倉庫庫存，或不讓兩個人同時訂到同一航班、同一劇場的同一個座位。這些約束都要求存在一個由所有節點共同認可的最新值，例如賬戶餘額、庫存數量或座位佔用狀態。
實際應用有時可以寬鬆處理此類約束。例如航班超售後，可以把旅客轉到另一趟航班，併為造成的不便提供補償。在這種情況下，線性一致性未必必要；[“及時性與完整性”](/tw/ch13#sec_future_integrity)會進一步討論這種寬鬆解釋的約束。
不過，關聯式資料庫裡常見的硬性唯一約束確實需要線性一致性。外來鍵約束、屬性約束等其他約束則可以不依賴線性一致性來實現 [^20]。
#### 跨通道時序依賴 {#cross-channel-timing-dependencies}
請注意[圖 10-1](/tw/ch10/#fig_consistency_linearizability_0)中的一個細節：如果 Aaliyah 沒有喊出比分，Bryce 就不會知道自己的查詢結果已經陳舊。他只會在幾秒後再次重新整理，並最終看到終場比分。之所以能察覺違反線性一致性的現象，只是因為系統裡還有一條額外的通訊通道——Aaliyah 的聲音傳到了 Bryce 耳中。
計算機系統中也會出現類似情形。假設某網站允許使用者上傳影片，後臺程序會把影片轉碼為畫質較低的版本，以便透過慢速網路流式播放。系統架構和資料流如[圖 10-5](/tw/ch10/#fig_consistency_transcoder)所示。
影片轉碼器必須收到明確指令才會執行轉碼作業，這條指令由 Web 伺服器透過訊息佇列傳送（參見[“訊息傳遞系統”](/tw/ch12#sec_stream_messaging)）。Web 伺服器不會把整段影片塞進佇列，因為大多數訊息代理是為短訊息設計的，而影片可能有數十兆位元組甚至更大。它會先把影片寫入檔案儲存服務，確認寫入完成後，再將轉碼指令放入佇列。
**圖 10-5.** 一個不滿足線性一致性的系統：Alice 和 Bob 在不同時刻看到上傳的影象，因此 Bob 的請求建立在陳舊資料之上。
如果檔案儲存服務滿足線性一致性，這套系統就能正常工作；否則便可能出現競態條件：訊息佇列（[圖 10-5](/tw/ch10/#fig_consistency_transcoder)中的步驟 3 和 4）也許比儲存服務內部的複製傳播得更快。這樣一來，轉碼器獲取原始影片時（步驟 5），可能讀到檔案的舊版本，甚至什麼也讀不到。如果它轉碼了舊版本，檔案儲存中的原始影片與轉碼版本就會永久不一致。
問題的根源在於，Web 伺服器與轉碼器之間存在兩條不同的通訊通道：檔案儲存和訊息佇列。沒有線性一致性提供的新鮮度保證，兩條通道之間就可能發生競態。這與[圖 10-1](/tw/ch10/#fig_consistency_linearizability_0)完全類似：一條通道是資料庫複製，另一條則是從 Aaliyah 嘴裡到 Bryce 耳中的現實聲音。
能接收推送通知的移動應用也可能遇到類似競態：應用收到通知後會向伺服器獲取相關資料；如果讀請求可能落到滯後的副本上，推送通知也許很快就到了，緊隨其後的資料讀取卻看不到通知所指的更新。
線性一致性不是避免這類競態的唯一辦法，卻是最容易理解的一種。如果額外的通訊通道由你控制——訊息佇列屬於這種情況，Aaliyah 和 Bryce 之間的交流則不屬於——也可以採用與[“讀己之寫”](/tw/ch6#sec_replication_ryw)類似的替代方案，只是系統會更加複雜。
### 實現線性一致性系統 {#sec_consistency_implementing_linearizable}
看過線性一致性的幾個用途後，接下來思考如何實現一個提供線性一致語義的系統。
線性一致性本質上要求系統“表現得彷彿只有一份資料，而且所有操作都原子地作用於它”，因此最簡單的實現就是真的只儲存一份資料。可惜這種方式無法容錯：儲存這份資料的節點一旦失效，資料就會丟失，至少也會在節點恢復前無法訪問。
讓我們重新審視[第 6 章](/tw/ch6#ch_replication)介紹的複製方法，看看它們能否實現線性一致性：
單主複製（可能線性一致）
: 在單主複製系統中，領導者儲存用於寫入的主副本，其他節點上的追隨者則維護備份。只要所有讀寫都由領導者處理，通常就有可能滿足線性一致性。但這依賴一個前提：你必須確切知道誰是領導者。正如[“分散式鎖和租約”](/tw/ch9#sec_distributed_lock_fencing)所述，節點完全可能誤以為自己仍是領導者；如果這個自以為是的領導者繼續處理請求，就很可能破壞線性一致性 [^21]。採用非同步複製時，故障切換甚至可能丟失已經提交的寫入，同時違反永續性與線性一致性。
對單主資料庫進行分片、讓每個分片擁有各自的領導者，不會影響線性一致性，因為它只保證單個物件。跨分片事務則是另一個問題（參見[“分散式事務”](/tw/ch8#sec_transactions_distributed)）。
共識演算法（很可能線性一致）
: 有些共識演算法本質上是增加了自動領導者選舉和故障切換的單主複製。它們經過精心設計以避免腦裂，因而能夠安全實現線性一致的儲存。例如，ZooKeeper 使用 Zab 共識演算法 [^22]，etcd 使用 Raft [^23]。不過，系統採用了共識，並不等於它的所有操作都滿足線性一致性：如果某個節點處理讀取前沒有確認自己仍是領導者，那麼在剛剛選出新領導者時，它就可能返回陳舊結果。
多主複製（非線性一致）
: 多主複製系統通常不滿足線性一致性，因為多個節點會併發處理寫入，再把結果非同步複製到其他節點。因此，它們可能產生需要[“處理寫入衝突”](/tw/ch6#sec_replication_write_conflicts)的併發寫入。
無主複製（很可能不滿足線性一致性）
: 對於採用無主複製的系統（Dynamo 風格，參見[“無主複製”](/tw/ch6#sec_replication_leaderless)），有人聲稱，只要要求仲裁讀寫滿足 *w* + *r* > *n*，就能得到“強一致性”。這取決於具體演算法以及“強一致性”的定義，但通常並不準確。
Cassandra 和 ScyllaDB 等系統採用基於日曆時鐘的“最後寫入者勝”來解決衝突，這幾乎肯定不滿足線性一致性，因為時鐘偏差使時間戳無法保證與事件的實際順序一致（參見[“對同步時鐘的依賴”](/tw/ch9#sec_distributed_clocks_relying)）。即使採用仲裁讀寫，仍然可能出現違反線性一致性的行為，下一節會給出例子。
#### 線性一致性與仲裁 {#sec_consistency_quorum_linearizable}
直覺上，Dynamo 風格模型中的仲裁讀寫似乎應當滿足線性一致性。但當網路延遲變化不定時，仍然可能出現競態，如[圖 10-6](/tw/ch10/#fig_consistency_leaderless)所示。
**圖 10-6.** 當網路延遲變化不定時，僅靠法定人數不足以保證線性一致性。
在[圖 10-6](/tw/ch10/#fig_consistency_leaderless)中，*x* 的初始值為 0。一個寫入客戶端把請求發往全部三個副本（*n* = 3，*w* = 3），要將 *x* 更新為 1。與此同時，客戶端 A 從兩個節點讀取，達到讀法定人數（*r* = 2），並在其中一個節點上看到了新值 1；同樣與寫入併發的客戶端 B，則從另外兩個節點讀取，兩個節點都返回舊值 0。
儘管滿足法定人數條件 *w* + *r* > *n*，這次執行仍不滿足線性一致性：B 的請求開始於 A 的請求完成之後，卻返回了舊值，而 A 已經讀到新值。（這又是[圖 10-1](/tw/ch10/#fig_consistency_linearizability_0)中 Aaliyah 和 Bryce 的情形。）
可以讓 Dynamo 風格的法定人數讀寫滿足線性一致性，但要犧牲效能：讀取方必須先同步完成[“追趕錯過的寫入”](/tw/ch6#sec_replication_read_repair)所述的讀修復，再把結果返回應用 [^24]；寫入方則必須在寫入前先讀取達到法定人數的節點的最新狀態，取得此前所有寫入中的最大時間戳，並確保新寫入使用更大的時間戳 [^25] [^26]。Riak 因為效能代價而不執行同步讀修復。Cassandra 的仲裁讀確實會等待讀修復完成 [^27]，但它使用日曆時鐘生成時間戳，因而仍然不滿足線性一致性。
而且，這種方式只能實現線性一致的讀寫；無法實現線性一致的比較並設定，因為後者需要共識演算法 [^28]。
總之，最穩妥的假設是：採用 Dynamo 風格複製的無主系統即使使用仲裁讀寫，也不提供線性一致性。
### 線性一致性的代價 {#sec_linearizability_cost}
既然有些複製方式能夠提供線性一致性，有些不能，我們就有必要更仔細地考察它的利弊。
[第 6 章](/tw/ch6#ch_replication)已經討論過不同複製方式的適用場景。例如，對多地區複製而言，多主複製往往是不錯的選擇（參見[“跨地域執行”](/tw/ch6#sec_replication_multi_dc)）。[圖 10-7](/tw/ch10/#fig_consistency_cap_availability)展示了這樣一種部署。
**圖 10-7.** 如果網路分割槽使客戶端無法聯絡足夠多的副本，它們就無法處理寫入。
考慮兩個地區之間網路中斷時會發生什麼。假設各地區內部的網路仍然正常，客戶端也能訪問本地區域，但兩個地區彼此無法通訊。這種情況稱為 *網路分割槽*（*network partition*）。
在多主資料庫中，每個地區都可以繼續正常工作：一地的寫入原本就非同步複製到另一地，因此網路中斷期間只需暫存排隊，連線恢復後再相互交換。
若採用單主複製，領導者必然位於其中一個地區。所有寫入和線性一致讀取都必須發給領導者；因此，連線到追隨者所在地區的客戶端，必須跨地區同步地把讀寫請求傳送到領導者所在地區。
單主配置下，一旦地區間網路中斷，追隨者所在地區的客戶端便無法聯絡領導者，因而既不能寫入資料庫，也不能執行線性一致讀取。它們仍可從追隨者讀取，但結果可能陳舊，不滿足線性一致性。如果應用要求線性一致的讀寫，那麼所有無法聯絡領導者的地區都會在網路中斷期間變得不可用。
能直接連線領導者所在地區的客戶端不受影響，應用在那裡仍可正常工作；但只能訪問追隨者所在地區的客戶端會一直停擺，直到網路鏈路修復。
#### CAP 定理 {#the-cap-theorem}
這個問題並非單主複製與多主複製特有：任何線性一致的資料庫，無論怎樣實現，都會面對同樣的困境。它也不限於多地區部署；任何不可靠的網路都可能發生這種情況，即使是在同一地區內。具體權衡如下：
* 如果應用 *要求* 線性一致性，而網路故障使一部分副本與其他副本失去聯絡，那麼斷開的副本就不能繼續處理請求：它們只能等待網路恢復，或立即返回錯誤；無論哪種方式，都變得 *不可用*。這種選擇有時稱為 *CP*（網路分割槽時保持一致）。
* 如果應用 *不要求* 線性一致性，就可以讓各副本在彼此斷開時仍獨立處理請求，例如採用多主複製。這樣，應用在網路故障期間仍然 *可用*，但行為不滿足線性一致性。這種選擇稱為 *AP*（網路分割槽時保持可用）。
因此，不要求線性一致性的應用可以更好地容忍網路問題。這一認識通常稱為 *CAP 定理* [^29] [^30] [^31] [^32]，由 Eric Brewer 於 2000 年命名，不過早在 20 世紀 70 年代，分散式資料庫設計者就已瞭解這種權衡 [^33] [^34] [^35]。
CAP 最初只是一個沒有精確定義的經驗法則，目的是引發對資料庫權衡的討論。當時許多分散式資料庫都專注於在共享儲存的機器叢集上提供線性一致語義 [^19]；CAP 則鼓勵資料庫工程師探索更廣闊的分散式無共享系統設計空間，而後者更適合承載大規模 Web 服務 [^36]。CAP 推動了這種觀念轉變，也幫助催生了 NoSQL 運動以及 21 世紀頭十年中期湧現的大批新型資料庫技術。
> [!TIP] 幫不上忙的 CAP 定理
>
> CAP 有時被概括成 *一致性、可用性、分割槽容錯性，三者擇二*。遺憾的是，這種說法會誤導人 [^32]：網路分割槽是一類故障，並不是可以自由取捨的選項——不管你願不願意，它都會發生。
>
> 網路正常時，系統完全可以同時提供一致性（線性一致性）與全面可用性；發生網路故障時，才必須在線性一致性和全面可用性之間取捨。因此，更準確的說法是：*發生分割槽時，要麼一致，要麼可用* [^37]。網路越可靠，面臨這種選擇的次數就越少，但它終究無法徹底避免。
>
> CP/AP 分類還有幾個缺陷 [^4]。其中的 *一致性* 被嚴格定義為線性一致性，定理對較弱的一致性模型隻字未提；*可用性* 的形式化定義 [^30] 也不符合這個詞的通常含義 [^38]。許多通常認為高度可用、具備容錯能力的系統，其實並不滿足 CAP 那套特殊的可用性定義。還有些系統設計者出於充分理由，既不提供線性一致性，也不提供 CAP 所假設的那種可用性，因此既不能歸為 CP，也不能歸為 AP [^39] [^40]。
>
> 總而言之，圍繞 CAP 的誤解與混淆太多，它無助於我們更好地理解系統，因此最好避免使用 CAP 這一框架。
>
> 形式化的 CAP 定理 [^30] 適用範圍極窄：它只考察一種一致性模型（線性一致性）和一種故障（網路分割槽；Google 的資料表明，網路分割槽造成的事故不到 8% [^41]），對網路延遲、節點失效以及其他權衡都沒有說明。因此，CAP 雖然在歷史上影響深遠，對實際系統設計卻幾乎沒有指導價值 [^4] [^38]。
>
> 有人嘗試把 CAP 推廣到更一般的情形。例如，*PACELC 原則* 指出，即便網路正常，系統設計者也可能為了降低延遲而削弱一致性 [^39] [^40] [^42]：發生網路分割槽（P）時，需要在可用性（A）與一致性（C）之間選擇；否則（E），沒有分割槽時，則可能在低延遲（L）與一致性（C）之間選擇。不過，這個定義繼承了 CAP 的若干問題，例如對一致性和可用性的定義仍然有違直覺。
>
> 分散式系統領域還有許多更有意義的不可能性結論 [^43]，CAP 也早已被更精確的結果取代 [^44] [^45]。如今，它主要只剩下歷史意義。
#### 線性一致性與網路延遲 {#linearizability-and-network-delays}
線性一致性雖然很有用，實際滿足它的系統卻少得出人意料。甚至現代多核 CPU 上的 RAM 也不滿足線性一致性 [^46]：一個 CPU 核上的執行緒寫入某個記憶體地址後，另一個核上的執行緒稍晚讀取同一地址，也不保證能看見前一個執行緒寫入的值，除非使用 *記憶體屏障* 或 *柵欄* [^47]。
原因在於，每個 CPU 核都有自己的快取和儲存緩衝區。預設情況下，記憶體訪問會先經過快取，修改再非同步寫回主存。訪問快取遠快於訪問主存 [^48]，因此這種機制對現代 CPU 的效能不可或缺。但系統裡也因此出現了多份資料——主存中一份，各級快取裡可能還有幾份——而且它們非同步更新，於是失去了線性一致性。
為什麼要作這種取捨？用 CAP 定理解釋多核處理器的記憶體一致性模型毫無意義：在同一臺計算機內，我們通常假定通訊可靠，也不指望某個 CPU 核與計算機其他部分斷開後還能正常工作。這裡犧牲線性一致性是為了 *效能*，而不是容錯 [^39]。
許多不提供線性一致性保證的分散式資料庫也是如此：主要目的是提高效能，而非增強容錯 [^42]。線性一致性很慢，而且始終如此，並非只在網路故障時才慢。
有沒有更高效的線性一致儲存實現？答案似乎是否定的。Attiya 和 Welch [^49] 證明：要獲得線性一致性，讀寫請求的響應時間至少與網路延遲的不確定程度成正比。在大多數計算機網路這種延遲高度不穩定的環境裡（參見[“超時和無界延遲”](/tw/ch9#sec_distributed_queueing)），線性一致讀寫的響應時間必然很高。不存在更快的線性一致性演算法，而較弱的一致性模型卻可以快得多，因此這種取捨對延遲敏感型系統十分重要。[“及時性與完整性”](/tw/ch13#sec_future_integrity)將討論如何在不犧牲正確性的前提下繞開線性一致性。
## ID 生成器和邏輯時鐘 {#sec_consistency_logical}
許多應用在建立資料庫記錄時，都要為其分配某種唯一 ID，作為以後引用該記錄的主鍵。單節點資料庫通常使用自增整數，它的優點是隻需 64 位即可儲存；如果能確定記錄數永遠不會超過 40 億，甚至可以只用 32 位，不過這樣做頗有風險。
自增 ID 還有一個好處：ID 順序可以反映記錄的建立順序。例如，[圖 10-8](/tw/ch10/#fig_consistency_id_generator)中的聊天應用會在訊息發出時為其分配自增 ID。按 ID 遞增順序展示訊息，對話就能保持合理的先後關係：Aaliyah 的問題得到 ID 1，而 Bryce 隨後的回答得到更大的 ID 3。
**圖 10-8.** 兩個不同節點可能生成相互衝突的 ID。
這種單節點 ID 生成器也是一個線性一致系統。每次取 ID 都會原子地遞增計數器並返回遞增前的值，這稱為 *獲取並增加*（fetch-and-add）操作。線性一致性保證：如果 Aaliyah 的訊息在 Bryce 開始發訊息之前已經發布完成，那麼 Bryce 的 ID 必須更大。[圖 10-8](/tw/ch10/#fig_consistency_id_generator)中 Aaliyah 與 Caleb 的訊息彼此併發，因此線性一致性不規定二者的 ID 順序，只要求它們互不相同。
記憶體中的單節點 ID 生成器很容易實現：直接使用 CPU 提供的原子遞增指令，就能讓多個執行緒安全地更新同一個計數器。要把計數器做成持久的稍微麻煩一些，否則節點崩潰重啟後計數器會復位，產生重複 ID。但更棘手的問題是：
* 單節點 ID 生成器不具備容錯能力，因為這個節點本身就是單點故障。
* 如果要在另一個地區建立記錄，僅僅為了取得 ID，可能就得跨越半個地球往返一次，速度很慢。
* 寫入吞吐量很高時，這個節點可能成為瓶頸。
ID 生成器還有幾種替代方案：
分片 ID 分配
: 可以讓多個節點分別分配 ID，例如一個只生成偶數，另一個只生成奇數。更一般地，可以在 ID 中預留若干位來儲存分片編號。這種 ID 仍然緊湊，卻失去了順序含義：看到 ID 為 16 和 17 的兩條聊天訊息，並不能斷定訊息 16 先發出，因為兩個 ID 來自不同節點，而其中一個節點的進度可能領先於另一個。
預分配 ID 塊
: 單節點生成器不必逐個發放 ID，也可以一次分配一整塊。例如，節點 A 取得 1 到 1,000，節點 B 取得 1,001 到 2,000；此後各節點可在自己的區間內獨立發號，快用完時再申請下一塊。但這種方案同樣無法保證正確順序：一條訊息可能先從 1,001 到 2,000 的區間取得 ID，而稍後另一節點發出的訊息卻從 1 到 1,000 的區間取得了更小的 ID。
隨機 UUID
: 可以採用 *通用唯一識別符號*（UUID），也稱 *全域性唯一識別符號*（GUID）。它最大的好處是，任意節點都能在本地生成，無需通訊；代價是佔用更多空間（128 位）。UUID 有多個版本，最簡單的第 4 版本質上是一個足夠長的隨機數，兩個節點碰巧選中同一值的機率微乎其微。可惜這類 ID 的順序也是隨機的，比較兩個 ID 無法判斷哪個更新。
為日曆時鐘時間戳補充唯一性資訊
: 如果各節點透過 NTP 讓日曆時鐘大致準確，可以把時間戳放在 ID 的高位，再用額外資訊填充其餘位，保證即使時間戳相同，完整 ID 仍然唯一。例如，可以加入分片編號和分片內自增序列號，或一段足夠長的隨機值。第 7 版 UUID [^50]、Twitter Snowflake [^51]、ULID [^52]、Hazelcast Flake ID 生成器、MongoDB ObjectID 等許多方案都採用這種思路 [^50]。這類 ID 生成器既可以在應用程式碼中實現，也可以放在資料庫內部 [^53]。
這些方案都能生成唯一 ID——至少碰撞機率低到幾乎可以忽略——但它們提供的順序保證遠弱於單節點自增方案。
正如[“用於事件排序的時間戳”](/tw/ch9#sec_distributed_lww)所述，日曆時鐘時間戳至多隻能給出近似順序：如果較早的寫入讀取了略快的時鐘，較晚的寫入讀取了略慢的時鐘，時間戳順序就可能與事件實際順序相反。非單調時鐘還可能突然跳變，甚至讓同一節點生成的時間戳順序出錯。因此，基於日曆時鐘的 ID 生成器通常不滿足線性一致性。
使用原子鐘或 GPS 接收器進行高精度時鐘同步，可以減少這種順序錯亂。但如果無需特殊硬體，也能生成唯一且順序正確的 ID，當然更好。這正是 *邏輯時鐘*（*logical clock*）要解決的問題。
### 邏輯時鐘 {#sec_consistency_timestamps}
在[“不可靠的時鐘”](/tw/ch9#sec_distributed_clocks)中，我們討論了日曆時鐘和單調時鐘。二者都屬於 *物理時鐘*，度量的是經過了多少秒（或毫秒、微秒等）。
分散式系統還經常使用另一類時鐘，稱為 *邏輯時鐘*（*logical clock*）。物理時鐘是計算流逝秒數的硬體裝置；邏輯時鐘則是一種計算已發生事件數量的演算法。因此，邏輯時間戳不能告訴你現在是幾點，卻 *可以* 相互比較，判斷哪個較早、哪個較晚。
邏輯時鐘的要求通常是：
* 時間戳緊湊（只有幾個位元組）且唯一；
* 任意兩個時間戳都可以比較，也就是構成 *全序*；
* 時間戳順序與因果關係 *一致*：如果操作 A 先於 B 發生，那麼 A 的時間戳小於 B 的時間戳。（我們在[“‘先發生’關係與併發”](/tw/ch6#sec_replication_happens_before)中討論過因果關係。）
單節點 ID 生成器滿足這些要求，而前面幾種分散式 ID 生成器不滿足因果順序要求。
#### Lamport 時間戳 {#lamport-timestamps}
幸運的是，有一種簡單方法可以生成與因果關係 *一致* 的邏輯時間戳，並將其用作分散式 ID。這就是 Leslie Lamport 於 1978 年提出的 *Lamport 時鐘* [^54]；介紹它的論文如今已成為分散式系統領域引用次數最多的論文之一。
[圖 10-9](/tw/ch10/#fig_consistency_lamport_ts)展示了 Lamport 時鐘如何用於[圖 10-8](/tw/ch10/#fig_consistency_id_generator)中的聊天示例。每個節點都有唯一識別符號；[圖 10-9](/tw/ch10/#fig_consistency_lamport_ts)使用“Aaliyah”“Bryce”和“Caleb”作為標識，實際系統則可以使用隨機 UUID 等值。此外，每個節點維護一個計數器，記錄自己處理過多少次操作。Lamport 時間戳就是一個二元組（*計數器*，*節點 ID*）。不同節點的計數器值有時相同，但加入節點 ID 後，每個時間戳仍然唯一。
**圖 10-9.** Lamport 時間戳給出了與因果關係一致的全序。
節點每生成一次時間戳，都會先遞增本地計數器並使用新值。節點每次看到其他節點生成的時間戳時，如果其中的計數器值大於自己的本地值，就把本地計數器向前推進到同一個值。
在[圖 10-9](/tw/ch10/#fig_consistency_lamport_ts)中，Aaliyah 發出自己的訊息時尚未看見 Caleb 的訊息，Caleb 也一樣。假設兩人的計數器初始值都是 0，他們各自將其遞增為 1，並把新值附在訊息上。Bryce 收到這兩條訊息後，把自己的計數器推進到 1；隨後他回覆 Aaliyah 的訊息，再把本地計數器遞增為 2，並將 2 附在回覆上。
比較兩個 Lamport 時間戳時，先比較計數器值。例如，(2, “Bryce”) 大於 (1, “Aaliyah”)，也大於 (1, “Caleb”)。若計數器相同，再按通常的字串字典序比較節點 ID。因此，本例中的時間戳順序為 (1, “Aaliyah”) < (1, “Caleb”) < (2, “Bryce”)。
#### 混合邏輯時鐘 {#hybrid-logical-clocks}
Lamport 時間戳很適合表示事件發生順序，但也有一些侷限：
* 它與物理時間沒有直接關係，所以無法據此查詢某個具體日期釋出的所有訊息；物理時間必須另行儲存。
* 如果兩個節點從不通訊，一個節點的計數器增長就永遠不會反映到另一個節點上。因此，不同節點在大致同一時刻生成的事件，計數器值可能相差懸殊。
*混合邏輯時鐘*（*hybrid logical clock*，HLC）兼具物理日曆時鐘的優點與 Lamport 時鐘的順序保證 [^55]。它像物理時鐘一樣以秒或微秒計數；又像 Lamport 時鐘一樣，在看到其他節點更大的時間戳時，把自己的本地值向前推進到對方的時間戳。因此，如果某個節點的時鐘偏快，其他節點與它通訊後也會相應地把時鐘向前推進。
混合邏輯時鐘每次生成時間戳時也會遞增，從而保證始終單調向前，即使底層物理時鐘因 NTP 校正而向後跳變也不例外。因此，混合邏輯時鐘可能略微領先於底層物理時鐘；演算法會盡量把這項誤差控制在最小範圍內。
因此，混合邏輯時間戳幾乎可以像普通日曆時間戳一樣使用，同時還多了一項性質：其順序與先發生關係一致。它不依賴特殊硬體，只要求各時鐘大致同步。CockroachDB 就使用了混合邏輯時鐘。
#### Lamport/混合邏輯時鐘 vs. 向量時鐘 {#lamporthybrid-logical-clocks-vs-vector-clocks}
在[“多版本併發控制（MVCC）”](/tw/ch8#sec_transactions_snapshot_impl)中，我們討論過快照隔離的一種常見實現：為每個事務分配事務 ID，讓它看見 ID 較小的事務所做的寫入，同時隱藏 ID 較大的事務所做的寫入。Lamport 時鐘和混合邏輯時鐘很適合生成這些事務 ID，因為它們可以保證快照與因果關係一致 [^56]。
多個時間戳併發生成時，這些演算法會任意規定它們之間的順序。因此，只看兩個時間戳，通常無法判斷二者是併發生成，還是一個先於另一個發生。（在[圖 10-9](/tw/ch10/#fig_consistency_lamport_ts)中，因為 Aaliyah 與 Caleb 的訊息具有相同計數器值，可以斷定它們彼此併發；但計數器值不同時，就無法作出這種判斷。）
如果需要判斷記錄是否併發建立，就得采用另一種演算法，例如 *向量時鐘*（*vector clock*）。它的缺點是時間戳大得多，可能需要為系統中的每個節點儲存一個整數。有關併發檢測的更多細節，參見[“檢測併發寫入”](/tw/ch6#sec_replication_concurrent)。
### 線性一致的 ID 生成器 {#sec_consistency_linearizable_id}
Lamport 時鐘與混合邏輯時鐘雖然提供了實用的順序保證，卻仍弱於前面那種線性一致的單節點 ID 生成器。回想一下，線性一致性要求：只要請求 A 在請求 B 開始前已經完成，B 的 ID 就必須更大，即使二者從未彼此通訊。Lamport 時鐘只能保證節點新生成的時間戳大於它此前 *見過* 的所有時間戳，對未曾見過的時間戳則無法作出任何保證。
[圖 10-10](/tw/ch10/#fig_consistency_permissions)展示了不滿足線性一致性的 ID 生成器會造成什麼問題。假設某個社交網站的使用者 A 想把一張難為情的照片只分享給朋友。A 的賬戶原本公開；A 先在膝上型電腦上把賬戶設為私密，隨後又用手機上傳照片。這些操作由 A 依次完成，因此 A 有理由認為，上傳的照片會受新的私密賬戶許可權保護。
**圖 10-10.** 一個使用 Lamport 時間戳的許可權系統。
賬戶許可權與照片儲存在兩個獨立資料庫中（也可能是同一資料庫的不同分片），並假設二者都用 Lamport 時鐘或混合邏輯時鐘為寫入分配時間戳。照片資料庫沒有讀取賬戶資料庫，因此它的本地計數器可能稍微落後，導致照片上傳得到的時間戳反而小於賬戶設定更新的時間戳。
接著，假設一位並非 A 好友的訪客正在瀏覽 A 的個人資料，而這次讀取由實現快照隔離的 MVCC 處理。訪客讀取的時間戳可能大於照片上傳，卻小於賬戶許可權更新。系統於是認定，在這個快照中賬戶仍是公開的，並把本不該讓訪客看到的照片顯示出來。
這個問題有幾種可能的修復方式。也許照片資料庫應在寫入前讀取使用者賬戶狀態，但開發者很容易漏掉這項檢查。如果 A 的所有操作都來自同一臺裝置，裝置上的應用或許能跟蹤該使用者最近一次寫入的時間戳；可本例中使用者同時使用膝上型電腦和手機，事情就沒那麼簡單。
這裡最簡單的解決方案，是使用線性一致的 ID 生成器，保證照片上傳取得的 ID 一定大於賬戶許可權變更的 ID。
#### 實現線性一致的 ID 生成器 {#implementing-a-linearizable-id-generator}
確保 ID 分配滿足線性一致性的最簡單辦法，確實是使用單個節點。這個節點只需在收到請求時原子遞增計數器並返回結果，同時持久化計數器值，以免崩潰重啟後產生重複 ID，再用單主複製實現容錯。實際系統也採用這種方案：受 Google Percolator [^57] 啟發，TiDB/TiKV 將其稱為 *時間戳預言機*（timestamp oracle）。
可以透過批次預留來避免每次請求都寫盤和複製。ID 生成器先寫入一條記錄，宣告某一批 ID；這條記錄持久化並完成複製後，節點便可按順序把其中的 ID 發給客戶端。在這一批快要用完前，再提前持久化並複製下一批。這樣，節點崩潰重啟或故障切換到追隨者時，可能會跳過一些 ID，卻絕不會發出重複或順序錯誤的 ID。
ID 生成器很難分片：多個分片獨立發號後，就無法再保證整體順序滿足線性一致性。它也很難分佈到多個地區，因此地理分散式資料庫中的所有 ID 請求，都得發往某個固定地區的節點。好在 ID 生成器的工作十分簡單，單個節點就能承擔很高的請求吞吐量。
如果不想採用單節點 ID 生成器，還有 Google Spanner 的做法，參見[“用於全域性快照的同步時鐘”](/tw/ch9#sec_distributed_spanner)。它依賴一種物理時鐘：返回的不是單個時間戳，而是一個時間戳區間，表示時鐘讀數的不確定性；系統會等待這個不確定區間完全過去之後再返回結果。
只要不確定區間確實可靠——真實物理時間始終落在區間內——這個過程同樣能保證：若一個請求在另一個請求開始前完成，後一個請求就取得更大的時間戳。它無需節點間通訊就能實現線性一致的 ID 分配；即使請求來自不同地區，也能正確排序，不必等待跨地區往返。代價是必須有相應的軟硬體支援，既要讓時鐘高度同步，又要計算必要的不確定區間。
#### 使用邏輯時鐘強制約束 {#enforcing-constraints-using-logical-clocks}
在[“約束與唯一性保證”](/tw/ch10#sec_consistency_uniqueness)中，我們看到，線性一致的比較並設定可以用來實現分散式鎖、唯一性約束等構造。於是自然會問：邏輯時鐘或線性一致的 ID 生成器，是否也足以實現這些功能？
答案是：還不夠。若多個節點都在爭搶同一把鎖或註冊同一個使用者名稱，可以用邏輯時鐘為請求分配時間戳，並選出時間戳最小者。如果時鐘滿足線性一致性，那麼此後所有請求生成的時間戳都更大，也就不可能再出現比當前勝者更小的時間戳。
可惜問題還有一半沒有解決：節點怎樣知道自己的時間戳就是最小的？要做到確定無疑，它必須收到 *每一個* 可能生成時間戳的其他節點的訊息 [^54]。只要其中一個節點失效，或因網路問題無法聯絡，整個系統就會停滯，因為誰也無法排除那個節點擁有更小時間戳的可能。這顯然不是我們想要的容錯系統。
要以容錯方式實現鎖、租約等構造，需要比邏輯時鐘或 ID 生成器更強的工具：我們需要共識。
## 共識 {#sec_consistency_consensus}
本章已經見過好幾個例子：只用單個節點時，事情十分簡單；一旦還要求容錯，就會困難得多：
* 只設一個領導者，並讓所有讀寫都由它處理，資料庫便可以具有線性一致性。可是，如果這個領導者失效，怎樣才能在避免腦裂的同時完成故障切換？怎樣確保某個自認為仍是領導者的節點，其實沒有在此期間被投票罷免？
* 單節點上的線性一致 ID 生成器，不過是一個帶有原子“獲取並增加”指令的計數器；但如果這個節點崩潰了呢？
* 原子比較並設定（CAS）操作用途廣泛：例如，多個程序爭搶鎖或租約時決定誰能獲得它，或者確保給定名稱的檔案或使用者具有唯一性。在單個節點上，CAS 可能只需一條 CPU 指令；但怎樣才能讓它容錯？
事實證明，這些都是同一個分散式系統基本問題的不同例項：*共識*（*consensus*）。共識是分散式計算中最重要、最基本的問題之一；同時，它也出了名地難以正確實現 [^58] [^59]，許多系統都曾在這裡栽過跟頭。至此，我們已經討論過複製（[第 6 章](/tw/ch6#ch_replication)）、事務（[第 8 章](/tw/ch8#ch_transactions)）、系統模型（[第 9 章](/tw/ch9#ch_distributed)）以及線性一致性（本章），終於可以正面處理共識問題了。
最著名的共識演算法包括檢視戳複製（Viewstamped Replication，VSR）[^60] [^61]、Paxos [^58] [^62] [^63] [^64]、Raft [^23] [^65] [^66] 和 Zab [^18] [^22] [^67]。這些演算法有不少相似之處，但並不完全相同 [^68] [^69]。它們採用非拜占庭系統模型：網路通訊可以被任意延遲或丟棄，節點可以崩潰、重啟或斷開連線；但除此之外，演算法假定節點都會正確遵守協議，不會採取惡意行為。
另一些共識演算法可以容忍一部分拜占庭節點，也就是不正確遵守協議的節點（例如，它們會向不同節點傳送相互矛盾的訊息）。這類演算法通常假定，出現拜占庭故障的節點少於三分之一 [^26] [^70]。這樣的 *拜占庭容錯*（BFT）共識演算法會用於區塊鏈 [^71]。不過，正如 [“拜占庭故障”](/tw/ch9#sec_distributed_byzantine) 所述，BFT 演算法不在本書的討論範圍之內。
> [!TIP] 共識的不可能性
>
> 你可能聽說過 FLP 結果 [^72]——這個名字取自三位作者 Fischer、Lynch 和 Paterson。它證明：只要存在節點崩潰的可能，就沒有一種演算法能保證 *始終* 達成共識。分散式系統必須假定節點可能崩潰，這豈不是意味著可靠的共識根本不可能？可我們現在又在討論實現共識的演算法，這究竟是怎麼回事？
>
> 首先，FLP 並沒有說共識永遠無法達成，只是說我們無法保證共識演算法 *每次都能* 終止。此外，FLP 的證明針對非同步系統模型中的確定性演算法（見 [“系統模型與現實”](/tw/ch9#sec_distributed_system_model)），也就是說，演算法不能使用任何時鐘或超時。只要允許演算法根據超時懷疑另一個節點可能已經崩潰——哪怕這種懷疑偶爾會出錯——共識就變得可以解決 [^73]。甚至只需允許演算法使用隨機數，也足以繞過這個不可能性結果 [^74]。
>
> 因此，儘管 FLP 的共識不可能性結果在理論上極為重要，分散式系統在實踐中通常仍能達成共識。
### 共識的多面性 {#sec_consistency_faces}
共識可以用幾種不同的方式表達：
* *單值共識*（*single-value consensus*）與原子 *比較並設定* 操作非常相似，可以用來實現鎖、租約和唯一性約束。
* 構建 *僅追加日誌*（*append-only log*）同樣需要共識；這個問題通常形式化為 *全序廣播*（*total order broadcast*）。有了日誌，就可以構建 *狀態機複製*（*state machine replication*）、基於領導者的複製、事件溯源以及其他許多有用的機制。
* 多資料庫或多分片事務的 *原子提交*（*atomic commitment*），要求所有參與者就是否提交或中止事務達成一致。
下面很快就會逐一探討這些形式。事實上，這幾個問題彼此等價：只要有一種演算法能解決其中一個問題，就可以把它轉換成其他任意一種問題的解法。這是一個相當深刻、甚至有些出人意料的洞見！也正因為如此，儘管它們表面上截然不同，我們仍可以把它們統統歸入“共識”這一範疇。
#### 單值共識 {#single-value-consensus}
共識的標準表述涉及讓多個節點就單個值達成一致。例如：
* 採用單主複製的資料庫初次啟動時，或現有領導者失效時，可能有多個節點同時試圖成為領導者。同樣，多個節點也可能競相獲取同一把鎖或同一份租約。共識可以幫助它們決定由誰勝出。
* 如果幾個人同時試圖預訂飛機上的最後一個座位、劇院裡的同一個座位，或用相同的使用者名稱註冊賬戶，共識演算法可以確定哪一個請求應當成功。
更一般地說，一個或多個節點可以 *提議* 某個值，而共識演算法從中 *決定* 一個值。在上述例子中，每個節點都可以提議自己的 ID，演算法則決定哪個節點 ID 應當成為新的領導者、租約持有者或機票／戲票的購買者。在這種形式化定義下，共識演算法必須滿足以下屬性 [^26]：
一致同意
: 任意兩個節點都不會作出不同的決定。
完整性
: 節點一旦決定了某個值，就不能再決定另一個值來改變主意。
有效性
: 如果某個節點決定了值 *v*，那麼 *v* 必須由某個節點提議過。
終止
: 每個未崩潰的節點最終都能決定某個值。
如果需要決定多個值，可以為每個值分別執行一個共識演算法例項。例如，可以為劇院中每個可預訂的座位分別執行一次共識，從而為每個座位作出一項決定（確定一位買家）。
一致同意與完整性定義了共識的核心思想：所有節點都決定相同的結果，而且一旦作出決定，就不能再改變主意。有效性排除了平凡的解法：例如，無論節點提議什麼，演算法都一律決定 `null`；這種演算法滿足一致同意與完整性，卻不滿足有效性。
如果不關心容錯，滿足前三個屬性很容易：只需把一個節點硬編碼為“獨裁者”，由它作出所有決定即可。但這個節點一旦失效，系統便再也無法作出任何決定——這與沒有故障切換的單主複製如出一轍。所有困難都源於容錯這一要求。
終止屬性形式化了容錯的含義。它實質上要求共識演算法不能永遠無所作為——換句話說，演算法必須取得進展。即使一部分節點失效，其餘節點仍須作出決定。（終止是一種活性屬性，另外三種則是安全屬性，見 [“安全性與活性”](/tw/ch9#sec_distributed_safety_liveness)。）
如果崩潰的節點還有可能恢復，當然可以等它回來。然而，共識必須保證，即使某個節點突然消失而且永遠不再回來，系統仍能作出決定。（不要只想象軟體崩潰；想象一場地震引發山體滑坡，徹底摧毀了節點所在的資料中心。必須假定這個節點被埋在 30 英尺深的泥土下，再也不會重新上線。）
當然，如果 *所有* 節點都已崩潰，無一仍在執行，那麼任何演算法都不可能決定任何事情。演算法能容忍的故障數量存在上限：事實上，可以證明，任何共識演算法都要求至少多數節點正常執行，才能保證終止 [^73]。這組多數節點可以安全地構成法定人數（見 [“讀寫仲裁”](/tw/ch6#sec_replication_quorum_condition)）。
因此，終止屬性以少於一半節點崩潰或不可達為前提。不過，即使多數節點失效，或網路出現嚴重問題，大多數共識演算法仍能保證安全屬性——一致同意、完整性與有效性——始終成立 [^75]。所以，大規模中斷可能令系統無法處理請求，卻不能迫使共識系統作出彼此矛盾的決定，從而破壞其正確性。
#### 比較並設定作為共識 {#compare-and-set-as-consensus}
比較並設定（CAS）操作會檢查某個物件的當前值是否等於預期值。如果相等，它就以原子方式把物件更新為新值；否則保持物件不變並返回錯誤。
有了容錯且線性一致的 CAS 操作，就很容易解決共識問題：先把物件設為空值；每個想提議某個值的節點都呼叫 CAS，把預期值設為空，把新值設為自己要提議的值（假定該值非空）。物件最終被設成什麼值，共識決定的就是什麼值。
反過來，有了共識的解法，也可以實現 CAS：每當一個或多個節點想以相同的預期值執行 CAS 時，就透過共識協議提議各次 CAS 呼叫中的新值，再把物件設為共識所決定的值。新值未獲選中的 CAS 呼叫返回錯誤。預期值不同的 CAS 呼叫，則分別執行共識協議。
由此可見，CAS 與共識彼此等價 [^28] [^73]。兩者在單個節點上都很簡單，難點都在於如何實現容錯。我們曾在 [“以物件儲存為後端的資料庫”](/tw/ch6#sec_replication_object_storage) 中見過分散式環境下的 CAS：物件儲存的條件寫入操作只有在當前客戶端上次讀取之後，同名物件沒有被其他客戶端建立或修改時，才允許寫入發生。
不過，線性一致的讀寫暫存器不足以解決共識。FLP 結果表明，在非同步崩潰停止模型中，確定性演算法無法解決共識 [^72]；但我們在 [“線性一致性與仲裁”](/tw/ch10#sec_consistency_quorum_linearizable) 中看到，線性一致的暫存器可以在這一模型下透過法定人數讀寫來實現 [^24] [^25] [^26]。由此可以推知，線性一致的暫存器無法解決共識。
#### 共享日誌作為共識 {#sec_consistency_shared_logs}
我們已經見過多種日誌，例如複製日誌、事務日誌和預寫日誌。日誌儲存一系列 *日誌條目*（*log entry*），任何讀取者都會以相同順序看到相同的條目。有時，只有一個寫入者有權向日志追加新條目；而在 *共享日誌*（*shared log*）中，多個節點都可以請求追加條目。單主複製就是一個例子：任何客戶端都可以請求領導者執行寫入，領導者把寫入追加到複製日誌，隨後所有追隨者都按照與領導者相同的順序應用這些寫入。
更形式化地說，共享日誌支援兩種操作：請求把一個值加入日誌，以及讀取日誌條目。它必須滿足以下屬性：
最終追加
: 如果某個節點請求把一個值加入日誌，而且該節點沒有崩潰，那麼它最終必須能在某條日誌條目中讀到這個值。
可靠交付
: 日誌條目不會丟失：如果某個節點讀到了某條日誌條目，那麼每個未崩潰的節點最終也必須讀到它。
僅追加
: 節點一旦讀到某條日誌條目，該條目便不可再改變；新條目只能追加在它之後，不能插入它之前。節點重新讀取日誌時，必須以初次讀取時的相同順序看到相同條目，即使它曾經崩潰並重啟也不例外。
一致性
: 如果兩個節點都讀到了某條日誌條目 *e*，那麼在 *e* 之前，它們必須以相同順序讀到完全相同的日誌條目序列。
有效性
: 如果某個節點讀到了一條包含某值的日誌條目，那麼此前必有某個節點請求把這個值加入日誌。
> [!NOTE]
> 共享日誌在形式上稱為 *全序廣播*（*total order broadcast*）、*原子廣播*（*atomic broadcast*）或 *全序組播*（*total order multicast*）協議 [^26] [^76] [^77]。這些術語只是用不同說法描述同一件事：請求把一個值加入日誌稱為“廣播”這個值，讀取日誌條目則稱為“交付”這條日誌。
有了共享日誌的實現，就很容易解決共識問題：每個想提議某個值的節點都請求把它加入日誌，而第一條日誌條目中讀出的值就是決定值。由於所有節點都按相同順序讀取日誌條目，它們必然會就哪個值最先交付達成一致 [^28]。
反過來，有了共識的解法，也可以實現共享日誌。具體細節稍顯複雜，但基本思路如下 [^73]：
1. 為日誌中每個未來的條目預留一個槽位，併為每個槽位分別執行一個共識演算法例項，以決定該條目應當包含什麼值。
2. 節點想向日志加入某個值時，就為一個尚未決定的槽位提議這個值。
3. 共識演算法為某個槽位作出決定，而且此前所有槽位也都已有決定後，就把決定值追加為新的日誌條目；其後所有已經連續作出決定的槽位，其決定值也一併追加到日誌。
4. 如果提議值沒有被某個槽位選中，想加入這個值的節點就改為向後面的槽位重新提議。
這說明，共識等價於全序廣播，也等價於共享日誌。沒有故障切換的單主複製不滿足活性要求，因為領導者一旦崩潰，系統就會停止交付訊息。一如既往，真正的挑戰在於如何安全、自動地完成故障切換。
#### 獲取並增加作為共識 {#fetch-and-add-as-consensus}
我們在 [“線性一致的 ID 生成器”](/tw/ch10#sec_consistency_linearizable_id) 中看到，線性一致的 ID 生成器距離解決共識只差一步，卻終究還差一點。這樣的 ID 生成器可以用“獲取並增加”操作實現：它以原子方式遞增計數器，並返回計數器的舊值。
有了 CAS 操作，實現獲取並增加很容易：先讀取計數器的值，再執行一次 CAS，把預期值設為剛才讀到的值，把新值設為舊值加一。如果 CAS 失敗，就從頭重試，直到成功為止。存在爭用時，這種實現不如原生的獲取並增加操作高效，但兩者在功能上等價。既然共識可以實現 CAS，自然也可以實現獲取並增加。
反過來，如果有了容錯的獲取並增加操作，能否解決共識？假設計數器初值為零，每個想提議某個值的節點都呼叫獲取並增加來遞增計數器。由於這項操作具有原子性，其中一個節點會讀到初始值零，其他節點讀到的值則都至少已經遞增過一次。
現在規定，讀到零的節點勝出，其提議值成為決定值。這對讀到零的節點當然沒問題，其他節點卻陷入了困境：它們知道自己沒有勝出，卻不知道其他節點中究竟誰贏了。勝者可以發訊息告知其他節點，但如果它還沒來得及傳送訊息就崩潰了呢？其餘節點將一直懸而未決，無法決定任何值，共識也就不能終止。它們也不能改選另一個節點，因為讀到零的節點日後仍可能恢復，並有充分理由決定自己提議的值。
有一個例外：我們能夠確定提議值的節點不超過兩個。此時，兩個節點可以先互相傳送各自的提議值，再分別執行獲取並增加。讀到零的節點決定自己的值，讀到一的節點則決定另一個節點的值。這樣就解決了兩個節點之間的共識問題，因此我們說獲取並增加的 *共識數*（*consensus number*）為二 [^28]。相比之下，CAS 和共享日誌可以在任意數量的節點提議值時解決共識，所以它們的共識數為 ∞（無窮大）。
#### 原子提交作為共識 {#atomic-commitment-as-consensus}
在 [“分散式事務”](/tw/ch8#sec_transactions_distributed) 中，我們見過 *原子提交*（*atomic commitment*）問題：參與分散式事務的所有資料庫或分片，要麼全都提交事務，要麼全都中止。我們還見過 *兩階段提交*（*two-phase commit*，2PC）演算法，它依賴一個構成單點故障的協調者。
共識與原子提交是什麼關係？乍看之下，兩者十分相似——都要求節點達成某種一致。不過，它們之間存在一項重要區別：共識可以決定任意一個被提議的值；原子提交則要求，只要 *任何* 參與者投票中止，演算法就 *必須* 中止。更準確地說，原子提交必須滿足以下屬性 [^78]：
一致同意
: 任意兩個節點都不會決定不同的結果。
完整性
: 節點一旦決定了某個結果，就不能再決定另一個結果來改變主意。
有效性
: 如果某個節點決定提交，那麼此前所有節點都必須投票提交；只要任何節點投票中止，所有節點都必須中止。
非平凡性
: 如果所有節點都投票提交，而且沒有發生通訊超時，那麼所有節點都必須決定提交。
終止
: 每個未崩潰的節點最終都能決定提交或中止。
有效性確保事務只有在所有節點都同意時才能提交；非平凡性則確保演算法不能簡單地一律中止（但只要節點間發生任何通訊超時，它就允許中止）。另外三項屬性與共識基本相同。
有了共識的解法，可以用多種方式解決原子提交 [^78] [^79]。其中一種做法如下：準備提交事務時，每個節點把自己的提交或中止票傳送給其他所有節點。某個節點如果收到自己以及所有其他節點的提交票，就透過共識演算法提議“提交”；如果收到中止票或遇到超時，就透過共識演算法提議“中止”。節點得知共識演算法的決定後，再據此提交或中止事務。
在這種演算法中，只有所有節點都投票提交，才可能有人提議“提交”。只要有任何節點投票中止，共識演算法收到的所有提議都會是“中止”。如果所有節點都投票提交，但部分通訊發生超時，就可能有些節點提議“中止”，另一些節點提議“提交”；這時最終提交還是中止並不重要，只要所有節點採取相同的決定即可。
反過來，有了容錯的原子提交協議，也可以解決共識。每個想提議某個值的節點都在一組法定人數節點上發起事務，並在每個節點上執行一次單節點 CAS：如果暫存器尚未被另一個事務設值，就將其設為本節點的提議值。CAS 成功時節點投票提交，否則投票中止。如果原子提交協議決定提交這個事務，其值就成為共識的決定值；如果原子提交中止，提議節點就用一個新事務重試。
由此可見，原子提交與共識也彼此等價。
### 共識的實踐 {#sec_consistency_total_order}
前面已經看到，單值共識、CAS、共享日誌與原子提交彼此等價：其中任意一個問題的解法，都可以轉換為其他問題的解法。這個理論洞見很有價值，卻沒有回答一個實際問題：共識有這麼多種表述，實踐中究竟哪一種最有用？
答案是：大多數共識系統都提供共享日誌，也就是全序廣播。Raft、檢視戳複製和 Zab 直接提供共享日誌；Paxos 提供的是單值共識，但實踐中，採用 Paxos 的系統大多使用名為 Multi-Paxos 的擴充套件，它同樣提供共享日誌。
#### 使用共享日誌 {#sec_consistency_smr}
共享日誌與資料庫複製十分契合：如果每條日誌條目都代表一次資料庫寫入，而每個副本都以相同順序、使用確定性邏輯處理相同的寫入，那麼所有副本最終都會處於一致狀態。這個思想稱為 *狀態機複製*（*state machine replication*）[^80]，也是我們在 [“事件溯源與 CQRS”](/tw/ch3#sec_datamodels_events) 中見過的事件溯源原理。共享日誌對流處理也很有用，我們將在 [第 12 章](/tw/ch12#ch_stream) 看到這一點。
類似地，共享日誌還可以實現可序列化事務。正如 [“實際序列執行”](/tw/ch8#sec_transactions_serial) 所述，如果每條日誌條目都代表一個將以儲存過程形式執行的確定性事務，而且每個節點都以相同順序執行這些事務，那麼事務就是可序列化的 [^81] [^82]。
> [!NOTE]
> 採用強一致性模型的分片資料庫，通常會為每個分片分別維護一份日誌。這樣做提高了可伸縮性，卻也限制了資料庫能跨分片提供的一致性保證（例如一致快照與外來鍵引用）。跨分片的可序列化事務並非不能實現，但需要額外協調 [^83]。
共享日誌的另一個強大之處在於，它很容易改造成其他形式的共識：
* 前面已經說明怎樣用它實現單值共識和 CAS：只需決定日誌中最先出現的值。
* 如果需要許多個單值共識例項（例如，劇院裡每個被多人爭訂的座位各一個例項），可以在日誌條目中寫入座位號，並以包含該座位號的第一條日誌條目作為決定。
* 如果需要原子的獲取並增加操作，可以把要加到計數器上的數字寫進日誌條目；計數器的當前值就是截至目前所有日誌條目中數字的總和。還可以對日誌條目簡單計數，以此生成柵欄令牌（見 [“用柵欄機制隔離殭屍與延遲請求”](/tw/ch9#sec_distributed_fencing_tokens)）。例如，在 ZooKeeper 中，這個序列號稱為 `zxid` [^18]。
#### 從單主複製到共識 {#from-single-leader-replication-to-consensus}
前面已經看到，如果由一個“獨裁者”節點作出決定，單值共識就很容易；類似地，如果只有一個領導者有權向共享日誌追加條目，共享日誌也很容易實現。問題在於：這個節點失效時，怎樣才能實現容錯？
傳統的單主複製資料庫並沒有解決這個問題，而是把領導者故障切換留給管理員手工操作。人類的反應速度終究有限，這種方式難免造成相當長的停機時間，也不滿足共識的終止屬性。共識要求演算法能夠自動選出新的領導者。（並非所有共識演算法都有領導者，但常用演算法通常都有 [^84]。）
然而，這裡有一個難題。前面討論腦裂時說過，所有節點必須就誰是領導者達成一致，否則兩個不同節點可能都自認為是領導者，進而作出彼此矛盾的決定。如此看來，選舉領導者需要共識，解決共識又需要領導者。怎樣才能跳出這個先有雞還是先有蛋的困局？
事實上，共識演算法並不要求任何時刻都只有一個領導者。它們提供的是稍弱一些的保證：協議定義一個 *紀元編號*（*epoch number*；Paxos 稱為 *投票編號*，*ballot number*，檢視戳複製稱為 *檢視編號*，*view number*，Raft 稱為 *任期編號*，*term number*），並保證每個紀元內的領導者是唯一的。
如果一個節點在指定的超時時間內始終沒有收到現任領導者的訊息，因而認為它已經失效，這個節點就可能發起投票，選舉新的領導者。這次選舉會取得一個大於以往所有紀元的新紀元編號。如果兩個不同紀元的領導者發生衝突——也許前任領導者其實並未失效——紀元編號較高的領導者說了算。
領導者要向共享日誌追加下一條記錄，必須先確認不存在紀元編號更高的其他領導者，否則後者可能會追加不同的條目。它可以向一組法定人數節點收集選票，這組節點通常是多數，但並非總是如此 [^85]。只有在不知道任何更高紀元領導者的情況下，節點才會投贊成票。
因此，這裡需要兩輪投票：第一輪選舉領導者；第二輪對領導者提議追加的下一條日誌條目進行表決。兩輪投票的法定人數必須相互重疊：如果某項提議表決透過，投贊成票的節點中，至少要有一個參加過最近一次成功的領導者選舉 [^85]。所以，如果提議表決透過，而且投票過程沒有發現編號更高的紀元，現任領導者便可以斷定，沒有紀元編號更高的領導者當選，因而可以安全地把提議條目追加到日誌 [^26] [^86]。
這兩輪投票表面上很像兩階段提交，實際上卻是兩種截然不同的協議。在共識演算法中，任何節點都可以發起選舉，而且只需一組法定人數節點響應；在 2PC 中，只有協調者能請求投票，並且必須從 *每個* 參與者那裡得到“同意”票，事務才能提交。
#### 共識的微妙之處 {#subtleties-of-consensus}
Raft、Multi-Paxos、Zab 和檢視戳複製都採用這一基本結構：先由一組法定人數節點投票選舉領導者；此後，領導者想追加的每一條日誌條目，還要經過另一組法定人數節點投票 [^68] [^69]。每條新日誌條目都要同步複製到一組法定人數節點，才會向發起寫入的客戶端確認成功。這樣即使現任領導者失效，日誌條目也不會丟失。
不過，魔鬼藏在細節裡，而這些演算法的差異也恰恰體現在細節中。例如，舊領導者失效並選出新領導者後，演算法必須保證，新領導者會保留舊領導者在失效前已經追加的所有日誌條目。Raft 的做法是：只有日誌至少與多數追隨者一樣新鮮的節點，才有資格成為新領導者 [^69]。Paxos 則允許任何節點成為新領導者，但要求它先從其他節點補齊日誌，才能開始追加自己的新條目。
> [!TIP] 領導者選舉中的一致性與可用性
>
> 如果希望共識演算法嚴格保證 [“共享日誌作為共識”](/tw/ch10#sec_consistency_shared_logs) 中列出的屬性，那麼新領導者在處理任何寫入或線性一致讀取之前，必須掌握所有已經確認的日誌條目。這是保證上述屬性的必要條件。如果一個資料陳舊的節點成為新領導者，它可能會改寫舊領導者已經寫入的日誌條目，從而違反共享日誌的僅追加屬性。
>
> 有些系統會選擇削弱共識屬性，以便更快地從領導者失效中恢復。例如，Kafka 可以啟用 *非同步副本選舉*（unclean leader election），允許任何副本成為領導者，即使它沒有追上最新進度。另外，在採用非同步複製的資料庫中，領導者失效時，根本無法保證任何追隨者已經趕上最新進度。
>
> 放棄“新領導者必須掌握最新資料”這一要求，或許能提高效能與可用性，卻也如同在薄冰上行走，因為共識理論已經不再適用。沒有故障時，系統固然可以正常工作；但一旦遇到 [第 9 章](/tw/ch9#ch_distributed) 討論的種種問題，就很容易造成大量資料丟失或損壞。
另一個微妙之處是：舊領導者在失效前已經提議了某條日誌條目，但追加該條目的投票尚未結束，演算法應當如何處理。關於這些細節，可以參閱本章末尾的參考文獻 [^23] [^69] [^86]。
對於用共識演算法做複製的資料庫，不僅寫入要轉成日誌條目並複製到一組法定人數節點。如果還要保證線性一致讀取，讀取也必須像寫入一樣經過法定人數投票，以確認那個自認為是領導者的節點確實仍掌握最新資料。etcd 的線性一致讀取就是這樣實現的。
大多數共識演算法的標準形式都假定節點集合固定不變：節點可以下線後重新上線，但哪些節點有權投票，在叢集建立時便已確定。實踐中，卻經常需要在系統配置中新增新節點或移除舊節點。共識演算法因此擴充套件出了 *重新配置* 功能。向系統增加新地區，或把系統從一個位置遷往另一個位置時，這項功能尤其有用：可以先加入新節點，再移除舊節點。
#### 共識的利弊 {#pros-and-cons-of-consensus}
共識演算法雖然複雜而微妙，卻是分散式系統領域的一項重大突破。共識本質上就是“正確實現的單主複製”：領導者失效時自動進行故障切換；即使面對 [第 9 章](/tw/ch9#ch_distributed) 討論的所有問題，也能保證已提交的資料不會丟失，系統絕不會發生腦裂。
既然帶自動故障切換的單主複製本質上就是共識的一種定義，那麼，任何提供自動故障切換、卻沒有采用經過驗證的共識演算法的系統，都很可能不安全 [^87]。當然，採用經過驗證的共識演算法，並不能保證整個系統一定正確——錯誤仍可能潛伏在許多其他角落——但至少是一個良好的開端。
儘管如此，共識並未無處不在，因為它的好處也有代價。共識系統總要有嚴格多數節點才能執行：要容忍一個節點故障，至少需要三個節點；要容忍兩個節點故障，至少需要五個。每項操作都必須與一組法定人數節點通訊，因此不能靠增加節點來提高吞吐量（實際上，每增加一個節點，演算法反而會變慢）。如果網路分割槽把一部分節點同其餘節點隔開，只有多數派所在的一側能夠取得進展，另一側則會阻塞。
共識系統通常依靠超時來檢測失效節點。在網路延遲變化很大的環境中，尤其是跨多個地理區域部署的系統，超時時間很難調好：設得太長，故障恢復會耗時很久；設得太短，又會觸發大量不必要的領導者選舉，導致效能極差——系統花在選舉領導者上的時間，可能比花在有用工作上的還多。
有些共識演算法對網路問題格外敏感。例如，Raft 已被發現存在一些棘手的邊界情況 [^88] [^89]：即使整個網路都執行正常，只要有一條特定鏈路始終不可靠，領導權就可能在兩個節點之間來回跳轉，或者現任領導者不斷被迫辭職，導致系統實際上永遠無法取得進展。怎樣設計對不可靠網路更穩健的演算法，至今仍是一個開放的研究問題。
如果系統既希望高可用，又不願承擔共識的成本，真正可行的選擇只有改用較弱的一致性模型，例如 [第 6 章](/tw/ch6#ch_replication) 討論的無主複製或多主複製。這些方法通常不提供線性一致性；不過，對於並不需要線性一致性的應用，這已經足夠。
### 協調服務 {#sec_consistency_coordination}
任何想提供線性一致操作的分散式資料庫，都能從共識演算法中受益；許多現代分散式資料庫確實也用共識演算法做複製。不過，有一類系統尤其倚重共識：ZooKeeper、etcd、Consul 等 *協調服務*（*coordination service*）。它們表面上與普通鍵值儲存相似，卻不像大多數資料庫那樣以通用資料儲存為目標。
協調服務的用途，是協調另一個分散式系統中的多個節點。例如，Kubernetes 依賴 etcd；Spark 和 Flink 在高可用模式下，則依賴後臺執行的 ZooKeeper。協調服務只儲存少量足以全部放入記憶體的資料（同時仍會寫入磁碟以保證永續性），再用容錯共識演算法把這些資料複製到多個節點。
協調服務以 Google 的 Chubby 鎖服務為藍本 [^17] [^58]，把共識演算法與幾項對構建分散式系統格外有用的功能結合在一起：
鎖與租約
: 前面已經看到，共識系統可以實現具備容錯能力的原子比較並設定（CAS）操作。協調服務以此實現鎖和租約：多個節點併發爭搶同一份租約時，只有一個能夠成功。
柵欄機制
: 正如 [“分散式鎖和租約”](/tw/ch9#sec_distributed_lock_fencing) 所述，以租約保護某項資源時，需要用 *柵欄機制* 防止客戶端在程序暫停或網路嚴重延遲時相互干擾。共識系統可以為每條日誌條目分配單調遞增的 ID，以此生成柵欄令牌（ZooKeeper 使用 `zxid` 和 `cversion`，etcd 使用修訂號）。
故障檢測
: 客戶端與協調服務維持一個長期會話，並定期交換心跳，確認對方是否仍然存活。即使連線暫時中斷或某臺伺服器失效，客戶端持有的租約仍然有效；但如果心跳中斷的時間超過租約超時，協調服務就會認定客戶端已經失效，並釋放其租約。（ZooKeeper 把這種隨會話到期自動消失的條目稱為 *臨時節點*，*ephemeral node*。）
變更通知
: 客戶端可以要求協調服務在某些鍵發生變化時主動傳送通知。這樣一來，客戶端便能得知另一個客戶端何時加入叢集（根據它寫入協調服務的值），或何時失效（它的會話超時，臨時節點隨之消失），無須再頻繁輪詢服務來發現變化。
故障檢測與變更通知本身並不需要共識；但把它們同確實需要共識的原子操作、柵欄機制組合起來，對分散式協調就格外有用。
> [!TIP] 用協調服務管理配置
>
> 應用與基礎設施通常都有超時時間、執行緒池大小等配置引數。有時，人們會把這類配置資料以鍵值對形式存入協調服務。程序啟動時載入最新配置，並訂閱此後的變更通知。配置變化後，程序可以立即採用新設定，也可以透過重啟來載入最新設定。
>
> 配置管理本身並不需要協調服務的共識能力；不過，如果系統本來就在執行協調服務，順便利用它的通知功能會很方便。另一種辦法是讓程序定期從檔案或 URL 輪詢配置更新，從而不必依賴專門的協調服務。
#### 將工作分配給節點 {#allocating-work-to-nodes}
如果某個程序或服務有多個例項，需要從中選出一個領導者或主例項，協調服務就很有用。領導者失效時，應當由其他某個節點接管。這對單主資料庫必不可少，也適用於作業排程器等有狀態系統。
另一種場景是分配分片資源（資料庫、訊息流、檔案儲存、分散式 Actor 系統等）：系統需要決定每個分片交給哪個節點。新節點加入叢集時，需要把一部分分片從現有節點移到新節點，以重新平衡負載；節點被移除或失效時，則要由其他節點接手它的工作。
審慎組合協調服務中的原子操作、臨時節點與通知機制，就可以完成這類任務。實現得當時，應用能在無需人工干預的情況下自動從故障中恢復。即使已經有 Apache Curator 之類基於 ZooKeeper 客戶端 API 提供高層工具的庫，這仍然不是一件容易的事；但無論如何，都遠勝於從頭實現所需的共識演算法——後者極易埋下錯誤。
專用協調服務還有一個優點：無論依賴它協調的分散式系統有多少節點，協調服務本身都可以只執行在一組固定節點上，通常是三個或五個。例如，一個儲存系統擁有數千個分片；若讓數千個節點共同執行共識演算法，效率會低得驚人。把共識“外包”給少量執行協調服務的節點，要合理得多。
協調服務管理的資料通常變化緩慢，例如“IP 地址為 10.1.1.23 的節點是分片 7 的領導者”這類分配關係，往往幾分鐘或幾小時才會變一次。協調服務並非用來儲存每秒可能變化數千次的資料；這類資料更適合交給常規資料庫。或者，也可以用 Apache BookKeeper [^90] [^91] 之類的工具，複製服務內部快速變化的狀態。
#### 服務發現 {#service-discovery}
ZooKeeper、etcd 和 Consul 也經常用於 *服務發現*（*service discovery*），即找出應當連線哪個 IP 地址才能訪問特定服務（見 [“負載均衡器、服務發現和服務網格”](/tw/ch5#sec_encoding_service_discovery)）。雲環境中的虛擬機器不斷建立和銷燬，通常無法預先知道服務的 IP 地址。常見做法是讓服務在啟動時把自己的網路端點註冊到服務登錄檔，供其他服務查詢。
用協調服務做服務發現很方便：故障檢測與變更通知功能，讓客戶端很容易跟蹤服務例項的增減。如果系統已經用協調服務管理租約、鎖或領導者選舉，繼續用它做服務發現也順理成章，因為它本來就知道哪個節點應當接收服務請求。
不過，服務發現使用共識往往有些殺雞用牛刀。這個場景通常不要求線性一致性；高可用與低延遲反而更加重要，因為一旦服務發現不可用，整個系統都會停擺。因此，更常見的做法是快取服務發現資訊，並接受結果可能略有陳舊。例如，基於 DNS 的服務發現就透過多層快取獲得良好的效能與可用性。
為支援這類用途，ZooKeeper 提供了 *觀察者*（observer）節點。這些副本會接收日誌、維護一份 ZooKeeper 資料副本，卻不參與共識演算法的投票。觀察者上的讀取可能陳舊，因而不具備線性一致性；但即使網路中斷，讀取仍可繼續，而且快取還能提高系統所能支援的讀取吞吐量。
## 總結 {#summary}
本章探討了容錯系統中的強一致性：它是什麼，又該怎樣實現。我們深入研究了強一致性的一種常用形式化定義——線性一致性。它要求複製資料表現得彷彿只有一個副本，而且所有操作都以原子方式作用於這個副本。當某些資料在讀取時必須是最新的，或需要解決競態條件時（例如多個節點併發建立同名檔案），線性一致性就很有用。
線性一致性很有吸引力，因為它易於理解：資料庫的行為就像單執行緒程式中的一個變數。但它的缺點是速度慢，網路延遲較大時尤其如此。許多複製演算法都無法保證線性一致性，哪怕乍看之下似乎能夠提供強一致性。
接著，我們把線性一致性的概念應用到 ID 生成器。單節點自增計數器具有線性一致性，卻不能容錯。許多分散式 ID 生成方案也無法保證，ID 的順序與事件實際發生的順序一致。Lamport 時鐘、混合邏輯時鐘等邏輯時鐘，可以給出與因果關係一致的順序，卻不具備線性一致性。
由此，我們引出了共識：達成共識，就是以一種所有節點都認同結果、而且事後不能改變主意的方式作出決定。許多問題實際上都可以歸約為共識，而且彼此等價——換句話說，只要有一個問題的解法，就能把它轉換成其他所有問題的解法。這些等價問題包括：
線性一致的比較並設定操作
: 暫存器必須根據當前值是否等於操作給出的引數，以原子方式 *決定* 是否設定新值。
鎖和租約
: 多個客戶端併發爭搶鎖或租約時，鎖會 *決定* 由哪一個成功獲取。
唯一性約束
: 多個事務併發建立鍵相同、彼此衝突的記錄時，約束必須 *決定* 允許哪一個，又讓哪一個因違反約束而失敗。
共享日誌
: 多個節點併發請求向日志追加條目時，日誌會 *決定* 條目的追加順序。全序廣播也與之等價。
原子事務提交
: 參與分散式事務的所有資料庫節點，必須作出相同的 *決定*：提交事務，或是中止事務。
線性一致的獲取並增加操作
: 這項操作可以實現 ID 生成器。多個節點可以併發呼叫它，而它會 *決定* 各節點遞增計數器的順序。這種方法實際上只能解決兩個節點之間的共識，前面幾種則適用於任意數量的節點。
如果只有一個節點，或者願意把決策權交給一個節點，所有這些問題都很簡單。單主資料庫正是如此：全部決策權都歸領導者所有，這也是此類資料庫能夠提供線性一致操作、唯一性約束、複製日誌等功能的原因。
可是，一旦這個領導者失效，或網路中斷令它不可達，系統便無法繼續取得進展，只能等待人工完成故障切換。Raft、Paxos 等廣泛使用的共識演算法，本質上就是內建了自動領導者選舉與故障切換的單主複製。
共識演算法經過精心設計，能保證故障切換期間不會丟失任何已經提交的寫入，也不會讓系統陷入多個節點同時接受寫入的腦裂狀態。為此，每次寫入和每次線性一致讀取都必須得到一組法定人數節點（通常是多數節點）的確認。這個過程代價不菲，跨地理區域時尤其如此；但若想獲得共識所提供的強一致性與容錯能力，這項代價無法避免。
ZooKeeper、etcd 等協調服務同樣建立在共識演算法之上。它們提供鎖、租約、故障檢測和變更通知等功能，有助於管理分散式應用的狀態。如果要做的事情可以歸約為共識，而且還必須容錯，最好使用協調服務。它不能保證實現一定正確，卻很可能幫上忙。
共識演算法複雜而微妙，但背後有一套自 20 世紀 80 年代以來不斷發展的豐富理論體系。這套理論讓我們能夠構建出這樣的系統：既容忍 [第 9 章](/tw/ch9#ch_distributed) 討論的各種故障，又保證資料不被破壞。這是分散式系統工程的一項非凡成就；本章末尾的參考文獻列出了其中若干重要工作。
不過，共識並不總是正確的工具。有些系統並不需要它所提供的強一致性，以較弱的一致性換取更高可用性和更好效能，反而更加合適。在這些場景中，人們通常採用 [第 6 章](/tw/ch6#ch_replication) 討論過的無主複製或多主複製；本章介紹的邏輯時鐘，對這類系統也很有幫助。
### 參考文獻
[^1]: Maurice P. Herlihy and Jeannette M. Wing. [Linearizability: A Correctness Condition for Concurrent Objects](https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf). *ACM Transactions on Programming Languages and Systems* (TOPLAS), volume 12, issue 3, pages 463–492, July 1990. [doi:10.1145/78969.78972](https://doi.org/10.1145/78969.78972)
[^2]: Leslie Lamport. [On interprocess communication](https://www.microsoft.com/en-us/research/publication/interprocess-communication-part-basic-formalism-part-ii-algorithms/). *Distributed Computing*, volume 1, issue 2, pages 77–101, June 1986. [doi:10.1007/BF01786228](https://doi.org/10.1007/BF01786228)
[^3]: David K. Gifford. [Information Storage in a Decentralized Computer System](https://bitsavers.org/pdf/xerox/parc/techReports/CSL-81-8_Information_Storage_in_a_Decentralized_Computer_System.pdf). Xerox Palo Alto Research Centers, CSL-81-8, June 1981. Archived at [perma.cc/2XXP-3JPB](https://perma.cc/2XXP-3JPB)
[^4]: Martin Kleppmann. [Please Stop Calling Databases CP or AP](https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html). *martin.kleppmann.com*, May 2015. Archived at [perma.cc/MJ5G-75GL](https://perma.cc/MJ5G-75GL)
[^5]: Kyle Kingsbury. [Call Me Maybe: MongoDB Stale Reads](https://aphyr.com/posts/322-call-me-maybe-mongodb-stale-reads). *aphyr.com*, April 2015. Archived at [perma.cc/DXB4-J4JC](https://perma.cc/DXB4-J4JC)
[^6]: Kyle Kingsbury. [Computational Techniques in Knossos](https://aphyr.com/posts/314-computational-techniques-in-knossos). *aphyr.com*, May 2014. Archived at [perma.cc/2X5M-EHTU](https://perma.cc/2X5M-EHTU)
[^7]: Kyle Kingsbury and Peter Alvaro. [Elle: Inferring Isolation Anomalies from Experimental Observations](https://www.vldb.org/pvldb/vol14/p268-alvaro.pdf). *Proceedings of the VLDB Endowment*, volume 14, issue 3, pages 268–280, November 2020. [doi:10.14778/3430915.3430918](https://doi.org/10.14778/3430915.3430918)
[^8]: Paolo Viotti and Marko Vukolić. [Consistency in Non-Transactional Distributed Storage Systems](https://arxiv.org/abs/1512.00168). *ACM Computing Surveys* (CSUR), volume 49, issue 1, article no. 19, June 2016. [doi:10.1145/2926965](https://doi.org/10.1145/2926965)
[^9]: Peter Bailis. [Linearizability Versus Serializability](http://www.bailis.org/blog/linearizability-versus-serializability/). *bailis.org*, September 2014. Archived at [perma.cc/386B-KAC3](https://perma.cc/386B-KAC3)
[^10]: Daniel Abadi. [Correctness Anomalies Under Serializable Isolation](https://dbmsmusings.blogspot.com/2019/06/correctness-anomalies-under.html). *dbmsmusings.blogspot.com*, June 2019. Archived at [perma.cc/JGS7-BZFY](https://perma.cc/JGS7-BZFY)
[^11]: Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. [Highly Available Transactions: Virtues and Limitations](https://www.vldb.org/pvldb/vol7/p181-bailis.pdf). *Proceedings of the VLDB Endowment*, volume 7, issue 3, pages 181–192, November 2013. [doi:10.14778/2732232.2732237](https://doi.org/10.14778/2732232.2732237), extended version published as [arXiv:1302.0309](https://arxiv.org/abs/1302.0309)
[^12]: Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. [*Concurrency Control and Recovery in Database Systems*](https://www.microsoft.com/en-us/research/people/philbe/book/). Addison-Wesley, 1987. ISBN: 978-0-201-10715-9, available online at [*microsoft.com*](https://www.microsoft.com/en-us/research/people/philbe/book/).
[^13]: Andrei Matei. [CockroachDB’s consistency model](https://www.cockroachlabs.com/blog/consistency-model/). *cockroachlabs.com*, February 2021. Archived at [perma.cc/MR38-883B](https://perma.cc/MR38-883B)
[^14]: Murat Demirbas. [Strict-serializability, but at what cost, for what purpose?](https://muratbuffalo.blogspot.com/2022/08/strict-serializability-but-at-what-cost.html) *muratbuffalo.blogspot.com*, August 2022. Archived at [perma.cc/T8AY-N3U9](https://perma.cc/T8AY-N3U9)
[^15]: Ben Darnell. [How to talk about consistency and isolation in distributed DBs](https://www.cockroachlabs.com/blog/db-consistency-isolation-terminology/). *cockroachlabs.com*, February 2022. Archived at [perma.cc/53SV-JBGK](https://perma.cc/53SV-JBGK)
[^16]: Daniel Abadi. [An explanation of the difference between Isolation levels vs. Consistency levels](https://dbmsmusings.blogspot.com/2019/08/an-explanation-of-difference-between.html). *dbmsmusings.blogspot.com*, August 2019. Archived at [perma.cc/QSF2-CD4P](https://perma.cc/QSF2-CD4P)
[^17]: Mike Burrows. [The Chubby Lock Service for Loosely-Coupled Distributed Systems](https://research.google/pubs/pub27897/). At *7th USENIX Symposium on Operating System Design and Implementation* (OSDI), November 2006.
[^18]: Flavio P. Junqueira and Benjamin Reed. [*ZooKeeper: Distributed Process Coordination*](https://www.oreilly.com/library/view/zookeeper/9781449361297/). O’Reilly Media, 2013. ISBN: 978-1-449-36130-3
[^19]: Murali Vallath. [*Oracle 10g RAC Grid, Services & Clustering*](https://www.oreilly.com/library/view/oracle-10g-rac/9781555583217/). Elsevier Digital Press, 2006. ISBN: 978-1-555-58321-7
[^20]: Peter Bailis, Alan Fekete, Michael J. Franklin, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. [Coordination Avoidance in Database Systems](https://arxiv.org/abs/1402.2237). *Proceedings of the VLDB Endowment*, volume 8, issue 3, pages 185–196, November 2014. [doi:10.14778/2735508.2735509](https://doi.org/10.14778/2735508.2735509)
[^21]: Kyle Kingsbury. [Call Me Maybe: etcd and Consul](https://aphyr.com/posts/316-call-me-maybe-etcd-and-consul). *aphyr.com*, June 2014. Archived at [perma.cc/XL7U-378K](https://perma.cc/XL7U-378K)
[^22]: Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini. [Zab: High-Performance Broadcast for Primary-Backup Systems](https://marcoserafini.github.io/assets/pdf/zab.pdf). At *41st IEEE International Conference on Dependable Systems and Networks* (DSN), June 2011. [doi:10.1109/DSN.2011.5958223](https://doi.org/10.1109/DSN.2011.5958223)
[^23]: Diego Ongaro and John K. Ousterhout. [In Search of an Understandable Consensus Algorithm](https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf). At *USENIX Annual Technical Conference* (ATC), June 2014.
[^24]: Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. [Sharing Memory Robustly in Message-Passing Systems](https://www.cs.huji.ac.il/course/2004/dist/p124-attiya.pdf). *Journal of the ACM*, volume 42, issue 1, pages 124–142, January 1995. [doi:10.1145/200836.200869](https://doi.org/10.1145/200836.200869)
[^25]: Nancy Lynch and Alex Shvartsman. [Robust Emulation of Shared Memory Using Dynamic Quorum-Acknowledged Broadcasts](https://groups.csail.mit.edu/tds/papers/Lynch/FTCS97.pdf). At *27th Annual International Symposium on Fault-Tolerant Computing* (FTCS), June 1997. [doi:10.1109/FTCS.1997.614100](https://doi.org/10.1109/FTCS.1997.614100)
[^26]: Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. [*Introduction to Reliable and Secure Distributed Programming*](https://www.distributedprogramming.net/), 2nd edition. Springer, 2011. ISBN: 978-3-642-15259-7, [doi:10.1007/978-3-642-15260-3](https://doi.org/10.1007/978-3-642-15260-3)
[^27]: Niklas Ekström, Mikhail Panchenko, and Jonathan Ellis. [Possible Issue with Read Repair?](https://lists.apache.org/thread/wwsjnnc93mdlpw8nb0d5gn4q1bmpzbon) Email thread on *cassandra-dev* mailing list, October 2012.
[^28]: Maurice P. Herlihy. [Wait-Free Synchronization](https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf). *ACM Transactions on Programming Languages and Systems* (TOPLAS), volume 13, issue 1, pages 124–149, January 1991. [doi:10.1145/114005.102808](https://doi.org/10.1145/114005.102808)
[^29]: Armando Fox and Eric A. Brewer. [Harvest, Yield, and Scalable Tolerant Systems](https://radlab.cs.berkeley.edu/people/fox/static/pubs/pdf/c18.pdf). At *7th Workshop on Hot Topics in Operating Systems* (HotOS), March 1999. [doi:10.1109/HOTOS.1999.798396](https://doi.org/10.1109/HOTOS.1999.798396)
[^30]: Seth Gilbert and Nancy Lynch. [Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services](https://www.comp.nus.edu.sg/~gilbert/pubs/BrewersConjecture-SigAct.pdf). *ACM SIGACT News*, volume 33, issue 2, pages 51–59, June 2002. [doi:10.1145/564585.564601](https://doi.org/10.1145/564585.564601)
[^31]: Seth Gilbert and Nancy Lynch. [Perspectives on the CAP Theorem](https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf). *IEEE Computer Magazine*, volume 45, issue 2, pages 30–36, February 2012. [doi:10.1109/MC.2011.389](https://doi.org/10.1109/MC.2011.389)
[^32]: Eric A. Brewer. [CAP Twelve Years Later: How the ‘Rules’ Have Changed](https://sites.cs.ucsb.edu/~rich/class/cs293-cloud/papers/brewer-cap.pdf). *IEEE Computer Magazine*, volume 45, issue 2, pages 23–29, February 2012. [doi:10.1109/MC.2012.37](https://doi.org/10.1109/MC.2012.37)
[^33]: Susan B. Davidson, Hector Garcia-Molina, and Dale Skeen. [Consistency in Partitioned Networks](https://www.cs.rice.edu/~alc/old/comp520/papers/DGS85.pdf). *ACM Computing Surveys*, volume 17, issue 3, pages 341–370, September 1985. [doi:10.1145/5505.5508](https://doi.org/10.1145/5505.5508)
[^34]: Paul R. Johnson and Robert H. Thomas. [RFC 677: The Maintenance of Duplicate Databases](https://tools.ietf.org/html/rfc677). Network Working Group, January 1975.
[^35]: Michael J. Fischer and Alan Michael. [Sacrificing Serializability to Attain High Availability of Data in an Unreliable Network](https://sites.cs.ucsb.edu/~agrawal/spring2011/ugrad/p70-fischer.pdf). At *1st ACM Symposium on Principles of Database Systems* (PODS), March 1982. [doi:10.1145/588111.588124](https://doi.org/10.1145/588111.588124)
[^36]: Eric A. Brewer. [NoSQL: Past, Present, Future](https://www.infoq.com/presentations/NoSQL-History/). At *QCon San Francisco*, November 2012.
[^37]: Adrian Cockcroft. [Migrating to Microservices](https://www.infoq.com/presentations/migration-cloud-native/). At *QCon London*, March 2014.
[^38]: Martin Kleppmann. [A Critique of the CAP Theorem](https://arxiv.org/abs/1509.05393). arXiv:1509.05393, September 2015.
[^39]: Daniel Abadi. [Problems with CAP, and Yahoo’s little known NoSQL system](https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html). *dbmsmusings.blogspot.com*, April 2010. Archived at [perma.cc/4NTZ-CLM9](https://perma.cc/4NTZ-CLM9)
[^40]: Daniel Abadi. [Hazelcast and the Mythical PA/EC System](https://dbmsmusings.blogspot.com/2017/10/hazelcast-and-mythical-paec-system.html). *dbmsmusings.blogspot.com*, October 2017. Archived at [perma.cc/J5XM-U5C2](https://perma.cc/J5XM-U5C2)
[^41]: Eric Brewer. [Spanner, TrueTime & The CAP Theorem](https://research.google.com/pubs/archive/45855.pdf). *research.google.com*, February 2017. Archived at [perma.cc/59UW-RH7N](https://perma.cc/59UW-RH7N)
[^42]: Daniel J. Abadi. [Consistency Tradeoffs in Modern Distributed Database System Design](https://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf). *IEEE Computer Magazine*, volume 45, issue 2, pages 37–42, February 2012. [doi:10.1109/MC.2012.33](https://doi.org/10.1109/MC.2012.33)
[^43]: Nancy A. Lynch. [A Hundred Impossibility Proofs for Distributed Computing](https://groups.csail.mit.edu/tds/papers/Lynch/podc89.pdf). At *8th ACM Symposium on Principles of Distributed Computing* (PODC), August 1989. [doi:10.1145/72981.72982](https://doi.org/10.1145/72981.72982)
[^44]: Prince Mahajan, Lorenzo Alvisi, and Mike Dahlin. [Consistency, Availability, and Convergence](https://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2036.pdf). University of Texas at Austin, Department of Computer Science, Tech Report UTCS TR-11-22, May 2011. Archived at [perma.cc/SAV8-9JAJ](https://perma.cc/SAV8-9JAJ)
[^45]: Hagit Attiya, Faith Ellen, and Adam Morrison. [Limitations of Highly-Available Eventually-Consistent Data Stores](https://www.cs.tau.ac.il/~mad/publications/podc2015-replds.pdf). At *ACM Symposium on Principles of Distributed Computing* (PODC), July 2015. [doi:10.1145/2767386.2767419](https://doi.org/10.1145/2767386.2767419)
[^46]: Peter Sewell, Susmit Sarkar, Scott Owens, Francesco Zappa Nardelli, and Magnus O. Myreen. [x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors](https://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf). *Communications of the ACM*, volume 53, issue 7, pages 89–97, July 2010. [doi:10.1145/1785414.1785443](https://doi.org/10.1145/1785414.1785443)
[^47]: Martin Thompson. [Memory Barriers/Fences](https://mechanical-sympathy.blogspot.com/2011/07/memory-barriersfences.html). *mechanical-sympathy.blogspot.co.uk*, July 2011. Archived at [perma.cc/7NXM-GC5U](https://perma.cc/7NXM-GC5U)
[^48]: Ulrich Drepper. [What Every Programmer Should Know About Memory](https://www.akkadia.org/drepper/cpumemory.pdf). *akkadia.org*, November 2007. Archived at [perma.cc/NU6Q-DRXZ](https://perma.cc/NU6Q-DRXZ)
[^49]: Hagit Attiya and Jennifer L. Welch. [Sequential Consistency Versus Linearizability](https://courses.csail.mit.edu/6.852/01/papers/p91-attiya.pdf). *ACM Transactions on Computer Systems* (TOCS), volume 12, issue 2, pages 91–122, May 1994. [doi:10.1145/176575.176576](https://doi.org/10.1145/176575.176576)
[^50]: Kyzer R. Davis, Brad G. Peabody, and Paul J. Leach. [Universally Unique IDentifiers (UUIDs)](https://www.rfc-editor.org/rfc/rfc9562). RFC 9562, IETF, May 2024.
[^51]: Ryan King. [Announcing Snowflake](https://blog.x.com/engineering/en_us/a/2010/announcing-snowflake). *blog.x.com*, June 2010. Archived at [archive.org](https://web.archive.org/web/20241128214604/https%3A//blog.x.com/engineering/en_us/a/2010/announcing-snowflake)
[^52]: Alizain Feerasta. [Universally Unique Lexicographically Sortable Identifier](https://github.com/ulid/spec). *github.com*, 2016. Archived at [perma.cc/NV2Y-ZP8U](https://perma.cc/NV2Y-ZP8U)
[^53]: Rob Conery. [A Better ID Generator for PostgreSQL](https://bigmachine.io/2014/05/29/a-better-id-generator-for-postgresql/). *bigmachine.io*, May 2014. Archived at [perma.cc/K7QV-3KFC](https://perma.cc/K7QV-3KFC)
[^54]: Leslie Lamport. [Time, Clocks, and the Ordering of Events in a Distributed System](https://www.microsoft.com/en-us/research/publication/time-clocks-ordering-events-distributed-system/). *Communications of the ACM*, volume 21, issue 7, pages 558–565, July 1978. [doi:10.1145/359545.359563](https://doi.org/10.1145/359545.359563)
[^55]: Sandeep S. Kulkarni, Murat Demirbas, Deepak Madeppa, Bharadwaj Avva, and Marcelo Leone. [Logical Physical Clocks](https://doi.org/10.1007/978-3-319-14472-6_2). *18th International Conference on Principles of Distributed Systems* (OPODIS), December 2014. [doi:10.1007/978-3-319-14472-6\_2](https://doi.org/10.1007/978-3-319-14472-6_2)
[^56]: Manuel Bravo, Nuno Diegues, Jingna Zeng, Paolo Romano, and Luís Rodrigues. [On the use of Clocks to Enforce Consistency in the Cloud](http://sites.computer.org/debull/A15mar/p18.pdf). *IEEE Data Engineering Bulletin*, volume 38, issue 1, pages 18–31, March 2015. Archived at [perma.cc/68ZU-45SH](https://perma.cc/68ZU-45SH)
[^57]: Daniel Peng and Frank Dabek. [Large-Scale Incremental Processing Using Distributed Transactions and Notifications](https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf). At *9th USENIX Conference on Operating Systems Design and Implementation* (OSDI), October 2010.
[^58]: Tushar Deepak Chandra, Robert Griesemer, and Joshua Redstone. [Paxos Made Live – An Engineering Perspective](https://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chandra07paxos.pdf). At *26th ACM Symposium on Principles of Distributed Computing* (PODC), June 2007. [doi:10.1145/1281100.1281103](https://doi.org/10.1145/1281100.1281103)
[^59]: Will Portnoy. [Lessons Learned from Implementing Paxos](https://blog.willportnoy.com/2012/06/lessons-learned-from-paxos.html). *blog.willportnoy.com*, June 2012. Archived at [perma.cc/QHD9-FDD2](https://perma.cc/QHD9-FDD2)
[^60]: Brian M. Oki and Barbara H. Liskov. [Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems](https://pmg.csail.mit.edu/papers/vr.pdf). At *7th ACM Symposium on Principles of Distributed Computing* (PODC), August 1988. [doi:10.1145/62546.62549](https://doi.org/10.1145/62546.62549)
[^61]: Barbara H. Liskov and James Cowling. [Viewstamped Replication Revisited](https://pmg.csail.mit.edu/papers/vr-revisited.pdf). Massachusetts Institute of Technology, Tech Report MIT-CSAIL-TR-2012-021, July 2012. Archived at [perma.cc/56SJ-WENQ](https://perma.cc/56SJ-WENQ)
[^62]: Leslie Lamport. [The Part-Time Parliament](https://www.microsoft.com/en-us/research/publication/part-time-parliament/). *ACM Transactions on Computer Systems*, volume 16, issue 2, pages 133–169, May 1998. [doi:10.1145/279227.279229](https://doi.org/10.1145/279227.279229)
[^63]: Leslie Lamport. [Paxos Made Simple](https://www.microsoft.com/en-us/research/publication/paxos-made-simple/). *ACM SIGACT News*, volume 32, issue 4, pages 51–58, December 2001. Archived at [perma.cc/82HP-MNKE](https://perma.cc/82HP-MNKE)
[^64]: Robbert van Renesse and Deniz Altinbuken. [Paxos Made Moderately Complex](https://people.cs.umass.edu/~arun/590CC/papers/paxos-moderately-complex.pdf). *ACM Computing Surveys* (CSUR), volume 47, issue 3, article no. 42, February 2015. [doi:10.1145/2673577](https://doi.org/10.1145/2673577)
[^65]: Diego Ongaro. [Consensus: Bridging Theory and Practice](https://github.com/ongardie/dissertation). PhD Thesis, Stanford University, August 2014. Archived at [perma.cc/5VTZ-2ADH](https://perma.cc/5VTZ-2ADH)
[^66]: Heidi Howard, Malte Schwarzkopf, Anil Madhavapeddy, and Jon Crowcroft. [Raft Refloated: Do We Have Consensus?](https://www.cl.cam.ac.uk/research/srg/netos/papers/2015-raftrefloated-osr.pdf) *ACM SIGOPS Operating Systems Review*, volume 49, issue 1, pages 12–21, January 2015. [doi:10.1145/2723872.2723876](https://doi.org/10.1145/2723872.2723876)
[^67]: André Medeiros. [ZooKeeper’s Atomic Broadcast Protocol: Theory and Practice](http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf). Aalto University School of Science, March 2012. Archived at [perma.cc/FVL4-JMVA](https://perma.cc/FVL4-JMVA)
[^68]: Robbert van Renesse, Nicolas Schiper, and Fred B. Schneider. [Vive La Différence: Paxos vs. Viewstamped Replication vs. Zab](https://arxiv.org/abs/1309.5671). *IEEE Transactions on Dependable and Secure Computing*, volume 12, issue 4, pages 472–484, September 2014. [doi:10.1109/TDSC.2014.2355848](https://doi.org/10.1109/TDSC.2014.2355848)
[^69]: Heidi Howard and Richard Mortier. [Paxos vs Raft: Have we reached consensus on distributed consensus?](https://arxiv.org/abs/2004.05074). At *7th Workshop on Principles and Practice of Consistency for Distributed Data* (PaPoC), April 2020. [doi:10.1145/3380787.3393681](https://doi.org/10.1145/3380787.3393681)
[^70]: Miguel Castro and Barbara H. Liskov. [Practical Byzantine Fault Tolerance and Proactive Recovery](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/01/p398-castro-bft-tocs.pdf). *ACM Transactions on Computer Systems*, volume 20, issue 4, pages 396–461, November 2002. [doi:10.1145/571637.571640](https://doi.org/10.1145/571637.571640)
[^71]: Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis. [SoK: Consensus in the Age of Blockchains](https://doi.org/10.1145/3318041.3355458). At *1st ACM Conference on Advances in Financial Technologies* (AFT), October 2019. [doi:10.1145/3318041.3355458](https://doi.org/10.1145/3318041.3355458)
[^72]: Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. [Impossibility of Distributed Consensus with One Faulty Process](https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf). *Journal of the ACM*, volume 32, issue 2, pages 374–382, April 1985. [doi:10.1145/3149.214121](https://doi.org/10.1145/3149.214121)
[^73]: Tushar Deepak Chandra and Sam Toueg. [Unreliable Failure Detectors for Reliable Distributed Systems](https://courses.csail.mit.edu/6.852/08/papers/CT96-JACM.pdf). *Journal of the ACM*, volume 43, issue 2, pages 225–267, March 1996. [doi:10.1145/226643.226647](https://doi.org/10.1145/226643.226647)
[^74]: Michael Ben-Or. [Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols](https://homepage.cs.uiowa.edu/~ghosh/BenOr.pdf). At *2nd ACM Symposium on Principles of Distributed Computing* (PODC), August 1983. [doi:10.1145/800221.806707](https://doi.org/10.1145/800221.806707)
[^75]: Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. [Consensus in the Presence of Partial Synchrony](https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf). *Journal of the ACM*, volume 35, issue 2, pages 288–323, April 1988. [doi:10.1145/42282.42283](https://doi.org/10.1145/42282.42283)
[^76]: Xavier Défago, André Schiper, and Péter Urbán. [Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey](https://dspace.jaist.ac.jp/dspace/bitstream/10119/4883/1/defago_et_al.pdf). *ACM Computing Surveys*, volume 36, issue 4, pages 372–421, December 2004. [doi:10.1145/1041680.1041682](https://doi.org/10.1145/1041680.1041682)
[^77]: Hagit Attiya and Jennifer Welch. *Distributed Computing: Fundamentals, Simulations and Advanced Topics*, 2nd edition. John Wiley & Sons, 2004. ISBN: 978-0-471-45324-6, [doi:10.1002/0471478210](https://doi.org/10.1002/0471478210)
[^78]: Rachid Guerraoui. [Revisiting the Relationship Between Non-Blocking Atomic Commitment and Consensus](https://citeseerx.ist.psu.edu/pdf/5d06489503b6f791aa56d2d7942359c2592e44b0). At *9th International Workshop on Distributed Algorithms* (WDAG), September 1995. [doi:10.1007/BFb0022140](https://doi.org/10.1007/BFb0022140)
[^79]: Jim N. Gray and Leslie Lamport. [Consensus on Transaction Commit](https://dsf.berkeley.edu/cs286/papers/paxoscommit-tods2006.pdf). *ACM Transactions on Database Systems* (TODS), volume 31, issue 1, pages 133–160, March 2006. [doi:10.1145/1132863.1132867](https://doi.org/10.1145/1132863.1132867)
[^80]: Fred B. Schneider. [Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial](https://www.cs.cornell.edu/fbs/publications/SMSurvey.pdf). *ACM Computing Surveys*, volume 22, issue 4, pages 299–319, December 1990. [doi:10.1145/98163.98167](https://doi.org/10.1145/98163.98167)
[^81]: Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi. [Calvin: Fast Distributed Transactions for Partitioned Database Systems](https://cs.yale.edu/homes/thomson/publications/calvin-sigmod12.pdf). At *ACM International Conference on Management of Data* (SIGMOD), May 2012. [doi:10.1145/2213836.2213838](https://doi.org/10.1145/2213836.2213838)
[^82]: Mahesh Balakrishnan, Dahlia Malkhi, Ted Wobber, Ming Wu, Vijayan Prabhakaran, Michael Wei, John D. Davis, Sriram Rao, Tao Zou, and Aviad Zuck. [Tango: Distributed Data Structures over a Shared Log](https://www.microsoft.com/en-us/research/publication/tango-distributed-data-structures-over-a-shared-log/). At *24th ACM Symposium on Operating Systems Principles* (SOSP), November 2013. [doi:10.1145/2517349.2522732](https://doi.org/10.1145/2517349.2522732)
[^83]: Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobber, Michael Wei, and John D. Davis. [CORFU: A Shared Log Design for Flash Clusters](https://www.usenix.org/system/files/conference/nsdi12/nsdi12-final30.pdf). At *9th USENIX Symposium on Networked Systems Design and Implementation* (NSDI), April 2012.
[^84]: Vasilis Gavrielatos, Antonios Katsarakis, and Vijay Nagarajan. [Odyssey: the impact of modern hardware on strongly-consistent replication protocols](https://vasigavr1.github.io/files/Odyssey_Eurosys_2021.pdf). At *16th European Conference on Computer Systems* (EuroSys), April 2021. [doi:10.1145/3447786.3456240](https://doi.org/10.1145/3447786.3456240)
[^85]: Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. [Flexible Paxos: Quorum Intersection Revisited](https://drops.dagstuhl.de/opus/volltexte/2017/7094/pdf/LIPIcs-OPODIS-2016-25.pdf). At *20th International Conference on Principles of Distributed Systems* (OPODIS), December 2016. [doi:10.4230/LIPIcs.OPODIS.2016.25](https://doi.org/10.4230/LIPIcs.OPODIS.2016.25)
[^86]: Martin Kleppmann. [Distributed Systems lecture notes](https://www.cl.cam.ac.uk/teaching/2425/ConcDisSys/dist-sys-notes.pdf). *University of Cambridge*, October 2024. Archived at [perma.cc/SS3Q-FNS5](https://perma.cc/SS3Q-FNS5)
[^87]: Kyle Kingsbury. [Call Me Maybe: Elasticsearch 1.5.0](https://aphyr.com/posts/323-call-me-maybe-elasticsearch-1-5-0). *aphyr.com*, April 2015. Archived at [perma.cc/37MZ-JT7H](https://perma.cc/37MZ-JT7H)
[^88]: Heidi Howard and Jon Crowcroft. [Coracle: Evaluating Consensus at the Internet Edge](https://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p85.pdf). At *Annual Conference of the ACM Special Interest Group on Data Communication* (SIGCOMM), August 2015. [doi:10.1145/2829988.2790010](https://doi.org/10.1145/2829988.2790010)
[^89]: Tom Lianza and Chris Snook. [A Byzantine failure in the real world](https://blog.cloudflare.com/a-byzantine-failure-in-the-real-world/). *blog.cloudflare.com*, November 2020. Archived at [perma.cc/83EZ-ALCY](https://perma.cc/83EZ-ALCY)
[^90]: Ivan Kelly. [BookKeeper Tutorial](https://github.com/ivankelly/bookkeeper-tutorial). *github.com*, October 2014. Archived at [perma.cc/37Y6-VZWU](https://perma.cc/37Y6-VZWU)
[^91]: Jack Vanlightly. [Apache BookKeeper Insights Part 1 — External Consensus and Dynamic Membership](https://medium.com/splunk-maas/apache-bookkeeper-insights-part-1-external-consensus-and-dynamic-membership-c259f388da21). *medium.com*, November 2021. Archived at [perma.cc/3MDB-8GFB](https://perma.cc/3MDB-8GFB)