大綱

1.分布式系統特點

2.分布式系統的理論

3.兩階段提交Two-Phase Commit(2PC)

4.三階段提交Three-Phase Commit(3PC)

5.Paxos島的故事來對應ZooKeeper

6.Paxos算法推導過程

7.Paxos協議的核心思想

8.ZAB算法簡述

6.Paxos算法推導過程

(1)Paxos的概念

(2)問題描述

(3)推導過程

(4)Proposer生成提案

(5)Acceptor批準提案

(6)Paxos算法描述

(7)Learner學習被選定的value

(8)如何保證Paxos算法的活性

(1)Paxos的概念

一.Paxos的角色

二.Paxos的提案

三.Paxos角色對數據達成一致的情況

一.Paxos的角色

在Paxos算法中，有三種角色：Proposer、Acceptor、Learner。在具體的實現中，一個進程可能同時充當多種角色。比如一個進程可能既是Proposer又是Acceptor又是Learner。

還有一個重要概念叫提案(Proposal)，最終要達成一致的value就在提案里。

假如只有一個角色，那么其實就是分布式節點自己。各自認為自己的表達是正確的，這時候是無法達成一致的。所以需要引入多一個角色來處理各個節點的表達，最后還要引入一個角色將達成一致的結果同步給各分布式節點。

二.Paxos的提案

暫且認為提案(Proposal)只包含value，但在接下來的推導過程中會發現如果提案(Proposal)只包含value會有問題。

暫且認為Proposer可以直接提出提案，在接下來的推導過程中會發現：如果Proposer直接提出提案也會有問題，需要增加一個學習提案的過程。

Proposer可以提出(propose)提案，Acceptor可以批準(accept)提案。如果某個提案被選定(chosen)，那么該提案里的value就被選定了。

注意：批準和選定是不一樣的，批準未必就代表選定。根據后面所述，多數Acceptor批準了某提案，才能認為該提案被選定了。

三.Paxos角色對數據達成一致的情況

對某個數據的值達成一致，指的是：Proposer、Acceptor、Learner都認為同一個value被選定(chosen)。

Proposer、Acceptor、Learner分別在什么情況才認為某個value被選定：

情況一：Proposer

只要Proposer發出的提案被Acceptor批準，那么Proposer就認為該提案里的value被選定了。

情況二：Acceptor

只要Acceptor批準了某個提案，那么Acceptor就認為該提案里的value被選定了。

情況三：Learner

Acceptor告訴Learner哪個value被選定，Learner就認為那個value被選定。

上面只有一個節點時是沒問題的，但多個節點時批準就不能等于選定了。

(2)問題描述

一.該一致性算法的基本實現目標

二.該一致性算法滿足的安全性

三.推導該一致性算法的默認條件

四.提案被選定的規定

一.該一致性算法的基本實現目標

假設有一組可以提出(propose)value的進程集合(value在提案Proposal里)，那么一個一致性算法需要做出如下保證。

保證一：在提出的這么多value中，只有一個value會被選定(chosen)

保證二：如果沒有value被提出，那么就不應該有value被選定

保證三：如果一個value被選定，那么所有進程都應該能學習(learn)或者獲取到這個被選定的value

二.該一致性算法滿足的安全性

一個分布式算法有兩個最重要的屬性：安全性(Safety)和活性(Liveness)。安全性是指那些需要保證永遠都不會發生的事情，活性是指那些最終一定會發生的事情。

對于一致性算法，安全性要求如下：

要求一：只有被提出的value才能被選定

要求二：只有一個value能被選定

要求三：如果某進程認為某value被選定，則該value必須是真的被選定

在對Paxos算法的介紹中，我們不去精確定義其活性需求，只需要確保：Paxos算法的目標是保證最終有一個提出的value被選定，當一個value被選定后，進程最終也能學習或者獲取到這個value。

三.推導該一致性算法的默認條件

假設三個角色間可通過發送消息來進行通信，那么默認以下兩個情況：

情況一：每個角色以任意的速度執行，可能因出錯而停止，也可能會重啟。同時即使一個value被選定后，所有的角色也可能失敗然后重啟。除非失敗后重啟的角色能記錄某些信息，否則重啟后無法確定被選定的值。

情況二：消息在傳遞過程中可能任意延遲、可能會重復、也可能丟失。但是消息不會被損壞，即消息內容不會被篡改，也就是無拜占庭將軍問題。即各將軍管理的軍隊被地理分割開，只能依靠通訊員傳遞信息，而通信員可能存在叛徒篡改信息欺騙將軍。

四.提案被選定的規定

下面規定在存在多個Acceptor的情況下，如何判斷選定一個提案。

