1.分布式系統的難題

張大胖遇到了一個難題。

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

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

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

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

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

現在余額到底是多少呢？

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

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

2.誰來當老大？

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

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

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

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

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

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

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

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

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

比如節點A等待170ms , 節點B等待200ms ,  節點C等待250ms 。

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

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

節點A得知其他兩個節點同意了，投票計數變為3，已經過了半數， 就明白自己可以當老大了。

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

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

此時節點B和節點C就成了“小弟”。

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

上圖中節點C占據了先機，率先發起競選投票。

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

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

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

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

3.數據的復制

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

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

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

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

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

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

1.  客戶端發送數據給節點A （“老大”）。

節點A 先把數據記錄到日志中，即此時處于“未提交狀態”

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

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

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

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