面試官：談談分佈式一致性機制，我一臉懵逼。。

作者：mageek
來源：http://mageek.cn/archives/88/

是的，曾經我被面試官問到分佈式一致性機制，當時我一臉懵逼。。

分佈式中一致性是非常重要的，分爲弱一致性和強一致性。

現在主流的一致性協議一般都選擇的是弱一致性的特殊版本：最終一致性。下面就從分佈式系統的基本原則講起，再整理一些遵循這些原則的協議或者機制，爭取通俗易懂。

但是要真正實施起來把這些協議落地，可不是一篇文章能說清楚的，有太多的細節，要自己去看論文吶（順着維基百科找就行了）。

基本原則與理論

CAP（Consistency 一致性，Availability 可用性，Partition tolerance 分區容錯性）理論是當前分佈式系統公認的理論，亦即一個分佈式系統不可能同時滿足這三個特性，只能三求其二。對於分佈式系統，P 是基本要求，如果沒有 P 就不是分佈式系統了，所以一般都是在滿足 P 的情況下，在 C 和 A 之間尋求平衡。

ACID（Atomicity 原子性，Consistency 一致性，Isolation 隔離性，Durability 持久性）是事務的特點，具有強一致性，一般用於單機事務，分佈式事務若採用這個原則會喪失一定的可用性，屬於 CP 系統。

BASE（Basically Availabe 基本可用，Soft state 軟狀態，Eventually consistency 最終一致性）理論是對大規模的互聯網分佈式系統實踐的總結，用弱一致性來換取可用性，不同於 ACID，屬於 AP 系統。

2PC

2 Phase Commit，兩階段提交，系統有兩個角色協調者和參與者，事務提交過程分爲兩階段：

  1. 提交事務請求（投票階段）

    協調者向參與者發送事務內容，詢問是否可以執行事務提交操作，等待響應

參與者執行事務操作，並將 undo 和 redo 日誌記錄

參與者回覆協調者，執行成功則回 Yes 否則 No

  1. 執行事務提交（執行階段）

該協議可以視爲強一致的算法，通常用來保證多份數據操作的原子性，也可以實現數據副本之間的一致性，實現簡單，但是缺點也很多，比如單點故障（協調者掛了整個系統就沒法對外服務，任一節點掛了事務就沒法執行，沒有容錯機制）、阻塞（兩個階段都涉及同步等待阻塞，極大降低了吞吐量）、數據不一致（參與者回覆 Yes/No 後如果因爲網絡原因沒有收到提交 / 中斷請求，此時它就不知道該如何操作了，導致集羣數據不一致）……

2PC 有些優化手段：超時判斷機制，比如協調者發出事務請求後等待所有參與者反饋，若超過時間沒有蒐集完畢所有回覆則可以多播消息取消本次事務；互詢機制，參與者 P 回覆 yes 後，等待協調者發起最終的 commitabort，如果沒收到那麼可以詢問其他參與者 Q 來決定自身下一步操作，避免一直阻塞（如果其他參與者全都是等待狀態，那麼 P 也只能一直阻塞了）。所以 2PC 的阻塞問題是沒辦法徹底解決的。

當然，如果網絡環境較好，該協議一般還是能很好的工作的，2PC 廣泛應用於關係數據庫的分佈式事務處理，如 mysql 的內部與外部 XA 都是基於 2PC 的，一般想要把多個操作打包未原子操作也可以用 2PC。

3PC

3 Phase Commit，三階段提交，是二階段提交的改進，系統也有兩個角色協調者和參與者，事務提交過程分爲三階段：

  1. 事務詢問（canCommit）

  1. 執行事務預提交（preCommit）

  1. 執行事務提交（doCommit）

三階段相對於兩階段的改善就是把準備階段一分爲二，亦即多了一個 canCommit 階段，按我理解這樣就類似於 TCP 的三步握手，多了一次確認，增大了事務執行成功的概率。而且 3PC 的協調者即使出了故障，參與者也能繼續執行事務所以解決了 2PC 的阻塞問題，但是也可能因此導致集羣數據不一致。

另外，如果你想搞清楚分佈式事務相關問題，系列面試題和答案我全部整理好了，微信搜索 Java 技術棧，在後臺發送：面試，可以在線閱讀。

