目錄

　　1.Paxos算法是什么？

　　2.團(tuán)建主席的選舉過程

　　3.Paxos第一階段：申請(qǐng)階段

　　4.Paxos第二階段：比較順利的投票階段

　　5.Paxos第二階段：如果投票不太順利呢？

　　6.引申：Paxos算法專業(yè)名詞解釋

　　（1）Paxos算法是什么？

　　Paxos算法是一個(gè)非常經(jīng)典的算法，在分布式系統(tǒng)中有非常廣泛的使用，比如在大名鼎鼎的ZooKeeper中就有很核心的使用。

　　現(xiàn)在出去面試難度越來越大，尤其是一些知名的互聯(lián)網(wǎng)公司。因?yàn)檫@些互聯(lián)網(wǎng)公司的系統(tǒng)都會(huì)用到各種各樣的技術(shù)，比如上述所說的ZooKeeper。

　　前幾年，一個(gè)候選人出去面試大廠的Java職位，可能就讓你說一下對(duì)ZooKeeper的原理的理解以及使用就可以了。

　　但是現(xiàn)在競爭越來越激烈，出去面試可能就會(huì)直接讓你說一個(gè)技術(shù)底層的核心算法實(shí)現(xiàn)，比如Paxos算法就是現(xiàn)在大廠越來越多會(huì)問到的一個(gè)問題。

　　但是像Paxos這類算法實(shí)在是非常的枯燥難懂，很多文章講這個(gè)都是用了一大堆的專業(yè)術(shù)語，還有很多的數(shù)學(xué)公式，而且里面很多概念都解釋不清楚。

　　而對(duì)于工程方向的技術(shù)人來說，對(duì)Paxos算法只要從一個(gè)高層次的角度，對(duì)他核心的思想理解就已經(jīng)可以了。

　　所以本文我們用比較通俗易懂的方式，從一個(gè)有趣的角度來描述一下Paxos算法的核心思想，幫助你在大廠面試中脫穎而出！

　　（2）團(tuán)建主席的選舉過程

　　假如現(xiàn)在一個(gè)公司的團(tuán)隊(duì)里有25個(gè)人，現(xiàn)在這25個(gè)人之間需要找一個(gè)人出來作為團(tuán)建主席，也就是專門負(fù)責(zé)這個(gè)團(tuán)隊(duì)團(tuán)建相關(guān)的組織事宜，比如組織大家出去旅游、出去吃喝玩樂。

　　這個(gè)團(tuán)建的場景，以及團(tuán)建主席這個(gè)角色大家應(yīng)該很熟悉。

　　提示音：

　　其實(shí)這個(gè)場景引申到技術(shù)里，就是非常典型的一個(gè)分布式系統(tǒng)選舉的場景。如果有25臺(tái)機(jī)器，這些機(jī)器之間要選舉出來某一臺(tái)機(jī)器來作為一個(gè)Leader角色的節(jié)點(diǎn)，負(fù)責(zé)對(duì)集群進(jìn)行整體上的管控，是不是就跟一個(gè)團(tuán)隊(duì)選舉一個(gè)團(tuán)建主席一個(gè)道理。

　　此時(shí)肯定有人說，那還不簡單，找一個(gè)人作為投票負(fù)責(zé)人，先讓有興趣擔(dān)任團(tuán)建主席的人自愿申請(qǐng)?zhí)崦约海缓蟠蠹曳謩e對(duì)這些人進(jìn)行投票，投票給誰都告訴那個(gè)投票負(fù)責(zé)人，由那個(gè)人統(tǒng)計(jì)各個(gè)候選人的票數(shù)，看哪個(gè)人的票數(shù)多最后就選擇誰當(dāng)團(tuán)建主席就可以了。

　　這個(gè)方案確實(shí)是沒問題的，但是Paxos算法是不認(rèn)可這種方式的。

　　從Paxos算法的角度而言，它會(huì)覺得如果大家都依賴一個(gè)投票負(fù)責(zé)人來進(jìn)行投票，那萬一投票負(fù)責(zé)人突然失聯(lián)了怎么辦？

　　比如家里有人生病了去醫(yī)院了，或者自己突然食物中毒去醫(yī)院了，那大家不就沒法選舉出來一個(gè)團(tuán)建主席了？

　　提示音：

　　引申到技術(shù)里，那就是25臺(tái)機(jī)器挑選了其中一臺(tái)機(jī)器作為投票選舉的負(fù)責(zé)人，專門收集大家的投票，然后票數(shù)排序，最后選擇出來一臺(tái)機(jī)器，那萬一那臺(tái)機(jī)器突然宕機(jī)了怎么辦？是不是會(huì)導(dǎo)致選舉失敗？所以Paxos算法是不接受這種方式的。

　　如下圖所示：

　　所以現(xiàn)在大家就換一個(gè)思路了，這25個(gè)人不要通過一個(gè)投票負(fù)責(zé)人的方式來投票選舉，而是互相之間發(fā)送短信，就通過互相發(fā)送短信的方式來選舉一個(gè)團(tuán)建主席。

