【分散式技術專題】「分散式技術架構」一文帶你釐清分散式事務協定及分散式一致性協定的演演算法原理和核心流程機制（Paxos篇）

概念簡介

Paxos是一種基於訊息傳遞具有高度容錯特性的一致性演演算法，是目前公認的解決分散式一致性問題最有效的演演算法之一。

發展歷史

Paxos演演算法的發展歷史追溯到古希臘，當時有一個名為「Paxos「的小島， 島上採用一會的形式通過法令， 議會中議員通過信使進行訊息傳遞，議員與信使都是兼職的，他們隨時都有可能會離開議會，並且信使有可能傳遞重複的資訊，也有可能一去不復返，因此議會要保證在這種情況下法令仍然能夠正確的產生，並且不會起衝突。

Paxos演演算法分析

對於Paxos演演算法而言要解決上述資訊傳遞的一致性問題，那麼要保證一下幾點：

• 在這些提案中，只有一個被選定
• 如果沒有提案被提出，就不會有選定的提案
• 當提案被選定以後，程序應該可以獲取被選定的提案資訊

對於一致性來說，安全性需求如下

• 只有被提出的提案才能被選定
• 只有一個提案被選定
• 如果某個程序認為某個提案被選定了，那麼這個提案必須是真的被選定的那個

三種參與角色

• Proposer（提議者）
• Acceptor（決策者）
• Leamner（最終決策學習者）

問題場景分析

一個元素參與者可能扮演多個角色 （Proposer | Acceptor | Leamner） ，假設不同的參與者之間可以通過收發訊息來進行通訊。每個參與者以任意的速度執行，可能會因為出錯而停止，也可能會重啟，訊息在傳輸過程中可能會出現不可預知的延遲，也有可能會重複或者丟失，但訊息不會被損壞，即訊息內容不能被篡改。

Paxos演演算法場景問題分析

首先，我們採用將建立角色處理模式的場景化分析，先從Acceptor的模式開始處理和分析，分析對應的執行流程以及對應的問題。

單個Acceptor模式

在處於單Acceptor模式下的時候，如以下圖所示。

最簡單的選定方式是隻有一個Acceptor， Proposer傳送給該Acceptor提案以後， Acceptor直接選擇第一個提案為被選定的提案。但這種做法一旦Acceptor出問題， 整個系統將無法正常工作。

多個Acceptor模式

Proposer向多個Acceptor集合傳送提案， 每個Acceptor都可能會批准(Accept) 該提案， 當足夠多個Acceptor批准這個提案的時候， 我們就認為該提案被選定了。

實現一致性的條件約束（1）

在沒有失敗和訊息丟失的情況下，如果我們希望即使只有一個提案被提出，仍然可以選出一個提案，1個Acceptor必須批准他收到的第一個提案。

該條件約束所出現的問題

如果多個提案被不同的Proposer同時提出， 這可能會導致雖然每個Acceptor都批准了他收到的第一個提案， 但是沒有一個提案是多個人批准的，也就是沒有多數的Acceptor集合，如下圖所示。

為了解決此問題所以引入了【實現一致性的條件約束（2）】進行資料控制。

實現一致性的條件約束（2）

一個提案被選定需要被半數以上的Acceptor接受。

它是在【實現一致性的條件約束（1）】的基礎上， 一個Acceptor能夠批准不止一個提案。我們使用全域性的編號來唯一的標識每一個Acceptor批准的提案， 當一個具有某Value的提案被半數以上的Acceptor批准以後， 我們就認為該Value被選定。

注意：提案和value不是一個概念， 提案是由一個編號與value組成的結構體， 因此我們用【編號，Value】來表示一個提案。

提案的結構體分析

提案的資訊資料結構體主要有：提案編號+value兩部分組成。

• 提案編號：給每個提案加上一個提案編號，表示提案被提出的順序，不同的編號可以有相同的內容。
• value：提案的內容

該條件約束所出現的問題

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

為了解決此問題所以引入了【實現一致性的條件約束（3）】進行資料控制。

實現一致性的條件約束（3）

如果提案編號為M， Value為V的提案(即【M，V】)被選定了，那麼所有比M_編號更高的， 且被選定的提案， 其Value值必須也是V。

因為提案編號是全序的， 【實現一致性的條件約束（3）】就保證了只有一個Value值被選定這一關鍵安全性屬性。同時，一個提案被選定，其首先必須被至少一個Acceptor批准， 因此我們可以通過滿足如下條件來滿足【實現一致性的條件約束（3）】。

案例推薦

假設總的有5個Acceptor，Proposer2提出 [M1,V1] 的提案，Acceptor2~5（半數以上）均接受了該提案，於是對於Acceptor 2~5和Proposer2來講， 它們都認為V1被選定。

