目錄

　　1.Paxos算法是什么？

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

　　3.Paxos第一階段：申請階段

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

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

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

　?。?）Paxos算法是什么？

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

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

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

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

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

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

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

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

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

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

　　提示音：

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

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

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

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

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

　　提示音：

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

　　如下圖所示：

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

　　這個好處在于哪怕25個人里有12個人都因為工作忙、在開會、孩子生病了，然后沒法通過短信的方式參與投票，但是剩余的13個人還是有超過半數(shù)的人在這里，他們就可以完成最終的投票。

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

　　提示音：

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

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

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

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

　　下圖展示了這個過程：

　　（3）Paxos第一階段：申請階段

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

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

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

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

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

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

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

　?。?）Paxos第二階段：一個比較順利的投票階段

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

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

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

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

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

　　另一種情況，此時要是某個其他成員跟1個知道“張三”投票結(jié)果的隊長溝通，然而它跟另外2個知道“張三”投票結(jié)果的隊長沒建立上溝通，卻跟剩下的2個還不知道“張三”投票結(jié)果的隊長溝通，這個成員因為感知到了其中1個隊長已經(jīng)選擇了“張三”，此時他就會嘗試說，我就投票給“張三”了，通知另外2個還在茫然中的隊長是“張三”。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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