本文來自王卓的投稿，老劉做了修改。

王卓是北京郵電大學碩士，研究方向為區(qū)塊鏈技術(shù)、共識算法及零知識證明，對區(qū)塊鏈技術(shù)底層有較深的理解。

張大胖的部門連續(xù)加班三個月，系統(tǒng)終于上線了!

經(jīng)理打算組織一次部門聚餐， 犒勞一下大家。至于去哪家飯店，就留給大家來討論了。

沒想到的是，這一伙人爭得不可開交，誰都說不過誰，其中，爭吵得最兇的是張大胖和劉瘦子，張大胖想去吃火鍋， 劉瘦子想去吃燒烤， 剩下三個員工是墻頭草， 也不知道聽誰的。

經(jīng)理看到這一群不省油的燈，突然想到一個辦法，說到：“別吵了!咱們都是寫程序的，用一個算法來解決這個問題吧。”

大家聽到算法，一下子就來了興致：“什么算法?”

“就是大名鼎鼎的Paxos啊，它有點兒復(fù)雜，大家正好學習一下。 這次咱們要出去聚餐，但是張大胖和劉瘦子的意見不統(tǒng)一，我們最終還是要選一家，這叫達成共識。這個共識啊只要有超過半數(shù)的人同意就可以了。”

“在開始之前，我先說幾個要求， 咱們的目的是一起去吃飯，所以張大胖你不能給小A說去吃火鍋，給小B說去吃燒烤，又給小C說去吃料理。你這樣來回搗亂我可要罰你工資了!”

張大胖嘿嘿笑著同意。

“還有你，劉瘦子，如果小A，小B或者小C已經(jīng)有人同意張大胖的意見了，你就別墨跡，別再堅持你的意見，跟著去吃就好了。”

劉瘦子也點頭。

“***小A，小B，小C你們仨，你們同意了一個人的提議就別來回當墻頭草，確定吃哪個飯店就不要改啦!”

張大胖他們五個人聽到經(jīng)理講了這些要求，默默記在心里。

經(jīng)理接著說：“具體的算法也不難，就兩個階段：

1.給自己拉票階段，這一階段的目的是爭奪“發(fā)言權(quán)”，只有多數(shù)人同意聽你“發(fā)言”，才能進入下一階段

2.確認階段：確定去那個飯店吃飯。

經(jīng)理一邊說，一邊給出了算法具體的步驟，張大胖劉瘦子一看，很簡單啊!迫不及待地就開始玩起來了。

經(jīng)理心里偷偷地笑了：簡單!哼!等玩起來了夠你倆折騰的!

***次游戲

1.拉票階段

張大胖人比較聰明，看到小A、小B、小C這三個家伙頭發(fā)亂糟糟的，以及標配的格子襯衫，一想就知道還沒有女朋友。

為了讓這三個人聽自己的，張大胖想出來一個點子：聽我的提議，我給你們每人介紹一位女生!

小A，小B聽到了，非常高興，張大哥解決單身問題，聽張大哥的!

與此同時，他倆在小本子上記下：介紹一位女生， 我可以同意飯店提議!

張大胖樂了，自己這么輕松已經(jīng)取得3個人的支持，小A, 小B加上我自己(我自己不會人格分裂反對我自己)， 已經(jīng)是多數(shù)派了，不管小C是否同意， 我都有了發(fā)言權(quán)了。

 

2.確定飯店

張大胖給小A, 小B說， 我給你們介紹一位女生，去吃火鍋!

小A, 小B 都表示同意，在小本子上記下： 介紹一位女生，去吃火鍋。

 

張大胖收到結(jié)果，知道自己的Paxos算法已經(jīng)執(zhí)行完畢， 高興地宣布：“行了,我們已經(jīng)達成了共識，可以去吃火鍋了! ”

第二次游戲

劉瘦子傻眼了：“張大胖你這家伙下手太快了，你這樣搞，一點意思都沒有啊， 不行，我們再玩一次!”

張大胖說：“沒問題， 我還怕你不成?”

話雖這么說，他趕緊和小A，小B,小C聯(lián)系：給你們介紹一位女生，要支持我啊。

小A, 小B表示同意，在本子上記下：介紹一位女生， 我可以飯店提議!

結(jié)果小C說了句，張大胖，你不實在哈，劉瘦子說給我介紹倆女生呢!

原來小C由于已經(jīng)聽了劉瘦子的話了，本子記得是：介紹兩位女生，我可以同意飯店提議!

 

張大胖心說，這劉瘦子也不笨嘛，也知道用這種方式來拉攏人。

不過既然有小A、小B答應(yīng)自己，，張大胖知道自己有了多數(shù)派的同意!

自己趕快給他們說去哪吃就行，別讓這幾個墻頭草跑了! 然后哼著小曲兒去找女生聯(lián)系方式了。

找到聯(lián)系方式以后，張大胖進入第二階段，準備徹底終結(jié)這次飯店之爭。

小A順利地同意了吃火鍋的提議， 記錄了下來：介紹一位女生，去吃火鍋。

