Paxos算法

**Paxos 算法**是萊斯利・蘭伯特（英語：Leslie Lamport，LaTeX 中的「La」）於 1990 年提出的一種基於消息傳遞且具有高度容錯特性的共識（consensus）算法。

需要注意的是，Paxos 常被誤稱為「一致性算法」。但是「一致性（consistency）」和「共識（consensus）」並不是同一個概念。Paxos 是一個共識（consensus）算法。

## 問題和假設

分布式系統中的節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。基於消息傳遞通信模型的分布式系統，不可避免的會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重複。在最普通的 Paxos 場景中，先不考慮可能出現「消息篡改」（即拜占庭錯誤的情況）。Paxos 算法解決的問題是在一個可能發生前述異常（即排除消息篡改之外的其他任何異常）的分布式系統中，如何對某個值的看法相同，保證無論發生以上任何異常，都不會破壞決議的共識機制。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「共識算法」以保證每個節點看到的指令一致。一個通用的共識算法可以應用在許多場景中，是分布式計算中的重要問題。因此從 20 世紀 80 年代起對於共識算法的研究就沒有停止過。

為描述 Paxos 算法，Lamport 虛擬了一個叫做 Paxos 的希臘城邦，這個島按照議會民主制的政治模式制訂法律，但是沒有人願意將自己的全部時間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務員都不能承諾別人需要時一定會出現，也無法承諾批准決議或者傳遞消息的時間。但是這裡假設沒有拜占庭將軍問題（Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現錯誤的消息）；只要等待足夠的時間，消息就會被傳到。另外，Paxos 島上的議員是不會反對其他議員提出的決議的。

對應於分布式系統，議員對應於各個節點，制定的法律對應於系統的狀態。各個節點需要進入一個一致的狀態，例如在獨立 Cache 的對稱多處理器系統中，各個處理器讀內存的某個字節時，必須讀到同樣的一個值，否則系統就違背了一致性的要求。一致性要求對應於法律條文只能有一個版本。議員和服務員的不確定性對應於節點和消息傳遞通道的不可靠性。

## 算法

### 算法的提出與證明

首先將議員的角色分為 proposers，acceptors，和 learners（允許身兼數職）。proposers 提出提案，提案信息包括提案編號和提議的 value；acceptor 收到提案後可以接受（accept）提案，若提案獲得多數派（majority）的 acceptors 的接受，則稱該提案被批准（chosen）；learners 只能「學習」被批准的提案。劃分角色後，就可以更精確的定義問題：

1. 決議（value）只有在被 proposers 提出後才能被批准（未經批准的決議稱為「提案（proposal）」）；
2. 在一次 Paxos 算法的執行實例中，只批准（chosen）一個 value；
3. learners 只能獲得被批准（chosen）的 value。

```
在 Leslie Lamport 之後發表的paper中將 majority 替換為更通用的 quorum 概念，但在描述classic paxos的論文  Paxos made simple（頁面存檔備份，存於網際網路檔案館） 中使用的還是majority的概念。
```

另外還需要保證 progress。這一點以後再討論。

作者通過不斷加強上述 3 個約束（主要是第二個）獲得了 Paxos 算法。

批准 value 的過程中，首先 proposers 將 value 發送給 acceptors，之後 acceptors 對 value 進行接受（accept）。為了滿足只批准一個 value 的約束，要求經「多數派（majority）」接受的 value 成為正式的決議（稱為「批准」決議）。這是因為無論是按照人數還是按照權重劃分，兩組「多數派」至少有一個公共的 acceptor，如果每個 acceptor 只能接受一個 value，約束 2 就能保證。

於是產生了一個顯而易見的新約束：

```
P1：一个 acceptor 必须接受（accept）第一次收到的提案。
```

注意 P1 是不完備的。如果恰好一半 acceptor 接受的提案具有 value A，另一半接受的提案具有 value B，那麼就無法形成多數派，無法批准任何一個 value。

約束 2 並不要求只批准一個提案，暗示可能存在多個提案。只要提案的 value 是一樣的，批准多個提案不違背約束 2。於是可以產生約束 P2：

