1.分布式系統(tǒng)的難題

張大胖遇到了一個(gè)難題。

他們公司的有個(gè)服務(wù)器，上面保存著寶貴的數(shù)據(jù)，領(lǐng)導(dǎo)Bill 為了防止它掛掉， 要求張大胖想想辦法把數(shù)據(jù)做備份。

張大胖發(fā)揮了抽象的能力，在腦海里浮出了這么一個(gè)畫(huà)面， 這個(gè)唯一的機(jī)器可以成為一個(gè)節(jié)點(diǎn)：

為了提高可用性，可以增加幾臺(tái)機(jī)器，通過(guò)局域網(wǎng)連接起來(lái)，形成一個(gè)了分布式的系統(tǒng)：

數(shù)據(jù)在每個(gè)節(jié)點(diǎn)上都存放一份不就可以高枕無(wú)憂(yōu)了？

可張大胖很快發(fā)現(xiàn)這不是一件容易的事情，比如每個(gè)節(jié)點(diǎn)都保存著一個(gè)賬戶(hù)的余額100元，現(xiàn)在有人通過(guò)節(jié)點(diǎn)A向該賬戶(hù)增加了20元， 還有人通過(guò)節(jié)點(diǎn)B向該賬戶(hù)減去了30元。

現(xiàn)在余額到底是多少呢？

為了保持一致性， 節(jié)點(diǎn)A得把"余額加上20"這樣的消息發(fā)給B, C ， 節(jié)點(diǎn)B得把“余額減去30”這樣的消息發(fā)送到A, C， 如果網(wǎng)絡(luò)出了問(wèn)題，消息沒(méi)有發(fā)送到別的節(jié)點(diǎn)， 或者某個(gè)節(jié)點(diǎn)干脆壞掉了，那數(shù)據(jù)極有可能出現(xiàn)不一致。

如果用戶(hù)在這個(gè)不一致的系統(tǒng)上繼續(xù)操作，很快就會(huì)陷入混亂。

2.誰(shuí)來(lái)當(dāng)老大？

張大胖想了半天，覺(jué)得不能這么無(wú)序地操作，得給這三個(gè)節(jié)點(diǎn)找個(gè)“老大”。

所有的操作都通過(guò)“老大”來(lái)進(jìn)行，然后讓老大把消息發(fā)給各個(gè)“小弟”。

可是誰(shuí)來(lái)當(dāng)老大呢？  還有，這個(gè)老大如果掛掉了怎么辦？

可以手工地調(diào)整， 例如節(jié)點(diǎn)A掛掉了， 就手工地讓節(jié)點(diǎn)B當(dāng)“老大” ， 讓節(jié)點(diǎn)C當(dāng)“小弟”。

但是這就有點(diǎn)麻煩了，能不能自動(dòng)化地來(lái)實(shí)現(xiàn)？

這個(gè)問(wèn)題很有意思， 張大胖入了迷，繼續(xù)深入思考： 建立一個(gè)競(jìng)選的機(jī)制， 就讓他們競(jìng)爭(zhēng)上崗吧。

初始情況下，每個(gè)節(jié)點(diǎn)都是候選人， 都可以向其他節(jié)點(diǎn)發(fā)起投票邀請(qǐng)，讓大家投自己，如果獲得的投票數(shù)過(guò)半，就可以當(dāng)“老大”了。

為了避免大家同時(shí)發(fā)起投票邀請(qǐng)，可以給每個(gè)節(jié)點(diǎn)都分配一個(gè)隨機(jī)的“選舉超時(shí)時(shí)間”（election timeout），通俗來(lái)講就是一個(gè)等待時(shí)間，在這段時(shí)間內(nèi)，一個(gè)節(jié)點(diǎn)必須耐心等待，過(guò)了這段時(shí)間，才可以競(jìng)爭(zhēng)上崗，爭(zhēng)當(dāng)老大。

每個(gè)節(jié)點(diǎn)都有一個(gè)計(jì)時(shí)器，從0開(kāi)始計(jì)時(shí)，誰(shuí)的等待時(shí)間到了, 就率先發(fā)起競(jìng)選，給其他節(jié)點(diǎn)打電話(huà)，要求他們投票讓自己成為老大。

