概念簡介
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] 的提案，Acceptor25（半數以上）均接受了該提案，于是對于Acceptor 25和Proposer2來講， 它們都認為V1被標明。
Acceptor1剛剛從當機狀态恢複過來(之前Acceptor1沒有收到過任何提案) ， 此時Proposer1向Acceptor1發送了[M2, V2] 的提案(V2且M2>M1) ，對于Acceptorl來講， 這是它收到的第一個提案。根據【實作一緻性的條件限制（1）】(一個Acceptor必須接受它收到的第一個提案) ，進而Acceptor1必須接受該提案！同時Acceptor1認為V2被標明，這就出現了兩個問題。
問題分析
- Acceptor1認為V2被標明，Acceptor2~5和Proposer2認為V1被標明，出現了不一緻。
- 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的提案。
算法總結
階段一
- Proposer選擇一個提案編号M， 然後向Acceptor的某個超過半數的子內建員發送編号為M的Prepare請求。
- 如果一個Acceptor收到一個編号為M的Prepare請求， 且編号M大于該Acceptor已經響應的所有Prepare請求的編号， 那麼它就會把已經準許過的最大的編号的提案作為相應回報給Proposer， 同時該Acceptor會承諾不會在準許任何編号小于M的提案。
階段二
- 如果Proposer收到來自半數以上的Acceptor對于其發出的編号為M的Prepare請求的響應，那麼它就會發送一個針對【M，V】提案的Accept請求給Acceptor。
注意：V的值就是收到的響應中編号最大的提案的值，如果響應中不包含任何提案，那麼他就是任意值
- 如果Acceptor收到的這個針對【M， V】的提案的Accept請求， 隻要該Acceptor尚未對編号大于M的Prepare請求作出響應， 他就可以通過這個提案。
看到這裡是不是覺得和我們分布式事務中的2PC的思路和流程差不多啊！
通知學習Learner的方案
方案1
一旦Acceptor準許了一個提案， 就将該提案發送給所有的Leamer
方案2
讓所有的Acceptor将它們對提案的準許情況， 統一發送給一個Learner， 再由它通知其他的Learner
方案3
方案2的主節點存在單點問題， 可以将主Leaner的範圍擴大， 即Acceptor可以将準許資訊發送給一個特定的Learner集合， 該集合中每個Leamer都可以在一個提案被標明後通知其他Leaner。
給你們的問題
- 設定多少個Acceptor最為合适？
- 如何控制每個Acceptor最多隻能準許一個提案？
連結：https://juejin.cn/post/7211346278289276987