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