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

張大胖遇到了一個難題。

他們公司的有個服務器，上面保存著寶貴的數據，領導Bill 為了防止它掛掉， 要求張大胖想想辦法把數據做備份。

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

為了提高可用性，可以增加幾臺機器，通過局域網連接起來，形成一個了分布式的系統(tǒng)：

數據在每個節(jié)點上都存放一份不就可以高枕無憂了？

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

現在余額到底是多少呢？

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

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

2.誰來當老大？

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

所有的操作都通過“老大”來進行，然后讓老大把消息發(fā)給各個“小弟”。

可是誰來當老大呢？  還有，這個老大如果掛掉了怎么辦？

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

但是這就有點麻煩了，能不能自動化地來實現？

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

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

為了避免大家同時發(fā)起投票邀請，可以給每個節(jié)點都分配一個隨機的“選舉超時時間”（election timeout），通俗來講就是一個等待時間，在這段時間內，一個節(jié)點必須耐心等待，過了這段時間，才可以競爭上崗，爭當老大。

每個節(jié)點都有一個計時器，從0開始計時，誰的等待時間到了, 就率先發(fā)起競選，給其他節(jié)點打電話，要求他們投票讓自己成為老大。

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

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

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

節(jié)點A得知其他兩個節(jié)點同意了，投票計數變?yōu)?，已經過了半數， 就明白自己可以當老大了。

節(jié)點A成為老大后，開始向節(jié)點B和節(jié)點C定時發(fā)送消息，B,C收到消息后也要回應，維持心跳。

B和C每次收到心跳消息，都得重置自己的計時器， 重新從0開始計數。

此時節(jié)點B和節(jié)點C就成了“小弟”。

如果節(jié)點A 不幸掛掉，節(jié)點B和節(jié)點C在自己的等待時間內收不到心跳消息，他們兩個就會重新競爭上崗。

上圖中節(jié)點C占據了先機，率先發(fā)起競選投票。

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

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

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

對于每個節(jié)點，處理流程其實非常簡單：

3.數據的復制

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

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

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

所以那個“老大”節(jié)點必須得承擔起協調的職責。

張大胖想了一個復制日志的辦法：  每個節(jié)點都有一個日志的隊列。

在真正把數據提交之前，先把數據追加到日志隊列中，然后向個“小弟”復制。

1.  客戶端發(fā)送數據給節(jié)點A （“老大”）。

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

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

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

4. 如果節(jié)點A收到響應超過了半數， 節(jié)點A就提交數據，通知客戶端數據保存成功。

5. 節(jié)點A在下一次心跳消息中，通知各個“小弟”該數據已經提交。各個“小弟”也提交自己的數據。

如果某個“小弟”不幸掛掉，那“老大”會不斷地嘗試聯系它， 一旦它重新開始工作，就需要從“老大”那里去復制數據，和“老大”保持一致。

4.RAFT

張大胖對這個初步的設計還比較滿意，他把這個方案交給領導Bill去審查。

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

“沒錯沒錯，領導總結得真是精準。” 張大胖拍馬屁。

“不過，”Bill 話鋒一轉， “ 你設計的日志的復制還有很多漏洞，我看你的設計中一共有5步， 如果在這5步中，那個“老大”節(jié)點A掛掉了怎么辦？數據是不是就不一致了？”

“這個...... ”  張大胖確實沒有仔細考慮。他暗自后悔，只顧低頭拉車，忘了抬頭看路，忽略了分布式環(huán)境下的復雜問題。

“不過你已經做得很不錯了，” 領導馬上鼓勵道， “你設計的這一套體系其實和RAFT算法非常類似。”

“RAFT？ ”

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

張大胖一聽說有現成的算法，立刻高興起來： “太好了，分布式的難題已經被別人解決，我去把它實現了。”

【本文為51CTO專欄作者“劉欣”的原創(chuàng)稿件，轉載請通過作者微信公眾號coderising獲取授權】

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