規定：Proposer會向一個Acceptor集合發送提案。同樣，集合中的每個Acceptor都可能會批準(Accept)該提案。當有足夠多的Acceptor批準這個提案時，我們就認為該提案被選定了。

所以，批準和選定是不一樣的，批準未必就代表選定。多數Acceptor批準了某提案，才能認為該提案被選定了。

足夠多指的是：我們假定足夠多的Acceptor其實是整個Acceptor集合的一個子集，并且讓這個集合大得可以包含Acceptor集合中的大多數成員，因為任意兩個包含大多數Acceptor的子集至少有一個公共成員。

(3)推導過程

一.要選定一個唯一提案的最簡單方案——只允許一個Acceptor存在

二.多個Acceptor和多個Proposer——如何使得只有一個value被選定

三.提案變成了一個由編號和value組成的組合體：[編號, value]

四.如何證明P2b

五.如何根據P2c去證明P2b

約束P1：一個Acceptor必須批準它收到的第一個提案。
規定R1：一個Proposer的提案能夠發送給多個Acceptor(Acceptor集合)。
規定R2：一個提案(value)被選定需要被半數以上的Acceptor批準。
規定R3：每一個Acceptor必須能夠批準不止一個提案(value)。約束P2：如果提案[M0, V0]被選定了：
那么所有比編號M0更高的且被選定的提案，其value值必須也是V0。約束P2a：如果提案[M0, V0]被選定了：
那么所有比編號M0更高的且被Acceptor批準的提案，其value值必須也是V0。約束P2b：如果提案[M0, V0]被選定了：
那么之后任何Proposer產生的編號更高的提案，其value值必須也是V0。約束P2c：對于任意的Mn和Vn，如果提案[Mn, Vn]被提出：
那么肯定存在一個半數以上的Acceptor組成的集合S，滿足以下條件中的任意一個：條件一：S中每個Acceptor都沒有批準過編號小于Mn的提案。
條件二：S中Acceptor批準過的編號小于Mn的且編號最大的提案的value為Vn。

一.要選定一個唯一提案的最簡單方案——只允許一個Acceptor存在

要使得只有一個value被選定，最簡單的方式莫過于只有一個Acceptor，當然可以有多個Proposer，這樣Proposer只能發送提案給該Acceptor。

此時，Acceptor就可以選擇它收到的第一個提案作為被選定的提案，這樣就能夠保證只有一個value會被選定。

但是，如果這個唯一的Acceptor宕機了，那么整個系統就無法工作。因此，必須要有多個Acceptor來避免Acceptor的單點問題。

二.多個Acceptor和多個Proposer——如何使得只有一個value被選定

如果希望即使只有一個Proposer提出一個value，該value也能被選定。那么，就得到下面的約束：

約束P1：一個Acceptor必須要批準它收到的第一個提案。

但是，這又會引出另一個問題：如果每個Proposer分別提出不同的value，發給不同的Acceptor。根據約束P1，每個Acceptor分別批準自己收到的第一個value，這就會導致不同的value被選定，出現value不一致。于是滿足不了只有一個value會被選定的要求，如下圖示：

上面是由于："一個提案只要被一個Acceptor批準，則該提案的value就被選定了"，以及"Acceptor和Proposer存在多個"，才導致value不一致問題。因此問題轉化為：在存在多個Acceptor和多個Proposer情況下，如何進行提案的選定？

最簡單的情況：如果一個Proposer的提案只發送給一個Acceptor，由上圖可知必然會導致value不一致問題。因此，可以有以下規定：

規定R1：一個Proposer的提案能夠發送給多個Acceptor(Acceptor集合)。

既然一個Proposer的提案能夠發送給多個Acceptor，當Proposer可以向Acceptor集合發送提案時，集合中的每個Acceptor都可能會批準該提案。當有足夠多的Acceptor批準這個提案時，我們才可認為該提案被選定了。那么什么才是足夠多呢？

我們假定足夠多的Acceptor是整個Acceptor集合的一個子集，并且讓該子集大得可以包含Acceptor集合中的大多數成員，因為任意兩個包含大多數Acceptor的子集至少有一個公共成員。因此，有了如下規定：

規定R2：一個提案(value)被選定需要被半數以上的Acceptor批準。

在約束P1(一個Acceptor必須要批準它收到的第一個提案)的基礎上，再加上規定R2(一個提案(value)被選定需要被半數以上的Acceptor批準)，假如每個Acceptor最多只能批準一個提案，那么又回到了下圖的問題：

因此，有了如下規定：

規定R3：每一個Acceptor必須能夠批準不止一個提案(value)。

既然一個Proposer的提案能夠發送給多個Acceptor，那么一個Acceptor就會收到多個提案。

