碼農們的聚餐，會複雜到什麼程度？

作者丨王卓

責編 | 仲培藝

本文經授權轉載自碼農翻身（ ID：coderising）

張大胖的部門連續加班三個月，系統終於上線了！

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

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

經理看到這一群不省油的燈，突然想到一個辦法，說道：「別吵了！咱們都是寫程序的，用一個演算法來解決這個問題吧。」

大家聽到演算法，一下子就來了興緻：「什麼演算法？」

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

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

張大胖嘿嘿笑著同意。

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

劉瘦子也點頭。

「最後小 A、小 B、小 C 你們仨，同意了一個人的提議就別來回當牆頭草，確定吃哪個飯店就不要改啦！」

張大胖他們五個人聽到經理講了這些要求，默默記在心裡。

經理接著說：「具體的演算法也不難，就兩個階段：

1. 給自己拉票階段，這一階段的目的是爭奪「發言權」，只有多數人同意聽你「發言」，才能進入下一階段；

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

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

經理心裡偷偷地笑了：簡單！哼！等玩起來了夠你倆折騰的！

第一次遊戲

拉票階段

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

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

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

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

張大胖樂了，自己這麼輕鬆已經取得 3 個人的支持，小 A、小 B 加上自己（我自己不會人格分裂反對我自己）， 已經是多數派了，不管小 C 是否同意， 我都有了發言權了。

確定飯店

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

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

張大胖收到結果，知道自己的 Paxos 演算法已經執行完畢， 高興地宣布：「行了，我們已經達成了共識，可以去吃火鍋了! 」

第二次遊戲

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

張大胖說：「沒問題， 我還怕你不成？」

話雖這麼說，他趕緊和小 A、小 B、小 C 聯繫：給你們介紹一位女生，要支持我啊。

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

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

原來小 C 由於已經聽了劉瘦子的話了，本子記得是：介紹兩位女生，我可以同意飯店提議！

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

不過既然有小 A、小 B 答應自己，張大胖知道自己有了多數派的同意！

自己趕快給他們說去哪吃就行，別讓這幾個牆頭草跑了！然後哼著小曲兒去找女生聯繫方式了。

找到聯繫方式以後，張大胖進入第二階段，準備徹底終結這次飯店之爭。

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

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

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

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

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

可是他和小 B 聯繫的時候，悲催地發現，張大胖已經提高了籌碼（3 位女生）。又把小 B 給拉走了！

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

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

至此，張大胖的 Paxos 演算法執行完畢，他知道大多數人已經同意去吃火鍋了。

劉瘦子再次發起拉票，試圖重新佔據優勢，可是他發現小 A 和小 B 已經接受了吃火鍋的提議。

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

劉瘦子想到經理之前定的規則：「如果已經有人接受過了飯店的提議，不能再墨跡了，跟著去吃就行了！」

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

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

總結

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

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

這個遊戲展示了執行過程遇到的典型情況。 完整的演算法參見文章的最後部分。

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

• Proposer：即張大胖和劉瘦子
• Acceptor：小 A、小 B、小 C， 也包括張大胖和劉瘦子

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

遊戲中的「介紹 n 位女生」，在 Paxos 演算法中，就是一個數字 n。

在 Basic Paxos 這個兩階段的協議中，Proposer 在第一階段發送 Prepare(n) 給其他人，試圖獲取「發言權」。 這裡的 Prepare(n) 就相當於「介紹 n 位女生」。

在第二階段發送 Accept(n,v) 來試圖確定結果，這裡的 n 還是「介紹n位女生」，v 是吃火鍋或者吃燒烤。

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

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

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

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

一個有趣的問題

聰明的你估計已經看出：如果張大胖和劉瘦子交替著爭奪發言權，例如：

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

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

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

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

……

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

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

演算法

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

演算法來自於：https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pptx

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

聲明：本文經授權轉載自碼農翻身，如需轉載請聯繫原作者。

【END】

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！