15分鐘入門Paxos

Paxos Made Simple(以下縮寫PMS)還是太長了，我們需要繼續對其進行閹割

synod演算法

synod演算法中有兩種角色，proposer和acceptor。兩者數量不必是1:1的。

一項議案可以進行很多輪(在下面把輪次記作proposal number)投票。每一輪投票，proposer都可以提出proposal(我們把proposal的內容稱為value)。

synod演算法可以保證：

• 對於同一個proposal number，所有的acceptor都只會accept相同的value
• 一項議案，在proposal number為N時，形成了決議，proposal number大於N的所有proposal的value都和決議的value相同。也就是一旦形成決議，value就不再會改變。

最簡單的情形，當然是假設所有proposer和acceptor都是老實的。假如有proposer或acceptor不老實，synod演算法就沒法工作了。

對於proposer來說，每一輪投票要分兩個階段。

+-------+----------+----------+| phase | proposer | acceptor |+-------+----------+----------+| 1 | prepare | promise |+-------+----------+----------+| 2 | propose | accept | (PMS里是accept/accepted)+-------+----------+----------+

定義proposer和acceptor之間的消息格式

-type promised() :: {proposal_number(), proposer()}.-type accepted() :: {proposal_number(), proposer(), value()}.-type request() :: {prepare, promised()} | {propose, accepted()}.-type reply() :: ok | {ok, promised()} %% | {ok, accepted()} | {ok, promised(), accepted()}.

PMS里沒有要求，但是曾博已經決定了，一個老實的acceptor在收到來自proposer的請求時，無論是否處理這個請求，都要告訴proposer，當前，promise過的proposal number最高的prepare請求，以及accept過的proposal number最高的propose請求，的內容分別是什麼。

Prepare階段

一個老實的proposer在發出propose之前，必須收到來自過半acceptor的promise。而一輪投票，一個老實的acceptor最多只會promise一個老實的proposer。根據抽屜原理，一輪投票，最多只有一個proposer能發出propose。這樣就保證了第一點。

舉個例子，一個老實的proposer p想得到第3輪投票的propose機會

p : {prepare, {3,p}} a b c d e propose?promised {3,p} {3,p} {3,p} {4,q} {5,r} Ypromised {3,q} {3,q} {3,r} {3,r} {3,p} N

消息格式里，一個值得注意的細節是，有一行被注釋掉了。一輪投票里，一個acceptor只收到過propose請求，但是從沒有收到過prepare請求的情況是存在的。

acceptor a b c d epromised x x xaccepted x x x

因為收到propose請求就表明，該輪能發propose請求的proposer已經決出了。所以一個老實的acceptor假裝已經收到過來自同一個proposer的prepare請求是不會導致錯誤的。

Propose階段

一個老實的proposer是不可以隨心所欲的propose任意value的。假如根據收到的reply里，可以看出有propose請求被accept過了，那麼就只能propose，proposal number最高的那個的value

p : {3,p,rock} a b c d e proposeaccepted {1,q,paper} {2,r,scissors} none x x {3,p,scissors}accepted none none none x x {3,p,rock}

而一個老實的acceptor在promise proposal number為N的prepare請求後，就不再處理proposal number小於N的所有請求。

一個老實的proposer，只有在一輪投票中收到來自過半的acceptor的accept之後，才能認為自己知道了這項議案的決議內容。

舉個例子，比如proposer p要能收到過半的accept，那麼其向acceptor c發送的propose請求，必須先於q的prepare請求被c處理。

a b c d ep:3:propose x x xq:4:prepare x x x

於是同樣根據抽屜原理，下一個能propose的proposer，必然會propose相同的value。

a b c d ex x x x x x x x

因為propose的是相同的value，所以無論是否能過半，後面的proposer在能propose時，看到的被accept的proposal number最高的propose請求的value都仍然是這個value。這樣就保證了第二點。

退避

理解了synod演算法，按最naive的方式實現，在現實中往往會變成這樣。

a b c d e1 p p q r s2 r t s q q3 s p r q r

不斷的重複開始prepare，沒有一個proposer有機會propose。為什麼？因為synod演算法，並不保證一定會形成決議啊。

一種應對方法是，沒搶到propose機會，proposer應該過一段時間再去搶下一輪。假如連續幾輪沒搶到，這個時間間隔應該是越來越大的。這種方法還是比較難以理解的。

一種更簡單的方法是，沒搶到propose機會，proposal number應該加一個隨機數，而proposer應該更加老實一點，假如看到有acceptor promise了別的proposer的prepare請求，proposer應該協助當前看到的proposal number最高的prepare請求的proposer，代其向acceptor發prepare請求。這也就是為什麼 promised() 里第二個元素是 proposer() 。

這種方法有個致命的缺陷就是，假如搶到propose機會的proposer，並沒有value需要propose，那就完全卡在那裡了。所以，我們修改請求格式，假如一個proposer沒啥需要propose的，那就peek，別prepare。

-type request() :: peek | {prepare, promised()} | {propose, accepted()}.

這樣，假如別的proposer搶到propose機會，半天沒動靜，那隻可能是那個proposer出問題了，那趕緊重新搶吧。

多副本狀態機

C1 C2 C3S0 ----> S1 ----> S2 ----> S3

單個狀態機，收到命令之後，執行命令，變成下一個狀態。而多副本的狀態機，需要先把命令寫入日誌，之後在各個狀態機副本里，執行日誌里記錄的命令。

可以藉助Synod演算法同步狀態機的日誌。日誌里每一條記錄，對應一項議案。一個老實的proposer和一個acceptor組成一個老實的節點。proposer從日誌的第一條記錄開始，逐條讀取對應的議案的決議。沒有命令需要寫入日誌就peek，有就prepare。假如當前議案的決議是別的proposer提交的命令，那麼要在下一項議案里重試。

因為一項議案只能一個決議。而節點卻有很多，所以通常會把多條命令合併到一條狀態機日誌里。

成員變更

這也可以看成是一個狀態機。狀態是一個集合。初始狀態是所有bootstrap節點。命令是加入一個節點和刪除一個節點。

因為proposer和acceptor數量不必是1:1的。新節點加入時，完全可以用自己的proposer來propose加入的命令。只是在propose之前，必須獲取從第一條日誌開始的所有日誌，並重放，且向同節點的acceptor發相應的propose請求。

加入節點的命令寫入後，新的節點裡的acceptor就正式加入了。刪除節點則可以由任意一個proposer來發起。

快照

因為節點個數是動態變化的，儘管不頻繁。可是總有一天，過半bootstrap節點會退出。此時，假如還是要求從第一條日誌開始重放，新的節點就再也加不進去了。

所以，我們要求老實的狀態機，必須定時生成snapshot，並告訴老實的節點，這個snapshot是在第N條日誌之前生成的。

成員狀態機的狀態應該改成，節點到N的映射。所有節點當前最小的N之前日誌都是可以切掉的。

結語

Paxos最簡單的形態就這麼點內容，剛好15分鐘。