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