論文閱讀筆記 - Paxos made simple

作者：劉旭晖 Raymond 轉載請注明出處

Email：colorant at 163.com

BLOG：http://blog.csdn.net/colorant/

更多論文閱讀筆記 http://blog.csdn.net/colorant/article/details/8256145

關鍵字

Paxos，一緻性

== 目标問題 ==

基本的問題就是一組程序在一個不可靠的通信環境下如何對一件事情達成一緻并獲知結果。 常見的具體應用，比如一組節點如何決定并獲知誰是主節點。

這裡不可靠的環境，指的是

• 程序本身可能崩潰重新開機
• 程序間通過發送消息傳遞資訊，消息可能丢失，可能失敗，重發，可能延遲，但是不會是錯誤的

== 核心思想 ==

為了友善描述和分析這個問題，做了如下定義

• 值（Valule）：要解決的問題，這裡定義為選擇一個值（Valule）
• 議案（Proposal） 任何程序對這個值的一個提議，我們叫做一個議案
• 三種角色：提議者Proposer（提出一個議案），準許者Acceptor（同意這個議案），觀察者Learner（獲知結果）。一個程序可以同時兼任這幾個角色。

對結果也做了一定的要求限制：

• 隻有被提出過的值可以被選擇
• 隻有一個值可以被選擇
• 一個程序不會知道一個值被選擇了，除非這個值真的被選擇了（也就是沒有錯誤資訊）

總體而言，問題的目标是保證，如果有一些值被提議了，那最終會有一個值會被選擇通過，如果一個值被選擇通過了，任一程序最終都會得知這個結果。值得注意的是，在這裡，最終哪個值被選擇了不重要（顯然如果每個程序都堅持自己的議案，那永遠不能達成一緻），重要的是有一個值最終被選擇了。

方案推理過程

最簡單的思考是，隻有一個準許者，是以提議者都把議案發給這個準許者，準許者會選擇并通過他收到的第一個議案，顯然，當這個準許者失效的時候，這個系統就不工作了。

那麼換一種方式，有多個準許者，提議者把議案分發給他們，準許者可以接受或否決這個議案，當過半的準許者接受這個議案的時候，就認為這個議案被通過了。

我們的最終目标是希望假設即使隻有一個值被一個提議者提出，最終這個值也将被選擇通過。這也就要求：

• P1：準許者應該準許它收到的第一個議案（顯然，如果不能保證這一點，前面的假設就可能不成立)

再來看如果有多個議案被同時提出，按照P1的要求，他們可能被不同的準許者接受，這樣假設有一個準許者失效了，也可能導緻任何一個議案都沒有達到過半接受的條件。要能繼續下去，就要求準許者應該可以準許多個議案。為了便于識别議案，我們進一步定義議案包含一個議案号碼（這個号碼必須是唯一的自然數）和一個值（可以相同）

這樣一個值被選擇通過，可以定義為一個包含這個值的議案被過半準許者接受了。我們要求隻能有一個值被選擇通過，但是這并不阻止我們可以允許多個議案被通過，前提是隻要我們保證這些議案包含的值是一樣的。這可以由以下條件保證：

• P2：如果一個包含值V的議案被通過，那麼任何被通過的比這個議案号碼高的議案都包含值V 

由于議案要被通過，前提是至少被一個提議者接受，那麼：

• P2A：如果一個包含值V的議案被通過，那麼任何被接受的比這個議案号碼高的議案都包含值V

我們可以通過滿足P2A來滿足P2。但是P1我們也是要滿足的，由于消息的不可靠性，如果一個之前沒有收到過任何議案的準許者收到了一個更高号碼的議案包含了一個不同于V的值，按照P1他必須接受，這就違反了P2A。 為了防止這種情況出現，我們要求：

• P2B：如果一個包含值V的議案被通過，那麼任何被提出的比這個議案号碼高的議案都包含值V

P2B顯然涵蓋了P2A，同時也和P1不沖突。但是如和保證P2B呢？可以通過以下條件來滿足：

• P2C：對于任意一個提案号碼n和值v，如果一個提案T(n)=v被提出，那麼必須有一個過半的準許者集合滿足，要麼，他們沒有接受過任何小于n的提案，要麼v是他們接受過的比n小的提案中号碼最大的提案的值。 

簡單的證明P2C包含P2B：如果一個v被通過，則任意一個過半準許者集合，至少有一個接受過v，那麼隻要滿足P2C，遞歸一下，也就要求每個更高号碼的議案都包含v

