哈嘍大家好啊，我是Hydra。

分布式系統(tǒng)共識算法Paxos相信大家都不陌生，它被稱為最難理解的算法不是沒有道理的，首先，它的發(fā)表之路就充滿了坎坷。

1990年，萊斯利·蘭伯特大佬寫了一篇論文，舉了一個城邦選舉的例子來介紹Paxos算法，然而大佬的幽默感并未得到審稿人的認(rèn)可，論文未發(fā)表成功…

1998年，蘭伯特重新發(fā)表論文《The Part-Time Parliament》描述算法，然而眾多學(xué)者并不買賬，直呼看不懂…

2001年，蘭伯特對算法的描述進行簡化，再次發(fā)表 《Paxos Made Simple》，這次Paxos成為了世界公認(rèn)最優(yōu)秀的分布式系統(tǒng)共識算法…

其實說白了，Paxos算法要解決的問題是一個分布式系統(tǒng)如何就某個值決議達(dá)成一致。比如說，一組進程現(xiàn)在正在提議某個數(shù)據(jù)的值，需要通過消息傳遞的方式使這個值達(dá)成一致，也就是最終僅能有一個值被選定。

但畢竟是大佬寫出來的東西，且不說邏輯推理部分，就算單拎出來論文中對兩個核心階段的描述來說，我等凡人理解起來也還是有些困難。

不信？那就讓英語六級的我先來簡單地翻譯一下。

階段1

a、提案者選擇一個提案號n?，發(fā)送一個提案號為n的prepare請求給大多數(shù)接受者。

b、如果一個接受者收到的編號為n的prepare?請求，并且編號比它已經(jīng)響應(yīng)過的任何prepare?請求的編號都大，那它就回應(yīng)這個請求，承諾不再接受任何編號小于n的提案，并回復(fù)它已經(jīng)接受的編號最大的提案（如果存在的話）。

階段2

a、如果提案者收到大多數(shù)接受者關(guān)于它編號為n的prepare?請求的回應(yīng)，它就給這些接受者發(fā)送一個編號為n?，值為v的accept?請求，v?是收到的回應(yīng)中編號最大的提案值。如果之前不存在任何一個提案的回復(fù)時，那么v可以是任意值，也就是可以由自己指定。

b、接受者收到編號為n的accept?請求時，只要它還沒有響應(yīng)編號比n?更高的prepare請求，那么它將接受該提案。

是不是還看不懂？那就對了，下面我們通過一個簡單的例子來描述這個過程。

記得小時候，有不少廣播電臺可以通過電話點歌，打電話給話務(wù)員告訴她你要點的歌，接下來就會播放。當(dāng)然了，這個過程不是免費的，肯定有不少小伙伴在月末父母交話費的時候，慘遭過社會的毒打。

既然是電臺熱線，那么肯定不只有一個話務(wù)員了，我們假定這個電臺同時存在3個話務(wù)員，并且她們之間是相互沒有交流的，那么當(dāng)短時間內(nèi)打進來很多電話時，要怎么決定放哪首歌呢？

首先，話務(wù)員之間遵從少數(shù)服從多數(shù)，那么為了獲得更多話務(wù)員的支持，你可以不斷給更多的話務(wù)員打電話。

其次，前面我們說過，這個過程是收費的，假定存在一條潛規(guī)則，電臺會更偏向于接受出價高的人的點歌請求，那么也就好辦了，你可以使了勁地加錢。

在這種環(huán)境下，聽眾想要點歌成功的話，就得靠上面兩個辦法。

這時，第一個聽眾打進來電話了，在第一個階段聽眾只能進行報價，還不能提出自己想要聽什么歌，這個報價就可以理解為算法中的編號n。

因為聽眾1是第一個打進熱線電話的，在他之前還不存在任何報價，所以這里話務(wù)員們會無條件地先接受第一個聽眾的報價并記錄下來，然后返回給聽眾1一個回復(fù)信息。

在回復(fù)的信息中，話務(wù)員不但需要告訴聽眾他的報價目前最高，已經(jīng)被認(rèn)可了，還要說明之前沒有接受過其他任何聽眾的點歌請求。

這時候聽眾1一看，自己已經(jīng)獲得了超過半數(shù)以上的話務(wù)員的認(rèn)可了，那么進入階段2，告訴話務(wù)員自己想要聽什么歌曲。當(dāng)然，在這個過程中，還得順帶著告訴話務(wù)員自己在上一階段中的報價是多少。

