建站
咨詢
售后
建站咨詢
新聞中心
本文來自王卓的投稿，老劉做了修改。
王卓是北京郵電大學(xué)碩士，研究方向?yàn)閰^(qū)塊鏈技術(shù)、共識(shí)算法及零知識(shí)證明，對(duì)區(qū)塊鏈技術(shù)底層有較深的理解。
張大胖的部門連續(xù)加班三個(gè)月，系統(tǒng)終于上線了!
經(jīng)理打算組織一次部門聚餐， 犒勞一下大家。至于去哪家飯店，就留給大家來討論了。
沒想到的是，這一伙人爭(zhēng)得不可開交，誰都說不過誰，其中，爭(zhēng)吵得最兇的是張大胖和劉瘦子，張大胖想去吃火鍋， 劉瘦子想去吃燒烤， 剩下三個(gè)員工是墻頭草， 也不知道聽誰的。
經(jīng)理看到這一群不省油的燈，突然想到一個(gè)辦法，說到：“別吵了!咱們都是寫程序的，用一個(gè)算法來解決這個(gè)問題吧?！?/p>
大家聽到算法，一下子就來了興致：“什么算法?”
“就是大名鼎鼎的Paxos啊，它有點(diǎn)兒復(fù)雜，大家正好學(xué)習(xí)一下。 這次咱們要出去聚餐，但是張大胖和劉瘦子的意見不統(tǒng)一，我們最終還是要選一家，這叫達(dá)成共識(shí)。這個(gè)共識(shí)啊只要有超過半數(shù)的人同意就可以了?！?/p>
“在開始之前，我先說幾個(gè)要求， 咱們的目的是一起去吃飯，所以張大胖你不能給小A說去吃火鍋，給小B說去吃燒烤，又給小C說去吃料理。你這樣來回?fù)v亂我可要罰你工資了!”
張大胖嘿嘿笑著同意。
“還有你，劉瘦子，如果小A，小B或者小C已經(jīng)有人同意張大胖的意見了，你就別墨跡，別再堅(jiān)持你的意見，跟著去吃就好了?！?/p>
劉瘦子也點(diǎn)頭。
“***小A，小B，小C你們仨，你們同意了一個(gè)人的提議就別來回當(dāng)墻頭草，確定吃哪個(gè)飯店就不要改啦!”
張大胖他們五個(gè)人聽到經(jīng)理講了這些要求，默默記在心里。
經(jīng)理接著說：“具體的算法也不難，就兩個(gè)階段：
1.給自己拉票階段，這一階段的目的是爭(zhēng)奪“發(fā)言權(quán)”，只有多數(shù)人同意聽你“發(fā)言”，才能進(jìn)入下一階段
2.確認(rèn)階段：確定去那個(gè)飯店吃飯。
經(jīng)理一邊說，一邊給出了算法具體的步驟，張大胖劉瘦子一看，很簡(jiǎn)單啊!迫不及待地就開始玩起來了。
經(jīng)理心里偷偷地笑了：簡(jiǎn)單!哼!等玩起來了夠你倆折騰的!
***次游戲
1.拉票階段
張大胖人比較聰明，看到小A、小B、小C這三個(gè)家伙頭發(fā)亂糟糟的，以及標(biāo)配的格子襯衫，一想就知道還沒有女朋友。
為了讓這三個(gè)人聽自己的，張大胖想出來一個(gè)點(diǎn)子：聽我的提議，我給你們每人介紹一位女生!
小A，小B聽到了，非常高興，張大哥解決單身問題，聽張大哥的!
與此同時(shí)，他倆在小本子上記下：介紹一位女生， 我可以同意飯店提議!
張大胖樂了，自己這么輕松已經(jīng)取得3個(gè)人的支持，小A, 小B加上我自己(我自己不會(huì)人格分裂反對(duì)我自己)， 已經(jīng)是多數(shù)派了，不管小C是否同意， 我都有了發(fā)言權(quán)了。
2.確定飯店
張大胖給小A, 小B說， 我給你們介紹一位女生，去吃火鍋!
小A, 小B 都表示同意，在小本子上記下： 介紹一位女生，去吃火鍋。
張大胖收到結(jié)果，知道自己的Paxos算法已經(jīng)執(zhí)行完畢， 高興地宣布：“行了,我們已經(jīng)達(dá)成了共識(shí)，可以去吃火鍋了! ”
第二次游戲
劉瘦子傻眼了：“張大胖你這家伙下手太快了，你這樣搞，一點(diǎn)意思都沒有啊， 不行，我們?cè)偻嬉淮?”
張大胖說：“沒問題， 我還怕你不成?”
話雖這么說，他趕緊和小A，小B,小C聯(lián)系：給你們介紹一位女生，要支持我啊。
小A, 小B表示同意，在本子上記下：介紹一位女生， 我可以飯店提議!
結(jié)果小C說了句，張大胖，你不實(shí)在哈，劉瘦子說給我介紹倆女生呢!
原來小C由于已經(jīng)聽了劉瘦子的話了，本子記得是：介紹兩位女生，我可以同意飯店提議!
張大胖心說，這劉瘦子也不笨嘛，也知道用這種方式來拉攏人。
不過既然有小A、小B答應(yīng)自己，，張大胖知道自己有了多數(shù)派的同意!
自己趕快給他們說去哪吃就行，別讓這幾個(gè)墻頭草跑了! 然后哼著小曲兒去找女生聯(lián)系方式了。
找到聯(lián)系方式以后，張大胖進(jìn)入第二階段，準(zhǔn)備徹底終結(jié)這次飯店之爭(zhēng)。
小A順利地同意了吃火鍋的提議， 記錄了下來：介紹一位女生，去吃火鍋。
沒想到的是，小B已經(jīng)反水了： 張大胖，你不實(shí)在哈，劉瘦子說給我介紹倆女生呢!
張大胖心想，真是墻頭草，看來只好從***階段的拉票重新開始了。
加大籌碼! 給他們每人介紹三位女生!果然，小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)接受了吃火鍋的提議。
他們說：“劉瘦子，我們很想答應(yīng)你，可是，我們已經(jīng)答應(yīng)吃火鍋的建議了，不能再變了，但是，為了表示對(duì)您的尊重，我們以后就認(rèn)定確定吃火鍋是得給我們介紹4位女生?！?/p>
劉瘦子想到經(jīng)理之前定的規(guī)則：“如果已經(jīng)有人接受過了飯店的提議，不能再墨跡了，跟著去吃就行了!”
他嘆了口氣，進(jìn)入了第二階段，確定飯店，不過他確定的也是“吃火鍋”
劉瘦子的Paxos算法也執(zhí)行完了， 最終達(dá)成了一致，去吃火鍋。
總結(jié)
我發(fā)現(xiàn)對(duì)于這個(gè)Basic Paxos算法，你要是理解了，會(huì)發(fā)現(xiàn)很簡(jiǎn)單，但是想把腦子中的東西描述出來，卻很難，因?yàn)槊總€(gè)參與者的狀態(tài)都在不斷地變化中，細(xì)節(jié)太多，分支太多。
所以就通過這個(gè)小游戲講述了Basic Paxos算法，說實(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) 來試圖確定結(jié)果，這里的n 還是“介紹n位女生”，v是吃火鍋或者吃燒烤。
由于有多個(gè)Proposer可以發(fā)送Prepare(n) 。這時(shí)候Acceptor就需要根據(jù)n的大小來確定聽誰的。所以就會(huì)出現(xiàn)像小B這樣的墻頭草，來回?fù)u擺。
Proposer在***階段得到大多數(shù)人支持以后，會(huì)進(jìn)入第二階段，發(fā)出Accept(n,v) 的消息給其他人。
某個(gè)Acceptor，例如小B，收到了張大胖的Accept(3,火鍋)，已經(jīng)記錄下了吃火鍋， 這時(shí)候即使收到的消息中是prepare(4) ，數(shù)字更大也不行。他就告訴劉瘦子，我已經(jīng)確定選火鍋了。
這時(shí)候的關(guān)鍵點(diǎn)就是劉瘦子要跟隨，不要堅(jiān)持自己的燒烤了。
一個(gè)有趣的問題
聰明的你估計(jì)已經(jīng)看出：如果張大胖和劉瘦子交替著爭(zhēng)奪發(fā)言權(quán)，例如：
張大胖介紹1位女生，爭(zhēng)取了小A, 小B
劉瘦子介紹2位女生，爭(zhēng)取了小B, 小C
張大胖介紹3位女生，又爭(zhēng)取了小A, 小B
劉瘦子介紹4位女生，又爭(zhēng)取了小B, 小C
……
這樣一來，無論是誰都無法進(jìn)入第二階段，算法永遠(yuǎn)無法完成。
一種解決辦法就是，可以讓他們開始新一輪爭(zhēng)取的時(shí)候，等待一個(gè)隨機(jī)的時(shí)間。讓其他人有機(jī)會(huì)去完成這個(gè)算法。
算法
貼一張?jiān)敿?xì)的算法，有興趣的可以仔細(xì)研究一下。
算法來自于：https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pptx 我覺得這個(gè)PPT講得還是比較好的。
【本文為專欄作者“劉欣”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過作者微信公眾號(hào)coderising獲取授權(quán)】
當(dāng)前文章：碼農(nóng)們的聚餐，會(huì)復(fù)雜到什么程度？
文章位置：http://www.dlmjj.cn/article/cdeodjs.html