考慮情形1：當多個Proposer將其提案發送給多個Acceptor后，突然大部分Acceptor掛了，只剩一個Acceptor存活，如何進行提案的批準。該存活的Acceptor收到多個提案，由規定R3，它可以批準多份提案，那么如何保證最后只有一個提案被選定保證value一致。

考慮情形2：有5個Acceptor，其中2個批準了提案v1，另外3個批準了提案v2。此時如果批準v2的3個Acceptor中有一個掛了，那么v1和v2的批準者都變成了2個，此時就沒法選定最終的提案。

因此，可以引入全局唯一編號來唯一標識每一個被Acceptor批準的提案：當一個具有某value值的提案被半數以上的Acceptor批準后，我們就認為該value被選定了，也就是該提案被選定了。唯一編號的作用其實就是用來輔助：當出現多個value都被同一半數批準時，可以選定唯一的value，比如選擇唯一編號最大的value。

三.提案變成了一個由編號和value組成的組合體：[編號, value]

由上可知，選定其實認的只是value值。當提案[value]變成[編號, value]后，是允許多個提案[編號, value]被選定的。根據規定R2(一個提案被選定需要半數以上的Acceptor批準)，存在多個提案被半數以上的Acceptor批準，此時就有多個提案被選定。那么就必須保證所有被選定的提案[編號, value]都具有相同的value值。否則，如果被選定的多個提案[編號, value]其value不同，又會出現不一致。因此，可以得到如下約束：

約束P2：如果提案[M0, V0]被選定了，那么所有比編號M0更高的且被選定的提案，它的value值也必須是V0。

編號可理解為提案被提出的時間，比編號M0更高可理解為晚提出。所以提案[M0,V0]被選定后，所有比該提案晚提出的提案被選定時。為了value一致，那么這些晚提出的被選定的提案的value也要是V0。而所有比該提案早提出的提案，可以忽視它不進行選定即可。

一個提案[編號, value]只有被Acceptor批準才可能被選定，因此我們可以把約束P2改寫成對"Acceptor批準的提案"的約束P2a：

約束P2a：如果提案[M0, V0]被選定了，那么所有比編號M0更高的且被批準的提案，它的value值也必須是V0。

所以提案[M0,V0]被選定后，所有比該提案晚提出的提案被批準時。為了value一致，那么這些晚提出的被批準的提案的value也要是V0。而所有比該提案早提出的提案，可以忽視它不進行批準即可。因此只要滿足了P2a，就能滿足P2。

由于通信是異步的，一個提案可能會在某個Acceptor還未收到任何提案時就被選定了。假設有5個Acceptor和2個提案，在Acceptor1沒收到任何提案情況下，其他4個Acceptor已經批準了來自Proposer2的提案。而此時Proposer1產生了一個具有其他value值的且編號更高的提案，并發送給了Acceptor1。那么根據P1，Acceptor1要批準該提案，但這與約束P2a矛盾。

因此，如果要同時滿足P1和P2a，需要對P2a進行強化。因為P2a只是說晚提出的提案被Acceptor批準時value才為V0，需要對P2a強化為晚提出的提案不管是否被批準其value都是V0。

約束P2b：如果提案[M0, V0]被選定了，那么之后任何Proposer產生的編號更高的提案，其value值必須也是V0。

否則一個提案得到多數批準被選定后，再提出一個值不同的新提案，這個提案會作為第一個提案發到某個Acceptor然后被批準，與P2a矛盾。

因為一個提案必須在被Proposer提出后才能被Acceptor批準，所以P2b可以推出P2a，P2a可以推出P2。

P2：提案[M,V]被選定后，晚提出的提案如果被選定，那么其value也是V；(否則會出現選定多個value了)
P2a：提案[M,V]被選定后，晚提出的提案如果被批準，那么其value也是V；(P2a可以推出P2)
P2b：提案[M,V]被選定后，晚提出的提案不管是否被批準，那么其value也是V；(否則根據P1可能會出現與P2a矛盾的情況)
而對于比提案[M,V]早提出的提案，可以采取忽略無視處理；(P2b可以推出P2a)P1：一個Acceptor必須批準它收到的第一個提案；(否則只有一個提案被提出時就無法選定一個value了)
R1：一個Proposer的提案能夠發送給多個Acceptor(Acceptor集合)；(否則根據P1, 就會出現選定多個value了)
R2：一個提案(value)被選定需要被半數以上的Acceptor批準；(選定提案時對足夠多的規定)
R3：每一個Acceptor必須能夠批準不止一個提案(value)；(否則一個提案就沒法做到被半數以上的Acceptor批準了)

四.如何證明P2b