沒想到的是，小B已經(jīng)反水了： 張大胖，你不實在哈，劉瘦子說給我介紹倆女生呢!

 

張大胖心想，真是墻頭草，看來只好從***階段的拉票重新開始了。

加大籌碼! 給他們每人介紹三位女生!果然，小B這兩個墻頭草再次反水，歡天喜地地支持自己了。

 

與此同時， 劉瘦子美滋滋地以為，自己用“介紹兩位女生”獲得了多數(shù)派的支持，可以進入第二階段，去確定飯店。

可是他和小B聯(lián)系的時候，悲催地發(fā)現(xiàn)，張大胖已經(jīng)提高了籌碼(3位女生)。 又把小B給拉走了!

劉瘦子趕緊查找通信錄，準備找出更多聯(lián)系方式，給他們介紹4位女生。

張大胖可沒有閑著，馬上進入第二階段，成功地確定了飯店。

 

至此，張大胖的Paxos算法執(zhí)行完畢，他知道大多數(shù)人已經(jīng)同意去吃火鍋了。

劉瘦子再次發(fā)起拉票，試圖重新占據(jù)優(yōu)勢，可是他發(fā)現(xiàn)小A和小B已經(jīng)接受了吃火鍋的提議。

他們說：“劉瘦子，我們很想答應(yīng)你，可是，我們已經(jīng)答應(yīng)吃火鍋的建議了，不能再變了，但是，為了表示對您的尊重，我們以后就認定確定吃火鍋是得給我們介紹4位女生。”

 

劉瘦子想到經(jīng)理之前定的規(guī)則：“如果已經(jīng)有人接受過了飯店的提議，不能再墨跡了，跟著去吃就行了!”

他嘆了口氣，進入了第二階段，確定飯店，不過他確定的也是“吃火鍋”

 

劉瘦子的Paxos算法也執(zhí)行完了， 最終達成了一致，去吃火鍋。

總結(jié)

我發(fā)現(xiàn)對于這個Basic Paxos算法，你要是理解了，會發(fā)現(xiàn)很簡單，但是想把腦子中的東西描述出來，卻很難，因為每個參與者的狀態(tài)都在不斷地變化中，細節(jié)太多，分支太多。

所以就通過這個小游戲講述了Basic Paxos算法，說實話，不太嚴謹，比如小A,小B,小C如果收到了帶著更多“賄賂”的Accept，雖然已經(jīng)確定了飯店，還是可以修改的，這一點在游戲中就沒提。

這個游戲展示了執(zhí)行過程遇到的典型情況。 完整的算法參見文章的***部分。

在Basic Paxos算法中，有兩個角色最為重要:

Proposer : 即張大胖和劉瘦子

Acceptor: 小A, 小B, 小C， 也包括張大胖和劉瘦子

一個人可以身兼多個角色。

游戲中的“介紹n位女生”，在Paxos算法中，就是一個數(shù)字n。

在Basic Paxos這個兩階段的協(xié)議中，Proposer 在***階段發(fā)送Prepare(n) 給其他人，試圖獲取“發(fā)言權(quán)”。 這里的prepare(n)就相當于“介紹n位女生”。

在第二階段發(fā)送Accept(n,v) 來試圖確定結(jié)果，這里的n 還是“介紹n位女生”，v是吃火鍋或者吃燒烤。

由于有多個Proposer可以發(fā)送Prepare(n) 。這時候Acceptor就需要根據(jù)n的大小來確定聽誰的。所以就會出現(xiàn)像小B這樣的墻頭草，來回搖擺。

Proposer在***階段得到大多數(shù)人支持以后，會進入第二階段，發(fā)出Accept(n,v) 的消息給其他人。

某個Acceptor，例如小B，收到了張大胖的Accept(3,火鍋)，已經(jīng)記錄下了吃火鍋， 這時候即使收到的消息中是prepare(4) ，數(shù)字更大也不行。他就告訴劉瘦子，我已經(jīng)確定選火鍋了。

這時候的關(guān)鍵點就是劉瘦子要跟隨，不要堅持自己的燒烤了。

一個有趣的問題

聰明的你估計已經(jīng)看出：如果張大胖和劉瘦子交替著爭奪發(fā)言權(quán)，例如：

張大胖介紹1位女生，爭取了小A, 小B

劉瘦子介紹2位女生，爭取了小B, 小C

張大胖介紹3位女生，又爭取了小A, 小B

劉瘦子介紹4位女生，又爭取了小B, 小C

……

這樣一來，無論是誰都無法進入第二階段，算法永遠無法完成。

一種解決辦法就是，可以讓他們開始新一輪爭取的時候，等待一個隨機的時間。讓其他人有機會去完成這個算法。

算法

貼一張詳細的算法，有興趣的可以仔細研究一下。

算法來自于：https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pptx 我覺得這個PPT講得還是比較好的。

 

 

 

【本文為51CTO專欄作者“劉欣”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號coderising獲取授權(quán)】

 

戳這里，看該作者更多好文