來(lái)源：https://zhuanlan.zhihu.com/p/130332285

作者：無(wú)知影

為什么需要一致性

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

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

3. 一致性算法就是為了解決上面兩個(gè)問(wèn)題。

一致性算法的定義

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

一致性的分類

強(qiáng)一致性

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

• Paxos

• Raft（muti-paxos）

• ZAB（muti-paxos）

弱一致性

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

• DNS系統(tǒng)

• Gossip協(xié)議

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

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

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

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

Paxos算法

概念介紹

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

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

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

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

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

Basic Paxos算法

步驟：

1. Propser準(zhǔn)備一個(gè)N號(hào)提案

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

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

4. Learner記錄提案

節(jié)點(diǎn)故障

• 若Proposer故障，沒(méi)關(guān)系，再?gòu)募褐羞x出Proposer即可

• 若Acceptor故障，表決時(shí)能達(dá)到多數(shù)派也沒(méi)問(wèn)題

潛在問(wèn)題-活鎖

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

Multi Paxos算法

根據(jù)Basic Paxos的改進(jìn)：整個(gè)系統(tǒng)只有一個(gè)Proposer，稱之為L(zhǎng)eader。

步驟：

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

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

3. 其他步驟和Basic Paxos相同

算法優(yōu)化

Multi Paxos角色過(guò)多，對(duì)于計(jì)算機(jī)集群而言，可以將Proposer、Acceptor和Learner三者身份集中在一個(gè)節(jié)點(diǎn)上，此時(shí)只需要從集群中選出Proposer，其他節(jié)點(diǎn)都是Acceptor和Learner，這就是接下來(lái)要討論的Raft算法

Raft算法

Paxos算法不容易實(shí)現(xiàn)，Raft算法是對(duì)Paxos算法的簡(jiǎn)化和改進(jìn)

概念介紹

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

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

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

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

Leader選舉

1. 每個(gè)Follower都持有一個(gè)定時(shí)器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ZAB算法

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

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

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

Gossip算法

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

1. 集群?jiǎn)?dòng)，如下圖所示（這里設(shè)置集群有20個(gè)節(jié)點(diǎn)）

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

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

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

長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