1 Multi-Paxos

樸素Paxos算法通過多輪的Prepare/Accept過程來確定一個值，Lamport稱這整個過程為一個Instance。Multi-Paxos是通過Paxos算法來確定很多個值，而且這些值的順序在各個節(jié)點完全一致。概括來講就是確定一個全局順序。

1.1 確定多個值

多個Instance怎么運(yùn)作？首先我們先構(gòu)建最簡易的模式，各個Instance獨立運(yùn)作下面的例子引自知乎Paxos理論介紹(2): Multi-Paxos與Leader的Multi-Paxos部分。

image

每個Instance獨立運(yùn)作一個樸素Paxos算法，我們保證僅當(dāng)Instance i的值被確定后，方可進(jìn)行i+1的Paxos算法，這樣我們就保證了Instance的有序性。

但這樣效率是比較差的，眾所周知樸素Paxos算法的Latency很高，Multi-Paxos算法希望找到多個Instance的Paxos算法之間的聯(lián)系，從而嘗試在某些情況去掉Prepare步驟。

2 Multi-Paxos算法描述

下面我嘗試描述一個Sample的演進(jìn)情況來闡述這個算法，因為這個算法的要點其實非常簡單，而且無需更多證明。

首先我們定義Multi-Paxos的參與要素：

• 3個參與節(jié)點 A/B/C.
• Prepare(b)=Prepare(bal) NodeA節(jié)點發(fā)起Prepare攜帶的編號。
• Promise(b)=Promise(bal) NodeA節(jié)點承諾的編號。
• Accept(b)=Accept(bal) NodeA節(jié)點發(fā)起Accept攜帶的編號。

1(A)的意思是A節(jié)點產(chǎn)生的編號1，2(B)代表編號2由B節(jié)點產(chǎn)生。綠色表示Accept通過，紅色表示拒絕。

下圖描述了A/B/C三個節(jié)點并行提交的演進(jìn)過程：

image

這種情況下NodeA節(jié)點幾乎每個Instance都收到其他節(jié)點發(fā)來的Prepare，導(dǎo)致Promise編號過大，迫使自己不斷提升編號來Prepare。這種情況并未能找到任何的優(yōu)化突破口。

下圖描述了只有A節(jié)點提交的演進(jìn)過程：

image

這種情況我們會立刻發(fā)現(xiàn)，在沒有其他節(jié)點提交的干擾下，每次Prepare的編號都是一樣的。于是乎我們想，為何不把Promised(b)變成全局的？來看下圖：

image

假設(shè)我們在Instance i進(jìn)行Prepare(b)，我們要求對這個b進(jìn)行Promise的生效范圍是Instance[i, ∞)，那么在i之后我們就無需在做任何Prepare了?？上攵?，假設(shè)上圖Instance 1之后都沒有任何除NodeA之外其他節(jié)點的提交，我們就可以預(yù)期接下來Node A的Accept都是可以通過的。那么這個去Prepare狀態(tài)什么時候打破？我們來看有其他節(jié)點進(jìn)行提交的情況：

image

Instance 4出現(xiàn)了B的提交，使得Promised(b)變成了2(B), 從而導(dǎo)致Node A的Accept被拒絕。而NodeA如何繼續(xù)提交？必須得提高自己的Prepare編號從而搶占Promised(b)。這里出現(xiàn)了很明顯的去Prepare的窗口期Instance[1,3]，而這種期間很明顯的標(biāo)志就是只有一個節(jié)點在提交。

2.1 Leader的作用

不Prepare直接Accept為啥是安全的

在一個Leader提交proposal的前提下，不會有其他Proposer提交，那么就不會出現(xiàn)Acceptor promised的最大編號大于proposal中所帶編號的情況，同樣也不會出現(xiàn)Acceptor accept的編號大于proposal中所帶編號的情況。因此這么做是安全的。

不Prepare直接Accept有什么好處

To achieve this, the round number I is included along with each value which is incremented in each round by the same Leader. Multi-Paxos reduces the failure-free message delay (proposal to learning) from 4 delays to 2 delays.
這句不太會翻譯，但大概的意思應(yīng)該就是：Multi-Paxos通過改變Promised(b)的生效范圍至全局的Instance，從而使得一些唯一節(jié)點的連續(xù)提交獲得去Prepare的效果。