即提案[M0,V0]被選定后，Proposer提出的編號更高的提案的value都為V0。如果要證明P2b成立，則具體是要證明：假設提案[M0,V0]已被選定，則編號大于M0的提案Mn，其value值都是V0。

通過對Mn使用第二數學歸納法來證明，也就是說需要證明結論：假設編號在M0到Mn-1之間的提案，其value值都是V0，那么編號為Mn的提案的value值也為V0。

第二數學歸納法：
要證明n時的value值為v，則先假設0~n-1時的value值都為v；
然后再推導出n時的value值為v；

證明：

根據第二數學歸納法，當提案[M0,V0]被選定時，要證明編號大于M0的提案Mn，其value值都是V0。也就是假設編號M0到Mn-1的提案的value值都是V0時，證明Mn的value值為V0。

因為編號為M0的提案已經被選定了，這意味著存在一個由半數以上的Acceptor組成的集合C，C中的每個Acceptor都批準了編號為M0的提案。

根據歸納假設，編號為M0的提案被選定意味著：C中的每個Acceptor都批準了一個編號在M0到Mn-1范圍內的提案，并且每個編號在M0到Mn-1范圍內的被Acceptor批準的提案，其value為V0。

根據歸納假設，因為編號M0到Mn-1的提案的value值都是V0，所以C中的Acceptor1可以批準M0提案，Acceptor2可以批準M0 + M1提案，Acceptor3可以批準M0 + M1 + M2 + M3提案......也就是C中每個Acceptor批準的一個M0到Mn-1范圍內的提案的value都是V0。

因為任何包含半數以上Acceptor的集合S都至少包含C中的一個成員，所以S中必然存在一個Acceptor，它批準的M0到Mn-1提案的value都是V0。這是根據歸納假設得出的結論，因此可以根據此而進一步加強到P2c。

因此只要滿足如下P2c，就能讓編號為Mn的提案的value值也為V0，也就是只要滿足P2c，就可以證明P2b。只要滿足如下P2c約束 + 上述歸納假設得出的結論，就能證明Mn也為V0。

約束P2c：對于任意的Mn和Vn，如果提案[Mn, Vn]被提出，則存在一個半數以上的Acceptor組成的集合S，滿足以下條件中的任一個。

條件一：S中每個Acceptor都沒有批準過編號小于Mn的提案

條件二：S中Acceptor批準過的編號小于Mn且編號最大的提案的value為Vn

五.如何根據P2c去證明P2b

從P1到P2c的過程其實是對一系列條件的逐步加強。如果需要證明這些條件可以保證一致性，那么就要反向推導：P2c => P2b => P2a => P2，然后通過P1和P2來保證一致性。

實際上，P2c規定了每個Propeser應該如何產生一個提案(P2c規定的提案生成規則)。對于產生的每個提案[Mn, Vn]，需要滿足：存在一個由超過半數的Acceptor組成的集合S滿足以條件的任意一個：

條件一：要么S中沒有Acceptor批準過編號小于Mn的任何提案

條件二：要么S中所有Acceptor批準的所有編號小于Mn的提案中，編號最大的那個提案的value值為Vn

當每個Proposer都按照這個規則來產生提案時，就可以保證滿足P2b了。

下面在P2c的生成規則下證明P2b：

首先假設提案[M0,V0]被選定了，設比該提案編號M0大的提案為[Mn,Vn]，那么在P2c的生成提案規則前提下，證明Vn = V0；

數學歸納法第一步：驗證某個初始值成立

當Mn = M0 + 1時，如果有這樣一個編號為Mn的提案，根據P2c的提案生成規則可知，一定存在一個超半數Acceptor的子集S，由于提案[M0, V0]已被選定，所以S中必然有Acceptor批準過編號小于Mn的提案，也就是M0提案，即此時P2c的提案生成規則的條件一不成立，進入條件二來生成Vn。

所以，由于S中有Acceptor已經批準了編號小于Mn的提案(即M0提案)。于是，Vn只能是多數集S中編號小于Mn但為最大編號的那個提案的值。而此時因為Mn = M0 + 1，因此理論上編號小于Mn但為最大編號的那個提案肯定是[M0, V0]，同時由于S和選定[M0, V0]的Acceptor集合都是多數集，故兩者肯定有交集，也就是說由于兩者都是多數集，所以S中必然存在一個Acceptor批準了M0。根據Mn = M0 + 1，M0其實就是編號小于Mn但是編號是最大的。這樣Proposer在確定Vn取值的時候，就一定會選擇V0(根據Vn只能是多數集S中編號小于Mn但為最大編號的那個提案的值)。

數學歸納法第二步：假設編號在M0 + 1到Mn - 1內成立，推導編號Mn也成立

