哈嘍大家好啊，我是Hydra。

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

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

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

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

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

但畢竟是大佬寫(xiě)出來(lái)的東西，且不說(shuō)邏輯推理部分，就算單拎出來(lái)論文中對(duì)兩個(gè)核心階段的描述來(lái)說(shuō)，我等凡人理解起來(lái)也還是有些困難。

不信？那就讓英語(yǔ)六級(jí)的我先來(lái)簡(jiǎn)單地翻譯一下。

階段1

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

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

階段2

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

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

是不是還看不懂？那就對(duì)了，下面我們通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)描述這個(gè)過(guò)程。

記得小時(shí)候，有不少?gòu)V播電臺(tái)可以通過(guò)電話點(diǎn)歌，打電話給話務(wù)員告訴她你要點(diǎn)的歌，接下來(lái)就會(huì)播放。當(dāng)然了，這個(gè)過(guò)程不是免費(fèi)的，肯定有不少小伙伴在月末父母交話費(fèi)的時(shí)候，慘遭過(guò)社會(huì)的毒打。

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

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

其次，前面我們說(shuō)過(guò)，這個(gè)過(guò)程是收費(fèi)的，假定存在一條潛規(guī)則，電臺(tái)會(huì)更偏向于接受出價(jià)高的人的點(diǎn)歌請(qǐng)求，那么也就好辦了，你可以使了勁地加錢(qián)。

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

這時(shí)，第一個(gè)聽(tīng)眾打進(jìn)來(lái)電話了，在第一個(gè)階段聽(tīng)眾只能進(jìn)行報(bào)價(jià)，還不能提出自己想要聽(tīng)什么歌，這個(gè)報(bào)價(jià)就可以理解為算法中的編號(hào)n。

因?yàn)槁?tīng)眾1是第一個(gè)打進(jìn)熱線電話的，在他之前還不存在任何報(bào)價(jià)，所以這里話務(wù)員們會(huì)無(wú)條件地先接受第一個(gè)聽(tīng)眾的報(bào)價(jià)并記錄下來(lái)，然后返回給聽(tīng)眾1一個(gè)回復(fù)信息。

在回復(fù)的信息中，話務(wù)員不但需要告訴聽(tīng)眾他的報(bào)價(jià)目前最高，已經(jīng)被認(rèn)可了，還要說(shuō)明之前沒(méi)有接受過(guò)其他任何聽(tīng)眾的點(diǎn)歌請(qǐng)求。

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

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

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

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

當(dāng)然了，在聽(tīng)眾1努力點(diǎn)歌的時(shí)候，其他聽(tīng)眾也不會(huì)閑著對(duì)不對(duì)？

聽(tīng)眾2雖然打進(jìn)電話晚了點(diǎn)，但是直接發(fā)動(dòng)鈔能力，把自己的報(bào)價(jià)提升到了兩塊，來(lái)和話務(wù)員們進(jìn)行通話。

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

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

如果這時(shí)候，再來(lái)一個(gè)聽(tīng)眾3打進(jìn)電話，并且嘗試以兩塊或以下的價(jià)格進(jìn)行報(bào)價(jià)給前兩個(gè)話務(wù)員的話，那么他的報(bào)價(jià)不會(huì)得到話務(wù)員的認(rèn)可。

這是因?yàn)槲覀兦懊嬲f(shuō)過(guò)了，話務(wù)員們都遵循拜金主義這一潛規(guī)則，所以她們不會(huì)接受比已記錄的最高報(bào)價(jià)還要低的報(bào)價(jià)。

在拒絕了聽(tīng)眾3之后，我們?cè)倩氐角懊娴膬晌宦?tīng)眾這邊。

接下來(lái)，我們根據(jù)聽(tīng)眾1和2誰(shuí)先打進(jìn)電話，把時(shí)間線劃分為兩個(gè)平行宇宙。

平行宇宙1

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

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