于是，聽眾1再次打進熱線，先單獨向話務(wù)員2發(fā)起了選歌提議。

在收到聽眾1的點歌請求后，話務(wù)員2看到聽眾1在請求中攜帶的之前報價是1塊，滿足大于等于自己記錄的最大報價這一條件，于是果斷接受聽眾1的點歌請求。

在接受點歌請求后，話務(wù)員2要記錄的東西又要增加了，她不但要記住已接受的請求的報價金額，還要記住已接受請求的點播歌曲。然后給聽眾1一個回復(fù)，表示我已經(jīng)接受了你的點歌請求。

當(dāng)然了，在聽眾1努力點歌的時候，其他聽眾也不會閑著對不對？

聽眾2雖然打進電話晚了點，但是直接發(fā)動鈔能力，把自己的報價提升到了兩塊，來和話務(wù)員們進行通話。

由于兩塊錢的報價高于本地記錄的最高報價，所以話務(wù)員1和話務(wù)員2都會認(rèn)可這個報價，所以她們會先把本地的最高報價值更新為兩塊。

但是接下來，由于本地記錄的信息有所不同，所以她們將會給出不同的答復(fù)。

如果這時候，再來一個聽眾3打進電話，并且嘗試以兩塊或以下的價格進行報價給前兩個話務(wù)員的話，那么他的報價不會得到話務(wù)員的認(rèn)可。

這是因為我們前面說過了，話務(wù)員們都遵循拜金主義這一潛規(guī)則，所以她們不會接受比已記錄的最高報價還要低的報價。

在拒絕了聽眾3之后，我們再回到前面的兩位聽眾這邊。

接下來，我們根據(jù)聽眾1和2誰先打進電話，把時間線劃分為兩個平行宇宙。

平行宇宙1

在平行宇宙1這條時間線里，我們假設(shè)聽眾1先打進電話。

這時，仍然只有話務(wù)員2接受了聽眾1的點歌請求，于是聽眾1繼續(xù)向其他話務(wù)員撥打電話，告訴她們自己要聽的歌。

在話務(wù)員3這里，她記錄的最高報價還是聽眾1之前的1塊，所以沒有意外，話務(wù)員3會接受聽眾1的點歌請求，并更新本地的記錄信息。

但是話務(wù)員1這就不一樣了，她所認(rèn)可的報價已經(jīng)漲到了2，所以舊的1塊錢報價已經(jīng)不能在她這里點歌了，因此話務(wù)員1會拒絕聽眾1的點歌請求。

盡管請求沒有得到話務(wù)員1的接受，但是前面我們說了，話務(wù)員之間要遵循少數(shù)服從多數(shù)的原則，聽眾1的點歌請求已經(jīng)被半數(shù)以上話務(wù)員接受，那么聽眾1確認(rèn)自己點的這首《東風(fēng)破》已被選定。

平行宇宙2

讓我們回到平行宇宙的分叉點，先回顧一下前情，這時聽眾2已經(jīng)向話務(wù)員1和話務(wù)員2發(fā)出過報價，并從話務(wù)員2那里得知她已經(jīng)以1塊錢的報價接受了《東風(fēng)破》這首歌的提案。

那么在這條時間線中，我們讓聽眾2先打給1、2號話務(wù)員。

聽眾2這時心里會想，我們杰迷們都是有素質(zhì)的人，盡管我之前想聽的是《簡單愛》，但聽一下《東風(fēng)破》貌似也挺不錯，那么我干脆支持聽眾1的選擇吧。

于是，報價已被認(rèn)可的他再次拿起電話打給兩位話務(wù)員，發(fā)起點歌請求。

話務(wù)員1和話務(wù)員2再次比較聽眾2這次攜帶的之前報價，均大于等于本地記錄的最高報價，所以接受他的點歌請求。在更新本地記錄的信息后，回復(fù)信息給聽眾2。

于是，聽眾2的點歌請求也獲得了半數(shù)以上話務(wù)員的承認(rèn)，那么聽眾2確認(rèn)自己點的歌被選定。

看到這里，是不是似乎感覺世界線產(chǎn)生了收束，難道之后的每一種結(jié)果都是《東風(fēng)破》將被選定？