比如節(jié)點(diǎn)A等待170ms , 節(jié)點(diǎn)B等待200ms ,  節(jié)點(diǎn)C等待250ms 。

由于節(jié)點(diǎn)A的等待時(shí)間最短， 會(huì)捷足先登， 它先增加自己的任期(Term)，這是一個(gè)整數(shù)，初始值為0 ， 然后給自己投了一票，然后打電話(huà)給節(jié)點(diǎn)B和節(jié)點(diǎn)C，要求他們都投它。

節(jié)點(diǎn)B和節(jié)點(diǎn)C收到了投票要求，如果自己還沒(méi)有發(fā)起競(jìng)選投票（等待時(shí)間未到），那只好同意節(jié)點(diǎn)A當(dāng)老大，與此同時(shí)要重置自己的計(jì)時(shí)器，重新從0開(kāi)始計(jì)時(shí)，也就是說(shuō)重新開(kāi)始新一輪的等待。

節(jié)點(diǎn)A得知其他兩個(gè)節(jié)點(diǎn)同意了，投票計(jì)數(shù)變?yōu)?，已經(jīng)過(guò)了半數(shù)， 就明白自己可以當(dāng)老大了。

節(jié)點(diǎn)A成為老大后，開(kāi)始向節(jié)點(diǎn)B和節(jié)點(diǎn)C定時(shí)發(fā)送消息，B,C收到消息后也要回應(yīng)，維持心跳。

B和C每次收到心跳消息，都得重置自己的計(jì)時(shí)器， 重新從0開(kāi)始計(jì)數(shù)。

此時(shí)節(jié)點(diǎn)B和節(jié)點(diǎn)C就成了“小弟”。

如果節(jié)點(diǎn)A 不幸掛掉，節(jié)點(diǎn)B和節(jié)點(diǎn)C在自己的等待時(shí)間內(nèi)收不到心跳消息，他們兩個(gè)就會(huì)重新競(jìng)爭(zhēng)上崗。

上圖中節(jié)點(diǎn)C占據(jù)了先機(jī)，率先發(fā)起競(jìng)選投票。

節(jié)點(diǎn)B慢了一步， 無(wú)奈中同意支持節(jié)點(diǎn)C ，  節(jié)點(diǎn)C獲得了超過(guò)半數(shù)的支持，成為“老大” ，  節(jié)點(diǎn)B成為“小弟”。

（可能有人會(huì)想到：節(jié)點(diǎn)B和節(jié)點(diǎn)C 同時(shí)發(fā)起競(jìng)選投票，每個(gè)節(jié)點(diǎn)的投票計(jì)數(shù)都是1 ，都過(guò)不了半數(shù)，  該怎么處理呢？ 很簡(jiǎn)單，再次發(fā)起一輪競(jìng)選投票即可，當(dāng)然為了防止B和C一直同時(shí)發(fā)起競(jìng)選投票，從而陷入***循環(huán)，要重置一個(gè)隨機(jī)的等待時(shí)間。）

投票過(guò)半數(shù)很重要，張大胖想，只有這樣才能保證“老大”節(jié)點(diǎn)的唯一性。

對(duì)于每個(gè)節(jié)點(diǎn)，處理流程其實(shí)非常簡(jiǎn)單：

3.數(shù)據(jù)的復(fù)制

張大胖費(fèi)了半天勁，終于把分布式系統(tǒng)中怎么自動(dòng)地選取“老大”節(jié)點(diǎn)給確定了。

接下來(lái)就是要把發(fā)給“老大”的數(shù)據(jù)，想辦法復(fù)制到“小弟”的節(jié)點(diǎn)上。 該怎么處理？

由于是分布式的，只有大多數(shù)節(jié)點(diǎn)都成功地保存了數(shù)據(jù)，才算保存成功。

所以那個(gè)“老大”節(jié)點(diǎn)必須得承擔(dān)起協(xié)調(diào)的職責(zé)。

