Consensus， Paxos和RSM

來自專欄 Consensus5 人贊了文章

本文不是完整的Paxos介紹，而是討論中遇到的問題的一些整理。可以結合"Paxos Made Simple"一文來理解。

理解未必都正確，歡迎探討。

如何去理解Paxos？

按照Consensus、Paxos協議和基於Paxos的Replicated State Machine(RSM)去理解。

• Consensus，是Paxos的目標，即它要保證做什麼；
• 兩階段演算法，描述它如何做到的；
• 基於Paxos的RSM: 解釋如何應用於一個分散式系統。

Consensus 是什麼？

• Consensus(共識)是一種特性，需要在整個過程中都滿足。它不是一次決定/決議。
• 含義：要麼還沒有值被選中，要麼只有一個值被選中，一旦有值被選中後不會更改。

文中「值被選中」是什麼含義？ 舉個例子？

舉例：

假設在金庸描寫的江湖上中，每年只允許為大俠們辦一件婚姻大事(結婚、離婚)，由東邪、西毒、南帝、北丐、中通五人組成的委員會投票決定，超過半數接受就算通過。

那麼，今年到底辦哪件大事？七公提議"郭靖結婚"，歐陽鋒提議讓"楊康結婚"。最終選中的值，是」郭靖結婚「 或者 」楊康結婚「。 注意，選中的不是歐陽鋒，也不是七公，而是某件事。這不是在選盟主！

對 「值被選中」的理解有哪些誤區？

• 認為是某個成員當選Leader
• 認為就是下面所說的某個值被選中

Consensus是怎麼推出來的？

P1，P2等，分別與Paper中的相應標號對應。

Consensus是如何保證的？

幾個長老開個會就定了的事情，為什麼搞兩個階段？

長老們是講信譽的，做了集體決定不會反悔，即使其中三個做了決定，其他兩個不知情。但是長老們很忙，他們是這麼工作的：

• 喜歡自由和清凈，各居一方，不會同時工作 (網路上各個節點非同步工作)。
• 大家通過書信往來，但書信可能丟失 （網路通信不是絕對可靠的，可能丟包）
• 隨時可能去雲遊，長期收不到信，更不不回信，甚至某天突然歸西了 ( 短時間宕機或者機器徹底壞掉都是可能的)
• 沒有人會偽造信件

以上大致對應了Paxos對模型的假設。

Majority是什麼？ 有沒有簡單的例子？

• Majority/多數派，即半數以上(不含半數)。
• 為什麼要半數以上？先記住多數派的必然相交特性： 一個非空集合的任意兩個多數派子集，必然有交集。 後面會看到這個特性的用途。
• 舉例： 如果從一個40人的班級中，抽取21人參加籃球比賽，再抽取21參加足球比賽，那麼一定有人參加了兩項比賽。

我們就說今年的大事，能夠形成多次決議么？

• 允許多次形成決議
• 但是選定的值必須相同

Proposal Number和Value是綁定的么？

• Proposal包含Value和Proposal Number。
• 被選定的是value，它不會改變，但伴隨被選定的value的PN可能會改變。

Phase1的含義是什麼？

• 對Proposer:

如果我的PN為n，並且某個小於n的PN已經形成了決議(選定了值v)，那麼我提議的一定還是這個v，沒有違背Consensus(P2b)；

為什麼成立？ 前面說過，兩個多數派，必有交集;

• 對Acceptor來說:

承諾不會再接受 PN小於n的request，阻止在此後形成小於n的決議。只要超過半數的Acceptor都阻止，那麼肯定可以成功阻止。

Phase 1有什麼副作用？

• 如果之前沒形成決議，那麼也會按照PN最大的Value去提議(實際上在幫別人做嫁衣)。但是這沒有違背Consensus特性 。
• 實際上提議者不需要去判斷到底有沒有形成決議，判斷是非常困難的。

舉個例子說下RSM又是怎麼回事？

• 如果我們總說今年，那麼今年又是哪一年？ 如何構成有意義的歷史呢？到底郭靖和楊康，誰先結婚了？
• 我們把多個「今年」變成一系列有順序的年，比如從南宗慶元五年開始，每年辦一件大事，那就是一個有意義的序列，我們可以查其中任意一年，到底誰結婚了，誰離婚了，哪些還是夫妻。這就是狀態機。但是每年的決議，是獨立的。
• 如果我們把「年度」變成事件執行的「順序」，而不需要真的間隔一年才做一次決策，那麼就是真的狀態機了。

Paxos需要leader么？ 問什麼文中又提到了Leader?

• Paxos不需要Leader。
• 基於Paxos的RSM需要Leader。

RSM在保證什麼？

• 各個Replicator，按照相同的順序，去apply相同的value(即按照相同順序執行相同的操作）。雖然它們之間是非同步的。
• 按照相同的順序去apply value，是應用的語義的需求。它不是Consensu要保證的內容。

基於Paxos的 RSM正確性是怎麼保證的？

• 如果每年都用Paxos形成了唯一不可改的決定，而按照順序apply，那麼後面是不是就比較簡單了？

RSM為什麼需要Leader?

• 如果沒有leader，實際上沒法響應讀操作。不知道找誰讀，大家都難以知道到底哪些形成決議了。讀不是paxos的兩階段解決的問題，靠leader來解決。
• Leader選舉完成，會在一次消息中，完成所有未決Instance的Phase 1(無限個)，從而減小網路交互次數，在其當選Leader期間，後續的提議只需要執行Phase 2。

常有人說Paxos具有並行性，到底並行在哪一步？

• 一般是相對Raft來說的，Paxos的決議是可以並行形成的，比如可以先對2018年的大事形成決議，然後再對2017年的形成決議。但是執行是，仍然先執行2017年的。
• 並行在Acceptor去接受Value的地方。對比：Raft稱為AppendEntry，也就是前面的沒搞定，後面的不能Append。
• RSM可能認為只需要保證某一部分決議的apply順序即可，不用完全按照順序，這也是一種並行。但是這是應用的語義決定的，不是Paxos自身的內容。

推薦閱讀：