一篇文章帶你了解Paxos算法Russell Cohen的回答

本文講的是<b>一篇文章帶你了解Paxos算法</b>，【編者的話】本文是Quora上關于Paxos算法的回答，兩位答者分别從不同的角度描述Paxos算法。Vineet Gupta的回答細緻入微，更偏向理論。Russell Cohen用具體的例子講解Paxos算法，相輔相成。

有很多關于一緻性（consensus）問題的解決方案，而這些解決方案中，我認為Paxos相對來說很好了解。

『達成一緻性』最簡單的例子就是結婚誓詞：

“你願意.......”（男：）“我願意！”（女：）“我願意！”

“現在我宣布你們...”

現在假設婚姻并非隻有兩個人，就像羅伯特·喬丹的《時間之輪》中的

“你願意...?”（男：）“我願意！”（女1：）“我願意！”（女2：）“我願意！”...

如果任何一個将會成為配偶的艾爾人不回應“我願意”，那這場婚禮将無法繼續。

表決階段。在表決階段，協調者将通知事務參與者準備送出或取消事務，然後進入表決過程。在表決過程中，參與者将告知協調者自己的決策：同意（事務參與者本地作業執行成功）或取消（本地作業執行故障）。

送出階段。在該階段，協調者将基于第一個階段的投票結果進行決策：送出或取消。當且僅當所有的參與者同意送出事務協調者才通知所有的參與者送出事務，否則協調者将通知所有的參與者取消事務。參與者在接收到協調者發來的消息後将執行響應的操作。

要注意的是票隻能投給（協調器）建議的值，每個節點隻能說是或否。節點不能再提出一個可供選擇的值。如果一個節點想提出自己的 值，它需要開始它自己的2PC。算法很簡單，由節點來決定某一個節點提出的值。它也不是非常低效的，對于N個節點，将交換3N條消息。

但是如果一個節點崩潰了會發生什麼？例如，假設在階段一協調器将提議的值發送給部分節點（并非全部）後，然後協調器就挂掉了。（這是會發生什麼？） 

現在一些節點已經開始了2PC循環，而另一些節點沒有意識到2PC循環已經發生。那些已經開始2PC循環的節點被阻塞在等待下一個階段上。

在我們的場景中，已經投票的資源管理單元也可能不得不鎖定一些資源，這樣資源管理不會因為等待協調器恢複并啟動階段二而耗盡時間。

如果階段二中的協調器未能把所有的送出資訊發送給全部節點而隻是部分節點後就崩潰了，相似的問題依然存在。我們可以讓另一個節點接管協調器職責觀察時間逾時來解決部分存在的問題。這個節點會和其它節點取得聯系并獲得它們的投票情況（要求它們必須投票）以及推動事務完成，但這一過程中進一步參與者可能發生故障，同時事務可能永遠不會恢複。我們的底線-在節點故障的情況下2PC無法可靠地操作。

2PC的關鍵問題是，萬一協調器挂掉了，沒有節點具備足夠的資訊來完成整個協定。這一點可以通過添加額外的步驟來解決：

1. 階段1和（2PC）相同-協調器給所有的節點發送一個值。

2. 階段2-新的步驟-一旦從上一步中所有節點都接收到“是”，協調器發送出“準備送出”消息。我們期望的是節點能夠執行可以撤消的工作，而且沒有什麼是不能撤消的。每一個節點向協調器确認它已經接收到“準備送出”消息了。

3. 階段3-類似2PC中階段二-如果協調器從所有節點接收到關于“準備送出”的确認資訊，它就繼續工作，将投票的結果發送給所有的節點要求他們送出。但是，如果所有節點都不确認，協調器會終止事務。

現在如果協調器在任何時刻崩潰，任何參與者都可以接管協調器的角色并查詢來自其它節點的狀态。

如果任何資源管理向恢複節點報告說它并沒有接收到“準備送出”的資訊，恢複節點便知道事務沒有送出給任何資源管理。現在要麼事務被悲觀地終止，要麼協定執行個體重新運作。

如果有一個管理單元送出事務後崩潰了，我們知道的是，其它每一個資源管理單元可能會收到“準備送出”的确認資訊，否則協調器不會進入送出階段。是以協調器是可以進入到最後一個階段的。

是以3PC能夠很好地工作盡管有節點故障。這是以在N個節點添加一個新的步驟為代價的，它導緻了較高的延時。