```
P2：一旦一个具有 value v 的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v。
```

註：通過某種方法可以為每個提案分配一個編號，在提案之間建立一個全序關係，所謂「之後」都是指所有編號更大的提案。

如果 P1 和 P2 都能夠保證，那麼約束 2 就能夠保證。

批准一個 value 意味著多個 acceptor 接受（accept）了該 value。因此，可以對 P2 進行加強：

```
P2a：一旦一个具有 value v 的提案被批准（chosen），那么之后任何 acceptor 再次接受（accept）的提案必须具有 value v。
```

由於通信是異步的，P2a 和 P1 會發生衝突。如果一個 value 被批准後，一個 proposer 和一個 acceptor 從休眠中甦醒，前者提出一個具有新的 value 的提案。根據 P1，後者應當接受，根據 P2a，則不應當接受，這種場景下 P2a 和 P1 有矛盾。於是需要換個思路，轉而對 proposer 的行為進行約束：

```
P2b：一旦一个具有 value v 的提案被批准（chosen），那么以后任何 proposer 提出的提案必须具有 value v。
```

由於 acceptor 能接受的提案都必須由 proposer 提出，所以 P2b 蘊涵了 P2a，是一個更強的約束。

但是根據 P2b 難以提出實現手段。因此需要進一步加強 P2b。

假設一個編號為 m 的 value v 已經獲得批准（chosen），來看看在什麼情況下對任何編號為 n（n>m）的提案都含有 value v。因為 m 已經獲得批准（chosen），顯然存在一個 acceptors 的多數派 C，他們都接受（accept）了 v。考慮到任何多數派都和 C 具有至少一個公共成員，可以找到一個蘊涵 P2b 的約束 P2c：

```
P2c：如果一个编号为 n 的提案具有 value v，该提案被提出（issued），那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n 
的任何提案，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。
```

可以用數學歸納法證明 P2c 蘊涵 P2b：

假設具有 value v 的提案 m 獲得批准，當 n=m+1 時，採用反證法，假如提案 n 不具有 value v，而是具有 value w，根據 P2c，則存在一個多數派 S1，要麼他們中沒有人接受過編號小於 n 的任何提案，要麼他們已經接受的所有編號小於 n 的提案中編號最大的那個提案是 value w。由於 S1 和通過提案 m 時的多數派 C 之間至少有一個公共的 acceptor，所以以上兩個條件都不成立，導出矛盾從而推翻假設，證明了提案 n 必須具有 value v；

若（m+1）..（N-1）所有提案都具有 value v，採用反證法，假如新提案 N 不具有 value v，而是具有 value w', 根據 P2c，則存在一個多數派 S2，要麼他們沒有接受過 m..（N-1）中的任何提案，要麼他們已經接受的所有編號小於 N 的提案中編號最大的那個提案是 value w'。由於 S2 和通過 m 的多數派 C 之間至少有一個公共的 acceptor，所以至少有一個 acceptor 曾經接受了 m，從而也可以推出 S2 中已接受的所有編號小於 n 的提案中編號最大的那個提案的編號範圍在 m..（N-1）之間，而根據初始假設，m..（N-1）之間的所有提案都具有 value v，所以 S2 中已接受的所有編號小於 n 的提案中編號最大的那個提案肯定具有 value v，導出矛盾從而推翻新提案 N 不具有 value v 的假設。根據數學歸納法，我們證明了若滿足 P2c，則 P2b 一定滿足。

P2c 是可以通過消息傳遞模型實現的。另外，引入了 P2c 後，也解決了前文提到的 P1 不完備的問題。

### 算法的內容

要滿足 P2c 的約束，proposer 提出一個提案前，首先要和足以形成多數派的 acceptors 進行通信，獲得他們進行的最近一次接受（accept）的提案（prepare 過程），之後根據回收的信息決定這次提案的 value，形成提案開始投票。當獲得多數 acceptors 接受（accept）後，提案獲得批准（chosen），由 acceptor 將這個消息告知 learner。這個簡略的過程經過進一步細化後就形成了 Paxos 算法。

