小議分散式系統的一致性模型

一致性 (Consistency) 一直是分散式系統里一個很重要的話題, 如果要了解一致性, 要從系統模式開始說起.

系統模型

系統模型 (System Model), 是描述系統的特性的一些假設, 基於這些假設才可以設計出各種各樣的分散式系統. 這些假設包括但不限於:

• 每個節點的計算能力以及它們的失效模式
• 節點間通信的能力以及是否可能失效
• 整個系統的屬性, 比如時序等等

其中每一點下面都會講到. 如果一個系統模型是基於最弱的假設的, 比如節點可能出現硬體錯誤、網路擁塞或斷開以及可能遭到惡意攻擊等等, 那基於這樣的系統模型的分散式系統可以運行在各種各樣的環境下, 因為它的容錯極高.

而如果我們做出了很強硬的假設, 比如節點不會 fail, 那基於此假設的系統不需要處理節點失效的問題, 但是因為假設太偏離現實, 所以很難在生產環境中真正去使用.

系統模型中的節點問題

節點, 可以理解為系統中的一個個虛擬機或者物理機, 它們是負責真正的計算和存儲業務的. 它們會運行確定性的演算法, 並且可以將數據寫入易失性存儲器 (內存) 或者持久性存儲器 (磁碟). 不同的存儲會受到不同失效模型的影響.

節點的失效模型是指可能使得節點失效的途徑. 在大多數實踐中, 系統都是假設節點只有在 crash 的時候會失效, 並且會在 crash 之後的某個時間點恢復工作.

這個模型並不是最弱的, 最弱的是著名的拜占庭失效, 也就是可以以任何方式失效. 基於拜占庭失效模型的演算法很少在生產環境中遇到, 這也很好想像, 因為實現的難度必然是很大的, 而且大多數時候也遇不到那麼多失效的方式. 因此最常用的還是 crash-recovery 模型.

系統模型中的網路問題

在上個年代中, 很少有系統會考慮網路分區的問題, 但是在現在這個環境下, 隨著系統的規模增長, 網路的失效也變得常見起來.

一般來說網路的失效模型比較簡單, 即直到網路恢復為止, 網路上的信息可能會丟失或者延遲.

系統模型中的時序問題

一般來說, 時序只有兩種模式, 非同步和同步. 同步是指

Processes execute in lock-step; there is a known upper bound on message transmission delay; each process has an accurate clock

非同步是指

No timing assumptions - e.g. processes execute at independent rates;

there is no bound on message transmission delay; useful clocks do not

exist

也就是說在同步模型中, 信息一定會在一定延遲內送達, 整個系統是有時序的邏輯的. 而在非同步模型中, 不存在系統全局的時序.

在現實中, 大部分的場景是部分同步的時序模型, 它們偶爾可以正常工作, 並提供一些上界, 但在某些情況下，消息會被無限期地延遲，時鐘也不同步。

共識問題

討論完系統模型, 接下來就可以在設計好的系統模型的假設下, 討論共識問題了. 所謂共識 (Consensus) 問題,

• 認同 (agreement): 一個決議過程中所有 N 個節點都認同一個結果
• 合法 (validity): 該結果必須由 N 個節點中的節點提出
• 可結束 (termination): 決議過程在一定時間內結束，不會無休止地進行下去

這個聽上去很簡單, 但是在比較弱的系統模型下, 有很多問題會導致共識是很難達成的. 比如如果網路中存在消息延時、丟失，節點間消息傳遞; 亦或者是節點存在 crash 的情況. 在這些假設下, 如何達成共識, 才是真正對現實中的分散式系統有價值的討論.

FLP 定理

這裡就不得不提到一個定理: FLP 定理. 該定理的論文是由 Fischer, Lynch and Patterson 三位作者於1985年發表,之後該論文獲得了 Dijkstra 獎。定理所依賴的系統模型很簡單:

