大家可能在各個場合都聽說過Paxos協議，畢竟這個開創性的協議是很多分布式協議的鼻祖，比如后面比較有名的Raft協議就是基于Paxos協議發展而來的。現實中也有很多產品在使用Paxos協議，像是Google的Chubby，Spanner，IBM的SVC等。 但是在筆者的學習過程中，發現介紹Paxos協議的很多，但是真正能把它講明白的卻很少。所以筆者特意花了一定的時間來研究Paxos協議，現把學習結果分析如下。

角色

在Paxos協議中存在5種角色: client, acceptor, proposer, learner, 和 leader。但在實際的實現中，一個服務可能同時扮演一個或者多個角色，這樣做的考慮是為了減少消息延遲和消息數量，提升整個Paxos協議的工作效率。

Client
Client 是指請求的發起端，Client發送請求給分布式系統，并等待回復。

Acceptor (Voters)
Acceptor 可以看做是消息請求的存儲器。一般來說Acceptors是由一定數量的服務組成的，當消息被發送給Acceptor， 只有大部分Acceptor確認接收此消息，該消息才會被存儲，否則該消息將被丟棄。

Proposer
Proposer 可以看做Client的代理人，Proposer將Client的消息請求發送給Acceptors，并等待Acceptors的確認。在發生消息沖突時，Proposer將會嘗試解決沖突。

Learner
Learners可以看做是所有被確認消息的執行器，一旦有Client的消息請求被Acceptors確認之后，Learners會做相應的處理（如：執行消息內容，發送回復給Client）。Learner可以有多個。

Leader
Paxos需要一個Leader來確保分布式系統可以按步驟進行下去。這里的Leader其實就是一個Proposer, Paxos協議會確保只有一個Proposer會被當做Leader。

Proposal Number & Agreed Value

Proposal Number 也叫提案編號，我們用n表示，對于每一個Proposer來說，每一個提案編號都是唯一的。
Agreed Value也叫確認值，我們用v來表示，v是Acceptors確認的值。
兩個值組合起來就是（n，v）。

Basic Paxos

Paxos協議有很多變種，這里我們首先介紹一下Basis Paxos，后面的文章我們會繼續介紹其他的Paxos協議。當然，既然是基礎的Paxos協議，搞懂了它，對于其他的Paxos協議自然手到擒來。

在Basic Paxos 協議中，有很多次的執行過程，每次執行過程產生一個單獨的執行結果。每次執行過程都有很多輪次，每一輪都有2個階段。

階段1

• 階段1A：Prepare

  在Prepare階段，一個Proposer會創建一個Prepare消息，每個Prepare消息都有唯一的提案編號n。n并不是將要提案的內容，而只是一個唯一的編號，用來標志這個Prepare的消息。
  n必須比該Proposer之前用過的所有編號都大，一般來說我們可以以數字遞增的方式來實現這個編號。
  接下來Proposer會把該編號發送給Acceptors，只有大多數Acceptors接收到Proposer發來的消息，該消息才算是發送成功。

• 階段1B：Promise

  所有的Acceptors都在等待從Proposers發過來的Prepare消息。當一個Acceptor收到從Proposer發過來的Prepare消息時候，會有兩種情況：

• 該消息中的n是Acceptor所有收到的Prepare消息中最大的一個，那么該Acceptor必須返回一個Promise消息給Proposer，告訴它后面所有小于n的消息我都會忽略掉。如果該Acceptor在過去的某個時間已經確認了某個消息，那么它必須返回那個消息的proposal number m 和 accepted value w （m，w）。如果該Acceptor在過去并沒有確認過任何消息，那么會返回NULL。

• 如果Prepare消息中的n小于該Acceptor之前接收到的消息，那么該消息會被Acceptor忽略（為了優化也可以返回一個拒絕消息給Proposer，告訴它不要再發小于n的消息給我了）。

階段2

• 階段2A：Accept

  如果一個Proposer從Acceptors接收到了足夠多的Promises（>n/2），這表示該Proposer可以開始下一個Accept請求的階段了，在Accept階段，Proposer需要設置一個值，然后向Acceptors發送Accept請求。
  在階段1B我們講到了，如果Acceptor之前確認過消息，那么會把該消息編號和消息的值（m，w）返回給Proposer， Proposer收到多個Acceptors返回過來的消息之后，會從中選擇編號最大的一個消息所對應的值z，并把他作為Accept請求的值（n，z）發給Acceptor。如果所有的Acceptors都沒有確認過消息，那么Proposer可以自主選擇要確認的值z。

• 階段 2b: Accepted
  當Acceptor接收到了Proposer的確認消息請求（n，z），如果該Acceptor在階段1b的時候沒有promise只接收>n的消息，那么該（n，z）消息就必須被Acceptor確認。
  當（n，z）消息被Acceptor確認時，Acceptor會發送一個Accepted（n，z）消息給Proposer 和所有的Learner。當然在大部分情況下Proposer和Learner這兩個角色可以合并。
  如果該Acceptor在階段1b的時候promise只接收>n的消息，那么該確認請求消息會被拒絕或者忽略。
  按照以上的邏輯就會出現在一個輪次中，Acceptor 確認多次消息的情況。什么情況下才會出現這樣的情況呢？ 我們舉個例子：
  Acceptor 收到Accept（n，z），然后返回了Accepted（n，z），接下來該Acceptor 又收到了Prepare（n+1)請求，按照階段1B的原則，Acceptor會 Promise （n+1，z），然后Acceptor 收到Accept（n+1，z），最后返回Accepted（n+1，z）。大家可以看到盡管Acceptor 確認了多次請求，但是最終會確保確認的值是保持一致的。