????????提到分布式算法，就不得不提 Paxos 算法，在過去幾十年里，它基本上是分布式共識的代名詞，因為當前一批常用的共識算法都是基于它改進的。比如，Fast Paxos 算法、Cheap Paxos、Raft 算法等。
????????由萊斯利·蘭伯特（Leslie Lamport）于1990年首次提出，并在后續文章中進一步闡述。Paxos 算法旨在解決在一個可能發生網絡分區、節點失效或其他異常情況的分布式環境中，如何讓所有參與決策的節點對某個值達成一致同意的問題。
????????蘭伯特提出的Paxos總共包含兩部分：
- 一個是 Basic Paxos 算法，描述的是多節點之間如何就某個值(提案Value)達成共識
- 另一個是 Multi-Paxos 思想，描述的是執行多個 Basic Paxos 實例，就一系列值達成共識
Basic Paxos
????????先來看一個例子
? ? ? ? 假設有一個分布式集群，由三個節點 A、B、C 組成，提供只讀 KV 存儲服務，創建只讀變量的時候，必須要先寫入數據，而且這個數據后續不能被修改。因此一個節點寫入只讀變量后就不能再修改了，所以所有節點必須要先對只讀變量達成共識，然后所有節點在一次創建這個只讀變量。
????????當有多個客戶端(如客戶端1、2)訪問這個系統試圖創建同一個只讀變量(如X)，客戶端1試圖創建值為3的X，客戶端2試圖創建值為7的X，這樣要如何達成共識，實現各節點上X值一直呢？
????????為了幫助人們更好的理解 Basic Paxos 算法，蘭伯特在講解時，也使用了一些獨有而且比較重要的概念，提案、準備(Prepare)請求、接受(Accept)請求、角色等等，其中最重要的就是角色。因為角色是對 Basic Paxos 中最核心的三個功能的抽象，比如，由接受者(Acceptor)對提議者的值進行投票，并存儲接受的值。
? ? ? ? 角色劃分
????????在 Basic Paxos 中，由提議者(Proposer)、接受者(Acceotor)、學習者(Learner)三種角色，如圖：
- 提議者(Proposer)：提議一個值，用于投票表決。為了方便演示，可以把客戶端1和2看做是提議者。但在絕大多數場景中，集群中收到客戶端請求的節點，才是提議者。這樣做的好處是，對業務代碼沒有侵入性，也就是說，我們不需要在代碼中實現算法邏輯，就可以像使用數據庫一樣訪問后端數據。
- 接受者(Acceptor)：對每個提議的值進行投票，并存儲接受的值，比如 A、B、C 三個節點。一般來說，集群中的所有節點都在扮演接受者的角色，參與共識協商，并接受和存儲數據。
? ? ? ? 這里需要強調一下：前面不是說接收客戶端請求的節點是提議者嗎？這里怎么又是接受者呢？這是因為一個節點（或進程）可以身兼多個角色。想象一下，一個 3 節點的集群，1 個節點收到了請求，那么該節點將作為提議者發起二階段提交，然后這個節點和另外 2 個節點一起作為接受者進行共識協商，就像下圖的樣子：
- 學習者(Leaner)：被告知投票的結果，接受達成的共識值，存儲保存，不參與投票的過程。一般來說，學習者是備份節點，比如“Master-Slave”模型中的Slave，被動的接受數據，容災備份。
? ? ? ? 達成共識過程
? ? ? ? 有這樣一個場景，假如你所在的公司有一個新項目需要開發，業務比較復雜，你的領導給組內每個成員下發了任務，要求每人寫一個項目方案，最終開會討論采用哪套方案，為了區分每套方案，每個方案都有一個標識，稱為提案編號，來唯一標識。
????????與你的做法類似，在 Basic Paxos 中，蘭伯特也使用提案代表一個提議。不過在提案中，除了提案編號，還包含了提議值。使用 [n, v] 表示一個提案，n 為提案編號，v 為提議值。
????????整個共識協商是分兩個階段進行的。假設客戶端 1 的提案編號為 1，客戶端 2 的提案編號為5，并假設節點 A、B 先收到來自客戶端1的準備請求，節點 C 先收到來自客戶端 2 的準備請求。
? ? ? ? 準備（Prepare）階段
????????先來看第一階段，首先客戶端 1、2 作為提議者，分別向所有接受者發送包含提案編號的準備請求：
? ? ? ??在準備請求時不需要準備提議的值的，只需要攜帶提案編號就可以了，這是容易誤解的地方。接著，當A、B收到提案編號為 1 的準備請求，節點 C 收到提案編號為 2 的準備請求后，將進行這樣的處理：
- 由于之前沒有通過任何提案，所以節點 A、B 將返回一個"尚無提案"的響應。也就說節點 A和 B 在告訴提議者，我之前沒有通過任何提案，并承諾以后不在響應提案編號小于等于 1 的準備請求，不會通過編號小于1的提案。
- 節點 C 也是如此，它將返回一個“尚無提案”的響應，并承諾以后不在響應提案編號小于 5 的提案，不會通過提案編號小于5的提案。
????????另外，當節點 A、B 收到提案編號為 5 的準備請求，和節點 C 收到提案編號為 1 的準備請求的時候，將進行這樣的處理：
- 當節點 A、B 收到提案編號為 5 的準備請求時，因為提案編號 5 大于他們之前響應的準備請求的提案編號 1，而且兩個節點都沒有通過任何提案，所以它將返回一個“尚無提案”的響應，并承諾以后不在響應提案編號小于 5 的準備請求，不會通過提案小于 5 的提案。
- 當節點 C 收到提案編號為 1 的準備請求時，由于天編號 1 小于之前響應的準備請求的提案編號 5，所以丟棄該準備請求，不做響應。
????????接受（Acceptor）階段
????????第二個階段也就是接受階段，首先客戶端 1、2 在收到大多數節點的準備響應之后，會分別發送接受請求：
- 當客戶端 1 收到大多數的接受者（節點A、B）的準備響應之后根據響應中提案編號最大的提案值，設置接受請求中的值。因為該值在來自節點 A、B 的準備響應中都為空，所以就把自己的提議值 3 作為提案的值，發送接受請求 [1, 3]。
- 當客戶端2收到大多數的接受者的準備響應后（節點A、B、C），根據響應中提案編號最大的提案值，來設置接受請求中的值。因為該值來自節點 A、B、C 準備響應都為空，所以就把自己的提議值7作為提案的值，發送接受請求 [5, 7]。
????????當三個節點接受到兩個客戶端的接受請求時，會進行這樣的處理：
- 當節點 A、B、C 接受到請求 [1, 3] 的時候，由于提案的提案編號 1 小于三個節點承諾能通過的提案的最小提案編號 5，所以提案 [1, 3] 將被拒絕。
- 當節點 A、B、C 接受到請求 [5, 7] 的時候，由于提案的提案編號 5 不小于三個節點承諾能通過的提案的最小提案編號 5，所以就通過提案 [5, 7]，也就是接受了值 7，三個節點就 X 值為 7 達成共識。
????????如果集群中有學習者，當接受者通過了一個提案時，就通知給所有的學習者。當學習者發現大多數的接受者都通過了某個提案，那么它也通過該提案，接受該提案的值。??
Multi-Paxos算法?
????????Basic Paxos 只能就單個值（Value）達成共識，一旦遇到為一系列的值實現共識的時候，它就不管用了。雖然蘭伯特提到可以通過多次執行 Basic Paxos 實例（比如每接收到一個值時，就執行一次 Basic Paxos 算法）實現一系列值的共識。但是，讀完論文后，雖然每個英文單詞都能讀懂，但還是不理解蘭伯特提到的 Multi-Paxos，為什么 Multi-Paxos 這么難理解呢？
????????蘭伯特并沒有把 Multi-Paxos 講清楚，只是介紹了大概的思想，缺少算法過程的細節和編程所必須的細節。這就導致了每個人實現的 Multi-Paxos 都不一樣。不過從本質上看，大家都是在蘭伯特提到的 Multi-Paxos 思想上補充細節，設計自己的 Multi-Paxos 算法，然后實現它（比如 Chubby 的 Multi-Paxos 實現、Raft 算法等）。
????????所以這里補充一下，蘭伯特提出的 Multi-Paxos 是一種思想，不是算法。而 Multi-Paxos 是一種統稱，它是指基于 Multi-Paxos 思想，通過多個 basic-Paxos 實現一系列值的共識算法。這一點尤為重要。
? ? ? ? 到這里 Paxos 共識算法就介紹完了。