Paxos

上面兩個協議的協調者都需要人爲設置而無法自動生成，是不完整的分佈式協議，而 Paxos 就是一個真正的完整的分佈式算法。系統一共有幾個角色：Proposer（提出提案）、Acceptor（參與決策）、Learner（不參與提案，只負責接收已確定的提案，一般用於提高集羣對外提供讀服務的能力），實踐中一個節點可以同時充當多個角色。提案選定過程也大概分爲 2 階段：

  1. Prepare 階段

  1. Accept 階段

  1. Learn 階段（本階段不屬於選定提案的過程）

Paxos 協議的容錯性很好，只要有超過半數的節點可用，整個集羣就可以自己進行 Leader 選舉，也可以對外服務，通常用來保證一份數據的多個副本之間的一致性，適用於構建一個分佈式的一致性狀態機。

Google 的分佈式鎖服務 Chubby 就是用了 Paxos 協議，而開源的 ZooKeeper 使用的是 Paxos 的變種 ZAB 協議。另外，分佈式系列面試題和答案全部整理好了，微信搜索 Java 技術棧，在後臺發送：面試，可以在線閱讀。

Raft

Raft 協議對標 Paxos，容錯性和性能都是一致的，但是 Raft 比 Paxos 更易理解和實施。系統分爲幾種角色：Leader（發出提案）、Follower（參與決策）、Candidate（Leader 選舉中的臨時角色）。

剛開始所有節點都是 Follower 狀態，然後進行 Leader 選舉。成功後 Leader 接受所有客戶端的請求，然後把日誌 entry 發送給所有 Follower，當收到過半的節點的回覆（而不是全部節點）時就給客戶端返回成功並把 commitIndex 設置爲該 entry 的 index，所以是滿足最終一致性的。

Leader 同時還會週期性地發送心跳給所有的 Follower（會通過心跳同步提交的序號 commitIndex），Follower 收到後就保持 Follower 狀態（並應用 commitIndex 及其之前對應的日誌 entry），如果 Follower 等待心跳超時了，則開始新的 Leader 選舉：首先把當前 term 計數加 1，自己成爲 Candidate，然後給自己投票並向其它結點發投票請求。

直到以下三種情況：

在選舉期間，Candidate 可能收到來自其它自稱爲 Leader 的寫請求，如果該 Leader 的 term 不小於 Candidate 的當前 term，那麼 Candidate 承認它是一個合法的 Leader 並回到 Follower 狀態，否則拒絕請求。

如果出現兩個 Candidate 得票一樣多，則它們都無法獲取超過半數投票，這種情況會持續到超時，然後進行新一輪的選舉，這時同時的概率就很低了，那麼首先發出投票請求的的 Candidate 就會得到大多數同意，成爲 Leader。

在 Raft 協議出來之前，Paxos 是分佈式領域的事實標準，但是 Raft 的出現打破了這一個現狀（raft 作者也是這麼想的，請看論文），Raft 協議把 Leader 選舉、日誌複製、安全性等功能分離並模塊化，使其更易理解和工程實現，將來發展怎樣我們拭目以待（挺看好）。

Raft 協議目前被用於 cockrouchDB，TiKV 等項目中，據我聽的一些報告來看，一些大廠自己造的分佈式數據庫也在使用 Raft 協議。

Gossip

Gossip 協議與上述所有協議最大的區別就是它是去中心化的，上面所有的協議都有一個類似於 Leader 的角色來統籌安排事務的響應、提交與中斷，但是 Gossip 協議中就沒有 Leader，每個節點都是平等的。

每個節點存放了一個 key,value,version 構成的列表，每隔一定的時間，節點都會主動挑選一個在線節點進行上圖的過程（不在線的也會挑一個嘗試），兩個節點各自修改自己較爲落後的數據，最終數據達成一致並且都較新。節點加入或退出都很容易。

去中心化的 Gossip 看起來很美好：沒有單點故障，看似無上限的對外服務能力…… 本來隨着 Cassandra 火了一把，但是現在 Cassandra 也被拋棄了，去中心化的架構貌似難以真正應用起來。歸根到底我覺得還是因爲去中心化本身管理太複雜，節點之間溝通成本高，最終一致等待時間較長……

