分布式一致性協(xié)議 Raft，自 2013 年論文發(fā)表之后就受到了技術(shù)領(lǐng)域的熱捧，我認(rèn)為相對(duì)于其他分布式一致性算法，Raft 有效的解決了分布式一致性算法過于復(fù)雜及難于實(shí)現(xiàn)的問題，這也是 Raft 能異軍突起的主要因素。

image.png

Raft 協(xié)議有效的借鑒了美國總統(tǒng)大選的策略，采用精英（Raft 稱呼這個(gè)精英為 Leader）領(lǐng)導(dǎo)全局的方案，整個(gè)集群中只有 Leader 可以處理 client 發(fā)送過來的請(qǐng)求，其他非 Leader 節(jié)點(diǎn)即使接收到請(qǐng)求也必須將其轉(zhuǎn)發(fā)到 Leader 節(jié)點(diǎn)進(jìn)行處理。Raft 集群中的成員分三種角色：

1. Leader
2. Follower
3. Condidate

Raft 的選舉過程

Raft 協(xié)議在集群初始狀態(tài)下是沒有 Leader 的, 集群中所有成員均是 Follower，在選舉開始期間所有 Follower 均可參與選舉，這時(shí)所有 Follower 的角色均轉(zhuǎn)變?yōu)?Condidate, Leader 由集群中所有的 Condidate 投票選出，最后獲得投票最多的 Condidate 獲勝，其角色轉(zhuǎn)變?yōu)?Leader 并開始其任期，其余落敗的 Condidate 角色轉(zhuǎn)變?yōu)?Follower 開始服從 Leader 領(lǐng)導(dǎo)。這里有一種意外的情況會(huì)選不出 Leader 就是所有 Condidate 均投票給自己，這樣無法決出票數(shù)多的一方，Raft 算法為了解決這個(gè)問題引入了北洋時(shí)期袁世凱獲選大總統(tǒng)的謀略，即選不出 Leader 不罷休，直到選出為止，一輪選不出 Leader，便令所有 Condidate 隨機(jī) sleap（Raft 論文稱為 timeout）一段時(shí)間，然后馬上開始新一輪的選舉，這里的隨機(jī) sleep 就起了很關(guān)鍵的因素，第一個(gè)從 sleap 狀態(tài)恢復(fù)過來的 Condidate 會(huì)向所有 Condidate 發(fā)出投票給我的申請(qǐng)，這時(shí)還沒有蘇醒的 Condidate 就只能投票給已經(jīng)蘇醒的 Condidate ，因此可以有效解決 Condiadte 均投票給自己的故障，便可快速的決出 Leader。

選舉出 Leader 后 Leader 會(huì)定期向所有 Follower 發(fā)送 heartbeat 來維護(hù)其 Leader 地位，如果 Follower 一段時(shí)間后未收到 Leader 的心跳則認(rèn)為 Leader 已經(jīng)掛掉，便轉(zhuǎn)變自身角色為 Condidate，同時(shí)發(fā)起新一輪的選舉，產(chǎn)生新的 Leader。

Raft 的數(shù)據(jù)一致性策略

Raft 協(xié)議強(qiáng)依賴 Leader 節(jié)點(diǎn)來確保集群數(shù)據(jù)一致性。即 client 發(fā)送過來的數(shù)據(jù)均先到達(dá) Leader 節(jié)點(diǎn)，Leader 接收到數(shù)據(jù)后，先將數(shù)據(jù)標(biāo)記為 uncommitted 狀態(tài)，隨后 Leader 開始向所有 Follower 復(fù)制數(shù)據(jù)并等待響應(yīng)，在獲得集群中大于 N/2 個(gè) Follower 的已成功接收數(shù)據(jù)完畢的響應(yīng)后，Leader 將數(shù)據(jù)的狀態(tài)標(biāo)記為 committed，隨后向 client 發(fā)送數(shù)據(jù)已接收確認(rèn)，在向 client 發(fā)送出已數(shù)據(jù)接收后，再向所有 Follower 節(jié)點(diǎn)發(fā)送通知表明該數(shù)據(jù)狀態(tài)為committed。