2.1 選舉一個Leader

下面是知乎文章中介紹的一個方法，個人感覺這個沒有一個標(biāo)準(zhǔn)的設(shè)計，暫時參考這個。

為何還要說Leader，雖然Multi-Paxos允許并行提交，但這種情況下效率是要退化到樸素Paxos的，所以我們并不希望長時間處于這種情況，Leader的作用是希望大部分時間都只有一個節(jié)點在提交，這樣才能最大發(fā)揮Mulit-Paxos的優(yōu)化效果。

怎么得到一個Leader，真的非常之簡單，Lamport的論文甚至的不屑一提。我們觀察Multi-Paxos算法，首先能做Accept(b)必然是b已經(jīng)被Promised了，而連續(xù)的Accept(b)被打斷，必然是由于Promised(b)被提升了，也就是出現(xiàn)了其他節(jié)點的提交(提交會先Prepare從而提升b)。那么重點來了，如何避免其他節(jié)點進(jìn)行提交，我們只需要做一件事即可完成。

收到來自其他節(jié)點的Accept，則進(jìn)行一段時間的拒絕提交請求。

這個解讀起來就是各個節(jié)點都想著不要去打破這種連續(xù)的Accept狀態(tài)，而當(dāng)有一個節(jié)點在連續(xù)的Accept，那么其他節(jié)點必然持續(xù)不斷的拒絕請求。這個Leader就這樣無形的被產(chǎn)生出來了，我們壓根沒有刻意去“選舉”，它就是來自于Multi-Paxos算法。

題外話：為何網(wǎng)上出現(xiàn)很多非常復(fù)雜的選舉Leader算法，有的甚至利用Paxos算法去選舉Leader，我覺的他們很有可能是沒有完全理解Multi-Paxos，走入了必須有Leader這個誤區(qū)。

用Paxos算法來進(jìn)行選舉是有意義的，但不應(yīng)該用在Leader上面。Paxos的應(yīng)用除了寫之外，還有很重要的一環(huán)就是讀，很多時候我們希望要讀到Latest，通常的做法就是選舉出一個Master。Master含義是在任一時刻只能有一個節(jié)點認(rèn)為自己是Master，在這種約束下，讀寫我都在Master上進(jìn)行，就可以獲得Latest的效果。Master與Leader有本質(zhì)上的區(qū)別，要達(dá)到Master這種強(qiáng)一致的唯一性，必須得通過強(qiáng)一致性算法才能選舉出來。而當(dāng)我們實現(xiàn)了Paxos算法后，選舉Master也就變得非常簡單了，會涉及到一些租約的東西，后面再分享。

3 算法示例

正常執(zhí)行成功

Multi-Paxos實際上是Basic Baxos的多instance執(zhí)行。下圖是一個初始的Leader（實際上是一個Proposer）執(zhí)行一次Basic Baxos的過程。

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

where V = last of (Va, Vb, Vc).

Phase 1 去掉之后的Multi-Paxos

在這個case中，接下來的instance（第I+1個instance）都使用的同一個Leader，因此直接跳過了phase1（接下來instance中Basic Paxos協(xié)議的phase 1，即省略prepare階段），其中Leader應(yīng)該是穩(wěn)定的，不能宕機(jī)或者故障。

這里出現(xiàn)故障應(yīng)該只是退化到Basic Paxos的情況。

Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Multi-Paxos when roles are collapsed

A common deployment of the Multi-Paxos consists in collapsing the role of the Proposers, Acceptors and Acceptors to "Servers". So, in the end, there are only "Clients" and "Servers".
意思就是Proposers，Acceptors，Acceptors沒有明確的角色區(qū)分，統(tǒng)稱為Servers。Server可以扮演以上三種任何角色，這樣部署起來就只有Clients和Servers區(qū)分。

Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N, I, {Va, Vb})
   |         X->|->|  Accept!(N, I, Vn)
   |         X<>X<>X  Accepted(N, I)
   |<--------X  |  |  Response
   |         |  |  |

Leader固定之后的一個instance

固定Leader之后，且角色合并成了Server跟Client。

Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N,I+1,W)
   |         X<>X<>X  Accepted(N,I+1)
   |<--------X  |  |  Response
   |         |  |  |