往更高處看，一個企業（甚至整個社會）不也是需要中心化的領導（或者制度）來管理嗎，如果沒有領導（或者制度）管理，大家就是一盤散沙，難成大事啊。

事實上現代互聯網架構只要把單點做得足夠強大，再加上若干個強一致的熱備，一般問題都不大。

NWR 機制

首先看看這三個字母在分佈式系統中的含義：

N：有多少份數據副本；W：一次成功的寫操作至少有 w 份數據寫入成功；R：一次成功的讀操作至少有 R 份數據讀取成功。點擊這個在線刷題鏈接，面試題很全了。

NWR 值的不同組合會產生不同的一致性效果，當 W+R>N 的時候，讀取操作和寫入操作成功的數據一定會有交集，這樣就可以保證一定能夠讀取到最新版本的更新數據，數據的強一致性得到了保證，如果 R+W<=N，則無法保證數據的強一致性，因爲成功寫和成功讀集合可能不存在交集，這樣讀操作無法讀取到最新的更新數值，也就無法保證數據的強一致性。

版本的新舊需要版本控制算法來判別，比如向量時鐘。

當然 R 或者 W 不能太大，因爲越大需要操作的副本越多，耗時越長。

Quorum 機制

Quorom 機制，是一種分佈式系統中常用的，用來保證數據冗餘和最終一致性的投票算法，主要思想來源於鴿巢原理。在有冗餘數據的分佈式存儲系統當中，冗餘數據對象會在不同的機器之間存放多份拷貝。但是同一時刻一個數據對象的多份拷貝只能用於讀或者用於寫。

分佈式系統中的每一份數據拷貝對象都被賦予一票。每一個操作必須要獲得最小的讀票數（Vr）或者最小的寫票數 (Vw）才能讀或者寫。如果一個系統有 V 票（意味着一個數據對象有 V 份冗餘拷貝），那麼這最小讀寫票必須滿足：

第一條規則保證了一個數據不會被同時讀寫。當一個寫操作請求過來的時候，它必須要獲得 Vw 個冗餘拷貝的許可。而剩下的數量是 V-Vw 不夠 Vr，因此不能再有讀請求過來了。同理，當讀請求已經獲得了 Vr 個冗餘拷貝的許可時，寫請求就無法獲得許可了。

第二條規則保證了數據的串行化修改。一份數據的冗餘拷貝不可能同時被兩個寫請求修改。

Quorum 機制其實就是 NWR 機制。

Lease 機制

master 給各個 slave 分配不同的數據，每個節點的數據都具有有效時間比如 1 小時，在 lease 時間內，客戶端可以直接向 slave 請求數據，如果超過時間客戶端就去 master 請求數據。一般而言，slave 可以定時主動向 master 要求續租並更新數據，master 在數據發生變化時也可以主動通知 slave，不同方式的選擇也在於可用性與一致性之間進行權衡。

租約機制也可以解決主備之間網絡不通導致的雙主腦裂問題，亦即：主備之間本來心跳連線的，但是突然之間網絡不通或者暫停又恢復了或者太繁忙無法回覆，這時備機開始接管服務，但是主機依然存活能對外服務，這是就發生爭奪與分區，但是引入 lease 的話，老主機頒發給具體 server 的 lease 必然較舊，請求就失效了，老主機自動退出對外服務，備機完全接管服務。另外，關注公衆號 Java 技術棧，在後臺回覆：面試，可以獲取我整理的分佈式系列面試題和答案，非常齊全。

參考：

https://en.wikipedia.org/wiki/Two-phase_commit_protocol
https://en.wikipedia.org/wiki/Three-phase_commit_protocol
https://en.wikipedia.org/wiki/Paxos(computer_science)
https://raft.github.io/
https://en.wikipedia.org/wiki/Raft_(computer_science)
https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
http://www.infoq.com/cn/articles/raft-paper
https://en.wikipedia.org/wiki/Gossip_protocol
https://book.douban.com/subject/26292004/
https://book.douban.com/subject/4848587/
https://book.douban.com/subject/25984046/
http://m635674608.iteye.com/blog/2343038_

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ZyW3GupsCPN4cEGPBMofuw

猜你喜歡