　　這個(gè)好處在于哪怕25個(gè)人里有12個(gè)人都因?yàn)楣ぷ髅Α⒃陂_會(huì)、孩子生病了，然后沒法通過短信的方式參與投票，但是剩余的13個(gè)人還是有超過半數(shù)的人在這里，他們就可以完成最終的投票。

　　這樣投票的過程就不用依賴于某個(gè)人了，哪怕將近一半的人都失聯(lián)了，還是可以選舉出來這個(gè)團(tuán)建主席。

　　提示音：

　　引申到技術(shù)里，就是25臺(tái)機(jī)器不要找一個(gè)投票負(fù)責(zé)人，它們互相之間發(fā)送消息進(jìn)行通信，來嘗試選舉出來一個(gè)團(tuán)建主席。

　　這樣哪怕有12臺(tái)機(jī)器都故障宕機(jī)了，但是剩余的已經(jīng)過半數(shù)的13臺(tái)機(jī)器還是能選舉出來一個(gè)團(tuán)建主席的，對(duì)系統(tǒng)容錯(cuò)性就有了大大的提升。

　　那么那25個(gè)人到底怎么通過互相發(fā)送短信來選舉一個(gè)團(tuán)建主席出來呢？

　　首先這25個(gè)人里，需要找出來其中5個(gè)人作為選舉隊(duì)長，這5個(gè)人負(fù)責(zé)跟所有人收發(fā)短信確定團(tuán)建主席的人選，然后假設(shè)有3個(gè)候選人是要提名作為團(tuán)建主席。

　　下圖展示了這個(gè)過程：

　　（3）Paxos第一階段：申請(qǐng)階段

　　首先，除了那5個(gè)隊(duì)長以外，所有人都需要在第一個(gè)階段嘗試申請(qǐng)跟投票隊(duì)長進(jìn)行溝通。

　　這個(gè)階段，每個(gè)團(tuán)隊(duì)成員都會(huì)給每個(gè)隊(duì)長發(fā)送一條短信，而且是不停的發(fā)送短信，短信內(nèi)容就是我申請(qǐng)跟你進(jìn)行溝通。

　　而每個(gè)隊(duì)長也會(huì)不停收到每個(gè)成員發(fā)送過來的短信，對(duì)于隊(duì)長來說，拿到短信就根據(jù)時(shí)間戳判斷，如果一個(gè)人發(fā)送過來的短信是最新的，那么就回話說我同意跟你進(jìn)行溝通。

　　如果一個(gè)成員收到超過半數(shù)（這里就是3個(gè)）的隊(duì)長的回信說同意溝通，那么就可以告訴那些同意溝通的隊(duì)長，自己想要投票給誰。

　　但是這里要注意一點(diǎn)，隊(duì)長是會(huì)不斷的收到別人發(fā)過來的短信的，所以很可能他剛剛答應(yīng)跟你溝通，結(jié)果立馬收到別人的短信，發(fā)現(xiàn)別人的短信更新，所以就同意跟別人進(jìn)行溝通了，你的溝通權(quán)就會(huì)被取消。

　　所以如果一個(gè)成員狂發(fā)短信的過程中，突然發(fā)現(xiàn)自己被超過半數(shù)的隊(duì)長同意溝通了，別著急高興。

　　這個(gè)成員需要趕緊繼續(xù)下一個(gè)階段，告訴那些隊(duì)長自己想要投票的候選人，要是發(fā)晚了，人家隊(duì)長可能就在跟別人溝通了，不會(huì)理你了！

　　（4）Paxos第二階段：一個(gè)比較順利的投票階段

　　這個(gè)時(shí)候一個(gè)成員獲得了跟半數(shù)以上隊(duì)長的溝通資格，然后就可以發(fā)送一條短信過去，說自己想要選舉的人是三個(gè)候選人里的誰，這個(gè)人選可能就是成員自己拍腦袋決定的，隨機(jī)選擇的一個(gè)候選人而已。

　　這時(shí)大家考慮一下，如果3個(gè)隊(duì)長都沒有收到其他成員發(fā)過來的更新的申請(qǐng)短信，都保持著跟這個(gè)成員的溝通，那么3個(gè)隊(duì)長收到他發(fā)過來的投票，比如說選舉“張三”當(dāng)做團(tuán)建主席，那就直接通過了！

　　這個(gè)時(shí)候成員發(fā)現(xiàn)3個(gè)隊(duì)長都回話說，就用你說的那個(gè)“張三”同學(xué)作為團(tuán)建主席了，那就定了，此時(shí)團(tuán)建主席就是這個(gè)“張三”了。

　　后續(xù)其他成員發(fā)申請(qǐng)短信給隊(duì)長的時(shí)候，如果它們跟那三個(gè)隊(duì)長獲得溝通權(quán)，三個(gè)隊(duì)長都會(huì)回復(fù)短信說，就是“張三”了，已經(jīng)選舉出來了。

