目錄

　　1.Paxos算法是什么？

　　2.團建主席的選舉過程

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

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

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

　　6.引申：Paxos算法專業名詞解釋

　　（1）Paxos算法是什么？

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

　　現在出去面試難度越來越大，尤其是一些知名的互聯網公司。因為這些互聯網公司的系統都會用到各種各樣的技術，比如上述所說的ZooKeeper。

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

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

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

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

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

　　（2）團建主席的選舉過程

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

　　這個團建的場景，以及團建主席這個角色大家應該很熟悉。

　　提示音：

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

　　此時肯定有人說，那還不簡單，找一個人作為投票負責人，先讓有興趣擔任團建主席的人自愿申請提名自己，然后大家分別對這些人進行投票，投票給誰都告訴那個投票負責人，由那個人統計各個候選人的票數，看哪個人的票數多最后就選擇誰當團建主席就可以了。

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

　　從Paxos算法的角度而言，它會覺得如果大家都依賴一個投票負責人來進行投票，那萬一投票負責人突然失聯了怎么辦？

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

　　提示音：

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

　　如下圖所示：

　　所以現在大家就換一個思路了，這25個人不要通過一個投票負責人的方式來投票選舉，而是互相之間發送短信，就通過互相發送短信的方式來選舉一個團建主席。

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

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

　　提示音：

　　引申到技術里，就是25臺機器不要找一個投票負責人，它們互相之間發送消息進行通信，來嘗試選舉出來一個團建主席。

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

　　那么那25個人到底怎么通過互相發送短信來選舉一個團建主席出來呢？

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

　　下圖展示了這個過程：

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

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

　　這個階段，每個團隊成員都會給每個隊長發送一條短信，而且是不停的發送短信，短信內容就是我申請跟你進行溝通。

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

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

　　但是這里要注意一點，隊長是會不斷的收到別人發過來的短信的，所以很可能他剛剛答應跟你溝通，結果立馬收到別人的短信，發現別人的短信更新，所以就同意跟別人進行溝通了，你的溝通權就會被取消。

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

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

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

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

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

　　這個時候成員發現3個隊長都回話說，就用你說的那個“張三”同學作為團建主席了，那就定了，此時團建主席就是這個“張三”了。

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

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

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

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

　　最后所有成員都會發現，最終的選舉結果，就是：張三。這是一個非常順利的投票階段。

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

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

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

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

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

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

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

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

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

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

　　（6）引申：Paxos算法專業名詞解釋

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

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

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

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