3PC在網絡分區情況下存在不足。假設所有收到“準備送出”資訊的資源管理都在分區的一側，其餘的都在另一邊。現在這會導緻每個分區都選擇一個恢複節點，這兩個恢複節點要麼送出事務，要麼終止事務。一旦網絡分區被移除，系統會得到不一緻的狀态。

先說重要的事-考慮下3PC，我們還需要更好的算法嗎？3PC唯一的問題是網絡分區，真的嗎？首先，我們假設網絡分區是唯一的問題（并不是，下面我們會看到）。在網絡分區的情況下，正确性真的是值得解決的問題嗎？今天，在雲計算和網際網路規模的服務下，其中的節點有可能在大陸的不同側或者跨越了大洋，我們确實需要分區容錯算法。

第二點是網絡分區并不是唯一的問題。當我們解決了單個節點永久故障的情況時，更一般的情況是，節點崩潰了，接着它重新恢複并且從崩潰的地方工作。這種<code>故障-恢複模式</code>也可以描述一個異步網絡模型，這種網絡模型中一個節點用來響應消息的時間是沒有上限的，是以你不能假設一個節點死了-也許它僅僅是響應緩慢或者是網絡緩慢。在這種模型中你不能判斷逾時。

3PC是<code>故障-停止</code>容錯，而不是<code>故障-恢複</code>容錯。不幸的是現實生活中需要的是<code>故障-恢複</code>容錯，是以我們需要更一般的解決方案。而這正是Paxos的用武之地。

Paxos中的基本步驟和2PC很像：

選擇一個節點作為上司者/提議者。

上司者選擇一個值并将它發給所有節點（Paxos中被稱為接收者），（這個值）封裝在<code>接收-請求</code>消息中，接收者可以回複拒絕或接受。

一旦多數節點都接受，共識就達成了同時協調器向所有節點廣播<code>送出</code>資訊。

Paxos與2PC主要不同點在于Paxos不要求所有節點都要同意（才會送出事務），隻要大部分節點同意就行。這是一個有趣的想法因為在兩個獨立的多數節點中至少存在一個正常工作的節點。這確定在給定的循環中，如果大部分節點贊同給定的值，任何随後努力提出一個新值的節點将會獲得來自其它節點的值而且這個節點也隻會贊同那個值（不會再提出自己的值了）。這也意味着Paxos算法不會阻塞即使一半的節點無法回複消息。

當然也可能發生是上司節點自己故障了。為了解決這個問題，Paoxs在給定的時間點不會隻向一個上司節點授權。它允許任何節點（在上司節點故障時）成為上司者并協調事務。這也自然意味着在特定情況下至少存在一個節點能稱為上司者。在上述情況下很可能存在兩個上司者并且他們發送了不同的值。是以如何達成共識呢？為了在這樣的設定下達成共識，Paxos介紹了兩種機制：

給上司者指定順序。這讓每個節點能夠區分目前上司者和舊的上司者，它阻止舊上司者（或許剛從舊的故障中恢複）擾亂已經達成的共識。

