分散式系統中的一致性

一致性是一個比較抽象的概念，涉及computer science的多個領域，例如：

1. 分散式數據存儲（例如分散式資料庫/分散式文件系統/消息隊列）的讀寫一致性
2. 傳統關係資料庫事務隔離級別，並發事務的一致性模型
3. 共享內存的多核架構中，多個cpu core之間的緩存一致性（cache coherence）
4. Web cache集群的數據一致性

第三個問題是計算機體系結構專註的問題。對於軟體開發者來說，只有少數的系統軟體開發者（例如操作系統內核、傳統關係資料庫等）需要關心。第四個問題在大規模web網站中會遇到。web cache不會用來做持久化存儲，開發者更多考慮的是性能問題，一致性是次要的。

與3、4不同，在前兩個場景，一致性問題至關重要。一致性，簡單的解釋就是正確性。對於資料庫/分散式存儲來說，如果無法滿足一定程度的正確性，沒有人可以放心使用。絕對的正確性是不存在的，那麼一定程度的正確性是什麼呢？這就引入了consistency model問題。不同的consistency model，對於一致性的條件，有著不同的要求。consistency model可以從多個角度來劃分，例如data centric，client centric。下圖展示了關係資料庫和分散式系統兩個不同領域中常見的一致性模型：

• 圖右半部分，是關係資料庫的consistency model。從上到下，一致性的級別越來越低，並發性能會更好些。不同資料庫對於事務隔離級別的定義有所不同。
• RR（repeatable read）
• > CS(cursor scability)
• > RC( read commit)。
• 圖左半部分，是從分散式系統的consistency model。WfR是write follows read， MR MW分別是monotonic read,monotonic write。
• Linearizable（線性）
• > Sequential（順序）
• > Causal（因果）
• > RyW(read your write)。
• 根據CAP理論，圖中紅色部分的一致性模型，無法滿足100%的可用性，只能達到CP：《Highly Available Transactions: Virtues and Limitations》

對於以上幾種一致性模型，做一些進一步的說明：

1. RyW(read your write)/WfR(write follow read)都是從session sticky的角度來看一致性問題。RyW，簡單的說是client寫了一個key/value，那麼下次讀key時候應該返回的是同樣的value，避免dirty read。WfR稍微有點複雜，大致上是說，如果一個寫操作依賴於上一個讀操作，那麼在所有節點上，上一次讀操作對應的寫操作，一定是在本次寫操作之前完成，主要是避免不同節點上寫的順序不同帶來的dirty write。
2. MR/MW：讀單增（monotonic read），寫單增(monotonic write )。讀單增，是說client讀到了一個值value，那麼後續所有的讀操作，要麼讀到這個value，要麼讀到這個value最新的更新，而不會讀到比這個value更老的版本。寫單增的定義跟讀單增類似。
3. linearizability，是在分散式系統中，是可以工程實現的、最高級別的一致性模型。

什麼是linearizability呢？介紹起來還有點複雜。詳細的形式化定義可以參考《Linearizability: A Correctness Condition for Concurrent Objects》。線性一致性又稱為原子一致性（atomic consistency），其核心思想主要是一下幾點：

1. 從分散式系統外部（client）看，每個操作（讀或者寫）都是原子的，對於這些原子操作，有一個嚴格執行的sequence。
2. 實際讀/寫操作，有latency（ request timestamp-response timestamp）。對於兩個讀寫操作X和Y來說，如果X(response timestamp)<Y(request timestamp)，那麼認為存在一個確定的順序，即X<Y；否則，認為X和Y是並發的，XY之間順序不確定的。
3. X1，X2，X3...是某個client的讀寫測試結果，因為存在並發的操作，無法完全確定這些操作的sequence。但是，可以窮舉出所有所有可能的Xi的順序。如果所有的可能順序中，其中存在一個順序，其測試結果滿足正確性的要求，那麼就認為本次讀寫操作滿足Linearizability。

從圖3中，可以更直觀的理解Linearizability的定義：

• (a)部分滿足線性，一個可能滿足要求的順序是：W(0)A -> W(1)B -> R(1)A -> W(0)C -> R(0)B。
• (b)部分不滿足線性，中間的三個操作存在並發的情況。總共有三個可能的順序，都會推出矛盾：
• W(0)A->W(1)B->R(1)A->W(0)C->R(1)B (最後一步矛盾)
• W(0)A->R(1)A->W(1)B->W(0)C->R(1)B （最後一步矛盾）
• W(0)A->R(1)A->W(0)C->W(1)B->R(1)B （第二步矛盾）

常見的分散式系統中，etcd通過raft協議，來保證讀寫的Linearizability。常見的nosql存儲，比如redis、cassandra，都是最終一致性，並不保證強一致。elasticell在etcd的single-raft的基礎上，實現了muliei-raft，是一個高性能、強一致性、動態scale的KV存儲。

deepfabric/elasticellgithub.com

最後要賣個關子，有沒有現成的工具或者框架，來驗證或者測試分散式存儲系統的一致性呢？且聽下會分解，elasticell和jepsen測試。

參考：

Session Guarantees for Weakly Consistent Replicated Datawww.cs.cornell.edu

Strong consistency modelsaphyr.comConsistency modelen.wikipedia.org

MP HERLIHY《 Linearizability: A Correctness Condition for Concurrent Objects》

PAPADIMITRIOU, C. H. 《The serializability of concurrent database updates.》

LAMPORT, L.《How to make a multiprocessor computer that correctly executes multiprocess programs. 》

推薦閱讀：