前言

---

?相關系列

• 《分布式 & 目錄》
• 《分布式 & Paxos算法 & 總結》
• 《分布式 & Paxos算法 & 問題》
  ?

?參考文獻

• 《圖解超難理解的 Paxos 算法（含偽代碼）》
• 《【超詳細】分布式一致性協議 - Paxos》
  ?
  ?

Basic-Paxos @ 基礎帕克索斯算法

---

????Paxos算法是目前公認解決分布式一致性問題的最有效算法之一，甚至可以說它是過去幾十年里一切分布式一致性算法的源頭。我們對Paxos算法進行描述時通常都會帶上“容錯&共識”兩個關鍵字，那么它們具體代表的是什么呢？

• 容錯：是指分布式系統在部分節點宕機的情況下依然能夠對外提供服務，即CAP理論中的分區容錯性；
• 共識：是指分布式系統的各節點都能就某個操作達成共識，即所有節點都批準執行這個操作。例如在分布式系統中操作A/B都想訪問某服務，那么令集群中的所有（超半數/自定義數量）服務都批準執行操作A/B的的過程就是所謂的達成共識。
  ?

?概念

????在正式對流程進行闡述之前，我們需要先對Paxos算法的各類角色&變量進行講解。Paxos算法具有四類角色…其名稱/作用具體如下：

• client @ 客戶端：負責向提案者發送操作請求；
• proposer @ 提案者：提案者負責接收&封裝客戶端的操作請求為proposal @ 提案，并為之生成全局唯一&增長的編號。隨后向各接收者廣播準備/接收請求，并根據其返回的通過/批準情況決定是否繼續發送接收請求/判定其已達成一致；
• acceptor @ 接收者：接收者負責對準備&接收請求中的提案進行判定，以決定是否通過/批準該提案；
• learner @ 學習者：學習者負責獲取已達成共識的提案并應用于分布式系統中。

????Paxos算法具有三類“持久化”變量…其名稱/作用具體如下：

• maxProposal @ 最大提案：接收者在準備請求中通過的最大提案編號；
• acceptedProposal @ 已批準提案：接收者在接收請求中批準的最大提案編號；
• acceptedValue @ 已批準值：接收者在接收請求中批準的最大提案值。
  ?

?流程

????Paxos算法的流程分為“批準/獲取”兩個部分，這其中“批準”部分負責提案的實際批準，具體又可分為“準備/接收”兩個階段；而“獲取”部分則負責提案批準后的對外開放。關于提案批準的完整流程具體如下：

• prepare @ 準備階段：提案者在接收到客戶端的操作請求后，其會將之封裝為提案并為之生成全局唯一&增長的編號，關于全局編號的具體生成方式此處不予討論；
• 提案者會向各接收者廣播（即全體發送）準備（當前提案編號）請求；
• 各接收者在收到準備（當前提案編號）請求后會比較“當前提案編號”和“最大提案”的大小，如果“當前提案編號” > “最大提案”則記錄“最大提案”為“當前提案編號”并返回通過回應。而如果該接收者曾chosen @ 選中/批準過某項提案，則“已批準提案/已批準值”會隨通過回應一同返回；否則便會無視請求/返回拒絕回應。而在未能收到超過半數/自定義數量通過回應的情況下，提案者會為提案生成重新新編號并再次開始流程；
• accept @ 接收階段：提案者在收到超過半數/自定義數量的通過回應后會向接收者廣播接收（當前提案編號&當前提案值）請求。如果在之前的準備請求回應中存在“已批準值”，那么在接收請求中攜帶的“當前提案值”就必須應用該值；否則就由當前提案者負責自定義。通過該規則可以得知：Paxos算法只支持單個值/操作的共識；
• 各接收者在收到接收（當前提案編號&當前提案值）請求后會再次比較“當前提案編號”與“最大提案”的大小，如果“當前提案編號” >= “最大提案”則記錄“已批準提案&已批準值”為“當前提案編號&當前提案值”，并將“當前提案編號”返回，意味著已批準當前提案；否則便將原本的“最大提案”返回；
• 提案者在收到超過半數/自定義數量的“當前提案編號”后便會認為各接收者已對當前提案達成共識，至此該提案便可以被學習者所獲取&應用于分布式系統了；否則便意味著當前提案被否決，提案者需要為提案重新生成新編號以再次開始流程。

????當提案達成共識后，如何讓學習者獲取該提案也是值得細究的問題。提案獲取通常有以下幾種方案：

• 全量發送：接收者一旦批準提案便將該提案廣播給所有學習者。這種做法雖然可以讓學習者盡快的獲得批準提案，但是卻需要每個接收者與所有學習者逐一進行通信，通信次數為二者乘積，所以效率較低；
• 主從同步：選定主學習者，提案批準后由接收者通知主學習者，并由主學習者負責通知其它的學習者。這個方案雖然多了一個步驟，但是通信次數大大降低，通信次數為學習者的數量。該方案同時引出另一個問題：主學習者隨時可能出現故障。
• 多主從同步：在主從同步的基礎上，由單個主學習者擴展成一個主學習者集合。集合中學習者數量越高，可靠性也越好。
  ?

?模擬

????為了更好的熟悉Paxos算法，此處我們舉例描述Paxos算法“提案批準”的完整過程，該案例中的Paxos集群共有A/B/C三個節點。注意！這里的任意節點都可同時扮演提案者&接收者。