限制上司者對值的選擇。一旦就某個值`達成了共識，Paxos強制将來的上司隻能選擇相同的值確定共識能延續下去。這一點是這樣實作的-接收節點發送它贊同的最新的值和它收到的上司者的序列号（來實作上一點）。新的上司者可以從接受者發送的值中選擇一個，萬一沒有任何接收節點發送值，上司者也可以選擇自己的值。

一個節點被選為上司者并且選擇序列号x和值v建立提議P1(x,v)。上司者把P1發送給接收者并等待大部分節點響應。

接收者一旦接收到提議P1(x,v)會做下面的事：

如果是接收者第一次收到提議而且它選擇贊同，回複“贊同”-這是接收者的承諾，它将承諾拒絕将來所有小于x的提議請求。- 如果接收者已經贊同了提議：

比較x和接收者贊同的提議的最高序列号，稱為P2(y,v2)

若x&lt;y,回應“拒絕”以及y的值- 若x&gt;y,回應“贊同”以及P2(y,v2)

- 如果大部分接收節點未能回應或者回應“拒絕”，上司者放棄這次協定并重新開始。

- 如果大部分接收節點回應“贊同”，上司者也會接受大部分節點接受的協定的值。上司者選擇這些值的任意一個并發送<code>接受請求</code>以及提議序列号和值。

- 當接收者收到<code>接受請求</code>消息，它隻在下面兩種情況符合時發送“接受”資訊，否則發送“拒絕”：

- 值和之前接受的提議中的任一值相同

- 序列号和接收者贊同的最高提議序列号相同

- 如果上司者沒有從大部分節點那接收到“接受”消息，它會放棄這次提議重新開始。但是如果接收到了大部分的“接受”消息，深思熟慮後協定也可能被終止。作為優化，上司者要給其它節點發送“送出”資訊。

正如人們所看到的，在故障容錯上Paxos要優于2PC：

上司者故障了-另一位（新的）上司者可以通過發出自己的協定來接管協定。

原先的（故障）上司者恢複後-兩個上司者可以同時存在，這歸功于下面的規則：隻贊同更高序列号的協定以及隻送出以前接受的值。

Paxos也比3PC更加容錯。具體地講，Paxos是分區容錯3PC不是。在3PC中，如果兩個分區分别贊同一個值，當分區合并的時候，會留給你一個不一緻的狀态。在Paxos中，大部分情況下這不會發生。除非某個分區占絕大多數，否則不會達成共識。如果某個分區占絕大多數并達成一個共識，那值就需要被其它分區中的節點接受。

Paxos存在的一個問題是，兩個上司者因為處于不同的分區導緻不能互相觀察，他們會努力向另一方投标，釋出一個比先前協定有更高序列号的協定。這可能導緻Paxos無法終止。最終這兩個互相觀察的上司者必須有一個需要做出退讓。

本文提供了一個非常清晰的解釋和證明：

我将努力提供一個清晰的總結：

Paxos算法的目的是幫助一些同等的節點就一個值達成一緻的協定。Paxos保證如果一個節點相信一個值已經被多數節點贊同，多數節點就再也不會贊同其它值。這個協定被設計使得任何共識必須得到大部分節點的認可。任何将來試圖達成共識的嘗試，如果成功了也必須經過至少一個節點的認可。

是以，任何已經做出決定的節點必須和多數中的一個節點通信。協定保證節點将能從多數節點贊同的值得到收獲。

下面講述它是如何運作的：

假設我們有3個節點：A、B和C。A将提出一個值"Foo"

Paxos将分3個階段執行。在每個階段，必須有多數節點達成一緻。

首先，我們來看準備階段。節點A發送準備請求給A、B、C。Paxos根據序列号來擔保。<code>準備請求</code>要求節點承諾：“我永遠不會接受序列号比<code>準備請求</code>小的提議。”（被詢問的節點）回複一個它們之前贊同的值（如果有的話）。（這一點非常重要）：節點A必須回應它接收到的最高序列号的值。這一行為提供了保證：先前得到的贊同的值将被保留。

接下來我們進入到接受階段。A發送一條接受請求給A，B和C。接受請求表示：“你接受Foo嗎？”。如果伴随的序列号不小于節點先前已經承諾過的序列号或者是節點先前接受的請求的序列号，那麼節點将接受新的值和序列号。

如果節點A從多數節點接收到的是“接受”，(Foo)這個值就被确定下來。Paxos循環也會終止不再詢問新的值。

階段三不是絕對必須的，但是如果在生産環境中實作Paxos算法，階段三會是重要的優化。A收到多數節點“接受”消息後，它發送“已經确定值”消息給A，B和C。這條消息讓所有節點知道已經選好了值，這會加快決定值的過程結束。

如果沒有這個消息，其它節點将繼續提出新的值來了解協定。在準備階段，它們不斷從預先約定的值中學習，一旦它們從協定得到結論，節點就會确認這個協定。

（為了便于了解）我掩蓋了一些關鍵的問題：

1. 所有的序列号必須單調遞增，而且不同節點序列号都不同。也就是說，A、B不能用同一個序列号k發送資訊。協定要求所有發送的消息必須包含序列号。在準備階段每個節點都要追蹤它遇到的最高接受請求和它承諾的（序列号）最高的值。

2. 故障情況。一次Paxos循環中很可能失敗，萬一失敗了，一個節點會用更高的序列号發起新的提議。

3. 終止情況。我所描述的Paxos版本不一定出現終止故障。對于正常的終止情況，（我描述的）Paxos算法還需要一些調整。

=========================================

譯者介紹

adolphlwq，南京資訊工程大學大學大四學生，對Docker充滿興趣，喜歡運動。現在正努力充電希望快速進步。

原文釋出時間為：2015-09-04 

本文作者：adolphlwq 

本文來自雲栖社群合作夥伴DockerOne，了解相關資訊可以關注DockerOne。

原文标題：一篇文章帶你了解Paxos算法