Paxos分布式系統(tǒng)共識(shí)算法？我愿稱其為點(diǎn)歌算法…
點(diǎn)擊關(guān)注公眾號(hào)，Java干貨及時(shí)送達(dá)??
分布式系統(tǒng)共識(shí)算法Paxos相信大家都不陌生，它被稱為最難理解的算法不是沒有道理的，首先，它的發(fā)表之路就充滿了坎坷。
1990年，萊斯利·蘭伯特大佬寫了一篇論文，舉了一個(gè)城邦選舉的例子來介紹Paxos算法，然而大佬的幽默感并未得到審稿人的認(rèn)可，論文未發(fā)表成功…
1998年，蘭伯特重新發(fā)表論文《The Part-Time Parliament》描述算法，然而眾多學(xué)者并不買賬，直呼看不懂…
2001年，蘭伯特對(duì)算法的描述進(jìn)行簡(jiǎn)化，再次發(fā)表 《Paxos Made Simple》，這次Paxos成為了世界公認(rèn)最優(yōu)秀的分布式系統(tǒng)共識(shí)算法…
其實(shí)說白了，Paxos算法要解決的問題是一個(gè)分布式系統(tǒng)如何就某個(gè)值決議達(dá)成一致。比如說，一組進(jìn)程現(xiàn)在正在提議某個(gè)數(shù)據(jù)的值，需要通過消息傳遞的方式使這個(gè)值達(dá)成一致，也就是最終僅能有一個(gè)值被選定。
但畢竟是大佬寫出來的東西，且不說邏輯推理部分，就算單拎出來論文中對(duì)兩個(gè)核心階段的描述來說，我等凡人理解起來也還是有些困難。
不信？那就讓英語六級(jí)的我先來簡(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)過的任何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í)，只要它還沒有響應(yīng)編號(hào)比n更高的prepare請(qǐng)求，那么它將接受該提案。
是不是還看不懂？那就對(duì)了，下面我們通過一個(gè)簡(jiǎn)單的例子來描述這個(gè)過程。
記得小時(shí)候，有不少廣播電臺(tái)可以通過電話點(diǎn)歌，打電話給話務(wù)員告訴她你要點(diǎn)的歌，接下來就會(huì)播放。當(dāng)然了，這個(gè)過程不是免費(fèi)的，肯定有不少小伙伴在月末父母交話費(fèi)的時(shí)候，慘遭過社會(huì)的毒打。
既然是電臺(tái)熱線，那么肯定不只有一個(gè)話務(wù)員了，我們假定這個(gè)電臺(tái)同時(shí)存在3個(gè)話務(wù)員，并且她們之間是相互沒有交流的，那么當(dāng)短時(shí)間內(nèi)打進(jìn)來很多電話時(shí)，要怎么決定放哪首歌呢？
首先，話務(wù)員之間遵從少數(shù)服從多數(shù)，那么為了獲得更多話務(wù)員的支持，你可以不斷給更多的話務(wù)員打電話。
其次，前面我們說過，這個(gè)過程是收費(fèi)的，假定存在一條潛規(guī)則，電臺(tái)會(huì)更偏向于接受出價(jià)高的人的點(diǎn)歌請(qǐng)求，那么也就好辦了，你可以使了勁地加錢。
在這種環(huán)境下，聽眾想要點(diǎn)歌成功的話，就得靠上面兩個(gè)辦法。
這時(shí)，第一個(gè)聽眾打進(jìn)來電話了，在第一個(gè)階段聽眾只能進(jìn)行報(bào)價(jià)，還不能提出自己想要聽什么歌，這個(gè)報(bào)價(jià)就可以理解為算法中的編號(hào)n。
因?yàn)槁牨?是第一個(gè)打進(jìn)熱線電話的，在他之前還不存在任何報(bào)價(jià)，所以這里話務(wù)員們會(huì)無條件地先接受第一個(gè)聽眾的報(bào)價(jià)并記錄下來，然后返回給聽眾1一個(gè)回復(fù)信息。
在回復(fù)的信息中，話務(wù)員不但需要告訴聽眾他的報(bào)價(jià)目前最高，已經(jīng)被認(rèn)可了，還要說明之前沒有接受過其他任何聽眾的點(diǎn)歌請(qǐng)求。
這時(shí)候聽眾1一看，自己已經(jīng)獲得了超過半數(shù)以上的話務(wù)員的認(rèn)可了，那么進(jìn)入階段2，告訴話務(wù)員自己想要聽什么歌曲。當(dāng)然，在這個(gè)過程中，還得順帶著告訴話務(wù)員自己在上一階段中的報(bào)價(jià)是多少。
于是，聽眾1再次打進(jìn)熱線，先單獨(dú)向話務(wù)員2發(fā)起了選歌提議。
在收到聽眾1的點(diǎn)歌請(qǐng)求后，話務(wù)員2看到聽眾1在請(qǐng)求中攜帶的之前報(bào)價(jià)是1塊，滿足大于等于自己記錄的最大報(bào)價(jià)這一條件，于是果斷接受聽眾1的點(diǎn)歌請(qǐng)求。
在接受點(diǎn)歌請(qǐng)求后，話務(wù)員2要記錄的東西又要增加了，她不但要記住已接受的請(qǐng)求的報(bào)價(jià)金額，還要記住已接受請(qǐng)求的點(diǎn)播歌曲。然后給聽眾1一個(gè)回復(fù)，表示我已經(jīng)接受了你的點(diǎn)歌請(qǐng)求。
當(dāng)然了，在聽眾1努力點(diǎn)歌的時(shí)候，其他聽眾也不會(huì)閑著對(duì)不對(duì)？
聽眾2雖然打進(jìn)電話晚了點(diǎn)，但是直接發(fā)動(dòng)鈔能力，把自己的報(bào)價(jià)提升到了兩塊，來和話務(wù)員們進(jìn)行通話。
由于兩塊錢的報(bào)價(jià)高于本地記錄的最高報(bào)價(jià)，所以話務(wù)員1和話務(wù)員2都會(huì)認(rèn)可這個(gè)報(bào)價(jià)，所以她們會(huì)先把本地的最高報(bào)價(jià)值更新為兩塊。
但是接下來，由于本地記錄的信息有所不同，所以她們將會(huì)給出不同的答復(fù)。
如果這時(shí)候，再來一個(gè)聽眾3打進(jìn)電話，并且嘗試以兩塊或以下的價(jià)格進(jìn)行報(bào)價(jià)給前兩個(gè)話務(wù)員的話，那么他的報(bào)價(jià)不會(huì)得到話務(wù)員的認(rèn)可。
這是因?yàn)槲覀兦懊嬲f過了，話務(wù)員們都遵循拜金主義這一潛規(guī)則，所以她們不會(huì)接受比已記錄的最高報(bào)價(jià)還要低的報(bào)價(jià)。
在拒絕了聽眾3之后，我們?cè)倩氐角懊娴膬晌宦牨娺@邊。
接下來，我們根據(jù)聽眾1和2誰先打進(jìn)電話，把時(shí)間線劃分為兩個(gè)平行宇宙。
平行宇宙1
在平行宇宙1這條時(shí)間線里，我們假設(shè)聽眾1先打進(jìn)電話。
這時(shí)，仍然只有話務(wù)員2接受了聽眾1的點(diǎn)歌請(qǐng)求，于是聽眾1繼續(xù)向其他話務(wù)員撥打電話，告訴她們自己要聽的歌。
在話務(wù)員3這里，她記錄的最高報(bào)價(jià)還是聽眾1之前的1塊，所以沒有意外，話務(wù)員3會(huì)接受聽眾1的點(diǎn)歌請(qǐng)求，并更新本地的記錄信息。
但是話務(wù)員1這就不一樣了，她所認(rèn)可的報(bào)價(jià)已經(jīng)漲到了2，所以舊的1塊錢報(bào)價(jià)已經(jīng)不能在她這里點(diǎn)歌了，因此話務(wù)員1會(huì)拒絕聽眾1的點(diǎn)歌請(qǐng)求。
盡管請(qǐng)求沒有得到話務(wù)員1的接受，但是前面我們說了，話務(wù)員之間要遵循少數(shù)服從多數(shù)的原則，聽眾1的點(diǎn)歌請(qǐng)求已經(jīng)被半數(shù)以上話務(wù)員接受，那么聽眾1確認(rèn)自己點(diǎn)的這首《東風(fēng)破》已被選定。
平行宇宙2
讓我們回到平行宇宙的分叉點(diǎn)，先回顧一下前情，這時(shí)聽眾2已經(jīng)向話務(wù)員1和話務(wù)員2發(fā)出過報(bào)價(jià)，并從話務(wù)員2那里得知她已經(jīng)以1塊錢的報(bào)價(jià)接受了《東風(fēng)破》這首歌的提案。
那么在這條時(shí)間線中，我們讓聽眾2先打給1、2號(hào)話務(wù)員。
聽眾2這時(shí)心里會(huì)想，我們杰迷們都是有素質(zhì)的人，盡管我之前想聽的是《簡(jiǎn)單愛》，但聽一下《東風(fēng)破》貌似也挺不錯(cuò)，那么我干脆支持聽眾1的選擇吧。
于是，報(bào)價(jià)已被認(rèn)可的他再次拿起電話打給兩位話務(wù)員，發(fā)起點(diǎn)歌請(qǐng)求。
話務(wù)員1和話務(wù)員2再次比較聽眾2這次攜帶的之前報(bào)價(jià)，均大于等于本地記錄的最高報(bào)價(jià)，所以接受他的點(diǎn)歌請(qǐng)求。在更新本地記錄的信息后，回復(fù)信息給聽眾2。
于是，聽眾2的點(diǎn)歌請(qǐng)求也獲得了半數(shù)以上話務(wù)員的承認(rèn)，那么聽眾2確認(rèn)自己點(diǎn)的歌被選定。
看到這里，是不是似乎感覺世界線產(chǎn)生了收束，難道之后的每一種結(jié)果都是《東風(fēng)破》將被選定？
其實(shí)，Paxos算法中最精彩的部分在于它更像是一場(chǎng)博弈，棋局中的每一步，都可能影響最終的結(jié)果。
平行宇宙β
讓我們把分叉點(diǎn)上的時(shí)間，再往前多回溯一點(diǎn)，回到下面這個(gè)時(shí)間點(diǎn)的狀態(tài)，這時(shí)話務(wù)員2剛接受了聽眾1的點(diǎn)歌請(qǐng)求，而聽眾2還沒有開始打熱線電話。
這次，我們站在上帝視角，讓聽眾2改變一下選擇，既然話務(wù)員2已經(jīng)被別人收買了，那么干脆避其鋒芒，直接向話務(wù)員1、3報(bào)價(jià)。
可想而知，聽眾2的報(bào)價(jià)會(huì)被兩位話務(wù)員都認(rèn)可。
在收到了半數(shù)以上話務(wù)員的報(bào)價(jià)認(rèn)可后，聽眾2先向話務(wù)員1發(fā)起點(diǎn)歌請(qǐng)求。
話務(wù)員1比對(duì)一下報(bào)價(jià)，嗯，沒有問題，更新本地的記錄，接受他的點(diǎn)歌請(qǐng)求。
講道理，現(xiàn)在的形勢(shì)對(duì)聽眾2真的是一片大好，只要再打個(gè)電話給話務(wù)員3，就能夠成功點(diǎn)歌了。
但是這個(gè)節(jié)骨眼上，聽眾2的室友喊他了，說：聽歌多沒意思，咱們一起來打一局刀塔吧。
聽眾2一想，沒毛病，那我先不點(diǎn)歌了。
而這時(shí)，聽眾1回過神來了，他在之前報(bào)價(jià)階段可是獲得過半數(shù)以上的認(rèn)可的，于是他帶著之前被認(rèn)可的報(bào)價(jià)打電話進(jìn)來點(diǎn)歌。
可是在兩位話務(wù)員那里，記錄的最高報(bào)價(jià)已經(jīng)升到了兩塊了，于是聽眾1的點(diǎn)歌請(qǐng)求會(huì)被拒絕。
到這，我們梳理一下，聽眾1的點(diǎn)歌請(qǐng)求得到了1個(gè)接受、2個(gè)拒絕，也就是說他的提議沒有被過半數(shù)以上的話務(wù)員接受。
無奈，聽眾1只能回到第一階段，從報(bào)價(jià)開始再重頭走一遍流程。并且這次，他把報(bào)價(jià)提升到了3塊。
三位話務(wù)員收到新的報(bào)價(jià)請(qǐng)求后，都會(huì)表示認(rèn)可，并且返回自己本地記錄的信息。
聽眾1這一次收到的三條報(bào)價(jià)認(rèn)可中，有兩條攜帶了之前被接受的點(diǎn)歌信息。那么新問題來了，他應(yīng)該選哪一首歌曲作為自己接下來要點(diǎn)播的歌曲呢？
在這里，聽眾要遵循的規(guī)則其實(shí)和話務(wù)員一致，他需要在這些返回的報(bào)價(jià)及歌曲信息中，選擇最高報(bào)價(jià)的歌曲，作為自己的接下來選歌的依據(jù)，因此他最終會(huì)選擇《簡(jiǎn)單愛》。
最終，在沒有其他聽眾中途打進(jìn)電話干擾的情況下，三位話務(wù)員都會(huì)接受聽眾1的點(diǎn)歌請(qǐng)求。
最終，聽眾1的點(diǎn)歌請(qǐng)求收到超過半數(shù)話務(wù)員的接受，于是他確認(rèn)《簡(jiǎn)單愛》這首歌會(huì)被選中。
最后
前面提到過，Paxos算法中的選舉過程就像是一場(chǎng)博弈，場(chǎng)上局勢(shì)瞬息萬變。
回顧一下上面3條不同的時(shí)間線，打進(jìn)電話順序的不同、選擇的話務(wù)員不同，都可能導(dǎo)致最終產(chǎn)生不同的結(jié)果。
而Paxos算法本身，并不關(guān)注最終選擇的是哪一個(gè)結(jié)果，它關(guān)注的是無論如何，在最后一定要能夠達(dá)成一個(gè)共識(shí)。
當(dāng)然了，也有可能遇到下面這種無法解決的情況…
在這種情況下，可能會(huì)有兩個(gè)聽眾交替報(bào)價(jià)成功，卻提議歌曲失敗，形成一個(gè)活鎖的局面。如果這樣下去，有可能一整天下來，一首歌曲都沒有被最終選取成功。
所以在某些情況下，需要選取一個(gè)主提案者，只有主提案者才能和過半的接受者進(jìn)行通信提出提案。
說白了，也就是我們常說的話事人。
那么，我們最后再做一個(gè)總結(jié)，其實(shí)在我看來，Paxos算法的關(guān)鍵，就在于后者要認(rèn)同前者，來避免無休止的爭(zhēng)端。
本文也只是對(duì)決議部分的兩階段通過示例進(jìn)行了說明，并忽略了算法中另一個(gè)角色學(xué)習(xí)者的內(nèi)容，如果有興趣的話，大家不妨去看看論文原文。
畢竟蘭伯特大佬都說了：
論文原文：
http://lamport.azurewebsites.net/pubs/paxos-simple.pdf
2. 設(shè)計(jì)了一個(gè)支撐 數(shù)億 用戶的系統(tǒng)
最近面試BAT，整理一份面試資料《Java面試BATJ通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點(diǎn)“在看”，關(guān)注公眾號(hào)并回復(fù) Java 領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
PS：因公眾號(hào)平臺(tái)更改了推送規(guī)則，如果不想錯(cuò)過內(nèi)容，記得讀完點(diǎn)一下“在看”，加個(gè)“星標(biāo)”，這樣每次新文章推送才會(huì)第一時(shí)間出現(xiàn)在你的訂閱列表里。
點(diǎn)“在看”支持小哈呀，謝謝啦