Acceptor1剛剛從宕機狀態恢復過來(之前Acceptor1沒有收到過任何提案) ， 此時Proposer1向Acceptor1傳送了[M2, V2] 的提案(V2且M2>M1) ，對於Acceptorl來講， 這是它收到的第一個提案。根據【實現一致性的條件約束（1）】(一個Acceptor必須接受它收到的第一個提案) ，從而Acceptor1必須接受該提案！同時Acceptor1認為V2被選定，這就出現了兩個問題。

問題分析

1. Acceptor1認為V2被選定，Acceptor2~5和Proposer2認為V1被選定，出現了不一致。

2. V1被選定了，但是編號更高的被Acceptor1接受的提案[M2,V2] 的value為V2，且V2不等於V1。且V2的編號還高於V1。

實現一致性的條件約束（4）

如果一個提案【M，V】被選定後， 那麼之後任何Proposer產生的編號更高的提案， 其Value的值都為V。

問題分析

如何確保在某個Value為V的提案被選定後， Proposer 提出的編號更高的提案的Value都是V呢?

實現分析

任意的N和V， 如果提案 [ N,V ] 被提出，那麼存在一個半數以上的Acceptor組成的集合S，需要執行以下兩個操作步驟：

• 集合S內的每個Acceptor都沒有批准過編號小於N的提案。
• 如果Acceptor已經接受過提案，那麼就向Proposer響應已經接受過的編號小於N的最大編號的提案。

Proposer生成提案

對於一個Proposer來說， 獲取那些已經通過的提案遠比預測未來可能會通過的提案來的簡單。因此Proposer在產生一個編號為M的提案時， 必須要知道當前某一個將要或已經被半數以上Acceptor批准的編號小於M但未最大的編號的提案。並且，Proposer會要求所有Acceptor都不要批准任何編號小於M的提案。

Proposer生成提案之前（Prepare階段）

應該先去學習已經被選定或者可能被選定的value，然後以該value作為自己提出的提案的value。如果沒有value被選定， Proposer才可以自己決定value的值。這樣才能達成一致。這個學習的階段是通過一個 【Prepare階段】 請求實現的。

• 向Proposer承諾保證不再接受任何編號小於N的提案
• 如果Acceptor已經接受過提案，那麼就向Proposer響應已經接受過的編號小於N的最大編號的提案

提案生成演演算法

如果Proposer收到了平數以上的Acceptor的響應， 那麼它就可以生成編號為N， Value為V的提案[N,V] 。這裡的V是所有的響應中編號最大的提案的Value。如果所有的響應中都沒有提案， 那麼此時V就可以由Proposer自己選擇。

Proposer生成提案之後（Accept請求）

Proposer將該提案傳送給半數以上的Acceptor集合， 並期望這些Acceptor能接受該提案。我們稱該請求為Accept請求。

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

Acceptor批准提案

• Acceptor可以忽略任何請求(包括Prepare請求和Accept請求) 而不用擔心破壞演演算法的安全性。因此， 我們這裡要討論的是什麼時候Acceptor可以響應一個請求。

• 一個Acceptor只要尚未響應過任何編號大於N的Prepare請求， 那麼他就可以接受這個編號為N的提案。

演演算法總結

階段一

1. Proposer選擇一個提案編號M， 然後向Acceptor的某個超過半數的子整合員傳送編號為M的Prepare請求。
2. 如果一個Acceptor收到一個編號為M的Prepare請求， 且編號M大於該Acceptor已經響應的所有Prepare請求的編號， 那麼它就會把已經批准過的最大的編號的提案作為相應反饋給Proposer， 同時該Acceptor會承諾不會在批准任何編號小於M的提案。

階段二

1. 如果Proposer收到來自半數以上的Acceptor對於其發出的編號為M的Prepare請求的響應，那麼它就會傳送一個針對【M，V】提案的Accept請求給Acceptor。

注意：V的值就是收到的響應中編號最大的提案的值，如果響應中不包含任何提案，那麼他就是任意值

2. 如果Acceptor收到的這個針對【M， V】的提案的Accept請求， 只要該Acceptor尚未對編號大於M的Prepare請求作出響應， 他就可以通過這個提案。

看到這裡是不是覺得和我們分散式事務中的2PC的思路和流程差不多啊！

通知學習Learner的方案

方案1

一旦Acceptor批准了一個提案， 就將該提案傳送給所有的Leamer

方案2

讓所有的Acceptor將它們對提案的批准情況， 統一傳送給一個Learner， 再由它通知其他的Learner

方案3

方案2的主節點存在單點問題， 可以將主Leaner的範圍擴大， 即Acceptor可以將批准資訊傳送給一個特定的Learner集合， 該集合中每個Leamer都可以在一個提案被選定後通知其他Leaner。

給你們的問題

1. 設定多少個Acceptor最為合適？

2. 如何控制每個Acceptor最多隻能批准一個提案？