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

作者：無知影

為什么需要一致性

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

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

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

一致性算法的定義

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

一致性的分類

強一致性

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

• Paxos

• Raft（muti-paxos）

• ZAB（muti-paxos）

弱一致性

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

• DNS系統(tǒng)

• Gossip協(xié)議

一致性算法實現(xiàn)舉例

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

• etcd分布式鍵值數(shù)據(jù)庫，采用了Raft算法

• ZooKeeper分布式應(yīng)用協(xié)調(diào)服務(wù)，Chubby的開源實現(xiàn)，采用ZAB算法

Paxos算法

概念介紹

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

2. Client用戶，類似社會民眾，負(fù)責(zé)提出建議

3. Propser議員，類似基層人大代表，負(fù)責(zé)幫Client上交提案

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

5. Learner提案接受者，類似記錄被通過提案的記錄員，負(fù)責(zé)記錄提案

Basic Paxos算法

步驟：

1. Propser準(zhǔn)備一個N號提案

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

3. Acceptor開始表決，Acceptor無條件同意從未接收過的N號提案，達(dá)到多數(shù)派同意后，進(jìn)入下一步

4. Learner記錄提案

節(jié)點故障

• 若Proposer故障，沒關(guān)系，再從集群中選出Proposer即可

• 若Acceptor故障，表決時能達(dá)到多數(shù)派也沒問題

潛在問題-活鎖

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

Multi Paxos算法

根據(jù)Basic Paxos的改進(jìn)：整個系統(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算法不容易實現(xiàn)，Raft算法是對Paxos算法的簡化和改進(jìn)

概念介紹

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

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

3. Candidate候選人，負(fù)責(zé)爭奪Leader

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

Leader選舉

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

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

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

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

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

6. 當(dāng)Leader節(jié)點出現(xiàn)故障而導(dǎo)致Leader失聯(lián)，沒有接收到心跳的Follower節(jié)點將準(zhǔn)備成為Candidate進(jìn)入下一輪Leader選舉

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

狀態(tài)復(fù)制

1. Leader負(fù)責(zé)接收來自Client的提案請求（紅色提案表示未確認(rèn)）

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

3. Follower接收到心跳以后回復(fù)Leader的心跳

4. Leader接收到多數(shù)派Follower的回復(fù)以后確認(rèn)提案并寫入自己的存儲空間中并回復(fù)Client

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

6. 若集群中出現(xiàn)網(wǎng)絡(luò)異常，導(dǎo)致集群被分割，將出現(xiàn)多個Leader

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

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

ZAB算法

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

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

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

Gossip算法

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

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

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

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

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

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