http://dockone.io/article/640
【編者的話】本文是Quora上關于Paxos算法的回答，兩位答者分別從不同的角度描述Paxos算法。Vineet Gupta的回答細致入微，更偏向理論。Russell Cohen用具體的例子講解Paxos算法，相輔相成。Vineet Gupta的回答
有很多關于一致性（consensus）問題的解決方案，而這些解決方案中，我認為Paxos相對來說很好理解。『達成一致性』最簡單的例子就是結婚誓詞：- “你愿意.......”（男：）“我愿意！”（女：）“我愿意！”
- “現在我宣布你們...”
現在假設婚姻并非只有兩個人，就像羅伯特·喬丹的《時間之輪》中的艾爾民俗：一位或者更多的艾爾女人可以成為first-sisters，而男人要么把她們全部娶回家要么一個也不娶。在艾爾人眼中，婚姻誓詞也許是下面這樣的：- “你愿意...?”（男：）“我愿意！”（女1：）“我愿意！”（女2：）“我愿意！”...
- “現在我宣布你們...”
如果任何一個將會成為配偶的艾爾人不回應“我愿意”，那這場婚禮將無法繼續。計算機科學家把上面的現象稱為二階段提交。二階段提交（2PC）
- 表決階段。在表決階段，協調者將通知事務參與者準備提交或取消事務，然后進入表決過程。在表決過程中，參與者將告知協調者自己的決策：同意（事務參與者本地作業執行成功）或取消（本地作業執行故障）。
- 提交階段。在該階段，協調者將基于第一個階段的投票結果進行決策：提交或取消。當且僅當所有的參與者同意提交事務協調者才通知所有的參與者提交事務，否則協調者將通知所有的參與者取消事務。參與者在接收到協調者發來的消息后將執行響應的操作。
要注意的是票只能投給（協調器）建議的值，每個節點只能說是或否。節點不能再提出一個可供選擇的值。如果一個節點想提出自己的 值，它需要開始它自己的2PC。算法很簡單，由節點來決定某一個節點提出的值。它也不是非常低效的，對于N個節點，將交換3N條消息。但是如果一個節點崩潰了會發生什么？例如，假設在階段一協調器將提議的值發送給部分節點（并非全部）后，然后協調器就掛掉了。（這是會發生什么？） - 現在一些節點已經開始了2PC循環，而另一些節點沒有意識到2PC循環已經發生。那些已經開始2PC循環的節點被阻塞在等待下一個階段上。
- 在我們的場景中，已經投票的資源管理單元也可能不得不鎖定一些資源，這樣資源管理不會因為等待協調器恢復并啟動階段二而耗盡時間。
如果階段二中的協調器未能把所有的提交信息發送給全部節點而只是部分節點后就崩潰了，相似的問題依然存在。我們可以讓另一個節點接管協調器職責觀察時間超時來解決部分存在的問題。這個節點會和其它節點取得聯系并獲得它們的投票情況（要求它們必須投票）以及推動事務完成，但這一過程中進一步參與者可能發生故障，同時事務可能永遠不會恢復。我們的底線-在節點故障的情況下2PC無法可靠地操作。三階段提交（3PC）
2PC的關鍵問題是，萬一協調器掛掉了，沒有節點具備足夠的信息來完成整個協議。這一點可以通過添加額外的步驟來解決：1. 階段1和（2PC）相同-協調器給所有的節點發送一個值。2. 階段2-新的步驟-一旦從上一步中所有節點都接收到“是”，協調器發送出“準備提交”消息。我們期望的是節點能夠執行可以撤消的工作，而且沒有什么是不能撤消的。每一個節點向協調器確認它已經接收到“準備提交”消息了。3. 階段3-類似2PC中階段二-如果協調器從所有節點接收到關于“準備提交”的確認信息，它就繼續工作，將投票的結果發送給所有的節點要求他們提交。但是，如果所有節點都不確認，協調器會終止事務。現在如果協調器在任何時刻崩潰，任何參與者都可以接管協調器的角色并查詢來自其它節點的狀態。- 如果任何資源管理向恢復節點報告說它并沒有接收到“準備提交”的信息，恢復節點便知道事務沒有提交給任何資源管理。現在要么事務被悲觀地終止，要么協議實例重新運行。
- 如果有一個管理單元提交事務后崩潰了，我們知道的是，其它每一個資源管理單元可能會收到“準備提交”的確認信息，否則協調器不會進入提交階段。所以協調器是可以進入到最后一個階段的。
因此3PC能夠很好地工作盡管有節點故障。這是以在N個節點添加一個新的步驟為代價的，它導致了較高的延時。3PC在網絡分區情況下存在不足。假設所有收到“準備提交”信息的資源管理都在分區的一側，其余的都在另一邊。現在這會導致每個分區都選擇一個恢復節點，這兩個恢復節點要么提交事務，要么終止事務。一旦網絡分區被移除，系統會得到不一致的狀態。Paxos-為什么麻煩？
先說重要的事-考慮下3PC，我們還需要更好的算法嗎？3PC唯一的問題是網絡分區，真的嗎？首先，我們假設網絡分區是唯一的問題（并不是，下面我們會看到）。在網絡分區的情況下，正確性真的是值得解決的問題嗎？今天，在云計算和互聯網規模的服務下，其中的節點有可能在大陸的不同側或者跨越了大洋，我們確實需要分區容錯算法。第二點是網絡分區并不是唯一的問題。當我們解決了單個節點永久故障的情況時，更一般的情況是，節點崩潰了，接著它重新恢復并且從崩潰的地方工作。這種故障-恢復模式也可以描述一個異步網絡模型，這種網絡模型中一個節點用來響應消息的時間是沒有上限的，因此你不能假設一個節點死了-也許它僅僅是響應緩慢或者是網絡緩慢。在這種模型中你不能判斷超時。3PC是故障-停止容錯，而不是故障-恢復容錯。不幸的是現實生活中需要的是故障-恢復容錯，因此我們需要更一般的解決方案。而這正是Paxos的用武之地。Paxos-它如何運行?
Paxos中的基本步驟和2PC很像：- 選擇一個節點作為領導者/提議者。
- 領導者選擇一個值并將它發給所有節點（Paxos中被稱為接收者），（這個值）封裝在
接收-請求消息中，接收者可以回復拒絕或接受。 - 一旦多數節點都接受，共識就達成了同時協調器向所有節點廣播
提交信息。
Paxos與2PC主要不同點在于Paxos不要求所有節點都要同意（才會提交事務），只要大部分節點同意就行。這是一個有趣的想法因為在兩個獨立的多數節點中至少存在一個正常工作的節點。這確保在給定的循環中，如果大部分節點贊同給定的值，任何隨后努力提出一個新值的節點將會獲得來自其它節點的值而且這個節點也只會贊同那個值（不會再提出自己的值了）。這也意味著Paxos算法不會阻塞即使一半的節點無法回復消息。當然也可能發生是領導節點自己故障了。為了解決這個問題，Paoxs在給定的時間點不會只向一個領導節點授權。它允許任何節點（在領導節點故障時）成為領導者并協調事務。這也自然意味著在特定情況下至少存在一個節點能稱為領導者。在上述情況下很可能存在兩個領導者并且他們發送了不同的值。所以如何達成共識呢？為了在這樣的設置下達成共識，Paxos介紹了兩種機制：- 給領導者指定順序。這讓每個節點能夠區分當前領導者和舊的領導者，它阻止舊領導者（或許剛從舊的故障中恢復）擾亂已經達成的共識。
- 限制領導者對值的選擇。一旦就某個值`達成了共識，Paxos強制將來的領導只能選擇相同的值確保共識能延續下去。這一點是這樣實現的-接收節點發送它贊同的最新的值和它收到的領導者的序列號（來實現上一點）。新的領導者可以從接受者發送的值中選擇一個，萬一沒有任何接收節點發送值，領導者也可以選擇自己的值。
協議步驟：
準備階段：
- 一個節點被選為領導者并且選擇序列號x和值v創建提議P1(x,v)。領導者把P1發送給接收者并等待大部分節點響應。
- 接收者一旦接收到提議P1(x,v)會做下面的事：
- 如果是接收者第一次收到提議而且它選擇贊同，回復“贊同”-這是接收者的承諾，它將承諾拒絕將來所有小于x的提議請求。
- 如果接收者已經贊同了提議：- 比較x和接收者贊同的提議的最高序列號，稱為P2(y,v2)
- 若x<y,回應“拒絕”以及y的值
- 若x>y,回應“贊同”以及P2(y,v2)
接受階段
- 如果大部分接收節點未能回應或者回應“拒絕”，領導者放棄這次協議并重新開始。- 如果大部分接收節點回應“贊同”，領導者也會接受大部分節點接受的協議的值。領導者選擇這些值的任意一個并發送接受請求以及提議序列號和值。- 當接收者收到接受請求消息，它只在下面兩種情況符合時發送“接受”信息，否則發送“拒絕”：- 值和之前接受的提議中的任一值相同- 序列號和接收者贊同的最高提議序列號相同- 如果領導者沒有從大部分節點那接收到“接受”消息，它會放棄這次提議重新開始。但是如果接收到了大部分的“接受”消息，深思熟慮后協議也可能被終止。作為優化，領導者要給其它節點發送“提交”信息。Paxos對故障的處理
如果Paxos算法中我們一次只授權唯一一個領導者，同時授權小部分節點，那樣會發生什么？所有節點都要投票嗎？是的，（這時）我們使用2PC。2PC是Paxos中的特例。正如人們所看到的，在故障容錯上Paxos要優于2PC：- 領導者故障了-另一位（新的）領導者可以通過發出自己的協議來接管協議。
- 原先的（故障）領導者恢復后-兩個領導者可以同時存在，這歸功于下面的規則：只贊同更高序列號的協議以及只提交以前接受的值。
Paxos也比3PC更加容錯。具體地講，Paxos是分區容錯3PC不是。在3PC中，如果兩個分區分別贊同一個值，當分區合并的時候，會留給你一個不一致的狀態。在Paxos中，大部分情況下這不會發生。除非某個分區占絕大多數，否則不會達成共識。如果某個分區占絕大多數并達成一個共識，那值就需要被其它分區中的節點接受。Paxos存在的一個問題是，兩個領導者因為處于不同的分區導致不能互相觀察，他們會努力向另一方投標，發布一個比先前協議有更高序列號的協議。這可能導致Paxos無法終止。最終這兩個互相觀察的領導者必須有一個需要做出退讓。這樣做是安全和活性間的折中。Paxos是安全的算法-一旦達成共識，贊同的值不會改變。但是，Paxos不能保證處在工作狀態-Paxos在稀少的情況下可能不被終止。事實上一個異步一致算法不能被保證既安全又處于活動狀態。我們稱這為FLP不可能結果。拓展閱讀
Russell Cohen的回答
本文提供了一個非常清晰的解釋和證明：http://nil.csail.mit.edu/6.824...我將努力提供一個清晰的總結：Paxos算法的目的是幫助一些同等的節點就一個值達成一致的協議。Paxos保證如果一個節點相信一個值已經被多數節點贊同，多數節點就再也不會贊同其它值。這個協議被設計使得任何共識必須得到大部分節點的認可。任何將來試圖達成共識的嘗試，如果成功了也必須經過至少一個節點的認可。因此，任何已經做出決定的節點必須和多數中的一個節點通信。協議保證節點將能從多數節點贊同的值得到收獲。下面講述它是如何運作的：假設我們有3個節點：A、B和C。A將提出一個值"Foo"Paxos將分3個階段執行。在每個階段，必須有多數節點達成一致。首先，我們來看準備階段。節點A發送準備請求給A、B、C。Paxos根據序列號來擔保。準備請求要求節點承諾：“我永遠不會接受序列號比準備請求小的提議。”（被詢問的節點）回復一個它們之前贊同的值（如果有的話）。（這一點非常重要）：節點A必須回應它接收到的最高序列號的值。這一行為提供了保證：先前得到的贊同的值將被保留。接下來我們進入到接受階段。A發送一條接受請求給A，B和C。接受請求表示：“你接受Foo嗎？”。如果伴隨的序列號不小于節點先前已經承諾過的序列號或者是節點先前接受的請求的序列號，那么節點將接受新的值和序列號。如果節點A從多數節點接收到的是“接受”，(Foo)這個值就被確定下來。Paxos循環也會終止不再詢問新的值。階段三不是絕對必須的，但是如果在生產環境中實現Paxos算法，階段三會是重要的優化。A收到多數節點“接受”消息后，它發送“已經確定值”消息給A，B和C。這條消息讓所有節點知道已經選好了值，這會加快決定值的過程結束。如果沒有這個消息，其它節點將繼續提出新的值來了解協議。在準備階段，它們不斷從預先約定的值中學習，一旦它們從協議得到結論，節點就會確認這個協議。（為了便于理解）我掩蓋了一些關鍵的問題：1. 所有的序列號必須單調遞增，而且不同節點序列號都不同。也就是說，A、B不能用同一個序列號k發送信息。協議要求所有發送的消息必須包含序列號。在準備階段每個節點都要追蹤它遇到的最高接受請求和它承諾的（序列號）最高的值。2. 故障情況。一次Paxos循環中很可能失敗，萬一失敗了，一個節點會用更高的序列號發起新的提議。3. 終止情況。我所描述的Paxos版本不一定出現終止故障。對于正常的終止情況，（我描述的）Paxos算法還需要一些調整。原文連接：Distributed Systems: What is a simple explanation of the Paxos algorithm?（翻譯：adolphlwq）=========================================譯者介紹adolphlwq，南京信息工程大學本科大四學生，對Docker充滿興趣，喜歡運動。現在正努力充電希望快速進步。