分散式系統理論進階 - Paxos

01-31

引言

《分散式系統理論基礎 - 一致性、2PC和3PC》一文介紹了一致性、達成一致性需要面臨的各種問題以及2PC、3PC模型，Paxos協議在節點宕機恢復、消息無序或丟失、網路分化的場景下能保證決議的一致性，是被討論最廣泛的一致性協議。

Paxos協議同時又以其「艱深晦澀」著稱，下面結合 Paxos Made Simple、The Part-Time Parliament 兩篇論文，嘗試通過Paxos推演、學習和了解Paxos協議。

Basic Paxos

何為一致性問題？簡單而言，一致性問題是在節點宕機、消息無序等場景可能出現的情況下，相互獨立的節點之間如何達成決議的問題，作為解決一致性問題的協議，Paxos的核心是節點間如何確定並只確定一個值(value)。

也許你會疑惑只確定一個值能起什麼作用，在Paxos協議里確定並只確定一個值是確定多值的基礎，如何確定多值將在第二部分Multi Paxos中介紹，這部分我們聚焦在「Paxos如何確定並只確定一個值」這一問題上。

和2PC類似，Paxos先把節點分成兩類，發起提議(proposal)的一方為proposer，參與決議的一方為acceptor。假如只有一個proposer發起提議，並且節點不宕機、消息不丟包，那麼acceptor做到以下這點就可以確定一個值：

P1. 一個acceptor接受它收到的第一項提議n

當然上面要求的前提條件有些嚴苛，節點不能宕機、消息不能丟包，還只能由一個proposer發起提議。我們嘗試放寬條件，假設多個proposer可以同時發起提議，又怎樣才能做到確定並只確定一個值呢？

首先proposer和acceptor需要滿足以下兩個條件：

1. proposer發起的每項提議分別用一個ID標識，提議的組成因此變為(ID, value)

2. acceptor可以接受(accept)不止一項提議，當多數(quorum) acceptor接受一項提議時該提議被確定(chosen)

