Paxos算法

一、基本要求

1、拜占庭将軍問題

    拜占庭帝國有許多支軍隊，不同的将軍之間必須制定一個統一的行動計劃，進而做出進攻或者撤退的決定。同時，各個将軍在地理上都是被分隔開來的，隻能依靠軍隊的通訊員來進行通訊。然而，在所有的通訊員中可能存在叛徒，這些叛徒可以任意篡改消息，進而達到欺騙将軍的目的。

2、要求

    假設有一組可以提出提案的程序集合，那麼對于一緻性算法來說，需要保證以下幾點：

1. 這些被提出的提案中，隻有一個會被標明；
2. 如果沒有提案被提出，那麼就不會有被標明的提案；
3. 當一個提案被標明後，程序可以擷取被標明的提案的資訊。

    分布式算法有兩個重要的屬性：安全性和活性。安全性是指需要保證永遠都不會發生的事情，活性是最終一定會發生的事情。這裡不精确的去定義活性的需求，隻讨論安全性的要求：

1. 隻有被提出的提案才能被標明；
2. 隻有一個值能被標明；
3. 如果某個程序認為某個提案被標明了，那麼這個提案必須真的是被標明的。

3、角色

    在Paxos算法中，涉及到三種角色：Proposer、Acceptor和Learner。Proposer是提出提案的角色，Acceptor是判斷是否接受提案的角色。在算法實作的過程中，不同的程序可能充當不同的角色。假設不同的參與者之間可以通過收發消息來進行通信，那麼：

1. 每個參與者以任意的速度執行，可能會因為出錯而停止，也可能會重新開機。同時，即使一個提案被標明後，所有的參與者也有可能會失敗或重新開機，是以除非失敗或重新開機的參與者可以記錄一些資訊，否則将無法确定最終的值；
2. 消息在傳播的過程中可能會出現不可預知的延遲，也可能會重複或丢失，但是消息不會被損毀，即消息内容不會被篡改（即拜占庭将軍問題）。

二、算法詳解

1、提案標明相關的兩個假設

    首先，确定一個基本概念，一個提案指的是[Mn, Vn]，其中Mn是一個全局唯一的編号，而Vn是提案的值，即需要送出的内容本身。

    P1：一個Acceptor隻要未響應過任何編号大于Mn的Prepare請求，那麼它就可以接受這個編号為Mn的提案；

    P2：對于産生的每個提案，需要滿足：存在一個超過半數的Acceptor組成的集合S，要麼S中沒有Acceptor準許過編号小于Mn的任何提案，要麼S中所有的Acceptor準許的所有編号小于Mn的提案中，編号最大的那個提案的Value值為Vn。

2、提案的生成

    根據上面的假設P2進行提案的生成。Proposer在産生一個編号為Mn的提案時，必須要知道某一個将要或者已經被半數以上的Acceptor準許的編号小于Mn的最大的編号的提案，并且Proposer會要求Acceptor不再準許任何編号小于Mn的提案。

2.1 提案生成算法

    根據上面的要求，得到提案生成算法：

1、Proposer選擇一個新的提案編号Mn，然後向某個Acceptor集合的成員發送請求，要求該集合中的Acceptor做出如下回應：

• 向Proposer承諾，保證不再準許任何編号小于Mn的提案；
• 如果Acceptor已經準許過任何提案，就想Proposer回報該提案的值。

    這個請求被稱為：編号為Mn的提案的Prepare請求。

2、根據Proposer收到的響應結果不同，有如下不同的Vn的處理方式：

• 如果Proposer收到了來自半數以上的Acceptor的響應結果，那麼它就可以産生編号為Mn、value為Vn的提案，這裡的Vn是所有響應中編号最大的提案的Value值；
• 如果Proposer收到的響應結果是半數以上的Acceptor都沒有準許過任何提案，即響應中不包含任何的天，那麼此時Vn的值可以由Proposer任意選擇。

2.2 Accept請求

    在确定提案之後，Proposer會将提案再次發送給某個Acceptor集合，并期望獲得它們的準許，這個請求被稱為Accept請求。需要注意的是，此時接受Accept請求的Acceptor集合不一定是之前響應Prepare請求的Acceptor集合，但是任意兩個半數以上的Acceptor集合，必定包含至少一個公共Acceptor。

3、提案的準許

    可以得到兩階段送出算法：

階段一：

1. Proposer選擇一個提案編号Mn，然後向Acceptor的某個超過半數的子內建員發送編号為Mn的Prepare請求；
2. 如果一個Acceptor收到一個編号為Mn的Prepare請求，且編号Mn大于該Acceptor已經響應的所有Prepare請求的編号，那麼它就會将已經準許過的最大編号的提案作為響應回報給Proposer，同時該Acceptor會承諾不會再準許任何編号小于Mn的提案。

階段2：

1. 如果Proposer收到來自半數以上的Acceptor對于其發出的編号為Mn的Prepare請求的響應，那麼它就會發送一個針對[Mn, Vn]提案的Accept請求給Acceptor。需要注意的是，Vn的值就是收到的響應中編号最大的提案的值，如果響應中不包含任何提案，那麼它就是任意值；
2. 如果Acceptor收到這個針對[Mn, Vn]提案的Accept請求，隻要該Acceptor尚未對編号大于Mn的Prepare請求作出響應，它就可以通過這個提案。

4、提案的擷取

    上述三節已經讨論了如何標明一個提案，這裡讨論如何讓Learner擷取提案。

    所有的Acceptor将它們對提案的審批情況，統一發送給一個特定的Learner集合，該集合中的每個Learner都可以在一個提案被標明後通知所有其他的Learner這個Learner集合中的Learner個數越多，可靠性就越好，但同時網絡通信的複雜度也就越高。

5、選取主Proposer

    Proposer如果發現自己提議的編号過小導緻被Acceptor拒絕，會擷取新的更大的編号并重發提議，這就可能導緻出現兩個Proposer循環交替的不斷提出兩個提議的死循環。可以通過標明一個主Proposer，并規定隻有主Proposer才能提出提議來避免這個問題。隻要主Proposer和過半的Acceptor能進行正常的網絡通信，那麼但凡Proposer提出一個編号更高的提議都會被準許。

    通過標明一個主Proposer，可以保證算法的活性。