在一個 paxos 實例中，每個提案需要有不同的編號，且編號間要存在全序關係。可以用多種方法實現這一點，例如將序數和 proposer 的名字拼接起來。如何做到這一點不在 Paxos 算法討論的範圍之內。

如果一個沒有 chosen 過任何 proposer 提案的 acceptor 在 prepare 過程中回答了一個 proposer 針對提案 n 的問題，但是在開始對 n 進行投票前，又接受（accept）了編號小於 n 的另一個提案（例如 n-1），如果 n-1 和 n 具有不同的 value，這個投票就會違背 P2c。因此在 prepare 過程中，acceptor 進行的回答同時也應包含承諾：不會再接受（accept）編號小於 n 的提案。這是對 P1 的加強：

```
P1a：当且仅当acceptor没有回应过编号大于n的prepare请求时，acceptor接受（accept）编号为n的提案。
```

現在已經可以提出完整的算法了。

#### 決議的提出與批准

通過一個決議分為兩個階段：

1. prepare 階段：
  1. proposer 選擇一個提案編號 n 並將 prepare 請求發送給 acceptors 中的一個多數派；
  2. acceptor 收到 prepare 消息後，如果提案的編號大於它已經回復的所有 prepare 消息 (回復消息表示接受 accept)，則 acceptor 將自己上次接受的提案回復給 proposer，並承諾不再回復小於 n 的提案；
2. 批准階段：
  1. 當一個 proposer 收到了多數 acceptors 對 prepare 的回覆後，就進入批准階段。它要向回復 prepare 請求的 acceptors 發送 accept 請求，包括編號 n 和根據 P2c 決定的 value（如果根據 P2c 沒有已經接受的 value，那麼它可以自由決定 value）。
  2. 在不違背自己向其他 proposer 的承諾的前提下，acceptor 收到 accept 請求後即批准這個請求。

這個過程在任何時候中斷都可以保證正確性。例如如果一個 proposer 發現已經有其他 proposers 提出了編號更高的提案，則有必要中斷這個過程。因此為了優化，在上述 prepare 過程中，如果一個 acceptor 發現存在一個更高編號的提案，則需要通知 proposer，提醒其中斷這次提案。

#### 實例

用實際的例子來更清晰地描述上述過程：

有 A1, A2, A3, A4, A5 5 位議員，就稅率問題進行決議。議員 A1 決定降稅率，因此它向所有人發出一個草案。這個草案的內容是：

```
现有的税率是什么?如果没有决定，我来决定一下. 提出时间：本届议会第3年3月15日;提案者：A1
```

在最簡單的情況下，沒有人與其競爭；信息能及時順利地傳達到其它議員處。

於是，A2-A5 回應：

```
我已收到你的提案，等待最终批准
```

而 A1 在收到 2 份回復後就發布最終決議：

```
税率已定为10%,新的提案不得再讨论本问题。
```

這實際上退化為二階段提交協議。

現在我們假設在 A1 提出提案的同時，A5 決定將稅率定為 20%:

```
现有的税率是什么?如果没有决定，我来决定一下.时间：本届议会第3年3月16日;提案者：A5
```

草案要通過侍從送到其它議員的案頭. A1 的草案將由 4 位侍從送到 A2-A5 那裡。現在，負責 A2 和 A3 的侍從將草案順利送達，負責 A4 和 A5 的侍從則不上班. A5 的草案則順利的送至 A4 和 A3 手中。

現在，A1, A2, A3 收到了 A1 的提案；A4, A3, A5 收到了 A5 的提案。按照協議，A1, A2, A4, A5 將接受他們收到的提案，侍從將拿著

```
我已收到你的提案，等待最终批准
```

的回覆回到提案者那裡。

而 A3 的行為將決定批准哪一個。

在討論之前我們要明確一點，提案是全局有序的。在這個示例中，是說每個提案提出的日期都不一樣。即第 3 年 3 月 15 日只有 A1 的提案；第 3 年 3 月 16 日只有 A5 的提案。不可能在某一天存在兩個提案。

