淺顯易懂地解讀Paxos演算法

什麼是Paxos演算法？

Paxos演算法是分散式技術大師Lamport提出的。

（世外高人的即視感，有木有？）

這個演算法的主要目的是：讓參與分散式處理的每個參與者逐步達成一致意見。用好理解的方式來說，就是在一個選舉過程中，讓不同的選民最終做出一致的決定。

Lamport為了講述這個演算法，假想了一個叫做Paxos的希臘城邦進行選舉的情景，這個演算法也是因此而得名。在他的假想中，這個城邦要採用民主提議和投票的方式選出一個最終的決議，但由於城邦的居民沒有人願意把全部時間和精力放在這種事情上，所以他們只能不定時的來參加提議，不定時來了解提議、投票進展，不定時的表達自己的投票意見。Paxos演算法的目標就是讓他們按照少數服從多數的方式，最終達成一致意見。

這樣做的意義何在呢？

如果你了解分散式系統，那就比較好理解上面做法的意義了。如果你不了解也沒關係，用最簡單的方式解釋：以前都是一台伺服器幹活，但是後來發現一台伺服器壞了，乾的活就要停下來。於是，聰明人發明了多台伺服器同時幹活的方案。但這個方案有個問題，多台伺服器同時提出下一步幹什麼事情時，最終聽誰的呢？這時，Paxos演算法橫空出世了，利用它，可以在這多台伺服器中間建立一種選舉機制，並通過這個機制最終讓所有伺服器對下一步動作達成一致意見。這樣，無論有多少台伺服器同時工作，都不會發生衝突啦～

下面開始介紹Paxos演算法的具體情況：

Paxos演算法其實很簡單，就是一個先提議再投票的過程。關鍵點包括：

1、演算法涉及的主要角色：

主要的角色就是「提議者」（向「接受者」提出提議）和「接受者」（收到「提議者」的提議後，向「提議者」表達自己的意見）。先有提議，再來表決，這個很好理解。（註：實際應用中，可以將一堆伺服器任意指定角色，一部分做「提議者」、一部分做「接受者」，也可以指定特定的伺服器做「提議者」，剩下的都是「接受者」。）

2、整個演算法的大致過程為：

第一階段：因為存在多個「提議者」，如果都提意見，那麼「接受者」接受誰的不接受誰的？太混亂了。所以，要先明確哪個「提議者」是意見領袖有權提出提議，未來，「接受者」們就主要處理這個「提議者」的提議了（這樣，也可以在提出提議時就盡量讓意見統一，謀求儘早形成多數派）。

第二階段：由上階段選出的意見領袖提出提議，「接受者」反饋意見。如果多數「接受者」接受了一個提議，那麼提議就通過了。

3、必須要了解的其他相關規則：

1）怎麼明確意見領袖呢？通過編號。每個「提議者」在第一階段先報個號，誰的號大，誰就是意見領袖。如果不好理解，可以想像為賄選。每個提議者先拿著鈔票賄賂一圈「接受者」，誰給的錢多，第二階段「接受者」就聽誰的。（註：這裡和下文提到的「意見領袖」，並不是一個新的角色，而是代表在那一輪賄賂成功的「提議者」。所以，請把意見領袖理解為賄賂中勝出的「提議者」即可）

2）有個跟選舉常識不一樣的地方，就是每個「提議者」不會執著於讓自己的提議通過，而是每個「提議者」會執著於讓提議儘快達成一致意見。所以，為了這個目標，如果「提議者」在賄選的時候，發現「接受者」已經接受過前面意見領袖的提議了，即便「提議者」賄選成功，也會默默的把自己的提議改為前面意見領袖的提議。所以一旦賄賂成功，勝出的「提議者」再提出提議，提議內容也是前面意見領袖的提議（這樣，在謀求儘早形成多數派的路上，又前進了一步）。

3）錢的多少很重要，如果錢少了，無論在第一還是第二階段「接受者」都不會尿你，直接拒絕。

