Paxos算法

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

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

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

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

另外還需要保證 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，那麼存在一個多數派，要麼他們中所有人都沒有接受（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不完備的問題。 ^[2] 

要滿足P2c的約束，proposer提出一個提案前，首先要和足以形成多數派的acceptors進行通信，獲得他們進行的最近一次接受（accept）的提案（prepare過程），之後根據回收的信息決定這次提案的value，形成提案開始投票。當獲得多數acceptors接受（accept）後，提案獲得批准（chosen），由proposer將這個消息告知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的提案。

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

決議的提出與批准

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

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