##### 情況一

假設 A1 的提案先送到 A3 處，而 A5 的侍從決定放假一段時間。於是 A3 接受並派出了侍從. A1 等到了兩位侍從，加上它自己已經構成一個多數派，於是稅率 10% 將成為決議. A1 派出侍從將決議送到所有議員處：

```
税率已定为10%,新的提案不得再讨论本问题。
```

A3 在很久以後收到了來自 A5 的提案。由於稅率問題已經討論完畢，開始討論某些議員在第 3 年 3 月 17 日提出的議案。因此這個 3 月 16 日提出的議案他不去理會。他自言自語地抱怨一句：

```
这都是老问题了，没有必要讨论了。
```

##### 情況二

依然假設 A1 的提案先送到 A3 處，但是這次 A5 的侍從不是放假了，只是中途耽擱了一會。這次，A3 依然會將 "接受" 回復給 A1. 但是在決議成型之前它又收到了 A5 的提案。則：

1. 如果 A5 提案的提出時間比 A1 的提案更晚一些，這裡確實滿足這種情況，因為 3 月 16 日晚於 3 月 15 日。，則 A3 回覆：

```
我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%,请明察。
```

於是，A1 和 A5 都收到了足夠的回覆。這時關於稅率問題就有兩個提案在同時進行。但是 A5 知道之前有人提出稅率為 10%. 於是 A1 和 A5 都會向全體議員廣播：

```
 税率已定为10%,新的提案不得再讨论本问题。
```

共識到了保證。

2. 如果 A5 提案的提出時間比 A1 的提案更早一些。假設 A5 的提案是 3 月 14 日提出，則 A3 直接不理會。

```
 A1不久后就会广播税率定为10%.
```

#### 決議的發布

一個顯而易見的方法是當 acceptors 批准一個 value 時，將這個消息發送給所有 learners。但是這個方法會導致消息量過大。

由於假設沒有 Byzantine failures，learners 可以通過別的 learners 獲取已經通過的決議。因此 acceptors 只需將批准的消息發送給指定的某一個 learner，其他 learners 向它詢問已經通過的決議。這個方法降低了消息量，但是指定 learner 失效將引起系統失效。

因此 acceptors 需要將 accept 消息發送給 learners 的一個子集，然後由這些 learners 去通知所有 learners。

但是由於消息傳遞的不確定性，可能會沒有任何 learner 獲得了決議批准的消息。當 learners 需要了解決議通過情況時，可以讓一個 proposer 重新進行一次提案。注意一個 learner 可能兼任 proposer。

#### Progress 的保證

根據上述過程當一個 proposer 發現存在編號更大的提案時將終止提案。這意味著提出一個編號更大的提案會終止之前的提案過程。如果兩個 proposer 在這種情況下都轉而提出一個編號更大的提案，就可能陷入活鎖，違背了 Progress 的要求。一般活鎖可以通過 **隨機睡眠 - 重試** 的方法解決。這種情況下的解決方案是選舉出一個 leader，僅允許 leader 提出提案。但是由於消息傳遞的不確定性，可能有多個 proposer 自認為自己已經成為 leader。Lamport 在 The Part-Time Parliament（頁面存檔備份，存於網際網路檔案館）一文中描述並解決了這個問題。

## Multi-Paxos

Paxos 的典型部署需要一組連續的被接受的值（value），作為應用到一個分布式狀態機的一組命令。如果每個命令都通過一個 Basic Paxos 算法實例來達到一致，會產生大量開銷。

如果 Leader 是相對穩定不變的，第 1 階段就變得不必要。 這樣，系統可以在接下來的 Paxos 算法實例中，跳過第 1 階段，直接使用同樣的 Leader。

為了實現這一目的，在同一個 Leader 執行每輪 Paxos 算法時，提案編號 I 每次遞增一個值，並與每個值一起發送。Multi-Paxos 在沒有故障發生時，將消息延遲 (從 propose 階段到 learn 階段) 從 4 次延遲降低為 2 次延遲。