根據假設，編號在M0 + 1到Mn - 1區間內的所有提案的value值為V0，需要證明的是編號為Mn的提案的value值也為V0。

由于編號在M0 + 1到Mn - 1區間內的所有提案都是按P2c的規則生成的，所以一定存在一個超半數Accepter的子集S，而且S中有Acceptor已經批準了編號小于Mn的提案(P2c條件一不成立)。于是，Vn只能是多數集S中編號小于Mn但為最大編號的那個提案的值。如果這個最大編號落在M0 + 1到Mn - 1區間內，那么Vn肯定是V0。如果不落在M0 + 1到Mn - 1區間內，則它的編號不可能比M0小，肯定是M0。這時因為S肯定會與批準[M0, V0]這個提案的Acceptor集合S'有交集，也就是說S中肯定存在一個Acceptor是批準了[M0, V0]的。又由于此時S中編號最大的提案其編號就是M0，根據上述，Vn只能是多數集S中編號小于Mn但為最大編號的那個提案的值。從而可知，此時Vn也是V0，因此得證。

(4)Proposer生成提案

在P2c的基礎上，如何進行提案的生成？

對于一個Proposer來說，獲取那些已經被通過的提案遠比預測未來可能會被通過的提案簡單。所以Proposer產生一個編號為M的提案時，必須要知道：當前某個已被半數以上Acceptor批準的編號小于M但為最大編號的提案，必須要求：所有的Acceptor都不要再批準任何編號小于M的提案。于是就引出了如下Proposer生成提案的算法：

步驟一：Proposer選擇一個新的編號M向某Acceptor集合的成員發送請求，即編號為M的提案的Prepare請求，要求集合中的Acceptor做出兩個回應。回應一是：向Proposer承諾，保證不再批準任何編號小于M的提案。回應二是：如果Acceptor已經批準過任何提案，那么就向Proposer反饋當前其已批準的、編號小于M但為最大編號的提案。

步驟二：如果Proposer收到了來自半數以上的Acceptor的響應結果，那么就可產生提案[M, V]，這里V取收到響應的編號最大的提案的value值。當然還存在另外一種情況，就是半數以上的Acceptor都沒有批準任何提案。也就是響應中不包含任何提案，那么此時V就可以由Proposer任意選擇。Proposer確定好生成的提案[M, V]后，會將該提案再次發送給某個Acceptor集合，并期望獲得它們的批準，此請求稱為編號為M的提案的Accept請求。

注意：此時接收Accept請求的Acceptor集合，不一定是之前響應Prepare請求的Acceptor集合。

(5)Acceptor批準提案

根據Proposer生成提案的算法，一個Acceptor可能會收到來自Proposer的兩種請求：編號為M的提案的Prepare請求和編號為M的提案的Accept請求。一個Acceptor會對Prepare請求做出響應的條件是：Acceptor可以在任何時候響應一個Prepare請求。一個Acceptor會對Accept請求做出響應的條件是：在不違背Acceptor現有承諾前提下，可響應任意Accept請求。

Acceptor可以忽略任何請求而不用擔心破壞算法的安全性。因此，我們這里要討論什么時候Acceptor可以響應一個請求。我們對Acceptor批準提案給出如下約束：

約束P1a：一個Acceptor只要尚未響應過任何編號大于M的Prepare請求，那么它就可以批準這個編號為M的提案。

可見，P1a包含了P1(一個Acceptor必須批準它收到的第一個提案)。

假設一個Acceptor收到一個編號為M的Prepare請求，在此之前它已經響應過編號大于M的Prepare請求。根據P1a，該Acceptor不可能再批準任何新的編號為M的提案，Acceptor也就沒有必有對這個Prepare請求做出響應。因此，該Acceptor可以忽略編號為M的Prepare請求。

因此，每個Acceptor只需記住：它已批準提案的最大編號 + 它已響應Prepare請求的最大編號。這樣即便Acceptor出現故障或者重啟，也能保證滿足P2c生成提案的規則。

而對于Proposer來說，只要它可以保證不會產生具有相同編號的提案，那么就可以丟棄任意的提案以及它所有的運行時狀態信息。

(6)Paxos算法描述

結合Proposer和Acceptor對提案的處理邏輯；可以得出類似于兩階段提交的算法執行過程。

階段一：(Prepare請求)

一.Proposer選擇一個提案編號M，然后向半數以上的Acceptor發送編號為M的Prepare請求。

二.如果一個Acceptor收到一個編號為M的Prepare請求，且M大于該Acceptor已經響應過的所有Prepare請求的編號，那么它就會將它已經批準過的編號最大的提案作為響應反饋給Proposer，同時該Acceptor承諾不再批準任何編號小于M的提案。

