Paxos算法簡述

Paxos算法是分布式中一個著名的一致性算法。它的假設前提是，在分布式系統中進程之間的通 信會出現丟失、延遲、重復等現象，但不會出現傳錯的現象。Paxos算法就是為了保證在這樣的系統中進程間基于消息傳遞就某個值達成一致。要理解 paxos算法最好還是看作者本人(Leslie Lamport)的論文《The Part-Time Parliament》。在這里只是簡單地介紹paxos最核心的思想，其實它還有很多的內容。

提議者和決議者是這里最重要的兩個角色，paxos最核心的算法就是定義他們之間的通訊規則來保證某個變量在分布式系統中的一致性。

提議者是提出議案的人。每個議案都有一個議案號，議案號是區別不同議案的唯一標識，而且議案號是有大小次序的。這里的提議者不像我們真實世界里的提議者，這里的提議者提的議案內容不能隨心所欲。提議者和決議者要遵循下面的規則：

1） 提議者先給議案決定一個議案號，注意整個系統中議案號都不能重復的。然后發消息給所有決議者，告訴他們我要提出第幾號議案。

第一階段，提議者甲向決議者A、B、C、D、E、F、G發出議案號16的消息。

2） 決議者收到提議者發來的議案號后先看這個議案號是否是自己收到的所有議案號中最大的。如果不是，就不予理會；如果是，就把自己最后一次投票的議案發回去，如果沒投過議案就回復沒投過議案。

第二階段，決議者收到甲發來的議案號16后根據自己的情況作出回復

A、D未投過任何議案所以回復(null)

B最后一次投了2號議案所以回復(2,α)

C、F最后一次投了5號議案所以回復(5,β)

E的最大議案號是21所以不用回復

G由于網絡原因沒收到消息

3） 當提議者收到過半回復后才能決定議案的內容。在所有回復中議案號最大的那個議案的內容就定為當前議案的內容。如果都回復沒投過議案，那議案內容就由自己定 了。如果只收到不過半數的回復，那么這個過程就這樣結束了。確定議案內容后就要把議案發給所有決議者。到此提議者的工作就可以結束了。

第三階段，甲根據回復確定16號議案的內容，然后正式提出16號議案。

甲收到過半數人的回復，回復的內容有(null)、(2,α)、(5,β)，其中5是最大的議案號，所以16號議案的內容就定為β,接著甲就把(16,β)發出去。

4） 決議者收到議案后，就要對它進行投票。如果這個議案號是自己收到的所以議案號中最大的，就要投這個議案的票；否則就不予理會。這里的投票沒有反對或贊成的類型之分。也就是可以認為只有贊成票。到此決議者的工作就可以結束了。

第四階段，決議者收到16號議案并對它投票。

A、B、C、G收到(16,β)后，由于16號是他們的最大號，所以會給這個議案投票

D、E、F收到(16,β)后，由于21號是他們的最大號，所以不投票。

這個算法保證了某個變量在分布式系統中要么沒有值，要么就只會有一個值。只要某個議案在某一刻有過半數的人投票，那么這個值就永遠定下來了。

如上圖，15號議案(內容是β)有了過半數的投票，那么它的下一號16號議案內容只能是β了，因為在第三階段收到的回復如果過半數，那么其中一定有 (15,β)，而15肯定是回復中最大的號，所以內容只能是β。而下下一號21號議案內容也只能是β，因為它的前兩個議案的內容都是β，如果收到的回復過 半數的話肯定包含(15,β)或(16,β)，而他們都是最大的兩個，所以內容也只能是β了。可以證明其后的所有議案內容都是β。雖然paxos算法可以 保證不會有兩個值，但顯然不能保證一定會有值。這也是理論上(CAP理論)不能解決的問題。

這里的算法是有改動的，提議者和決議者都還有后續的處理，而且關于上面的“過半數的決議者”也并不是paxos本身的描述。Paxos本身定義的是 一個更一般的“大多數”集合，每個議案都有一個“大多數”的決議者集合S，這些集合是兩兩相交的，對于每個議案，在第三階段要收到S中所有決議者的回復才 能繼續下去。如果某個議案得到相應S的全體投票，那么這個值就這么定下來了。