paxos
聲明：
- 本文思路完成模仿 朱一聰 老師的的 如何淺顯易懂地解說 Paxos 而得促绵，版權(quán)屬于 朱一聰 老師 败晴。只是為了自己理解更加透徹稳懒，又重新推導了一下而已场梆。文章發(fā)出已經(jīng)獲得 朱一聰 老師的同意。
- 本文最后結(jié)論完全引用 Paxos Made Simple 中文翻譯版
- 學習 paxos 請優(yōu)先選擇 Paxos Made Simple 和 Paxos lecture装哆，不要選擇本文蜕琴。本文僅能起到引導思路的作用
- 文章肯定有不嚴謹，推導不嚴謹?shù)牡胤匠В瑲g迎討論凸郑。
背景：
在一個高可用分布式存儲系統(tǒng)中，如果只使用一臺機器而昨，只要這臺機器故障，系統(tǒng)就會崩潰务嫡。所以肯定需要多臺機器植袍，但是由于網(wǎng)絡延遲，機器崩潰等原因厅篓，多臺機器對于數(shù)據(jù)很難達成共識（Consensus not Consistency）。而 paxos 協(xié)議就是用來使各個機器達成共識的協(xié)議档押。
如何理解共識（Consensus）：
共識就是在一個或多個進程提議了一個值應當是什么后叼耙，使系統(tǒng)中所有進程對這個值達成一致意見筛婉。但是必須明確：在一個完全異步且可能出現(xiàn)任何故障的系統(tǒng)中，不存在一個算法可以確保達到共識（FLP Impossibility）硕勿。
前提:
需要保證安全性：
- 只有被提出的提案才能被選定
- 只能有一個值被選定
- 如果某個進程認為某個提案被選定了，那么這個提案必須是真的被選定的那個
可能出現(xiàn)的場景
- 進程之間的通信可能出現(xiàn)故障
- 每個進程都可能提出不同的值
- 每個進程也可能隨時崩潰
- 進程之間傳輸?shù)臄?shù)據(jù)不會篡改
達成共識的條件
N 個進程中大多數(shù)（超過一半）進程都選定了同一個值
推導流程
假設存在三個進程 p1 p2 p3，共同決定 v 的值
1.1 每個進程只接受收到的第一個提案
場景 1.1.1
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 無
假設是 p1 的 proposal 優(yōu)先到達 p3查排，p2 的 proposal 在到達 p3 時會被拒絕，系統(tǒng)就 v = a 達成了共識砂代，反之如果 p2 的 proposal 優(yōu)先到達，系統(tǒng)會就 v = b 達成共識捶箱。
場景 1.1.2
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: v = c
這樣每個機器只能接受自己機器上的 proposal，對于 v 的值就永遠不能達成共識了晨川。
結(jié)論 1.1：
- 進程必須能夠多次改寫 v 的值愧怜，否則可能永遠達不成共識
- 進程必須接受第一個 proposal赔桌，否則可能永遠達不成共識（系統(tǒng)只有一個提案時）
1.2 每個進程只接受 proposal_id 大的提案
根據(jù) 1.1 的結(jié)論疾党，進程必須接受第一個 proposal竭钝， 所以需要一種拒絕策略或者修正后到達的 proposal 的 value 我們需要額外的信息作為依據(jù)來完成。
- 我們得到哪些信息呢庇茫？
提出 proposal 進程的標識 process_id，當前進行到輪次 round_number（每個進程自增） - 這些信息有什么用宁炫？
這兩個信息加在一起標識唯一的 proposal
暫定 proposal_id = round_number + process_id - 如何更新 proposal_id？
每個 process 的 proposal_id = max(proposal_id, a_proposal_id)
場景 1.2.1
假設 p1_proposal_id > p2_proposal_id
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 無
如果 p1 proposal 先到達 p3 ，p2 后到達袍辞，會形成
p1 proposal：v = a
p2 proposal: v = a
p3 proposal: v = a
系統(tǒng)就 v = a 達成共識威创。
場景 1.2.2
如果 p2 proposal 先到達 p3 , p1 后到達，p3 會先接受 p2 proposal吸申，形成
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: v = b
系統(tǒng)就 v = b 達成共識，因為 p1 proposal 也已經(jīng)發(fā)出日丹，接著又會形成
p1 proposal：v = a
p2 proposal: v = a
p3 proposal: v = a
系統(tǒng)又就 v = a 達成了共識。
在這個策略中，有兩個值先后達成共識湘今，不滿足安全性。
結(jié)論 1.2：
按照現(xiàn)有 1.2 策略存在proposal id 小 proposal 先到達旗们，系統(tǒng)多次就不同的值達成共識的問題。從如下幾個角度思考解決此問題
- p3 可以拒絕 p2 proposal(p2 proposal 先到達 p3，p2_proposal_id < p1_proposal_id )
- 限制 p1 提出的 proposal
1.3 p3 可以拒絕 p2 proposal 角度
- 發(fā)送帶有 proposal_id PreProposal,
- 接收到 PreProposal 的進程隔披，根據(jù) proposal_id = max(proposal_id, accept_proposal_id) 進行更新
- 進程發(fā)送 proposal
- 每個進程只接受 proposal_id 大的 proposal
假設 p1_proposal_id > p2_proposal_id
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 無
場景 1.3.1
- p1_PreProposal 攜帶 p1_proposal_id 到達 p3
- P3 更新 p3_proposal_id 為 p1_proposal_id, P2 更新 p2_proposal_id 為 p1_proposal_id
- p2_PreProposal 攜帶 p2_proposal_id 到達，p2_proposal_id < p1_proposal_id谒拴，被拒絕。
- p1_proposal (v = a)到達 p2, p3
- 此時系統(tǒng)就 v = a 達成共識
- p1: v = a
- p2: v = a
- p3: v = a
場景 1.3.2
- p2_PreProposal 攜帶 p2_proposal_id 進行廣播，到達 p3
- P3 更新 p3_proposal_id 為 p2_proposal_id
- p2_proposal (v = b)到達 p3易遣，系統(tǒng)此時會就 v = b 達成共識
- p1: v = a
- p2: v = b
- p3: v = b
- p1_PreProposal 攜帶 p1_proposal_id 進行廣播侨歉，到達 p2, p3, p2_proposal_id < p1_proposal_id炮温，p2 p3 更新 proposal_id 為 p1_proposal_id
- p1_proposal (v = a)到達 p2, p3
- 此時系統(tǒng)就 v = a 達成共識
- p1: v = a
- p2: v = a
- p3: v = a
結(jié)論 1.3:
1.3 策略解決了一部分問題，但是還是依賴消息到達的先后順序担巩。在某些條件下還是不能保證安全性送火。
1.4 限制 p1 提出的 proposal
現(xiàn)在已知 process_id round_number种吸，還能得到哪些信息坚俗？
按照 1.3 的策略笨鸡，我們只是更新了接受 pre_proposal 的 accept_process 的 proposal_id 為較大的 proposal_id姜钳，并沒有回復給發(fā)送 pre_propoal 的 send_process 任何消息。是不是可以把 accept_process 已經(jīng)獲得的提案的 proposal_id 和 proposal 這樣是不是限制 send_process 接下來發(fā)送的 proposal 形耗？現(xiàn)在模擬一下流程哥桥，看看能否解決 1.3 中存在的問題激涤。
- 發(fā)送帶有 proposal_id 的 PreProposal
- 接收到 PreProposal 的進程拟糕，根據(jù) proposal_id = max(proposal_id, accept_proposal_id) 進行更新，并回復當前進程已經(jīng)接收到的 proposal_id
- 進程發(fā)送 proposal
- 每個進程只接受 proposal_id 大的 proposal
假設 p1_proposal_id > p2_proposal_id
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 無
場景 1.4.1
- p2_PreProposal 攜帶 p2_proposal_id 進行廣播倦踢，到達 p3
- P3 更新 p3_proposal_id 為 p2_proposal_id
- P3 給 P2回復 (p2_proposal_id, v=NULL)
- p2_proposal (v = b)到達 p3送滞，系統(tǒng)此時會就 v = b 達成共識
- p1: v = a
- p2: v = b
- p3: v = b
- p1_PreProposal 攜帶 p1_proposal_id 進行廣播，到達 p2, p3, p2_proposal_id < p1_proposal_id辱挥，p2 p3 更新 proposal_id 為 p1_proposal_id
- P3 回復 P1 (p2_proposal_id, v=b)
- P1 發(fā)現(xiàn) P3 已經(jīng)接受了 v = b犁嗅，把自己的提案 v = a 修改成 v = b
- p1_proposal (v = b)到達 p2, p3
- 此時系統(tǒng)還是就 v = b 達成共識
- p1: v = b
- p2: v = b
- p3: v = b
問題得到了解決。
上文所有的推導晤碘，全部來源于三個進程褂微，看似問題已經(jīng)解決。但是這個流程能否一般化园爷，應用于 N 個進程呢宠蚂？提案數(shù)從 2 到 N 呢？
泛化推導童社，
場景 1.5 進程數(shù)從 3 到 N
Pi 進程集合：提出 PreProposal-i求厕，Proposal-i(v = a)
Qi 進程集合：接受了 Proposal-i 的超半數(shù)進程
Pj 進程集合：提出 PreProposal-j，Proposal-j(v = b)
Qj 進程集合：接受了 Proposal-j 的超半數(shù)進程
Pk 進程集合：Qi 和 Qj 的進程集合交集
只要 Pk 能夠拒絕 Proposal-i 和 Proposal-j 的一個就是安全的
每個 Proposal-j-id < Proposal-i-id
- Proposal-j 到達部分進程扰楼，此時系統(tǒng)未達成共識
- PreProposal-i 到達部分進程呀癣，此時系統(tǒng)未達成共識
- 所有接收到 PreProposal-i 的進程回復（Proposal-j-id蝙眶， v = b）或者 （NULL棺妓， NULL） 給 Pi
- Pi 接受到（Proposal-j-id，v = b）模闲，將 Proposal-i 原先的 v = a 修改成 v = b腾节，然后進行廣播忘嫉。
- 系統(tǒng)就 v = b 達成共識。
場景 1.6 不同的 proposal 由 2 到 N
假設 j - i = N案腺，b - a = N
Pi Pi+1 ... Pi+N-1 Pj 每個進程組都會提出 Proposal(v = a, a+1, .. a+N-1, b) Proposal_id 大小順序相反
Qi -> Qj 與 Pi 相對
Pk 是收到了很多不同提案的進程的集合庆冕，但是一直沒有達成共識。
- Proposal-i+1 Proposal-i+2 到達 Pk劈榨，系統(tǒng)并沒有達成共識访递。
- PreProposal-j 發(fā)出到達部分進程
- 接收到 PreProposal-j 的進程選擇 [(Proposal-i+1-id, v = a + 1), (Proposal-i+2-id, v = a + 2)] 其中的一個或者兩個一起回復給 Pj
- Pj 應該選擇哪個 v 值修改自己的 proposal 呢
- 回顧前邊的邏輯，每個進程會拒絕 Proposal-id 較小的提案同辣，Proposal-i+1-id > Proposal-i+2-id
- Proposal-i+1-id 相比 Proposal-i+2-id 的提案肯定先到 Pk 的拷姿，系統(tǒng)還有一部分進程沒有接收到 (Proposal-i+1-id, v = a + 1)惭载，沒有就 (Proposal-i+1-id, v = a + 1) 形成共識
- 假設 Pj 選擇 proposal_id 較小的 proposal ，那么會選擇 （Proposal-i+2-id, v = a + 2) 响巢，在 Pj 發(fā)出 （Proposal-j, v = a + 2) 之前描滔，沒有收到 (Proposal-i+1-id, v = a + 1) 的進程可能恰好收到了，系統(tǒng)就 v = a + 1 達成了共識踪古。此后（Proposal-j, v = a + 2) 達到了含长， 系統(tǒng)又 v = a + 2 達成的共識。系統(tǒng)兩次達成共識伏穆，存在問題拘泞。
- 假設 Pj 選擇 proposal_id 較大的 proposal，那么會選擇 （Proposal-i+1-id, v = a + 1) 枕扫，在 Pj 發(fā)出 （Proposal-j, v = a + 1) 之前陪腌，沒有收到 (Proposal-i+1-id, v = a + 1) 的進程可能恰好收到了，系統(tǒng)就 v = a + 1 達成了共識烟瞧。此后（Proposal-j, v = a + 2) 達到了诗鸭，還是 v = a + 1。不存在問題燕刻。
- 系統(tǒng)選擇 proposal_id 較大的修改依據(jù)
- Pj 選擇 proposal_id 較大的 proposal只泼，修改 v = a + 1剖笙，并發(fā)出 （Proposal-j, v = a + 2）
- 系統(tǒng)就 v = a + 2 達成共識
不能覆蓋的場景
如果每次 proposal 被接受之前卵洗，先接受了攜帶較大 proposal-id 的 PreProposal，這樣每次都會拒絕即將成功的達成共識的 proposal 系統(tǒng)每次都不會達成共識弥咪。這個場景可以通過不斷重試解決过蹂。
paxos
Proposer： 發(fā)起提案的進程
Acceptor： 接受題提案的進程
一個進程可能充當多個角色
Phase 1:
- Proposer 選擇一個提案編號 n，然后向 Acceptors 的某個 majority 集合的成員發(fā)送編號為 n 的prepare請求聚至。
- 如果一個Acceptor收到一個編號為 n 的prepare請求酷勺，且 n 大于它已經(jīng)響應的所有prepare請求的編號，那么它就會保證不會再通過(accept)任何編號小于 n 的提案扳躬，同時將它已經(jīng)通過的最大編號的提案(如果存在的話)作為響應脆诉。
Phase 2
- 如果 Proposer 收到來自半數(shù)以上的 Acceptor 對于它的 prepare 請求(編號為 n)的響應，那么它就會發(fā)送一個針對編號為 n 贷币，value 值為 v 的提案的 accept 請求給 Acceptors击胜，在這里 v 是收到的響應中編號最大的提案的值，如果響應中不包含提案役纹，那么它就是任意值偶摔。
- 如果 Acceptor 收到一個針對編號 n 的提案的accept請求，只要它還未對編號大于 n 的 prepare 請求作出響應促脉，它就可以通過這個提案辰斋。