• 節點只會因為 crash 而失效 (非拜占庭失效)
• 網路是可靠的, 只要進程非失敗，消息雖會被無限延遲，但最終會被送達；並且消息僅會被送達一次 (無重複)
• 非同步的時序模型, 與同步通信的最大區別是沒有時鐘、不能時間同步、不能使用超時、不能探測失敗、消息可任意延遲、消息可亂序

在現實中，一般網路會使用 TCP 協議 (保證了消息健壯、不重複、不亂序)，每個節點都有 NTP 時鐘同步 (可以使用超時), 如 FLP 定理的系統模型這樣的非同步場景相對比較少. 但是也還是存在一定的場景.

FLP 在這樣的系統模型下給出了一個很吃雞的結論: 在非同步通信場景，即使只有一個進程失敗，也沒有任何 (確定性) 演算法能保證非失敗進程達到一致性.

也就是說, 解決共識問題的演算法必須在不存在消息傳遞邊界的情況下放棄強一致 (safety) 或者可用性 (liveness)。

CAP 理論

CAP 恐怕要比 FLP 定理更出名一些. 甚至國內某 NewSQL 資料庫廠商 PingCAP 把它加入了自己公司的名字中.

這一理論是說

• 強一致性 (Strong Consistency): 如果系統對一個寫操作返回成功，那麼之後的讀請求都必須讀到這個新數據；如果返回失敗，那麼所有讀操作都不能讀到這個數據，對調用者而言數據具有強一致性
• 可用性 (Availability): 節點的失效不會導致其餘節點的工作收到影響
• 分區容錯性 (Partition tolerance): 在網路分區的情況下，被分隔的節點仍能正常對外服務

C、A、P 三者最多只能滿足其中兩個，和 FLP 定理一樣，CAP 定理也指出了一個不可達的結果 (impossibility result)。

但是需要注意的是, 這裡的 C 指的是強一致性, 而非一致性. 因此在現實中, 一致性的強弱與可用性是可以 trade-off 的. 那因此就存在一致性的模型.

一致性模型

一致性模型是描述一致性強弱的. 大類可分為強一致性和弱一致性模型. 但是其中又有很多小的不同.

其中強一致性模型主要是有兩種, 一種是線性一致性 (Linearizable consistency), 另一種是順序一致性 (Sequential consistency).

關鍵的區別在於，線性化的一致性要求操作生效的順序等於實際的實時操作排序。順序一致性允許操作被重新排序，只要在每個節點上觀察到的順序保持一致。作為用戶, 能區分兩者的唯一方法是，觀察系統的所有輸入和時間. 從客戶端與節點交互的角度來看，兩者是等價的。

而弱一致性則是有以客戶為中心的一致性模型 (Client-centric consistency models), 因果一致性 (Causal consistency) 和最終一致性 (Eventual consistency).

其中客戶為中心的一致性模型可能保證客戶永遠不會看到數據項的舊版本。這通常是通過在客戶端庫中構建額外的緩存來實現的，因此，如果客戶端移動到包含舊數據的副本節點，那麼客戶端庫就會返回緩存的值，而不是從副本中返回舊值。

最終一致性是系統保證如果沒有對某個對象的新更新操作，最終所有的訪問將返回這個對象的最後更新的值。這裡就有比較多的取捨了, 比如最終是多久之類的.

因果一致性可以理解為是最終一致性的變種, 如果進程 A 通知進程 B 它已經更新了一個數據項，那麼進程 B 的後續訪問將返回更新後的值，並且寫操作將被保證取代前一次寫入。和進程 A 沒有因果關係的 C 的訪問將遵循正常的最終一致性規則。

參考文章

• 分散式系統理論 - 從放棄到入門
• Distributed systems: for fun and profit
• FLP Impossibility

許可協議

• 本文遵守創作共享CC BY-NC-SA 3.0協議
• 網路平台轉載請聯繫 marketing@dongyue.io

歡迎關注我們的 GitHub 以及博客