其實，Paxos算法中最精彩的部分在于它更像是一場博弈，棋局中的每一步，都可能影響最終的結(jié)果。

平行宇宙β

讓我們把分叉點上的時間，再往前多回溯一點，回到下面這個時間點的狀態(tài)，這時話務(wù)員2剛接受了聽眾1的點歌請求，而聽眾2還沒有開始打熱線電話。

這次，我們站在上帝視角，讓聽眾2改變一下選擇，既然話務(wù)員2已經(jīng)被別人收買了，那么干脆避其鋒芒，直接向話務(wù)員1、3報價。

可想而知，聽眾2的報價會被兩位話務(wù)員都認(rèn)可。

在收到了半數(shù)以上話務(wù)員的報價認(rèn)可后，聽眾2先向話務(wù)員1發(fā)起點歌請求。

話務(wù)員1比對一下報價，嗯，沒有問題，更新本地的記錄，接受他的點歌請求。

講道理，現(xiàn)在的形勢對聽眾2真的是一片大好，只要再打個電話給話務(wù)員3，就能夠成功點歌了。

但是這個節(jié)骨眼上，聽眾2的室友喊他了，說：聽歌多沒意思，咱們一起來打一局刀塔吧。

聽眾2一想，沒毛病，那我先不點歌了。

而這時，聽眾1回過神來了，他在之前報價階段可是獲得過半數(shù)以上的認(rèn)可的，于是他帶著之前被認(rèn)可的報價打電話進來點歌。

可是在兩位話務(wù)員那里，記錄的最高報價已經(jīng)升到了兩塊了，于是聽眾1的點歌請求會被拒絕。

到這，我們梳理一下，聽眾1的點歌請求得到了1個接受、2個拒絕，也就是說他的提議沒有被過半數(shù)以上的話務(wù)員接受。

無奈，聽眾1只能回到第一階段，從報價開始再重頭走一遍流程。并且這次，他把報價提升到了3塊。

三位話務(wù)員收到新的報價請求后，都會表示認(rèn)可，并且返回自己本地記錄的信息。

聽眾1這一次收到的三條報價認(rèn)可中，有兩條攜帶了之前被接受的點歌信息。那么新問題來了，他應(yīng)該選哪一首歌曲作為自己接下來要點播的歌曲呢？

在這里，聽眾要遵循的規(guī)則其實和話務(wù)員一致，他需要在這些返回的報價及歌曲信息中，選擇最高報價的歌曲，作為自己的接下來選歌的依據(jù)，因此他最終會選擇《簡單愛》。

最終，在沒有其他聽眾中途打進電話干擾的情況下，三位話務(wù)員都會接受聽眾1的點歌請求。

最終，聽眾1的點歌請求收到超過半數(shù)話務(wù)員的接受，于是他確認(rèn)《簡單愛》這首歌會被選中。

最后

前面提到過，Paxos算法中的選舉過程就像是一場博弈，場上局勢瞬息萬變。

回顧一下上面3條不同的時間線，打進電話順序的不同、選擇的話務(wù)員不同，都可能導(dǎo)致最終產(chǎn)生不同的結(jié)果。

而Paxos算法本身，并不關(guān)注最終選擇的是哪一個結(jié)果，它關(guān)注的是無論如何，在最后一定要能夠達(dá)成一個共識。

當(dāng)然了，也有可能遇到下面這種無法解決的情況…

在這種情況下，可能會有兩個聽眾交替報價成功，卻提議歌曲失敗，形成一個活鎖的局面。如果這樣下去，有可能一整天下來，一首歌曲都沒有被最終選取成功。

所以在某些情況下，需要選取一個主提案者，只有主提案者才能和過半的接受者進行通信提出提案。

說白了，也就是我們常說的話事人。

那么，我們最后再做一個總結(jié)，其實在我看來，Paxos算法的關(guān)鍵，就在于后者要認(rèn)同前者，來避免無休止的爭端。

本文也只是對決議部分的兩階段通過示例進行了說明，并忽略了算法中另一個角色學(xué)習(xí)者的內(nèi)容，如果有興趣的話，大家不妨去看看論文原文。

畢竟蘭伯特大佬都說了：

論文原文：

http://lamport.azurewebsites.net/pubs/paxos-simple.pdf