Raft 如何處理 Leader 意外的？

1. client 發(fā)送數(shù)據(jù)到達(dá) Leader 之前 Leader 就掛了，因?yàn)閿?shù)據(jù)還沒有到達(dá)集群內(nèi)部，所以對(duì)集群內(nèi)部數(shù)據(jù)的一致性沒有影響，Leader 掛了之后，集群會(huì)進(jìn)行新的選舉產(chǎn)生新的 Leader，之前掛掉的 Leader 重啟后作為 Follower 加入集群，并同步 Leader 上的數(shù)據(jù)。這里最好要求 client 有重試機(jī)制在一定時(shí)間沒有收到 Leader 的數(shù)據(jù)已接收確認(rèn)后進(jìn)行一定次數(shù)的重試，并再次向新的 Leader 發(fā)送數(shù)據(jù)來確保業(yè)務(wù)的流暢性。

2. client 發(fā)送數(shù)據(jù)到 Leader，數(shù)據(jù)到達(dá) Leader 后，Leader 還沒有開始向 Folloers 復(fù)制數(shù)據(jù)，Leader就掛了，此時(shí)數(shù)據(jù)仍被標(biāo)記為 uncommited 狀態(tài)，這時(shí)集群會(huì)進(jìn)行新的選舉產(chǎn)生新的 Leader，之前掛掉的 Leader 重啟后作為 Follower 加入集群，并同步 Leader 上的數(shù)據(jù)，來保證數(shù)據(jù)一致性，之前接收到 client 的數(shù)據(jù)由于是 uncommited 狀態(tài)所以可能會(huì)被丟棄。這里同樣最好要求 client 有重試機(jī)制通過在一定時(shí)間在沒有收到 Leader 的數(shù)據(jù)已接收確認(rèn)后進(jìn)行一定次數(shù)的重試，再次向新的 Leader 發(fā)送數(shù)據(jù)來確保業(yè)務(wù)的流暢性。

3. client 發(fā)送數(shù)據(jù)到 Leader, Leader 接收數(shù)據(jù)完畢后標(biāo)記為 uncommited，開始向 Follower復(fù)制數(shù)據(jù)，在復(fù)制完畢一小部分 Follower 后 Leader 掛了，此時(shí)數(shù)據(jù)在所有已接收到數(shù)據(jù)的 Follower 上仍被標(biāo)記為 uncommitted，但國不可一日無君，此時(shí)集群將進(jìn)行新的選舉，而擁有最新數(shù)據(jù)的 Follower 變換角色為 Condidate，也就意味著 Leader 將在擁有最新數(shù)據(jù)的 Follower 中產(chǎn)生，新的 Leader 產(chǎn)生后所有節(jié)點(diǎn)開始從新 Leader 上同步數(shù)據(jù)確保數(shù)據(jù)的一致性，包括之前掛掉后恢復(fù)了狀態(tài)的 老Leader，這時(shí)也以 Follower 的身份同步新 Leader 上的數(shù)據(jù)。

