Paxos算法解析

Paxos是什麼

Paxos算法是基于消息傳遞且具有高度容錯特性的一緻性算法，是目前公認的解決分布式一緻性問題最有效的算法之一

問題産生的背景

在常見的分布式系統中，總會發生諸如機器當機或網絡異常（包括消息的延遲、丢失、重複、亂序，還有網絡分區）等情況。Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正确地在叢集内部對某個資料的值達成一緻，并且保證不論發生以上任何異常，都不會破壞整個系統的一緻性。

首先我們簡單介紹paxos所保證的一緻性的具體含義；達成一緻的條件(何時達成一緻）；基于的一個基本的數學原理；以及它需要滿足的假設。

什麼是一緻性?實際上這個詞在不同地方語義并不那麼一緻，Paxos面向的是一個理論的一緻問題，這個問題的通俗描述是：

有一個變量v，分布在N個程序中，每個程序都嘗試修改自身v的值，它們的企圖可能各不相同，例如程序A嘗試另v=a,程序B嘗試另v=b，但最終所有的程序會對v就某個值達成一緻,即上述例子中如果v=a是v達成一緻時的值，那麼B上，最終v也會為a。需要注意的是某個時刻達成一緻并不等價于該時刻所有程序的本地的v值都相同，有一個原因是程序可能挂掉，你不能要求挂掉的程序任何事；更像是最終所有存活的程序本地v的值都會相同。

這個一緻性需要滿足三個要求：

1.v達成一緻時的值是由某個程序提出的。這是為了防止像這樣的作弊方式：無論如何，最終都令每個程序的v為同一個預先設定好的值，例如都令v=2，那麼這樣的一緻也太容易了，也沒有任何實際意義。

2.一旦v就某個值達成了一緻，那麼v不能對另一個值再次達成一緻。這個要求稱為安全性。

3.一緻總是能夠達成，即v總會被決定為某個值。這是因為不想無休止的等待，這個要求也稱為活性。

Paxos中變量v達成一緻的條件： N個程序中大多數（超過一半） 程序都認為v是同一個值，例如c，那麼我們稱v被決定為c。這樣即使少數程序挂掉了，也不會使得一緻無法達成。

Paxos保證的一緻性如下：不存在這樣的情形，某個時刻v被決定為c，而另一個時刻v又決定為另一個值d。由這個定義我們也看到，當v的值被決定後，Paxos保證了它就像是個單機的不可變變量，不再更改。也是以，對于一個用戶端可以多次改寫值的可讀寫變量在不同的節點上的一緻性問題，Paxos并不能直接解決，它需要和狀态機複制結合。

Paxos基于的數學原理： 我們稱大多數程序組成的集合為法定集合，兩個法定集合必然存在非空交集，即至少有一個公共程序，稱為法定集合性質。 例如A,B,C,D,F程序組成的全集，法定集合Q1包括程序A,B,C，Q2包括程序B,C,D，那麼Q1和Q2的交集必然不在空，C就是Q1，Q2的公共程序。如果要說Paxos最根本的原理是什麼，那麼就是這個簡單性質。同時，可以注意到，這個性質和達成一緻的定義相呼應。

Paxos中程序之間是平等的，即不存在一個特殊的程序，這是由于如果協定依賴于某個特殊的程序，那麼這個程序挂掉勢必會影響協定;而對于分布式環境，無法保證單個程序必然必活，能夠容忍一定數量的程序挂掉，是分布式協定的必然要求。這是推導過程所要遵循的一個原則，就稱為平等性原則好了。

消息是程序間通信的唯一手段，對于分布式環境來說，這是顯然的。

Paxos要求滿足的前置假設隻有一個：消息内容不會被篡改；更正式的說是無拜占庭将軍問題。

假裝的推導總是先從一些具體的場景開始，既然Paxos的假設僅僅隻是消息不會被篡改,保證了這點任意場景下都能保證一緻性，那麼對于舉例的場景它必然是能夠保證一緻性的；是以不妨先使得協定流程能在目前場景下能保證一緻性，然後再舉出另一個場景，目前的協定流程無法再該場景下滿足一緻性，接着再豐富協定流程，滿足該場景，如此往複，最終得到完整的paxos協定，最後再不失一般性的論證協定對任意場景都能保證一緻性。

實際上一個程序存在兩個功能：

1. 程序主動嘗試令v的值被決定為某個值，向程序集合廣播提案。
2. 程序被動收到來自其它程序的提案，判斷是否要接受它。

是以可以把一個程序分為兩個角色，稱負責功能1的角色是提議者，記作Proposer，負責功能2的角色是接受者，記作Acceptor。由于兩者完全沒有耦合，是以并不一定需要在同個程序，但是為了方面描述，我們假定一個程序同時擔任兩種角色，而實際的工程實作也往往如此。

兩個階段：預提案階段和提案階段；兩種消息：預提案和提案；兩種角色：提議者和接受者

限制1：

P1：一個Acceptor必須接受它收到的第一個提案

這是為了保證肯定會有value被選中

但是，這又會引出另一個問題：如果每個Proposer分别提出不同的value，發給不同的Acceptor。根據P1，Acceptor分别接受自己收到的value，就導緻不同的value被標明。出現了不一緻

剛剛是因為『一個提案隻要被一個Acceptor接受，則該提案的value就被標明了』才導緻了出現上面不一緻的問題。是以，我們需要加一個規定：

規定：一個提案被標明需要被半數以上的Acceptor接受

這個規定又暗示了：『一個Acceptor必須能夠接受不止一個提案！』不然可能導緻最終沒有value被標明

于是，提案的内容中增加了提案編号，用來表示提案被提出的順序，令提案=提案編号+value

雖然允許多個提案被標明，但必須保證所有被標明的提案都具有相同的value值。否則又會出現不一緻

于是有了下面的限制：

P2：如果某個value為v的提案被標明了，那麼每個編号更高的被標明提案的value必須也是v

這是可以推出來的，如果value已經被標明，則大多數accept傳回給提議者的消息為《Pok，accepted_proposer_id，accepted_proposer_value》或《Pok，null，null》

一個提案隻有被Acceptor接受才可能被標明，是以我們可以把P2限制改寫成對Acceptor接受的提案的限制P2a

P2a：如果某個value為v的提案被標明了，那麼每個編号更高的被Acceptor接受的提案的value必須也是v