Paxos前傳-The Part-Time Parliament（一）

前言

之前研究了諸如Raft、ZAB等演算法，總覺得意猶未盡，因為只知其然而不知其何以然是一件非常非常不舒服的事情。

本文是對最早提出分散式一致性問題（雖然作者在論文中描述的好像是一個考古學問題）的Lamport的論文「The Part-Time Parliament」的讀書筆記，大部分內容是對論文的直接翻譯，同時也對一些較為晦澀的地方增加自己的理解注釋，可能會存在理解不精確的地方，希望大家多為斧正， 另外本文很多地方直接借用了中文的翻譯版，表示感謝，除了個別的筆誤，原始的中文翻譯版做的很好。

一致性問題本質上就是一群實體對某一個結論達成共識的問題，其核心在於如何設計一種演算法（流程）來保證，同時還要能夠從數學上嚴謹地證明演算法正確。Lamport在論文中展示了其幽默的一面，虛構了一個古希臘小島Paxon上的議會機構，議會的主要工作是確定律法，議會由眾多議員組成，一個律法的通過必須由多數議員投票方可。作者以此場景為出發點，通過詼諧輕鬆的語言和嚴謹的數學推導證明，得出了一個極其簡單的演算法Paxos，該演算法也為當前的大規模分散式系統設計奠定了理論基礎。

因為論文涉及到很多數學符號定義，在閱讀過程中可能會出現嘔吐、頭暈、眼花、健忘等不適，忍忍就好。

場景設計

公元 10 世紀初，愛琴海上的小島Paxos是一個興盛的商業貿易中心。經濟發展帶來了政治的進步。Paxos 的公民們用議會形式的政府取代了原先的神權統治。議會的主要作用在於確定律法以保證城市可以有序穩定運轉。所有律法都必須經由議會成員投票表決後方可生效實施，且已通過的律法必須被記錄在案。但是對 Paxos人來說，做生意才是頭等大事，城市職責反在其次（看來這個島上的居民還比較單純，不知道玩好政治就等於掌握經濟命脈這個道理），沒有Paxos人願意把他全部的時間投入到議會事務中。所以 Paxos 的議會必須在每個議員都可能隨時缺席的情況下也能工作下去，這就是所謂的「兼職議會」。

兼職議會所面對的問題正好能對應於今天的容錯式分散式系統所面對的問題：議員對應於分散式系統中的處理進程(processes)，而議員的缺席對應於處理進程的宕機。因此 Paxos 人的解決方法或許值得計算機科學借鑒（Lamport太謙虛了）。

要求

議會的主要任務就是決定這片土地上的法律，法律是由議會通過的一系列法令定義的。一個現代的議會可以僱傭秘書來記錄它的每一個活動，但是在Paxos，沒有一個人願意始終呆在議會大廳里作為一個秘書從頭到尾參與每一個會議。取而代之的是每一個議員都會維護一個律簿，用來記錄一系列已通過的法令，每個法令帶有一個唯一編號。例如議員A的律簿里有這樣一個條目：

155：橄欖稅是每噸 3 個銀幣

如果她相信議會通過的第155號法令設置了橄欖的賦稅為每噸 3 個銀幣。律簿是由檫不掉的墨水書寫的，所以其中的條目不能被改變。

議會協議的第一個需求就是律簿的一致性。也就是任何兩個律簿都不能有互相矛盾的內容。假設議員B在他的律簿中有這樣一個條目：

132：只有橄欖油可以用來做燈

那麼就不會有其他議員的律簿會記錄不同內容的第 132 號法令。當然，另一個議員的律簿里可能還沒有第 132 號法令的記錄，如果他還不知道第 132 號法令已經通過了。

僅僅有律簿的一致性（Consistency）還不夠，因為讓每個律簿都保留空白也能滿足一致性。所以需要一些要求（Requirement）來保證法令能最終通過並被記錄在律簿中。在現代的議會中，議員達不成一致妨礙了法令的通過。但是在 Paxos 不是這種狀況，這裡盛行的是相互信任的氣氛，議員願意通過任何被提交的法令。但是他們好遊歷的特性卻造成了問題。假如一組議員通過了 37 號法令：

37：禁止在聖殿的牆上種植

然後離開議會廳參加宴會去了，接下來另外一組議員進來議會廳，不知道剛剛發生了什麼事情，然後也通過了一個衝突的 37 號法令：

37：允許自由的藝術表達

那麼一致性就失去了除非足夠多的議員在議會廳里呆足夠長的時間，否則進展性(Progress)無法保證。因為 Paxos的議員不願意縮減他們在外面的活動，所以無法保證任何法令都會最終被通過。但是無論如何，議員們願意保證，只要他們在議會廳中，他們和他們的助手就會快速的處理所有的議會事務。這個保證使 Paxos 公民們能夠設計出一個滿足如下進展性條件的議會協議：

如果議員中的多數都在議會廳中，並且在一個足夠長的時間內沒有人進出議會廳，那麼任一被某個議員提議的法令都將會被通過，並且每一個被通過的法令都會出現在議會廳中每個議員的律簿上

假設

