一步一步理解Paxos算法

作者：jw （360電商技術組）

背景

Paxos 算法是Lamport于1990年提出的一種基于消息傳遞的一致性算法。由于算法難以理解起初并沒有引起人們的重視，使Lamport在八年后重新發表到 TOCS上。即便如此paxos算法還是沒有得到重視，2001年Lamport用可讀性比較強的敘述性語言給出算法描述。可見Lamport對 paxos算法情有獨鐘。近幾年paxos算法的普遍使用也證明它在分布式一致性算法中的重要地位。06年google的三篇論文初現“云”的端倪，其中的chubby鎖服務使用paxos作為chubby cell中的一致性算法，paxos的人氣從此一路狂飆。

Paxos是什么

Paxos 算法解決的問題是一個分布式系統如何就某個值（決議）達成一致。一個典型的場景是，在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們最后能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個“一致性算法”以保證每個節點看到的指令一致，是分布式計算中的重要問題。

Paxos的兩個原則

安全原則---保證不能做錯的事

1. 只能有一個值被批準，不能出現第二個值把第一個覆蓋的情況

2. 每個節點只能學習到已經被批準的值，不能學習沒有被批準的值

存活原則---只要有多數服務器存活并且彼此間可以通信最終都要做到的事

1. 最終會批準某個被提議的值

2. 一個值被批準了，其他服務器最終會學習到這個值

Paxos的兩個組件

Proposer

提議發起者，處理客戶端請求，將客戶端的請求發送到集群中，以便決定這個值是否可以被批準。

Acceptor

提議批準者，負責處理接收到的提議，他們的回復就是一次投票。會存儲一些狀態來決定是否接收一個值

Paxos定義

接下來用舉例的方式一步一步解釋Paxos為了完成一致性，必須要解決的一些問題。這里為了方便解釋，假設每一臺服務器都是一個Proposer，也是一個Acceptor

一個Acceptor

首先從最簡單的方式開始，假設只有一個Acceptor，讓它做決定是否批準一個值

如上圖，每一個proposer提議一個值給Acceptor來批準，然后Acceptor批準一個值作為最終的值。

但是這種簡單的方式，沒有辦法解決Acceptor crash的問題，如果唯一的Acceptor crash了，就沒有辦法知道哪個值被選擇了，就需要等待它重啟，這一條違反了存活原則，這個時候有4臺服務器存活，但已經沒有辦法工作了。

多個Acceptor

為了解決這個問題，就必須要用到一種多數選擇的方法。使用一個Acceptor的集合。然后只有其中的多數批準了一個值，這個值才可以確實是被最終被批準的。為了達到目的也需要一些技巧。

批準第一個達到的值

首先規定每個Acceptor必須批準第一個到達的值。哪個值達到多數批準就是最終批準的值

但是有一個問題，比如上圖，因為沒有值被多數批準，無法批準一個最終的值出來。這就需要Acceptor批準了一個值之后還要根據某種規則批準不同的值

批準每個提議的值

接下來規定Acceptor批準每個提議的值，但是這也會帶來一個問題，可能會批準出多個值

如圖，S1發出提議，S1，S2，S3批準 red為最終批準的值。S5隨后發出提議，s3，S4，S5批準，blue又為最終批準的值。此時S1，S2最終批準red，S3，S4，S5最終批準blue，這就違背了我們的一致性原則，最終只有一個值被選擇。

二段提交原則

要解決這個問題，就要S5在發送自己的提議之前，優先檢查有沒有已經被批準的值，如果有應該提議已經被批準的值而放棄自己的值，也就是放棄自己的blue改為提議red，這樣最終只有一個值被批準就是red。這個就是經典的二段提交原則。

不幸的是，二段提交還是存在另一個問題。

如圖，S1在發送提議之前，檢查沒有值被批準，因此提議red。但同時在所有Acceptor批準之前，S5也要進行提議，這個時候也檢查出沒有值被批準，所以它也把自己的blue作為提議發送給acceptor。接下來S5的提議優先到達S3，S4，S5，這些Acceptor先批準了blue，達到多數所以blue最終被批準了。但是隨后S1，S2，S3接收到了red進行批準。所以又出現了批準出多個值的問題。

提議排序

這個問題要解決，就需要一旦Acceptor批準了某個值，其他有沖突的值都應該被拒絕。也就是說S3隨后到達的red應該被拒絕，為了做到這一點。需要對Proposer進行排序，將排序在前的賦予高優先級，Acceptor批準優先級高的值，拒絕排序在后的值。

為了將提議進行排序，可以為每個提議賦予一個唯一的ID，規定這個ID越大，優先級越高

在提議者發送提議之前，就需要生成一個唯一的ID，而且需要比之前使用的或者生成的都要大

提議ID生成算法

在Google的Chubby論文中給出了這樣一種方法：假設有n個proposer，每個編號為ir(0<=ir<n)，proposor編號的任何值s都應該大于它已知的最大值，并且滿足：s %n = ir => s = m*n + ir

proposer已知的最大值來自兩部分：proposer自己對編號自增后的值和接收到acceptor的reject后所得到的值

以3個proposer P1、P2、P3為例，開始m=0,編號分別為0，1，2

1. P1提交的時候發現了P2已經提交，P2編號為1 > P1的0，因此P1重新計算編號：new P1 = 1*3+0 = 4

2. P3以編號2提交，發現小于P1的4，因此P3重新編號：new P3 = 1*3+2 = 5

Paxos算法

到此階段，要保證Paxos的兩個原則已經都滿足了，Paxos也就順利的實現了。

二段提交

prepare 階段：

1. Proposer 選擇一個提案編號 n 并將 prepare 請求發送給 Acceptors 中的一個多數派；

2. Acceptor 收到 prepare 消息后，如果提案的編號大于它已經回復的所有 prepare 消息，則 Acceptor 將自己上次接受的提案回復給 Proposer，并承諾不再回復小于 n 的提案；

acceptor階段：

1. 當一個 Proposer 收到了多數 Acceptors 對 prepare 的回復后，就進入批準階段。它要向回復 prepare 請求的 Acceptors 發送 accept 請求，包括編號 n 和根據 prepare階段 決定的 value（如果根據 prepare 沒有已經接受的 value，那么它可以自由決定 value）。

2. 在不違背自己向其他 Proposer 的承諾的前提下，Acceptor 收到 accept 請求后即接受這個請求。

prepare階段有兩個目的，第一檢查是否有被批準的值，如果有，就改用批準的值。第二如果之前的提議還沒有被批準，則阻塞掉他們以便不讓他們和我們發生競爭，當然最終由提議ID的大小決定。整個過程如下圖