階段二：(Accept請求)

一.如果Proposer收到半數以上Acceptor，對其發出的編號為M的Prepare請求的響應，那么它就會發送一個針對[M, V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編號最大的提案的value。如果響應中不包含任何提案，那么V就由Proposer自己決定。

二.如果Acceptor收到一個針對[M, V]提案的Accept請求，只要該Acceptor沒有對編號大于M的Prepare請求做出過響應，它就批準該提案。

(7)Learner學習被選定的value

Learner獲取提案，有三種方案：

(8)如何保證Paxos算法的活性

一個極端的活鎖場景：

(9)總結

二階段提交協議解決了分布式事務的原子性問題，保證了分布式事務的多個參與者要么都執行成功，要么都執行失敗。但是在二階段解決部分分布式事務問題的同時，依然存在一些難以解決的諸如同步阻塞、無限期等待和腦裂等問題。

三階段提交協議則是在二階段提交協議的基礎上，添加了PreCommit過程，從而避免了二階段提交協議中的無限期等待問題。

Paxos算法引入過半的理念，也就是少數服從多數的原則。Paxos算法支持分布式節點角色之間的輪換，極大避免了分布式單點故障。因此Paxos算法既解決了無限期等待問題，也解決了腦裂問題。

整個Paxos算法就是想說明：每個Proposer生成的提案都去爭取大多數Acceptor的批準。一旦有某個Proposer生成的提案[M0, V0]被大多數批準了，即便后面發現還有更多其他Proposer生成的提案[Mn, Vn]也被大多數Acceptor批準，那么這些提案的value值其實都是一樣的，都為V0。因此就可以讓每個Proposer都統一為一個value值為V0的提案，從而保證一致性。

7.Paxos協議的核心思想

(1)Paxos協議的核心思想

(2)Paxos協議的基本概念

(3)Paxos協議過程

(4)Paxos協議最終解決什么問題

(5)Paxos協議證明

(6)為什么要被多數派接受

(7)為什么需要做一個承諾

(8)為什么第二階段A要從返回的提議中選擇一個編號最大的

(9)Paxos協議的學習過程

(1)Paxos協議的核心思想

"與其預測未來，不如限制未來"，這應該是Paxos協議的核心思想。Paxos協議本身是比較簡單的，如何將Paxos協議工程化才是真正的難題。

(2)Paxos協議的基本概念

Proposal Value：提議的值

Proposal Number：提議編號，編號不能沖突

Proposal：提議 = 提議的值 + 提議編號

Proposer：提議發起者

Acceptor：提議接受者

Learner：提議學習者

說明一：協議中的Proposer有兩個行為，一個是向Acceptor發Prepare請求，另一個是向Acceptor發Accept請求。

說明二：協議中的Acceptor則會根據協議規則，對Proposer的請求作出應答。

說明三：最后Learner可以根據Acceptor的狀態，學習最終被確定的值。

為方便討論，記[n, v]為提議編號為n、提議值為v的提議，記(m, [n, v])為承諾了Prepare(m)請求編號不再比m小，并接受過提議[n, v]。

(3)Paxos協議過程

一.第一階段A

Proposer選擇一個提議編號n，向所有的Acceptor廣播Prepare(n)請求。

二.第一階段B

Acceptor接收到Prepare(n)請求，若提議編號n比之前接收的Prepare請求都要大，則返回承諾將不會接收提議編號比n小的提議，并且帶上之前Accept的提議中編號小于n的最大的提議，否則不予理會。

三.第二階段A

Proposer得到了多數Acceptor的承諾后，如果沒有發現有一個Acceptor接受過一個值，那么向所有的Acceptor發起自己的值和提議編號n。否則，從所有接受過的值中選擇對應的提議編號最大的，作為提議的值，此時提議編號仍然為n。

四.第二階段B

Acceptor接收到提議后，如果該提議編號不違反自己做過的承諾，則接受該提議。

需要注意的是，Proposer發出Prepare(n)請求后，得到多數派的應答。然后可以隨便再選擇一個多數派廣播Accept請求，這時不一定要將Accept請求發給有應答的Acceptor。

五.協議過程總結

上面的圖例中：首先P1廣播了Prepare請求，但是給A3的Prepare請求丟失了。不過A1、A2成功返回了，即該Prepare請求得到多數派的應答。然后P1可以廣播Accept請求，但是給A1的Accept請求丟失了。不過A2、A3成功接受了這個提議，因為這個提議被多數派(A2、A3形成多數派)接受，所以我們稱被多數派接受的提議對應的值被Chosen。

情況一：如果三個Acceptor之前都沒有接受過提議(即Accept請求)，那么在第一階段B中，就不用返回接受過的提議。

情況二：如果三個Acceptor之前接受過提議(即Accept請求)，那么就需要在第一階段B中，帶上之前Accept的提議中編號小于n的最大的提議值，進行返回。

如下圖示：Proposer廣播Prepare請求之后，收到了A1和A2的應答，應答中攜帶了它們之前接受過的[n1, v1]和[n2, v2]。Proposer則根據n1、n2的大小關系，選擇較大的那個提議對應的值。比如n1 > n2，那么就選擇v1作為提議值，最后向Acceptor廣播提議[n, v1]。

(4)Paxos協議最終解決什么問題

當一個提議被多數派接受后，這個提議對應的值會被Chosen(選定)。一旦有一個值被Chosen(選定)，那么只要按照協議的規則繼續交互。后續被Chosen的值都是同一個值，也就是保持了這個Chosen值的一致性。

(5)Paxos協議證明

上文就是基本Paxos協議的全部內容，其實是一個非常確定的數學問題。下面用數學語言表達，進而用嚴謹的數學語言加以證明。

一.Paxos原命題

如果一個提議[n0, v0]被大多數Acceptor接受，那么不存在提議[n1, v1]被大多數Acceptor接受，其中n0 < n1，v0 != v1。

二.Paxos原命題加強

如果一個提議[n0, v0]被大多數Acceptor接受，那么不存在Acceptor接受提議[n1, v1]，其中n0 < n1，v0 != v1。

三.Paxos原命題進一步加強

如果一個提議[n0, v0]被大多數Acceptor接受，那么不存在Proposer發出提議[n1, v1]，其中n0 < n1，v0 != v1。

如果"Paxos原命題進一步加強"成立，那么"Paxos原命題"顯然成立。下面通過證明"Paxos原命題進一步加強"，從而證明"Paxos原命題"。

四.歸納法證明

假設提議[m, v](簡稱提議m)被多數派接受，那么提議m到n(如果存在)對應的值都為v，其中n不小于m(m <= n)。

這里對n進行歸納假設，當n = m時，結論顯然成立。設n = k時結論成立，即如果提議[m, v]被多數派接受，那么提議m到k對應的值都為v，其中k不小于m(m <= k)。

當n = k + 1時，若提議k + 1不存在，那么結論成立。若提議k + 1存在，對應的值為v1。

因為提議m已經被多數派接受，又k + 1的Prepare被多數派承諾并返回結果。基于兩個多數派必有交集，易知提議k + 1的第一階段B有帶提議回來。那么v1是從返回的提議中選出來的，不妨設這個值是選自提議[t, v1]。

根據第二階段B，因為t是返回的提議中編號最大的，所以t >= m。又由第一階段A，知道t < n，即t < k + 1，也就是m <= t < k + 1。所以根據假設可知，提議m到k對應的值都為v。所以再根據m <= t < k + 1，可得出t對應的值就為v，即有v1 = v。因此由假設的n = k結論成立，可以推出n = k + 1成立。

于是對于任意的提議編號不小于m的提議n，對應的值都為v，所以命題成立。

五.反證法證明

要證明的是：如果一個提議[n0, v0]被大多數Acceptor接受，那么不存在Proposer發出提議[n1, v1]，其中n0 < n1，v0 != v1。

假設存在，不妨設n1是滿足條件的最小提議編號。

即存在提議[n1, v1]，其中n0 < n1，v0 != v1。-----------------------(A)

那么提議n0、n0 + 1、n0 + 2、...、n1 - 1對應的值為v0。-------------(B)

由于存在提議[n1, v1]，則說明大多數Acceptor已經接收n1的Prepare，并承諾將不會接受提議編號比n1小的提議。

又因為[n0, v0]被大多數Acceptor接受，所以存在一個Acceptor既對n1的Prepare進行了承諾，又接受了提議n0。

由協議的第二階段B可知，這個Acceptor先接受了[n0, v0]。所以發出[n1, v1]提議的Proposer會從大多數的Acceptor返回中得知，至少某個編號不小于n0而且值為v0的提議已經被接受。----------(C)

由協議的第二階段A知，該Proposer會從已經被接受的值中選擇一個提議編號最大的值，作為提議的值。由(C)知可該提議編號不小于n0，由協議第二階段B可知，該提議編號小于n1。于是由(B)知v1 == v0，與(A)矛盾。

所以命題成立。

(6)為什么要被多數派接受

因為兩個多數派之間必有交集，所以Paxos協議一般是2F + 1個Acceptor。然后允許最多F個Acceptor停機，而保證協議依然能夠正常進行，最終得到一個確定的值。

(7)為什么需要做一個承諾

可以保證第二階段A中Proposer的選擇不會受到未來變化的干擾。另外，對于一個Acceptor而言，這個承諾決定了：它回應提議編號較大的Prepare請求和接受提議編號較小的Accept請求的先后順序。

(8)為什么第二階段A要從返回的提議中選擇一個編號最大的

這樣選出來的提議編號一定不小于已經被多數派接受的提議編號，進而可以根據假設得到該提議編號對應的值是Chosen的那個值。

(9)Paxos協議的學習過程

如果一個提議被多數Acceptor接受，則這個提議對應的值被選定。一個簡單直接的學習方法就是：獲取所有Acceptor接受過的提議，然后看哪個提議被多數的Acceptor接受，那么該提議對應的值就是被選定的。

另外一個學習方法是：把Learner看作一個Proposer，根據協議流程，發起一個正常的提議，然后看這個提議是否被多數Acceptor接受。

注意：這里強調"一個提議被多數Acceptor接受"，而不是"一個值被多數Acceptor接受"。

上圖中，提議[3, v3]，[5, v3]分別被B、C接受。雖然出現了v3被多數派接受，但不能說明v3被選定(Chosen)。只有提議[7, v1]被多數派(A和C組成)接受，才能說v1被選定，而這個選定的值隨著協議繼續進行不會改變。

8.ZAB算法簡述

zk的ZAB協議是Paxos協議的一個精簡版。ZAB協議即Zookeeper Atomic Broadcast，zk原子廣播協議。ZAB協議是用來保證zk各個節點之間數據的一致性的。

ZAB協議包括以下特色：

特色一：Follower節點上全部的寫請求都轉發給Leader

特色二：寫操作嚴格有序

特色三：使用改編的兩階段提交協議來保證各個節點的事務一致性，半數以上的參與者回復yes即可

廣播模式：

廣播模式就是指zk正常工作的模式。正常狀況下，一個寫入命令會通過以下步驟被執行：

步驟一：Leader從客戶端或者Follower那里收到一個寫請求

步驟二：Leader生成一個新的事務并為這個事務生成一個唯一的ZXID

步驟三：Leader將這個事務以Proposal形式發送給全部的Follower節點

步驟四：Follower節點將收到的事務請求加入隊列，并發送ACK給Leader

步驟五：當Leader收到大多數Follower的ACK消息，會發送Commit請求

步驟六：當Follower收到Commit請求時，會判斷該事務的ZXID是否是比隊列中任何事務的ZXID都小來決定Commit

恢復模式：

當第一次啟動集群時，先啟動的過半機器中ZXID、myid最大的為Leader。當Leader故障時，zk集群進入恢復模式，此時zk集群不能對外提供服務。此時必須選出一個新的Leader完成數據一致后才能從新對外提供服務，zk官方宣稱集群能夠在200毫秒內選出一個新Leader。

正常模式下的幾個步驟，每一個步驟都有可能由于Leader故障而中斷，可是恢復過程只與Leader有沒有Commit有關。

首先看前三個步驟，只做了一件事，把事務發送出去。若是事務沒有發出去，全部Follower都沒有收到這個事務，Leader故障了，全部的Follower都不知道這個事務的存在。

根據心跳檢測機制，Follower發現Leader故障，需要重新選出一個Leader。此時會根據每一個節點ZXID來選擇。誰的ZXID最大，表示誰的數據最新，就會被選舉成新的Leader。若是ZXID都同樣，那么就表示在Follower故障以前，全部的Follower節點數據一致，此時選擇myid最大的節點成為新的Leader。

所以由于有一個固定的選舉標準會加快選舉流程，新的Leader選出來后，全部節點的數據同步一致后就能夠對外提供服務。

假設新的Leader選出來以后，原來的Leader又恢復了，此時原來的Leader會自動成為Follower。

以前的事務即便發送給新的Leader，由于新的Leader已經開啟了新的紀元，而原先的Leader中ZXID仍是舊的紀元，所以該事務就會被丟棄，而且該節點的ZXID也會更新成新的紀元。紀元就是標識當前Leader是第幾任Leader，至關于改朝換代時候的年號。

若是在Leader故障以前已經Commit，zk會根據ZXID或者myid選出數據最新的那個Follower作為新的Leader。

新Leader會為Follower創建FIFO的隊列，首先將自身有而Follower缺失的事務發送給該隊列，然后再將這些事務的Commit命令發送給Follower，這樣便保證了全部的Follower都保存了全部的事務數據。

ZAB協議確保那些已經在Leader提交的事務最終會被全部服務器提交，ZAB協議確保丟棄那些只在Leader提出或復制，但是沒有提交的事務。