(注: 注意以上「接受」和「確定」的區別）

我們約定後面發起的提議的ID比前面提議的ID大，並假設可以有多項提議被確定，為做到確定並只確定一個值acceptor要做到以下這點：

P2. 如果一項值為v的提議被確定，那麼後續只確定值為v的提議n

(注: 乍看這個條件不太好理解，謹記目標是「確定並只確定一個值」)

由於一項提議被確定(chosen)前必須先被多數派acceptor接受(accepted)，為實現P2，實質上acceptor需要做到：

P2a. 如果一項值為v的提議被確定，那麼acceptor後續只接受值為v的提議n

滿足P2a則P2成立 (P2a => P2)。

目前在多個proposer可以同時發起提議的情況下，滿足P1、P2a即能做到確定並只確定一個值。如果再加上節點宕機恢復、消息丟包的考量呢？

假設acceptor c 宕機一段時間後恢復，c 宕機期間其他acceptor已經確定了一項值為v的決議但c 因為宕機並不知曉；c 恢復後如果有proposer馬上發起一項值不是v的提議，由於條件P1，c 會接受該提議，這與P2a矛盾。為了避免這樣的情況出現，進一步地我們對proposer作約束：

P2b. 如果一項值為v的提議被確定，那麼proposer後續只發起值為v的提議n

滿足P2b則P2a成立 (P2b => P2a => P2)。

P2b約束的是提議被確定(chosen)後proposer的行為，我們更關心提議被確定前proposer應該怎麼做：

P2c. 對於提議(n,v)，acceptor的多數派S中，如果存在acceptor最近一次(即ID值最大)接受的提議的值為v，那麼要求v = v；否則v可為任意值n

滿足P2c則P2b成立 (P2c => P2b => P2a => P2)。

條件P2c是Basic Paxos的核心，光看P2c的描述可能會覺得一頭霧水，我們通過 The Part-Time Parliament 中的例子加深理解：

假設有A~E 5個acceptor，- 表示acceptor因宕機等原因缺席當次決議，x 表示acceptor不接受提議，o 表示接受提議；多數派acceptor接受提議後提議被確定，以上表格對應的決議過程如下：

ID為2的提議最早提出，根據P2c其提議值可為任意值，這裡假設為a
acceptor A/B/C/E 在之前的決議中沒有接受(accept)任何提議，因而ID為5的提議的值也可以為任意值，這裡假設為b
acceptor B/D/E，其中D曾接受ID為2的提議，根據P2c，該輪ID為14的提議的值必須與ID為2的提議的值相同，為a
acceptor A/C/D，其中D曾接受ID為2的提議、C曾接受ID為5的提議，相比之下ID 5較ID 2大，根據P2c，該輪ID為27的提議的值必須與ID為5的提議的值相同，為b；該輪決議被多數派acceptor接受，因此該輪決議得以確定
acceptor B/C/D，3個acceptor之前都接受過提議，相比之下C、D曾接受的ID 27的ID號最大，該輪ID為29的提議的值必須與ID為27的提議的值相同，為b

以上提到的各項約束條件可以歸納為3點，如果proposer/acceptor滿足下面3點，那麼在少數節點宕機、網路分化隔離的情況下，在「確定並只確定一個值」這件事情上可以保證一致性(consistency)：

B1(?): ?中每一輪決議都有唯一的ID標識
B2(?): 如果決議B被acceptor多數派接受，則確定決議B
B3(?): 對於?中的任意提議B(n,v)，acceptor的多數派中如果存在acceptor最近一次(即ID值最大)接受的提議的值為v，那麼要求v = v；否則v可為任意值

(注: 希臘字母?表示多輪決議的集合，字母B表示一輪決議)

另外為保證P2c，我們對acceptor作兩個要求：

1. 記錄曾接受的ID最大的提議，因proposer需要問詢該信息以決定提議值

2. 在回應提議ID為n的proposer自己曾接受過ID最大的提議時，acceptor同時保證(promise)不再接受ID小於n的提議

至此，proposer/acceptor完成一輪決議可歸納為prepare和accept兩個階段。prepare階段proposer發起提議問詢提議值、acceptor回應問詢並進行promise；accept階段完成決議，圖示如下：

還有一個問題需要考量，假如proposer A發起ID為n的提議，在提議未完成前proposer B又發起ID為n+1的提議，在n+1提議未完成前proposer C又發起ID為n+2的提議…… 如此acceptor不能完成決議、形成活鎖(livelock)，雖然這不影響一致性，但我們一般不想讓這樣的情況發生。解決的方法是從proposer中選出一個leader，提議統一由leader發起。

最後我們再引入一個新的角色：learner，learner依附於acceptor，用於習得已確定的決議。以上決議過程都只要求acceptor多數派參與，而我們希望盡量所有acceptor的狀態一致。如果部分acceptor因宕機等原因未知曉已確定決議，宕機恢復後可經本機learner採用pull的方式從其他acceptor習得。

Multi Paxos

通過以上步驟分散式系統已經能確定一個值，「只確定一個值有什麼用？這可解決不了我面臨的問題。」你心中可能有這樣的疑問。

其實不斷地進行「確定一個值」的過程、再為每個過程編上序號，就能得到具有全序關係(total order)的系列值，進而能應用在資料庫副本存儲等很多場景。我們把單次「確定一個值」的過程稱為實例(instance)，它由proposer/acceptor/learner組成，下圖說明了A/B/C三機上的實例：

不同序號的實例之間互相不影響，A/B/C三機輸入相同、過程實質等同於執行相同序列的狀態機(state machine)指令，因而將得到一致的結果。

proposer leader在Multi Paxos中還有助於提升性能，常態下統一由leader發起提議，可節省prepare步驟(leader不用問詢acceptor曾接受過的ID最大的提議、只有leader提議也不需要acceptor進行promise)直至發生leader宕機、重新選主。

小結

以上介紹了Paxos的推演過程、如何在Basic Paxos的基礎上通過狀態機構建Multi Paxos。Paxos協議比較「艱深晦澀」，但多讀幾遍論文一般能理解其內涵，更難的是如何將Paxos真正應用到工程實踐。

微信後台開發同學實現並開源了一套基於Paxos協議的多機狀態拷貝類庫PhxPaxos，PhxPaxos用於將單機服務擴展到多機，其經過線上系統驗證並在一致性保證、性能等方面作了很多考量。

本文提到的一些概念包括一致性(consistency)、一致性系統模型(system model)、多數派(quorum)、全序關係(total order)等，在以下文章中有介紹

《分散式系統理論基礎 - 一致性、2PC和3PC》

《分散式系統理論基礎 - 選舉、多數派和租約》

《分散式系統理論基礎 - 時間、時鐘和事件順序》

《分散式系統理論基礎 - CAP》