4. client 發(fā)送數(shù)據(jù)到 Leader，Leader 接收數(shù)據(jù)完畢后標(biāo)記為 uncommitted，開始向 Follower 復(fù)制數(shù)據(jù)，在復(fù)制完畢所有 Follower 節(jié)點(diǎn)或者大部分節(jié)點(diǎn)（大于 N/2），并接收到大部分節(jié)點(diǎn)接收完畢的響應(yīng)后，Leader 節(jié)點(diǎn)將數(shù)據(jù)標(biāo)記為 committed，這時(shí) Leader 掛了，此時(shí)已接收到數(shù)據(jù)的所有 Follower 節(jié)點(diǎn)上的數(shù)據(jù)狀態(tài)由于還沒有接收到 Leader 的 commited 通知，均處于 uncommited 狀態(tài)。這時(shí)集群進(jìn)行了新的選舉，新的 Leader 將在擁有最新數(shù)據(jù)的節(jié)點(diǎn)中產(chǎn)生，新的 Leader 產(chǎn)生后，由于 client 端因老 Leader 掛掉前沒有通知其數(shù)據(jù)已接收，所以會(huì)向新的 Leader 發(fā)送重試請(qǐng)求，而新的 Leader 上已經(jīng)存在了這個(gè)之前從老 Leader 上同步過來的數(shù)據(jù)，因此 Raft 集群要求各節(jié)點(diǎn)自身實(shí)現(xiàn)去重的機(jī)制，保證數(shù)據(jù)的一致性。

5. 集群腦裂的一致性處理，多發(fā)于雙機(jī)房的跨機(jī)房模式的集群。假設(shè)一個(gè) 5 節(jié)點(diǎn)的 Raft 集群，其中三個(gè)節(jié)點(diǎn)在 A 機(jī)房，Leader 節(jié)點(diǎn)也在 A 機(jī)房，兩個(gè)節(jié)點(diǎn)在 B 機(jī)房。突然 A、B 兩個(gè)機(jī)房之間因其他故障無法通訊，那么此時(shí) B 機(jī)房中的 2 個(gè)Follower 因?yàn)槭ヅc Leader 的聯(lián)系，均轉(zhuǎn)變自身角色為 Condidate。根據(jù) Leader 選舉機(jī)制，B 機(jī)房中產(chǎn)生了一個(gè)新的 Leader，這就發(fā)生了腦裂即存在 A 機(jī)房中的老 Leader 的集群與B機(jī)房新 Leader 的集群。Raft 針對(duì)這種情況的處理方式是老的 Leader 集群雖然剩下三個(gè)節(jié)點(diǎn)，但是 Leader 對(duì)數(shù)據(jù)的處理過程還是在按原來 5 個(gè)節(jié)點(diǎn)進(jìn)行處理，所以老的 Leader 接收到的數(shù)據(jù)，在向其他 4 個(gè)節(jié)點(diǎn)復(fù)制數(shù)據(jù)，由于無法獲取超過 N/2 個(gè) Follower 節(jié)點(diǎn)的復(fù)制完畢數(shù)據(jù)響應(yīng)（因?yàn)闊o法連接到 B 機(jī)房中的 2個(gè)節(jié)點(diǎn)），所以 client 在向老 Leader 發(fā)送的數(shù)據(jù)請(qǐng)求均無法成功寫入，而 client 向B機(jī)房新 Leader 發(fā)送的數(shù)據(jù)，因?yàn)槭切鲁闪⒌募?，所以可以成功寫入?shù)據(jù)，在A、B兩個(gè)機(jī)房恢復(fù)網(wǎng)絡(luò)通訊后，A 機(jī)房中的所有節(jié)點(diǎn)包括老 Leader 再以 Follower 角色接入這個(gè)集群，并同步新 Leader 中的數(shù)據(jù)，完成數(shù)據(jù)一致性處理。

因?yàn)樗惴ㄒ哉_性、高效性、簡(jiǎn)潔性為主要目標(biāo)，但這些目標(biāo)都不會(huì)達(dá)成直到你通過代碼實(shí)現(xiàn)它之前，所以接下來業(yè)余時(shí)間我將通過 Python 簡(jiǎn)單造一個(gè) Raft 的小輪子，敬請(qǐng)期待^_

• 點(diǎn)擊鏈接加入群【Python實(shí)戰(zhàn)交流群】：https://jq.qq.com/?_wv=1027&k=5qwTsxH
• 搜索 QQ 群號(hào) 397234385 入群【Python實(shí)戰(zhàn)交流群】
• 或 QQ 掃碼入群：

qq群.jpg