一致性模型

來自專欄遊戲服務端編程之路

本文討論的內容都是分散式系統中的一致性。

常見一致性演算法及其定義

概覽圖

含義說明

• 概述

從上到下，一致性逐步變弱

模型含義簡述linearizable線性一致性sequencial順序一致性casual因果一致性WFRwrite follow readRyWread your writeMR單調遞增讀MW單調遞增寫最終一致性最終收斂到一致，時間不一定

• 進一步說明

• 順序一致性

1. 在不同的processor上，有不同的執行序列
2. 對於所有的執行序列，可以找到一個順序，使得按照這個順序執行，對於所有的process來說，結果都是一樣的
3. 對於同一個processor來說，執行的順序與定義的順序一致
4. 如果不滿足2、3，則結果不成立

• RyW

  讀己只寫，對於自己寫的內容，再次讀取一定能讀到

• WFR
  如果一個寫操作依賴於上一個讀操作，那麼在所有節點上，上一次讀操作對應的寫操作，一定是在本次寫操作之前完成，主要是避免不同節點上寫的順序不同帶來的dirty write
• MR、MW
  單調遞增的讀寫保證，保證每次讀寫都不會讀到一個比上一次讀寫舊的版本

線性一致性

也叫強一致性性，可實現的，最高級別的一致性模型。線性一致性隱含了因果一致性。

直覺式定義

1. 一個系統看起來只有一個數據副本，並且所有的操作都是原子性的
2. 任何一個讀取返回新值後，所有後續讀取（在相同或其他客戶端上）也必須返回新值

線性一致性作用

• 分散式鎖
• 領導選舉
• 唯一性保證

複製系統的線性一致性

複製系統 是否線性一致 說明

單主複製 可能線性一致 比如腦裂

共識演算法 線性一致 處理了腦裂和陳舊副本

多主複製 非線性一致 多點寫入、寫入衝突

無主複製 可能不一致

LWW（最終寫入勝利）非線性一致 時鐘偏差，不能保證時鐘的時間戳與實際事件一致

線性一致性的代價

• 影響可用性
• 降低性能，吞吐量不會太高（etcd qps在1k左右）

順序保證

小知識點

• 順序導致因果
• 全序，偏序

  整個序列可比較為全序，否則為偏序（如數學中的集合）

• 線性一致性強於因果一致性

序列號

• 序列號
• 時間戳
• lamport 時間戳
  $(counter, node_id)形式的vector

全序廣播

• 可靠交付
  沒有消息丟失，如果消息被傳遞到一個節點，意味著一定會被傳遞到所有節點。
• 全序交付
  消息以相同的順序傳遞給每個節點。
• 狀態機複製

1. state machine replication
2. 一般基於壓縮日誌

• 全序廣播與線性一致性

• 利用全序廣播實現線性一致性

1. 寫append only log，這是非同步的
2. 等待消息寫入的結果，不立刻返回
3. 寫線性一致，讀不一定
4. 讀一致性保證，可以是顯式同步，追加消息等方案，參見etcd，zookeeper的實現

• 利用線性一致性實現全序廣播
  很簡單，利用線性一致性來實現一個全局遞增的index。

一致性系統關注

etcd 讀寫一致性的思考

• etcd是一個線性一致性的演算法
• 但實際上，寫是保證了線性一致 ，但由於讀可以從follower上讀，所以並不默認是線性一致的，需要有一定的策略來保證，詳見參考資料。

zookeeper 讀寫一致性

• 讀
  順序一致
• 寫
  線性一致

參考資料

1. Wikipedia一致性模型詞條
2. etcd一致性讀
3. zookeeper順序一致性的理解
4. DDIA chap9

推薦閱讀：