關於Paxos演算法，網上相關的文章很多，不過還是建議看lamport的原文。原文通過不斷加強約束，一步步的得到最後的結論，即：

For any v and n, if a proposal with value v and number n is issued,then

there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S .

我們以一個分散式的KV資料庫為例，分析Paxos的應用場景。首先，假設資料庫對外提供3種操作

  • Put
  • PutAppend
  • Get

Figure-1

在這樣的一個架構下，通過多臺server組成集羣來避免單點問題。但是，如圖所示的3臺server必須保持同步。也就是說，如果Client向集羣發送請求 Put("a", 1)並成功，那麼整個集羣中任意一臺server必須都含有數據("a", 1).

這裡的Put("a", 1)就是lamport論文中proposer提出的value，這個稍後解釋。對於資料庫集羣而言，所有的操作都是串列的，就像現在的資料庫都提供日誌功能一樣，每個操作都會記錄在日誌當中，並而是有先後順序的。如果我們的集羣先後收到3個操作請求，分別為

  • Put("a", 1)
  • Put("b", 2)
  • Put("c", 3)

那麼在對於資料庫集羣而言，應該有這麼一個表，類似為

+---+-------------+

|1 |Put("a", 1) |+---+-------------+|2 |Put("b", 2) |+---+-------------+

|3 |Put("c", 3) |

+---+-------------+

我們暫時稱它為狀態表。

這裡的標號1,2,3就對應論文中的Sequence。

下面我們就假設資料庫集羣是空的，即沒有任何數據。客戶端發送了上面3個請求，當然，這中間可能存在多個客戶端同時發送請求的情況。我們看看整個流程是怎麼樣的。

首先，假設Client1向集羣發送了Put("a", 1)， 這個請求雖然是發給集羣的，但實際上最後肯定會落實到某一個具體的server,這個過程可能通過負載均衡等方法得到，並不是我們關心的。我們就假設這個請求發到了server1。這時server1是空的，所以他查詢自己的狀態表，發現Seq1沒有對應的操作，按理說他可以將今天的第一個操作確定為Put("a", 1)，但由於它是集羣中的一份子，必須要協商一下。這個協商的過程，就是Paxos。他需要協商的問題是：

  • 第1個操作是否可以為Put("a", 1)

這裡的協商過程我們可以理解為一個函數, 函數的參數為操作的序號和操作，返回值為一個操作。

Op doPaxos(int seq, Op v){...}

這裡由於只有一個Client提出的操作的請求，不存在競爭，所以協商很順利，當server1調用這個協商函數的時候，返回的值就是它傳入的值，此時我們就可以認為集羣中的3臺server達成了一個共識，即集羣的第一個操作為Put("a", 1)。於是server1將自己的狀態表改

+---+-------------+

|1 |Put("a", 1) |+---+-------------+

需要注意的是，在協商的過程中，server2與server3也將自己的狀態表改為上面的樣子。這個狀態表同步的過程就是論文中的Learning階段。
可見，Paxos作為一致性演算法，在這裡例子當中保證的一致性其實就是狀態表的一致性。

有沒有協商不順利的情況呢？ 當然， 有！

這裡我們假設有出現了兩個客戶端，Client2和Client3。接著用上面的例子，Client2向集羣發送了請求Put("b", 2),假設這個請求最終到了server1上。同時， Client3向集羣發送了請求Put("c", 3), 假設這個求情發到了server2上。

Figure-2

此時server1和server2的狀態表是一樣的，這一點是由Paxos保證的。他們的不同之處在於：

  • server1的數據和server2不同，即server1裡麪包含一條數據，就是剛剛Client1請求的Put("a", 1), 但是server2是空的。
  • server1的sequence為2, 但是server2的sequence仍然為1。原因是server1已經做了一次Put操作，但是server2什麼都沒有做。

由於server1和server2的不同，因此他們處理各自請求的方式也不同。

先來看server2。server2從1開始遍歷自己的狀態表，發現1號操作非空，說明這是他遺漏的操作，於是server2也執行了操作Put("a", 1), 此時server2與server1的狀態完全一樣了。在此之後，server2會向上面server1一樣，調用doPaxos函數進行協商，即詢問集羣中的所有server咱們的第2個操作能否為Put("c", 3)

doPaxos(2, v);

其中v為 Put("c", 3)。

但就在此時，server1也調用了doPaxos進行協商，詢問集羣中的所有server第2個操作能否為Put("b", 2)。

這裡集羣中兩個server提出了不同的議題(lamport的論文中也使用了這種說法)，Paxos保證了最終會選出一個大家都同意的議題。我們這裡假設server1的議題最終被通過了。於是，集羣中所有server的狀態表都更新為

+---+-------------+

|1 |Put("a", 1) |+---+-------------+|2 |Put("b", 2) |+---+-------------+

並且server1向自己的database中插入("b", 2),並將自己的sequence更新為3.

而此時server2發現自己的狀態表中sequence2有了對應的操作，但很可惜不是自己提出的那個操作。這條信心表明集羣其實已經做了2個操作了，自己想要提出的這個操作Put("c", 3)已經不能作為集羣的第2個操作了。於是server2對自己的database進行Put("b", 2)操作, 然後將自己的sequence更新為3。再次調用doPaxos進行協商，試圖將自己的操作作為集羣的第3個操作，於是doPaxos的參數為

doPaxos(3, {Put("c", 3)})

此時由於只有一個提議，所以協商很順利。此時集羣中所有server的狀態表都為

+---+-------------+

|1 |Put("a", 1) |

+---+-------------+

|2 |Put("b", 2) |+---+-------------+|3 |Put("c", 3) |+---+-------------+

其中，server1包含2條數據，server2包含3條數據，server3為空。

我們假設此時Client1向集羣發送了Get("a")請求，並最終發到了server3。由於server3的sequence0為, 所以他會從1開始，將自己狀態表中的1,2,3號操作就執行一遍，直到到了sequence4時，發現狀態表為空，於是進行查詢操作，將結果返回Client。

由於Get是隻讀操作，因此沒必要協商，也沒必要將其寫入狀態表
推薦閱讀：
相關文章