碼農(nóng)們的聚餐，會(huì)復(fù)雜到什么程度？

作者：王卓 2019-04-01 11:05:24

張大胖的部門連續(xù)加班三個(gè)月，系統(tǒng)終于上線了!經(jīng)理打算組織一次部門聚餐，犒勞一下大家。至于去哪家飯店，就留給大家來(lái)討論了。

本文來(lái)自王卓的投稿，老劉做了修改。

王卓是北京郵電大學(xué)碩士，研究方向?yàn)閰^(qū)塊鏈技術(shù)、共識(shí)算法及零知識(shí)證明，對(duì)區(qū)塊鏈技術(shù)底層有較深的理解。

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

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

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

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

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

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

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

張大胖嘿嘿笑著同意。

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

劉瘦子也點(diǎn)頭。

“***小A，小B，小C你們仨，你們同意了一個(gè)人的提議就別來(lái)回當(dāng)墻頭草，確定吃哪個(gè)飯店就不要改啦!”

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

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

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

2.確認(rèn)階段：確定去那個(gè)飯店吃飯。

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

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

***次游戲

1.拉票階段

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

為了讓這三個(gè)人聽自己的，張大胖想出來(lái)一個(gè)點(diǎn)子：聽我的提議，我給你們每人介紹一位女生!

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

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

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

2.確定飯店

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

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

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

第二次游戲

劉瘦子傻眼了：“張大胖你這家伙下手太快了，你這樣搞，一點(diǎn)意思都沒有啊，不行，我們?cè)偻嬉淮?”

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

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

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

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

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

張大胖心說(shuō)，這劉瘦子也不笨嘛，也知道用這種方式來(lái)拉攏人。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

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

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

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

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

Proposer : 即張大胖和劉瘦子

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

一個(gè)人可以身兼多個(gè)角色。

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

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

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

由于有多個(gè)Proposer可以發(fā)送Prepare(n) 。這時(shí)候Acceptor就需要根據(jù)n的大小來(lái)確定聽誰(shuí)的。所以就會(huì)出現(xiàn)像小B這樣的墻頭草，來(lái)回?fù)u擺。

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

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