　　這個(gè)時(shí)候，其他成員都會(huì)直接遵守這個(gè)選舉結(jié)果，就認(rèn)為是“張三”了。

　　另一種情況，此時(shí)要是某個(gè)其他成員跟1個(gè)知道“張三”投票結(jié)果的隊(duì)長溝通，然而它跟另外2個(gè)知道“張三”投票結(jié)果的隊(duì)長沒建立上溝通，卻跟剩下的2個(gè)還不知道“張三”投票結(jié)果的隊(duì)長溝通，這個(gè)成員因?yàn)楦兄搅似渲?個(gè)隊(duì)長已經(jīng)選擇了“張三”，此時(shí)他就會(huì)嘗試說，我就投票給“張三”了，通知另外2個(gè)還在茫然中的隊(duì)長是“張三”。

　　此時(shí)另外兩個(gè)茫然的隊(duì)長也會(huì)選擇接受“張三”的投票結(jié)果，最后5個(gè)隊(duì)長都會(huì)接收“張三”這個(gè)投票結(jié)果，然后所有成員在跟隊(duì)長溝通的過程中，也必然會(huì)全部接收到“張三”這個(gè)投票結(jié)果。

　　最后所有成員都會(huì)發(fā)現(xiàn)，最終的選舉結(jié)果，就是：張三。這是一個(gè)非常順利的投票階段。

　　（5）Paxos第二階段：如果投票不太順利呢？

　　那么來復(fù)盤一下上面的情況，萬一要是投票的過程不太順利呢？

　　比如一個(gè)成員好不容易獲取了跟三個(gè)隊(duì)長的溝通資格，結(jié)果發(fā)送投票請(qǐng)求過去的時(shí)候，其中一個(gè)隊(duì)長已經(jīng)跟別人建立了溝通，此時(shí)就不會(huì)理睬你的投票。

　　那可能就只有2個(gè)隊(duì)長接收了你的“張三”的投票，但是沒到3個(gè)隊(duì)長就不能確定選擇“張三”。

　　這個(gè)時(shí)候怎么辦？可能在這種混亂的情況下，比如5個(gè)隊(duì)長里，其中2個(gè)隊(duì)長接收到的投票是“張三”，1個(gè)隊(duì)長是“李四”，2個(gè)隊(duì)長是“王五”，沒法確定選舉結(jié)果。

　　然后所有成員繼續(xù)持續(xù)不斷的重復(fù)上述步驟，跟隊(duì)長申請(qǐng)溝通，然后再嘗試投票。

　　假如一個(gè)成員跟3個(gè)隊(duì)長建立了溝通，其中2個(gè)隊(duì)長告訴他自己已經(jīng)接收到“張三”投票了，1個(gè)隊(duì)長告訴他自己已經(jīng)接收到“李四”投票了，那么這個(gè)成員會(huì)看哪個(gè)投票是最新的，比如說“李四”那個(gè)投票是最新的，那么他就會(huì)說，我就投“李四”了。

　　此時(shí)那2個(gè)接收到“張三”投票的隊(duì)長就會(huì)改變自己的選票為“李四”，然后就會(huì)出現(xiàn)3個(gè)隊(duì)長都接受了“李四”這個(gè)投票。

　　如果另外一個(gè)成員跟1個(gè)接收“李四”投票的隊(duì)長以及2個(gè)接收“王五”投票的隊(duì)長建立了溝通，會(huì)發(fā)現(xiàn)“李四“是最新選出來的，此時(shí)他會(huì)說，我就投給“李四”了。

　　然后那2個(gè)接收“王五”投票的隊(duì)長，也會(huì)接收“李四”的投票。以此類推，大家開一下自己的腦洞，這個(gè)過程可能會(huì)持續(xù)很長時(shí)間，直到最后，所有隊(duì)長都接受了“李四”的投票，所有成員也會(huì)接收“李四”的投票。

　　（6）引申：Paxos算法專業(yè)名詞解釋

　　其實(shí)上述過程已經(jīng)用一個(gè)簡單的投票選舉團(tuán)建主席的例子給簡化的非常通俗了，雖然還是有點(diǎn)燒腦，但是建議大家多看幾遍，肯定照著思路能大致想明白Paxos算法的一個(gè)思路。

　　他有兩個(gè)要點(diǎn)：一個(gè)是超過半數(shù)的運(yùn)用，一個(gè)是只用最新的投票。

　　Paxos算法里，對(duì)一堆機(jī)器中扮演隊(duì)長角色的機(jī)器叫做“Acceptor”，對(duì)于普通成員的角色叫做“Proposer”，互相發(fā)短信其實(shí)就是發(fā)消息進(jìn)行通信，短信的時(shí)間戳就是“epoch”。

　　大家把上述的過程換成機(jī)器之間的通信以及選舉，就能清楚這個(gè)過程了。