來源：https://zhuanlan.zhihu.com/p/130332285

作者：無知影

為什么需要一致性

1. 數據不能存在單個節(jié)點（主機）上，否則可能出現單點故障。

2. 多個節(jié)點（主機）需要保證具有相同的數據。

3. 一致性算法就是為了解決上面兩個問題。

一致性算法的定義

一致性就是數據保持一致，在分布式系統(tǒng)中，可以理解為多個節(jié)點中數據的值是一致的。

一致性的分類

強一致性

保證系統(tǒng)改變提交以后立即改變集群的狀態(tài)。

• Paxos

• Raft（muti-paxos）

• ZAB（muti-paxos）

弱一致性

也叫最終一致性，系統(tǒng)不保證改變提交以后立即改變集群的狀態(tài)，但是隨著時間的推移最終狀態(tài)是一致的。

• DNS系統(tǒng)

• Gossip協(xié)議

一致性算法實現舉例

• Google的Chubby分布式鎖服務，采用了Paxos算法

• etcd分布式鍵值數據庫，采用了Raft算法

• ZooKeeper分布式應用協(xié)調服務，Chubby的開源實現，采用ZAB算法

Paxos算法

概念介紹

1. Proposal提案，即分布式系統(tǒng)的修改請求，可以表示為[提案編號N，提案內容value]

2. Client用戶，類似社會民眾，負責提出建議

3. Propser議員，類似基層人大代表，負責幫Client上交提案

4. Acceptor投票者，類似全國人大代表，負責為提案投票，不同意比自己以前接收過的提案編號要小的提案，其他提案都同意，例如A以前給N號提案表決過，那么再收到小于等于N號的提案時就直接拒絕了

5. Learner提案接受者，類似記錄被通過提案的記錄員，負責記錄提案

Basic Paxos算法

步驟：

1. Propser準備一個N號提案

2. Propser詢問Acceptor中的多數派是否接收過N號的提案，如果都沒有進入下一步，否則本提案不被考慮

3. Acceptor開始表決，Acceptor無條件同意從未接收過的N號提案，達到多數派同意后，進入下一步

4. Learner記錄提案

節(jié)點故障

• 若Proposer故障，沒關系，再從集群中選出Proposer即可

• 若Acceptor故障，表決時能達到多數派也沒問題

潛在問題-活鎖

假設系統(tǒng)有多個Proposer，他們不斷向Acceptor發(fā)出提案，還沒等到上一個提案達到多數派下一個提案又來了，就會導致Acceptor放棄當前提案轉向處理下一個提案，于是所有提案都別想通過了。

Multi Paxos算法

根據Basic Paxos的改進：整個系統(tǒng)只有一個Proposer，稱之為Leader。

步驟：

1. 若集群中沒有Leader，則在集群中選出一個節(jié)點并聲明它為第M任Leader。

2. 集群的Acceptor只表決最新的Leader發(fā)出的最新的提案

3. 其他步驟和Basic Paxos相同

算法優(yōu)化

Multi Paxos角色過多，對于計算機集群而言，可以將Proposer、Acceptor和Learner三者身份集中在一個節(jié)點上，此時只需要從集群中選出Proposer，其他節(jié)點都是Acceptor和Learner，這就是接下來要討論的Raft算法

Raft算法

Paxos算法不容易實現，Raft算法是對Paxos算法的簡化和改進

概念介紹

1. Leader總統(tǒng)節(jié)點，負責發(fā)出提案

2. Follower追隨者節(jié)點，負責同意Leader發(fā)出的提案

3. Candidate候選人，負責爭奪Leader

Raft算法將一致性問題分解為兩個的子問題，Leader選舉和狀態(tài)復制

Leader選舉

1. 每個Follower都持有一個定時器

2. 當定時器時間到了而集群中仍然沒有Leader，Follower將聲明自己是Candidate并參與Leader選舉，同時將消息發(fā)給其他節(jié)點來爭取他們的投票，若其他節(jié)點長時間沒有響應Candidate將重新發(fā)送選舉信息

3. 集群中其他節(jié)點將給Candidate投票

4. 獲得多數派支持的Candidate將成為第M任Leader（M任是最新的任期）

5. 在任期內的Leader會不斷發(fā)送心跳給其他節(jié)點證明自己還活著，其他節(jié)點受到心跳以后就清空自己的計時器并回復Leader的心跳。這個機制保證其他節(jié)點不會在Leader任期內參加Leader選舉。

6. 當Leader節(jié)點出現故障而導致Leader失聯，沒有接收到心跳的Follower節(jié)點將準備成為Candidate進入下一輪Leader選舉

7. 若出現兩個Candidate同時選舉并獲得了相同的票數，那么這兩個Candidate將隨機推遲一段時間后再向其他節(jié)點發(fā)出投票請求，這保證了再次發(fā)送投票請求以后不沖突

狀態(tài)復制

1. Leader負責接收來自Client的提案請求（紅色提案表示未確認）

2. 提案內容將包含在Leader發(fā)出的下一個心跳中

3. Follower接收到心跳以后回復Leader的心跳

4. Leader接收到多數派Follower的回復以后確認提案并寫入自己的存儲空間中并回復Client

5. Leader通知Follower節(jié)點確認提案并寫入自己的存儲空間，隨后所有的節(jié)點都擁有相同的數據

6. 若集群中出現網絡異常，導致集群被分割，將出現多個Leader

7. 被分割出的非多數派集群將無法達到共識，即腦裂，如圖中的A、B節(jié)點將無法確認提案

8. 當集群再次連通時，將只聽從最新任期Leader的指揮，舊Leader將退化為Follower，如圖中B節(jié)點的Leader（任期1）需要聽從D節(jié)點的Leader（任期2）的指揮，此時集群重新達到一致性狀態(tài)

ZAB算法

ZAB也是對Multi Paxos算法的改進，大部分和raft相同,和raft算法的主要區(qū)別：

1. 對于Leader的任期，raft叫做term，而ZAB叫做epoch

2. 在狀態(tài)復制的過程中，raft的心跳從Leader向Follower發(fā)送，而ZAB則相反。

Gossip算法

Gossip算法每個節(jié)點都是對等的，即沒有角色之分。Gossip算法中的每個節(jié)點都會將數據改動告訴其他節(jié)點（類似傳八卦）。有話說得好："最多通過六個人你就能認識全世界任何一個陌生人"，因此數據改動的消息很快就會傳遍整個集群。

1. 集群啟動，如下圖所示（這里設置集群有20個節(jié)點）

2. 某節(jié)點收到數據改動，并將改動傳播給其他4個節(jié)點，傳播路徑表示為較粗的4條線

3. 收到數據改動的節(jié)點重復上面的過程直到所有的節(jié)點都被感染

特別推薦一個分享架構+算法的優(yōu)質內容，還沒關注的小伙伴，可以長按關注一下：

長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