實作邏輯

在實際實作中，P2是不可控的，P2A不完備，P2B不具可操作性，你不可能在提出議案時預知一個議案是否被通過。而P2C則是可以實作的，隻要我們要求提議者在發出提案之前得知過半準許者所接受的議案中比n小的最大号碼的議案的值什麼。由于消息的不确定性，我們可以知道準許者目前接受的議案的情況，但是不可能預知将來準許者所接受的議案，要保證我們得到的資訊是準确的，我們不是去預測将來，而是可以要求準許者不再接受比号碼n小的議案，這樣提議者的運作政策可以是這樣的：

提議者選擇一個議案号碼n，将這個議案号碼分發給準許者，并要求他們回複：

• 承諾不再接受比号碼n小的議案
• 他們接受過的比n小的議案中最大号碼議案的值v

我們稱這個過程為發出一個“準備請求”

當提議者收到過半準許者的回複後，他就可以發出正式的議案n了，議案的值是回複中最大号碼的議案的值v，如果回複中沒有任何議案被接受過，那麼可以任意選一個值作為議案的值。我們稱這個過程為發出一個“接受請求”

對于準許者，我們要求:

P1A： 如果一個準許者沒有回複過一個比号碼n大的議案的準備請求，那麼它可以接受号碼n的議案的接受請求。

崩潰重新開機等容錯：

為了滿足P2C，準許者即使崩潰重新開機過後，也要記得他的做過的回複，是以準許者需要記錄它接受過的最大号碼的議案，和他回複過的最大号碼的準備請求。 對于提議者，它可以任意放棄它之前發送的準備請求，隻要它不重複發送同樣号碼的議案就沒有問題。

觀察者：

準許者每接受一個提案後，就發送消息給每個觀察者，或者，發送給一些特定觀察者，再由這些觀察者發送給其它觀察者，以減少通訊量。觀察者也可以主動詢問準許者。從觀察者的角度，應該隻需要記錄與被接受的最高号碼的議案的值相同的其它議案的資訊就可以了，因為按照P2A的要求可以得知被接受的号碼低的議案，如果值不相同的話，是不會被通過的。

其它

個人了解，Paxos本身是一個保證議案的一緻性的方案，避免單點失敗的問題。但是為了高效性，一個Paxos的過程，通常還是希望保證隻有一個提議者提議案，是以基本可以認為平時還是有主節點的，如果主節點失敗或者别的節點認為自己是主節點時，由Paxos過程保證決策的順利進行。

實作上的問題

這裡的實作邏輯提供了一個解決沖突的方案，但是實作中，如何具體的操作這些步驟，大概會有各種各樣的細節問題，尤其是要考慮到效率，穩定性，可用性等等，比如

• 如何生成唯一的議案号，如何保證各個議案号的有序性，即如何比較他們的大小？
  • 每個提議者有一個分組的有序号碼（比如配置設定一個N*i+x？N總共有幾個提議者，X這個提議者第幾次議案，i這個提議者的序号），每次他們都使用自己比上一個号碼更大的号碼

• 如何保證議案被提出，即如何驅動這一過程能進行下去？如果之前的議案被放棄，大家都在等？有什麼政策保證新的議案被提出？如何驅動結果向一個議案被過半接受收斂，不會反複糾纏？
  • 要有Leader提議者，由Leader提議者發起議案，但是選擇Leader提議者又是一個問題，實踐中，随機和timeout機制是可行的方案(原文描述，可以想象，但是不完全了解），再有如何通知大家leader是誰等，需要找個具體實作看一看。

• 效率問題，一個paxos過程最少需要兩輪通訊，在很多跨區域的分布式系統中，Latency的問題就很突出，針對各種應用場合有各種的特定優化
• 各種實際系統失效問題：paxos過程中有一些假設，比如準許者要記住它作過的承諾，理論上這是靠将相關資訊記錄在磁盤上來實作，實際系統中，如果磁盤檔案崩潰了，Paxos過程的這一假設就不成立了，需要檢測和處理這種情況。

== 相關研究，項目等 ==

paxos made live : 基于Paxos的系統的實作，有很多工程實際問題，這篇Paper闡述了這些問題以及解決方案

Chubby : 基于Paxos算法建構的一個分布式鎖服務

Megastore ：使用Paxos進行跨資料中心副本同步，支援多點發起更新操作