4）上面2）中講到，如果「提議者」在賄選時，發現前面已經有意見領袖的提議，那就將自己的提議默默改成前面意見領袖的提議。這裡有一種情況，如果你是「提議者」，在賄賂的時候，「接受者1」跟你說「他見過的意見領袖的提議是方案1」，而「接受者2」跟你說「他見過的意見領袖提議是方案2」，你該怎麼辦？這時的原則也很簡單，還是：錢的多少很重要！你判斷一下是「接受者1」見過的意見領袖有錢，還是「接受者2」見過的意見領袖有錢？如何判斷呢？因為「接受者」在被「提議者」賄賂的時候，自己會記下賄賂的金額。所以當你賄賂「接受者」時，一旦你給的賄賂多而勝出，「接受者」會告訴你兩件事情：a.前任意見領袖的提議內容（如果有的話），b.前任意見領袖當時賄賂了多少錢。這樣，再面對剛才的情景時，你只需要判斷一下「接受者1」和「接受者2」告訴你的信息中，哪個意見領袖當時給的錢多，那你就默默的把自己的提議，改成那個意見領袖的提議。

5）最後這一部分最有意思，但描述起來有點繞，如果不能一下子就理解可以先看後面的例子。在整個選舉過程中，每個人誰先來誰後到，「接受者」什麼時間能夠接到「提議者」的信息，是完全不可控的。所以很可能一個意見領袖已經產生了，但是由於這個意見領袖的第二階段剛剛開始，絕大部分「接受者」還沒有收到這個意見領袖的提議。結果，這時突然衝進來了一個新的土豪「提議者」，那麼這個土豪「提議者」也是有機會讓自己的提議勝出的！這時就形成了一種博弈：a.上一個意見領袖要趕在土豪「提議者」賄賂到「接受者」前，趕到「接受者」面前讓他接受自己的提議，否則會因為自己的之前賄賂的錢比土豪少而被拒絕。b.土豪「提議者」要趕在上一個意見領袖將提議傳達給「接受者」前，賄賂到「接受者」，否則土豪「提議者」即便賄賂成功，也要默默的將自己的提議改為前任意見領袖的提議。這整個博弈的過程，最終就看這兩個「提議者」誰的進展快了。但最終一定會有一個意見領袖，先得到多數「接受者」的認可，那他的提議就勝出了。

4、總結

好啦，故事到這裡基本講述完了，咱們來總結一下，其實Paxos演算法就下面這麼幾個原則：

1）Paxos演算法包括兩個階段：第一個階段主要是賄選，還沒有提出提議；第二個階段主要根據第一階段的結果，明確接受誰的提議，並明確提議的內容是什麼（這個提議可能是賄選勝出「提議者」自己的提議，也可能是前任意見領袖的提議，具體是哪個提議，往下看，見下面第3點的內容）。

2）編號（賄賂金額）很重要，無論在哪個階段，編號（賄賂金額）小的，都會被鄙視（被拒絕）。

3）在第一階段中，一旦「接受者」已經接受了之前意見領袖的提議，那後面再來找這個「接受者」的「提議者」，即便在賄賂中勝出，也要被洗腦，默默將自己的提議改為前任意見領袖的提議，然後他會在第二階段提出該提議（也就是之前意見領袖的提議，以力爭讓大家的意見趨同）。如果「接受者」之前沒有接受過任何提議，那賄選勝出的「提議者」就可以提出自己的提議了。

5、舉例

最後舉個例子，加深一下印象：

有兩個「提議者」和三個「接受者」。

1）首先「提議者1」賄賂了3個「接受者」

2）3個「接受者」記錄下賄賂金額，因為目前只有一個「提議者」出價，因此$1就是最高的了，所以「接受者」們返回賄賂成功。此外，因為沒有任何先前的意見領袖提出的提議，因此「接受者」們告訴「提議者1」沒有之前接受過的提議（自然也就沒有上一個意見領袖的賄賂金額了）。

3）「提議者1」向「接受者1」提出了自己的提議：1號提議，並告知自己之前已賄賂$1。

