Paxos 分布式必問的內(nèi)容，沒有之一
Google Chubby 的作者 Mike Burrows 說過：There is only one consensus protocol, and that's Paxos.
引言
上文我們已經(jīng)詳細的闡述了共識問題并介紹了一些共識算法，其中 Paxos 算法是 Leslie Lamport 于 1990 年提出的共識算法，不幸的是采用希臘民主議會的比喻很明顯失敗了，Lamport 像寫小說一樣，把一個復雜的數(shù)學問題弄成了一篇帶有考古色彩的歷史小說。根據(jù)?Lamport 自己的描述[1]，三個審稿者都認為該論文盡管并不重要但還有些意思，只是應該把其中所有 Paxos 相關(guān)的故事背景刪掉。Lamport 對這些缺乏幽默感的人感到生氣，所以他不打算對論文做任何修改。
多年后，兩個在 SRC(Systems Research Center，DEC 于 1984 年創(chuàng)立，Lamport 也曾在此工作過)工作的人需要為他們正在構(gòu)建的分布式系統(tǒng)尋找一些合適算法，而 Paxos 恰恰提供了他們想要的。Lamport 就將論文發(fā)給他們，他們也沒覺得該論文有什么問題。
因此，Lamport 覺得論文重新發(fā)表的時間到了，"The Part-Time Parliament[2]" 最終在 1998 年公開發(fā)表。
可是很多人抱怨這篇論文根本看不懂啊，人們只記住了那個奇怪的故事，而不是 Paxos 算法。Lamport 走到哪都要被人抱怨一通。于是他忍無可忍，2001 年重新發(fā)表了一篇關(guān)于 Paxos 的論文——"Paxos Made Simple[3]"，這次論文中一個公式也沒有，摘要也只有一句話：
The Paxos algorithm, when presented in plain English, is very simple.
滿滿的都是嘲諷！
然而，可能是表述順序的原因，這篇論文還是非常難以理解，于是人們寫了一系列文章來解釋這篇論文（重復造論文），以及在工程上如何實現(xiàn)它。
其中，個人認為講解 Paxos 最好的視頻[4]來自于 Raft 算法作者 Diego Ongaro，本文采用 Diego 講義中的圖片來理解 Paxos 算法，也糾正了一個個人認為 Diego 筆誤的地方。
術(shù)語
基本概念
?Proposal Value：提案的值；?Proposal Number：提案編號；?Proposal：提案 = 提案編號 + 提案的值；?Chosen：批準，也叫選定。一旦某個值被 Chosen，后續(xù) Paxos 都必須用該值進行交互。
注：Proposal 有人叫“提議”有人叫“提案”，此處和維基百科里的翻譯保持一致，叫“提案”。
角色
?Proposer：提案發(fā)起者；?Acceptor：提案接收者；?Learner：提案學習者；
問題描述
為了高可用性，一種常見的設(shè)計是用一個 master 節(jié)點來寫，然后復制到各個 slave 節(jié)點。這種解決方法的問題在于，一旦 master 節(jié)點故障，整個服務將不可用或者數(shù)據(jù)不一致。
為了克服單點寫入問題，于是有了多數(shù)派（Quorum）寫，思路就是寫入一半以上的節(jié)點。即，如果集群中有 N 個節(jié)點，客戶端需要寫入 W >= N/2 + 1 個節(jié)點。不需要主節(jié)點。這種方法可以容忍最多 (N-1)/2 個節(jié)點故障。
但是問題依然存在：每個接收者該如何決定是否接受這次請求的值呢？
如果我們接受第一次收到的值，那么當出現(xiàn)以下情況（Split Votes），則沒有出現(xiàn)多數(shù)派，沒有一個值被 Chosen，算法無法終止，這違反了活性（liveness）。
為了解決 Split Votes 問題，我們允許接受多個不同的值，收到的每一個(every)請求都接受，這時候新的問題出現(xiàn)了，如下，可能不止一個值被 Chosen，這違反了安全性（safety）。
注意，Paxos 強調(diào)：
Once a value has been chosen, future proposals must propose the same value.
也就是說，我們討論的 Basic-Paxos 只會 Chosen 一個值?；诖?，就需要一個兩階段（2-phase）協(xié)議，對于已經(jīng) Chosen 的值，后面的提案也要使用相同的值。
如下圖這種情況，S3 直接拒絕?red?值，因為?blue?已經(jīng) Chosen，這樣就可以保證成功。
這種方式我們需要對提案進行排序。如果你熟悉分布式系統(tǒng)，應該能想到 "Time, Clocks and the Ordering of Events in a Distributed System[5]" 這篇論文，我們不能用時間來判斷提案的先后順序。
Proposal Number
一種簡單的方式就是每個請求一個唯一的編號，例如：seq_id?是自增的；同時為了避免崩潰重啟，必須能在本地持久化存儲。
Paxos
現(xiàn)在我們終于可以開始描述 Paxos 算法了。
如上所述，Paxos 是一個兩階段算法。我們把第一個階段叫做準備（Prepare）階段，第二個階段叫做接受（Accept）階段。分別對應兩輪 RPC。
第一輪 Prepare RPCs：
請求（也叫 Prepare 階段）：
Proposer 選擇一個提案編號 n，向所有的 Acceptor 廣播?Prepare(n)?請求。
這里 Prepare（n）不包含提案的值。
偽代碼：
send PREPARE(++n)響應（也叫 PROMISE 階段）：
Acceptor 接收到?Prepare（n)?請求，此時有兩種情況：
?如果 n 大于之前接受到的所有 Prepare 請求的編號，則返回?Promise()?響應，并承諾將不會接收編號小于 n 的提案。如果有提案被 Chosen 的話，Promise()?響應還應包含前一次提案編號和對應的值。?否則（即 n 小于等于 Acceptor 之前收到的最大編號）忽略，但常常會回復一個拒絕響應。
所以，Acceptor 需要持久化存儲 max_n、accepted_N 和 accepted_VALUE
偽代碼：
if (n > max_n)max_n = n // save highest n we've seen so farif (proposal_accepted == true) // was a proposal already accepted?respond: PROMISE(n, accepted_N, accepted_VALUE)elserespond: PROMISE(n)elsedo not respond (or respond with a "fail" message)
第二輪 Accept RPCs：
請求（也叫 PROPOSE 階段）：
當 Proposer 收到超過半數(shù) Acceptor?的?Promise()?響應后，Proposer 向多數(shù)派的 Acceptor 發(fā)起?Accept(n, value)?請求并帶上提案編號和值。（注：這里講義的算法流程圖是向所有的 Acceptor 發(fā)起?Accept()?請求，鄙人認為應該改為向多數(shù)派 Acceptor 發(fā)起。）
注意：Proposer 不一定是將?Accept()?請求發(fā)給有應答的多數(shù)派 Acceptors，可以再選另一個多數(shù)派 Acceptors 廣播?Accept()?請求。
關(guān)于值 value 的選擇：如果前面的 Promise 響應有返回?accepted_VALUE，那就使用這個值作為 value。如果沒有返回?accepted_VALUE，那可以自由決定提案值 value。
偽代碼：
did I receive PROMISE responses from a majority of acceptors?if yesdo any responses contain accepted values (from other proposals)?if yesval = accepted_VALUE // value from PROMISE message with the highest accepted IDif noval = VALUE // we can use our proposed valuesend Accept(ID, val) to at least a majority of acceptors
響應（也叫 ACCEPT 階段）：
Acceptor 收到?Accept()?請求，在這期間如果 Acceptor 沒有對比 n 更大的編號另行 Promise，則接受該提案。
偽代碼：
if (n >= max_n) // is the n the largest I have seen so far?proposal_accepted = true // note that we accepted a proposalaccepted_N = n // save the accepted proposal numberaccepted_VALUE = VALUE // save the accepted proposal datarespond: Accepted(N, VALUE) to the proposer and all learnerselsedo not respond (or respond with a "fail" message)
一些例子
情況 1：提案已 Chosen
1.S1 收到客戶端提案請求 X，于是 S1 向 S1-S3 發(fā)起?Prepare(3.1)?請求，PROMISE()?響應返回沒有提案被 Chosen2.由于 S1-S3 沒有任何提案被 Chosen，S1 繼續(xù)向 S1-S3 發(fā)送?Accept(3.1, X)?請求，提案被成功 Chosen3.在提案被 Chosen 后，S5 收到客戶端提案值為 Y 的請求，向 S3-S5 發(fā)送?Prepare(4.5)?請求，由于編號 4 > 3 會收到提案值為 X 已經(jīng)被 Chosen 的?PROMISE()?響應4.于是 S5?將提案值 Y 替換成 X，向 S1-S3 發(fā)送?Accept(4.5, X)?請求，提案再次被 Chosen
情況 2：提案未 Chosen，Proposer 可見
情況 2 和情況 1 類似，在 S3 Chosen 了提案后，S5 收到來自 S3 的?PROMISE()?響應包含了已經(jīng) Chosen 的提案值 X，所以同樣會將提案值替換成 X，最終所有 Acceptor 對 X 達成共識。
注意上面的偽代碼：do any responses contain accepted values，也就是說只要有一個 Acceptor 在?Promise()?響應中返回了提案值，就要用它來替換提案值。
情況 3：提案未提交，Proposer 不可見
情況 3 中，提案只被 S1 Chosen，S3 還未 Chosen 該提案，S3-S5 的?Promise()?響應中沒有任何提案信息，所以 S5 自行決定提案值為 Y，發(fā)送?Accept(4.5, Y)?請求。
由于此時 S3 承諾的提案編號 n 變?yōu)榱?4 且 4 大于 3，所以 S3 不再接受 S1 后續(xù)的?Accept(3.1, X)?請求。提案值 X 被阻止，而提案值 Y 最終被 Chosen。
活鎖
如圖：當 Proposer 在第一輪 Prepare 發(fā)出請求，還沒來得及后續(xù)的第二輪 Accept 請求，緊接著第二個 Proposer 在第一階段也發(fā)出編號更大的請求。如果這樣無窮無盡，Acceptor 始終停留在決定順序號的過程上，那大家誰也成功不了。
解決活鎖最簡單的方式就是引入隨機超時，這樣可以讓某個 Proposer 先進行提案，減少一直互相搶占的可能。
結(jié)語
Paxos 只從一個或多個值中選擇一個值，如果需要重復運行 Paxos 來創(chuàng)建復制狀態(tài)機，我們稱之為 multi-Paxos，但如果每個命令都通過一個Basic Paxos算法實例來達到一致，會產(chǎn)生大量開銷。對于 multi-Paxos 可以做一些優(yōu)化，我們在下篇文章中討論 Paxos 的變種。
References
[1]?Lamport 自己的描述:?http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxos[2]?The Part-Time Parliament:?https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf[3]?Paxos Made Simple:?https://lamport.azurewebsites.net/pubs/paxos-simple.pdf[4]?視頻:?https://www.youtube.com/watch?v=JEpsBg0AO6o[5]?Time, Clocks and the Ordering of Events in a Distributed System:?http://lamport.azurewebsites.net/pubs/time-clocks.pdf
后臺回復?學習資料?領(lǐng)取學習視頻
如有收獲，點個在看，誠摯感謝