????提案者A/B分別將X賦值成3/5的操作請求封裝為提案，并為之生成全局唯一&增長的編號1/2，隨后向各接收者廣播。在準備階段它們的交互結果如下：

• 提案者A/B分別進入準備階段，并向各接收者廣播準備（1/2）請求；
• 接收者A/B在收到提案者A的準備（1）請求后發現自身并沒有通過/批準任何準備/接收請求，因此直接返回空的通過回應；
• 接收者C由于在收到&通過提案者B的準備（2）請求之后再收到提案者A的準備（1）請求，并且提案者B的提案編號2大于提案者A的提案編號1，因此無視了準備（1）請求/返回了拒絕回應；
• 接收者A/B在收到提案者B的準備（2）請求后由于其提案編號2 > 已通過的提案編號1，因此兩者都會返回空的通過回應。

????由于提案者A/B的準備請求都收到了超過半數的通過回應，因此提案者A/B都將進入Paxos算法的接收階段。

• 提案者A向各接收者廣播接收（1&3）請求。由于之前的通過回應中沒有攜帶“已批準提案”，因此提案的值可以完全自定義；
• 接收者A/B/C在收到接收（1&3）請求后，由于其之前已經各自通過了準備（2）請求，因此其都會返回提案編號2來表示未曾批準該請求；
• 提案者A在收到回應后發現提案編號2比自己的提案編號1大，因此知曉自身提案未曾被批準，因此重新回到準備階段進行協商；
• 提案者B向各接收者廣播接收（2&5）請求。由于之前的通過回應中沒有攜帶“已批準提案”，因此提案的值可以完全自定義；
• 接收者A/B/C在收到接收（2&5）請求后，由于其都未通過提案編號更大的準備請求，因此其都會返回提案編號2來表示批準了該請求；
• 提案者B在收到回應后發現提案編號2與自身提案編號相同且數量超過半數，因此判定接收者對該提案已達成共識，學習者可正式獲取&應用該提案。

????在提案批準的流程中還有一種常見的情況是接收者在已批準某項提案的情況下收到提案編號更大的準備請求，這種情況下其就需要在通過回應中返回已批準提案的編號&值…模擬如下：

• 提案者B向各接收者廣播接收（3&6）請求；
• 接收者A收到&批準了提案者B的接收（3&6）請求；
• 提案者A向各接收者廣播準備（4）請求；
• 接收者B/C收到&通過提案者A的廣播準備（4）請求，并因此未批準提案者B的接收（3&6）請求；
• 接收者A收到&通過提案者A的準備（4）請求，并在通過回應中攜帶了已批準提案編號&值（3&6）；
• 提案者B判定接收者未能就提案達成共識，重新進入準備階段；
• 提案者A因為收到超過半數的通過請求而進入接收階段，向各接收者廣播接收（4&6）請求。這其中6是因為在之前接收者A的通過回應中包含有已批準提案值，因此該值便被作為了提案者A的提案值；
• 接收者A/B/C收到&批準了接收（4&6）請求，提案者A判定各接收者已就該提案達成共識。
  ?
  ?

Multi-Paxos算法 @ 多帕克索斯算法

---

????原始的Basic-Paxos算法只能達成一個值/操作的共識，而Leslie Lamport則提出可以通過多次執行Basic-Paxos算法來達成一系列值/操作的共識。但由于多次協商會增加通信開銷&影響協商活性（即指協商進入死循環），因此Leslie Lamport則進一步提出了名為Multi-Paxos算法的解決方案。

????Multi-Paxos算法對于Basic-Paxos算法的主要區別在于其引入了領導提案者的概念。在Multi-Paxos算法中，提案（準備&接收）請求的發送是由領導提案者專屬負責的。Multi-Paxos系統會在啟動時先通過Basic-Paxos算法從各提案者中選舉出唯一的領導提案者用于“串行”發送提案請求，這樣就能避免并發提交而解決Basic-Paxos算法的活鎖（接收者不斷通過編號更大的提案而導致無法批準已通過的舊提案，該問題正常情況下可通過隨機延遲的方式進行緩解）問題。此外由于領導提案者會連續發送提案請求，因此除去首個提案請求需要完整執行準備&接收兩個階段（為了應對網絡分區而保留，否則也可以不執行）外，后續提案請求的發送都可以只執行接收階段，從而便能減少RPC來提升共識的達成效率。

????Multi-Paxos算法可以支持多領導提案者并存的場景。在實際的Multi-Paxos系統中，由于網絡分區情況的存在，其可能出現選舉出多個領導提案者的情況。對于這種情況Multi-Paxos算法是提供支持的，因為如此一來其會自動退化成Basic-Paxos算法的多次執行場景。

????領導提案者的宕機會導致Multi-Paxos系統不可用。對于一個功能完善的Multi-Paxos系統，其應該具備對領導提案者的故障監測&轉移功能。理論上，領導提案者需要不斷向系統中的其它節點發送心跳以表示自身存活，而一旦在指定時間內未收到心跳（及一系列綜合性盤點），那么Multi-Paxos系統就會判定領導提案者已經宕機。這種情況下其就會選舉新的領導提案者來代替工作，即使舊領導提案者只是因為網絡分區而無法連接。而在不存在可用提案者的情況下，Multi-Paxos系統將陷入不可用的狀態。