### Multi-Paxos 中消息流的圖形表示

#### Multi-Paxos 沒有失敗的情況

在下面的圖中，只顯示了基本 Paxos 協議的一個實例 (或「執行」) 和一個初始 Leader (Proposer)。注意，Multi-Paxos 使用幾個 Basic Paxos 的實例。

```
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
   |         |          |  |  |       |  |
```

式中 V = (Va, Vb, Vc) 中最新的一個。

#### 跳過階段 1 時的 Multi-Paxos

在這種情況下，Basic Paxos 的後續實例 (由 I+1 表示) 使用相同的 Leader，因此，包含在 Prepare 和 Promise 的階段 1 (Basic Paxos 協議的這些後續實例) 將被跳過。注意，這裡要求 Leader 應該是穩定的，即它不應該崩潰或改變。

```
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
   |         |          |  |  |       |  |
```

## Fast-Paxos

Fast-Paxos 將 Basic-Paxos 進行了推廣，以減少端到端消息延遲。在 Basic-Paxos 中，從客戶端發起請求開始，到 Learn 階段結束的消息延遲是 3 個消息延遲。而 Fast-Paxos 允許 2 個消息延遲，但要求：

(1) 系統由 _3f+ 1_ 個 Acceptor 組成，以容忍最多 _f_ 個錯誤 (而不是 Basic-Paxos 的 _2f+1_)；

(2) 客戶端需要直接將請求發送到多個目標。

直觀上，如果 Leader 沒有提議任何 value，那麼客戶可以直接發送 _Accept_ 消息到向接收方發。Acceptor 會像 Basic-Paxos 一樣運行，向 Leader 和每個 Learner 發送 _Accepted_ 的消息，從而實現從客戶端到 Learner 的兩消息延遲。

如果 Leader 檢測到衝突，它通過發起新一輪投票，並發送 _Accept_ 消息來解決衝突，通常是一個 _Accepted_ 消息。這種有協調者參與的衝突恢復機制需要 4 個從客戶端到 Learner 的消息延遲。

如果 Leader 提前指定了一種衝突恢復機制，就可以實現另一種優化，它允許 Acceptors 自己執行衝突恢復。因此，無協調的衝突恢復可能實現三個消息延遲 (如果所有的 Learner 都是接收者，那麼只有兩個消息延遲)。

### 消息流: Fast-Paxos，無衝突

```
Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |
```

### 消息流：Fast-Paxos，衝突的建議

有協調這參與的衝突恢復。注意：協議沒有指定如何處理被丟棄的客戶端請求。

```
Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      X------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |
```

無協調者參與的相衝突恢復：

```
Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |
```

### 消息流：無協調者的衝突恢復、角色崩潰的 Fast-Paxos

(合併的 Acceptor/Learner)

```
Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X<>X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |
```

 

## 應用

微軟公司為簡化的 Paxos 算法申請了專利。但專利中公開的技術和本文所描述的不盡相同。

谷歌公司（Google 公司）在其分布式鎖服務中應用了 Multi-Paxos 算法。Chubby lock 應用於大表（Bigtable），後者在谷歌公司所提供的各項服務中得到了廣泛的應用。

谷歌公司（Google 公司）在其分布式資料庫 spanner 中使用 Multi-Paxos 作為分布式共識保證的基礎組件

Apache ZooKeeper 使用一個類 Multi-Paxos 的共識算法作為底層存儲協同的機制。

## 參考文獻

## 外部連結

* The Part-Time Parliament（頁面存檔備份，存於網際網路檔案館） ── Lamport 於 1998 年發表在 ACM Transactions on Computer Systems。

　
: 註：這是該算法第一次公開發表。

* Paxos Made Simple（頁面存檔備份，存於網際網路檔案館），2001 年。

　
: 註：Lamport 覺得同行無法接受他的幽默感，於是用容易接受的方法重新表述了一遍。

* Pinewiki 對 Paxos 算法的介紹