4）「接受者1」檢查了一下，目前記錄的賄賂金額就是$1，於是接受了這一提議，並把1號提議記錄在案。

5）在「提議者1」向「接受者2」「接受者3」發起提議前，土豪「提議者2」出現，他開始用$2賄賂「接受者1」與「接受者2」。

6）「接受者1」與「接受者2」立刻被收買，將賄賂金額改為$2。但是，不同的是：「接受者1」告訴「提議者2」,之前我已經接受過1號提議了，同時1號提議的「提議者」賄賂過$1；而，「接受者2」告訴「提議者2」，之前沒有接受過其他意見領袖的提議，也沒有上一個意見領袖的賄賂金額。

7）這時，「提議者1」回過神來了，他向「接受者2」和「接受者3」發起1號提議，並帶著信息「我前期已經賄賂過$1」。

8）「接受者2」「接受者3」開始答覆：「接受者2」檢查了一下自己記錄的賄賂金額，然後表示，已經有人出價到$2了，而你之前只出到$1，不接受你的提議，再見。但「接受者3」檢查了一下自己記錄的賄賂金額，目前記錄的賄賂金額就是$1，於是接受了這一提議，並把1號提議記錄在案。

9）到這裡，「提議者1」已經得到兩個接受者的贊同，已經得到了多數「接受者」的贊同。於是「提議者1」確定1號提議最終通過。

10）下面，回到「提議者2」。剛才說到，「提議者2」賄賂了「接受者1」和「接受者2」，被「接受者1」告知：「之前已經接受過1號提議了，同時1號提議的『提議者』賄賂過$1」，並被「接受者2」告知：「之前沒有接到過其他意見領袖的提議，也沒有其他意見領袖的賄賂金額」。這時「提議者2」，拿到信息後，判斷一下，目前賄賂過最高金額（即$1）的提議就是1號提議了，所以「提議者2」默默的把自己的提議改為與1號提議一致，然後開始向「接受者1」「接受者2」發起提議（提議內容仍然是1號提議），並帶著信息：之前自己已賄賂過$2。

11）這時「接受者1」「接受者2」收到「提議者2」的提議後，照例先比對一下賄賂金額，比對發現「提議者2」之前已賄賂$2，並且自己記錄的賄賂金額也是$2，所以接受他的提議，也就是都接受1號提議。

12）於是，「提議者2」也拿到了多數派的意見，最終通過的也是1號提議。

這裡再多說一句：

回到上面的第5）步，如果「提議者2」第一次先去賄賂「接受者2」「接受者3」會發生什麼？那很可能1號提議就不會成為最終選出的提議。因為當「提議者2」先賄賂到了「接受者2」「接受者3」，那等「提議者1」帶著議題再去找這兩位的時候，就會因為之前賄賂的錢少（$1<$2）而被拒絕。所以，這也就是剛才講到可能存在博弈的地方：a.「提議者1」要趕在「提議者2」賄賂到「接受者2」「接受者3」之前，讓「接受者2」「接受者3」接受自己的意見，否則「提議者1」會因為錢少而被拒絕；b.「提議者2」要趕在「提議者1」之前賄賂到「接受者」，否則「提議者2」即便賄賂成功，也要默默的將自己的提議改為「提議者1」的提議。但你往後推演會發現，無論如何，總會有一個「提議者」的提議獲得多數票而勝出。

以上，只是把大致的Paxos演算法的思路介紹了一下，因為情景實在太複雜，比如：「提議者」、「接受者」如果是4個、5個……，比如：「提議者」與「接受者」之間的交互誰先誰後，等等各類情況。但是，其實都是能夠嚴謹的推導出最後能夠選出一個多數派的，不過篇幅就會太長了。大家有興趣可以按照上面的思路，自己再模擬模擬「提議者」「接受者」數量或多或少，交互或先或後的各種情況，結果肯定是最終唯一一個提議會獲得多數票而勝出。

（完）
推薦閱讀：