http://www.cnblogs.com/bangerlee/p/5767845.html
選舉(election)是分布式系統(tǒng)實(shí)踐中常見的問題，通過打破節(jié)點(diǎn)間的對等關(guān)系，選得的leader(或叫master、coordinator)有助于實(shí)現(xiàn)事務(wù)原子性、提升決議效率。 多數(shù)派(quorum)的思路幫助我們在網(wǎng)絡(luò)分化的情況下達(dá)成決議一致性，在leader選舉的場景下幫助我們選出唯一leader。租約(lease)在一定期限內(nèi)給予節(jié)點(diǎn)特定權(quán)利，也可以用于實(shí)現(xiàn)leader選舉。
下面我們就來學(xué)習(xí)分布式系統(tǒng)理論中的選舉、多數(shù)派和租約。
選舉(electioin)
一致性問題(consistency)是獨(dú)立的節(jié)點(diǎn)間如何達(dá)成決議的問題，選出大家都認(rèn)可的leader本質(zhì)上也是一致性問題，因而如何應(yīng)對宕機(jī)恢復(fù)、網(wǎng)絡(luò)分化等在leader選舉中也需要考量。
Bully算法[1]是最常見的選舉算法，其要求每個節(jié)點(diǎn)對應(yīng)一個序號，序號最高的節(jié)點(diǎn)為leader。leader宕機(jī)后次高序號的節(jié)點(diǎn)被重選為leader，過程如下：
(a). 節(jié)點(diǎn)4發(fā)現(xiàn)leader不可達(dá)，向序號比自己高的節(jié)點(diǎn)發(fā)起重新選舉，重新選舉消息中帶上自己的序號
(b)(c). 節(jié)點(diǎn)5、6接收到重選信息后進(jìn)行序號比較，發(fā)現(xiàn)自身的序號更大，向節(jié)點(diǎn)4返回OK消息并各自向更高序號節(jié)點(diǎn)發(fā)起重新選舉
(d). 節(jié)點(diǎn)5收到節(jié)點(diǎn)6的OK消息，而節(jié)點(diǎn)6經(jīng)過超時時間后收不到更高序號節(jié)點(diǎn)的OK消息，則認(rèn)為自己是leader
(e). 節(jié)點(diǎn)6把自己成為leader的信息廣播到所有節(jié)點(diǎn)
回顧《分布式系統(tǒng)理論基礎(chǔ) - 一致性、2PC和3PC》就可以看到，Bully算法中有2PC的身影，都具有提議(propose)和收集反饋(vote)的過程。
在一致性算法Paxos、ZAB[2]、Raft[3]中，為提升決議效率均有節(jié)點(diǎn)充當(dāng)leader的角色。ZAB、Raft中描述了具體的leader選舉實(shí)現(xiàn)，與Bully算法類似ZAB中使用zxid標(biāo)識節(jié)點(diǎn)，具有最大zxid的節(jié)點(diǎn)表示其所具備的事務(wù)(transaction)最新、被選為leader。
多數(shù)派(quorum)
在網(wǎng)絡(luò)分化的場景下以上Bully算法會遇到一個問題，被分隔的節(jié)點(diǎn)都認(rèn)為自己具有最大的序號、將產(chǎn)生多個leader，這時候就需要引入多數(shù)派(quorum)[4]。多數(shù)派的思路在分布式系統(tǒng)中很常見，其確保網(wǎng)絡(luò)分化情況下決議唯一。
多數(shù)派的原理說起來很簡單，假如節(jié)點(diǎn)總數(shù)為2f+1，則一項(xiàng)決議得到多于 f 節(jié)點(diǎn)贊成則獲得通過。leader選舉中，網(wǎng)絡(luò)分化場景下只有具備多數(shù)派節(jié)點(diǎn)的部分才可能選出leader，這避免了多l(xiāng)eader的產(chǎn)生。
多數(shù)派的思路還被應(yīng)用于副本(replica)管理，根據(jù)業(yè)務(wù)實(shí)際讀寫比例調(diào)整寫副本數(shù)Vw、讀副本數(shù)Vr，用以在可靠性和性能方面取得平衡[5]。
租約(lease)
選舉中很重要的一個問題，以上尚未提到：怎么判斷l(xiāng)eader不可用、什么時候應(yīng)該發(fā)起重新選舉？最先可能想到會通過心跳(heart beat)判別leader狀態(tài)是否正常，但在網(wǎng)絡(luò)擁塞或瞬斷的情況下，這容易導(dǎo)致出現(xiàn)雙主。
租約(lease)是解決該問題的常用方法，其最初提出時用于解決分布式緩存一致性問題[6]，后面在分布式鎖[7]等很多方面都有應(yīng)用。
租約的原理同樣不復(fù)雜，中心思想是每次租約時長內(nèi)只有一個節(jié)點(diǎn)獲得租約、到期后必須重新頒發(fā)租約。假設(shè)我們有租約頒發(fā)節(jié)點(diǎn)Z，節(jié)點(diǎn)0、1和2競選leader，租約過程如下：
(a). 節(jié)點(diǎn)0、1、2在Z上注冊自己，Z根據(jù)一定的規(guī)則(例如先到先得)頒發(fā)租約給節(jié)點(diǎn)，該租約同時對應(yīng)一個有效時長；這里假設(shè)節(jié)點(diǎn)0獲得租約、成為leader
(b). leader宕機(jī)時，只有租約到期(timeout)后才重新發(fā)起選舉，這里節(jié)點(diǎn)1獲得租約、成為leader
租約機(jī)制確保了一個時刻最多只有一個leader，避免只使用心跳機(jī)制產(chǎn)生雙主的問題。在實(shí)踐應(yīng)用中，zookeeper、ectd可用于租約頒發(fā)。
小結(jié)
在分布式系統(tǒng)理論和實(shí)踐中，常見leader、quorum和lease的身影。分布式系統(tǒng)內(nèi)不一定事事協(xié)商、事事民主，leader的存在有助于提升決議效率。
本文以leader選舉作為例子引入和講述quorum、lease，當(dāng)然quorum和lease是兩種思想，并不限于leader選舉應(yīng)用。
最后提一個有趣的問題與大家思考，leader選舉的本質(zhì)是一致性問題，Paxos、Raft和ZAB等解決一致性問題的協(xié)議和算法本身又需要或依賴于leader，怎么理解這個看似“蛋生雞、雞生蛋”的問題？[8]
[1] Elections in a Distributed Computing System, Hector Garcia-Molina, 1982
[2] ZooKeeper’s atomic broadcast protocol: Theory and practice, Andre Medeiros, 2012
[3] In Search of an Understandable Consensus Algorithm, Diego Ongaro and John Ousterhout, 2013
[4] A quorum-based commit protocol, Dale Skeen, 1982
[5] Weighted Voting for Replicated Data, David K. Gifford, 1979
[6] Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency, Cary G. Gray and David R. Cheriton, 1989
[7] The Chubby lock service for loosely-coupled distributed systems, Mike Burrows, 2006
[8] Why is Paxos leader election not done using Paxos?