在話務(wù)員3這里，她記錄的最高報(bào)價(jià)還是聽(tīng)眾1之前的1塊，所以沒(méi)有意外，話務(wù)員3會(huì)接受聽(tīng)眾1的點(diǎn)歌請(qǐng)求，并更新本地的記錄信息。

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

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

平行宇宙2

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

那么在這條時(shí)間線中，我們讓聽(tīng)眾2先打給1、2號(hào)話務(wù)員。

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

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

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

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

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

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

平行宇宙β

讓我們把分叉點(diǎn)上的時(shí)間，再往前多回溯一點(diǎn)，回到下面這個(gè)時(shí)間點(diǎn)的狀態(tài)，這時(shí)話務(wù)員2剛接受了聽(tīng)眾1的點(diǎn)歌請(qǐng)求，而聽(tīng)眾2還沒(méi)有開(kāi)始打熱線電話。

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

可想而知，聽(tīng)眾2的報(bào)價(jià)會(huì)被兩位話務(wù)員都認(rèn)可。

在收到了半數(shù)以上話務(wù)員的報(bào)價(jià)認(rèn)可后，聽(tīng)眾2先向話務(wù)員1發(fā)起點(diǎn)歌請(qǐng)求。

話務(wù)員1比對(duì)一下報(bào)價(jià)，嗯，沒(méi)有問(wèn)題，更新本地的記錄，接受他的點(diǎn)歌請(qǐng)求。

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

但是這個(gè)節(jié)骨眼上，聽(tīng)眾2的室友喊他了，說(shuō)：聽(tīng)歌多沒(méi)意思，咱們一起來(lái)打一局刀塔吧。

聽(tīng)眾2一想，沒(méi)毛病，那我先不點(diǎn)歌了。

而這時(shí)，聽(tīng)眾1回過(guò)神來(lái)了，他在之前報(bào)價(jià)階段可是獲得過(guò)半數(shù)以上的認(rèn)可的，于是他帶著之前被認(rèn)可的報(bào)價(jià)打電話進(jìn)來(lái)點(diǎn)歌。

可是在兩位話務(wù)員那里，記錄的最高報(bào)價(jià)已經(jīng)升到了兩塊了，于是聽(tīng)眾1的點(diǎn)歌請(qǐng)求會(huì)被拒絕。

到這，我們梳理一下，聽(tīng)眾1的點(diǎn)歌請(qǐng)求得到了1個(gè)接受、2個(gè)拒絕，也就是說(shuō)他的提議沒(méi)有被過(guò)半數(shù)以上的話務(wù)員接受。

無(wú)奈，聽(tīng)眾1只能回到第一階段，從報(bào)價(jià)開(kāi)始再重頭走一遍流程。并且這次，他把報(bào)價(jià)提升到了3塊。

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

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

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

最終，在沒(méi)有其他聽(tīng)眾中途打進(jìn)電話干擾的情況下，三位話務(wù)員都會(huì)接受聽(tīng)眾1的點(diǎn)歌請(qǐng)求。

最終，聽(tīng)眾1的點(diǎn)歌請(qǐng)求收到超過(guò)半數(shù)話務(wù)員的接受，于是他確認(rèn)《簡(jiǎn)單愛(ài)》這首歌會(huì)被選中。

最后

前面提到過(guò)，Paxos算法中的選舉過(guò)程就像是一場(chǎng)博弈，場(chǎng)上局勢(shì)瞬息萬(wàn)變。

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

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

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

在這種情況下，可能會(huì)有兩個(gè)聽(tīng)眾交替報(bào)價(jià)成功，卻提議歌曲失敗，形成一個(gè)活鎖的局面。如果這樣下去，有可能一整天下來(lái)，一首歌曲都沒(méi)有被最終選取成功。

所以在某些情況下，需要選取一個(gè)主提案者，只有主提案者才能和過(guò)半的接受者進(jìn)行通信提出提案。

說(shuō)白了，也就是我們常說(shuō)的話事人。

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

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

畢竟蘭伯特大佬都說(shuō)了：

論文原文：

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