張大胖想了一個(gè)復(fù)制日志的辦法：  每個(gè)節(jié)點(diǎn)都有一個(gè)日志的隊(duì)列。

在真正把數(shù)據(jù)提交之前，先把數(shù)據(jù)追加到日志隊(duì)列中，然后向個(gè)“小弟”復(fù)制。

1.  客戶(hù)端發(fā)送數(shù)據(jù)給節(jié)點(diǎn)A （“老大”）。

節(jié)點(diǎn)A 先把數(shù)據(jù)記錄到日志中，即此時(shí)處于“未提交狀態(tài)”

2. 在下一次的心跳消息中， 數(shù)據(jù)被發(fā)送給各個(gè)“小弟”。

3. 各個(gè)“小弟” 也把數(shù)據(jù)記錄到日志中（也處于未提交狀態(tài)），然后向“老大”報(bào)告自己已經(jīng)記錄了日志。

4. 如果節(jié)點(diǎn)A收到響應(yīng)超過(guò)了半數(shù)， 節(jié)點(diǎn)A就提交數(shù)據(jù)，通知客戶(hù)端數(shù)據(jù)保存成功。

5. 節(jié)點(diǎn)A在下一次心跳消息中，通知各個(gè)“小弟”該數(shù)據(jù)已經(jīng)提交。各個(gè)“小弟”也提交自己的數(shù)據(jù)。

如果某個(gè)“小弟”不幸掛掉，那“老大”會(huì)不斷地嘗試聯(lián)系它， 一旦它重新開(kāi)始工作，就需要從“老大”那里去復(fù)制數(shù)據(jù)，和“老大”保持一致。

4.RAFT

張大胖對(duì)這個(gè)初步的設(shè)計(jì)還比較滿(mǎn)意，他把這個(gè)方案交給領(lǐng)導(dǎo)Bill去審查。

Bill 看了以后，笑道： “你現(xiàn)在其實(shí)就是在折騰一個(gè)一致性算法， 說(shuō)白了就是允許一組機(jī)器像一個(gè)整體一樣工作，即使其中一些機(jī)器出現(xiàn)故障也能夠繼續(xù)工作下去。”

“沒(méi)錯(cuò)沒(méi)錯(cuò)，領(lǐng)導(dǎo)總結(jié)得真是精準(zhǔn)。” 張大胖拍馬屁。

“不過(guò)，”Bill 話(huà)鋒一轉(zhuǎn)， “ 你設(shè)計(jì)的日志的復(fù)制還有很多漏洞，我看你的設(shè)計(jì)中一共有5步， 如果在這5步中，那個(gè)“老大”節(jié)點(diǎn)A掛掉了怎么辦？數(shù)據(jù)是不是就不一致了？”

“這個(gè)...... ”  張大胖確實(shí)沒(méi)有仔細(xì)考慮。他暗自后悔，只顧低頭拉車(chē)，忘了抬頭看路，忽略了分布式環(huán)境下的復(fù)雜問(wèn)題。

“不過(guò)你已經(jīng)做得很不錯(cuò)了，” 領(lǐng)導(dǎo)馬上鼓勵(lì)道， “你設(shè)計(jì)的這一套體系其實(shí)和RAFT算法非常類(lèi)似。”

“RAFT？ ”

“對(duì)，RAFT是個(gè)分布式的一致性算法，相比復(fù)雜難懂的Paxos， RAFT在可理解，可實(shí)現(xiàn)性上做了很大的改進(jìn)。 你這里的‘老大’，RAFT算法叫做Leader， ‘小弟’叫做Follower，不過(guò)人家對(duì)日志的復(fù)制，以及如何確保數(shù)據(jù)的一致性有著非常詳細(xì)的規(guī)定。 ”

張大胖一聽(tīng)說(shuō)有現(xiàn)成的算法，立刻高興起來(lái)： “太好了，分布式的難題已經(jīng)被別人解決，我去把它實(shí)現(xiàn)了。”

【本文為51CTO專(zhuān)欄作者“劉欣”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)作者微信公眾號(hào)coderising獲取授權(quán)】

戳這里，看該作者更多好文