通過提供給議員必要的資源，議會協議的要求(requirements)是可以達到的。每個議員收到了一個結實耐用的律簿來記錄法令，一支筆，和擦不掉墨水。議員如果離開過議會廳，可能會在回來後忘記了他們曾經做過什麼（（比如）在一個悲劇的事故里，議員 Twvey 被掉下來的雕像擊中了頭部而永久失憶了），所以他們會把一些重要的議會任務記在律簿的背面。律簿上的法令條目永遠不會改變，但是律簿背面的備註(notes)可能會被劃掉。

議員任何時候都會帶著他們的律簿，並且總是能夠從律簿上閱讀到法令條目和尚未劃掉的備註。律簿由最精良的羊皮紙做成，只用來記錄最重要的備註(notes)。其他備註會被記錄到小紙條(a slip of paper)上，這些小紙條可能會在議員離開議會廳後丟失。議會廳里比較嘈雜，影響聽覺，不可能在裡面做演講。議員只能通過信使來通信，並且有專款來供議員僱用任意多他們需要的信使。信使不會篡改消息，但是他可能會忘記他遞送過了

某個消息，並再次遞送它。像他們服務的議員一樣，信使也只花他們部分的時間在議會職責上。一個信使在投遞一個消息前可能會離開議會廳去從事其他的事情，比如一次為期6個月的航海。他甚至可能會一去不復返，在這種情況下消息永遠也不會被送達。

儘管議員和信使可以隨時離開或進入，但是只要他們在議會廳里，他們就會專註於議會事務。只要呆在議會廳，信使會很快速的投遞消息，議員會立即快速的處理任何他們收到的消息。Paxos 的官方記錄聲稱議員和信使絕對的誠實並嚴格遵循議會協議。大多數學者僅僅把這當做將 Paxos 描繪為在道德上優越於其東方鄰國的宣傳。不誠實，儘管稀少，但毫無疑問一定是存在的，但由於官方文本里從未提及，我們也不知道議會是怎樣應付不誠實的議員或信使的。

定義說明

Paxos議會採用投票表決的方式來通過法令，這也是民主國家的做法。一個法令只有被特定集合的議員投贊成票才算通過，通過後該法令便被記錄在議員的律簿之上。根據現代民主，一般這個特定集合是多數派成員。每一個議員均可以發起提案，每一個提案可能無法在一輪投票中通過，於是該投票可能需要經過多輪投票。為此，我們定義如下幾個符號，便於後續推導：

：表示一輪表決

：表決編號，每一輪表決編號均唯一

：被表決的法令

：表決的法定人數集（一般指多數派）

：表決的投贊成票的議員集（贊成的投票，不贊成的不投票）

：所有表決集合

一輪表決是成功的當且僅當

Paxos 的數學家在一個由多輪表決構成的集合上定義了3個條件，然後展示了如果已經進行過的表決滿足這些條件，那麼一致性會得到保證，進行性也是可能的。頭兩個條件比較簡單，可以被非正式的描述如下：

： 中的每一輪表決，都有一個唯一的編號

： 中任意兩輪表決的法定人數集中，至少有一個公共的牧師成員

：對於 中每一輪表決 ，如果 的法定人數集中的任何一個牧師在 中一個更小輪的表決中投過(贊成)票，那麼 的法令與所有這些更小輪表決中最大那次表決法令相同。

下圖幫助詮釋了這一段隱晦的文本。手稿畫出了5個牧師

• 編號為2的表決是最小（早）的表決，從而這輪投票的條件也都滿足
• 編號為5的表決中沒有牧師在更小號的投票中投過票，這輪的條件也滿足
• 這輪表決的定額集合中，唯一一個在更小編號的表決中投過票的牧師是 ，他在編號為2的表決中投了票，所以要求這輪的法令和2的法令必須相等，成立
• 這是一次成功的表決。27輪表決的定額集合是 。牧師 沒有在更小號的表決中投過票。投過票的小編號表決只有2和5，這兩個更小編號表決中最大的是5，所以條件要求本輪的法令和5的法令相同，成立
• 本輪的定額集合是 。 投過票的小編號表決只有14， 在表軍5和27中投過票， 在表決2和27中投過票，其中表決最大的一個是27，所以條件要求29的法令和27的法令相同。

正式的表述 需要更多的符號標記。我們用符號 表示一個投票，那麼 包含 3個組成部分：投票的牧師 ，本輪表決的編號 和所表決的法令 。Paxos人同時定義了 , 的投票 為 投票。對於 的所有編號為 的表決，不會以 作為法令。對於任意牧師 ，他們定義了 作為唯一的 投票 , 。

Paxos數學家為所有投票定義了一個全局順序，但是手稿里包含了這個定義那一部分遺失了，剩下的片段顯示，對於任意 和 ，如果 ，那麼 。

對於任意的表決組成的集合 ，定義集合 為包含所有滿足如下條件的投票

： ，使得 ，(即用 表示所有在 中的投票）。

如果 是一個議員， 是一個表決的編號或 ，則 定義為 中由 投出的表決編號小於 的最大的投票 或者 。 因為 比所有 實際投出的票都要小，這就意味著 是下面集合中的最大投票：

對於任意非空的牧師集合 ， 定義為對於所有 ，所有 中的最大值。

於是，條件 正式表述如下：

• 
• 
• 

推薦閱讀：