分布式一致性算法：可能比你想象得更復雜

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成為“小弟”。