這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。
——Mike Burrows（Google Chubby 的作者）
Paxos是學習分佈式系統無法繞開的一環，從理論上看Paxos是非常優雅的，但是實現起來就沒有那麼簡單了。《 The Part-Time Parliament 》又看不懂，只能看《 Paxos Made Simple 》和 視頻教程 這種東西才能維持的了生活這樣子。
Paxos
基本問題
假設一組進程可以提議一些值，共識算法需要保證最終只有一個提議的值被選中。對於共識的安全性要求如下：
- 只有被提出的值才有可能被選中
- 只有一個值被選中
- 進程只會學習選中的值
Paxos算法中有三中主體：提議者（proposer）、接受者（acceptor）和學習者（learner），一個進程可以扮演多種主體。
- 任何主體會以任意速度執行，可能停機或者重啟
- 消息會花費任意長的時間傳遞，會丟失或者重複，但是不會被破壞
選一個值
一個最簡單的方案就是設置唯一接受者，讓它選擇第一接收到的值，但是這樣是無法處理接受者崩潰的情況的。因此比較安全的方法是設置多個接受者，選擇當大多數接受者接收的值。
可以嘗試設計一個要求：
P1. 接受者接收它收到的第一個提議。
然而，如果不存在一個被大多數接受的值，那麼就無法達成共識了。因此最好讓接受者可以接收多個提議，每個提議用一個遞增的數字進行編號。現在接受者可以接收多個提議了，但是需要保證所有選中的提議都包含同一個值，根據編碼遞增性質，可以給出要求：
P2. 如果一個包含值v的提議被選中，任何選中的高編號的提議必須包含值v。
一個提議被選中的前提是至少被一個接受者接收，所以通過滿足一下條件來滿足P2：
P2a. 如果一個包含值v的提議被選中，任何被接受的高編號的提議必須包含值v。
如果一個剛甦醒的提議者給沒有接收過任何提議的接受者一個高編號的提議，那就有可能破壞P2a，因此可以加強為：
P2b. 如果一個包含值v的提議被選中，任何由提議者提出的高編號的提議必須包含值v。
進一步可以通過滿足P2c來滿足P2b：
P2c. 對於任意的v和n，如果一個包含值v，編號為n的提議被提出，存在一個由大多數接受者組成的集合S，那麼必然為兩種情況之一：
- S中不存在任何接受者接受了編號小於n的提議
- v就是S中接受者已經接受的最高編號並且編號小於n的提議的值
根據P2c的要求，提議者在提議之前必須知道編號小於n的最大編號提議，包括那些已經被接受的或者將要被接受的。一個提議是否會被接受無法預測，但是可以讓接受者保證不接受編號小於n的提議。
這就需要提議者事先發送一個帶編號n的準備請求給接受者，要求接受者返回：
- 一個承諾：它不會接收任何編號小於n的提議
- 已經接受的最高編號的提議
如果提議者發出的準備請求得到了大多數接受者的回應，那麼它將編號n包含值v的提議發送給這些接受者，那麼v是回應中最高編號的提議值，如果沒有提議，那麼可以是任意值。
因此對於接受要求就是：
P1a 接受者接受一個編號n的提議當且僅當它沒有響應過編號大於n的準備請求。
階段1：
- 提議者選擇一個提議編號n，然後將帶有編號n的準備請求發送給大多數接受者。
- 如果一個接受者接收到一個準備請求，其編號n大於任何已經回應過的準備請求，那麼接收者返回一個承諾：它不會接收任何編號小於n的提議，以及已經接受的最高編號的提議。
階段2：
- 如果提議者發出的準備請求得到了大多數接受者的回應，那麼它將編號n包含值v的提議發送給這些接受者，那麼v是回應中最高編號的提議值，如果沒有提議，那麼可以是任意值。
- 如果接收者收到了編號為n的接受請求，除非已經回應了一個更高編號的準備請求，否則接收這個提議。
學習選到值
最簡單的策略就是讓每個接受者把選中的提議發送給全部的學習者，但是這樣的消息數量巨大。消息最少的方法是將每個接受者將選中的提議發送給一個特殊的學習者，然後又轉給全體學習者。只有一個負責轉發的特殊學習者容錯性較差，可以設置多個這樣的學習者。如果消息丟失的話，學習者可能得不到大多數接受者的選擇提議，這個時候可以通過新的提議獲取，比如讓提議者主動發起一個提議。
進展
如果有兩個提議者互相不停打斷對方的準備階段，那麼永遠沒有提議被選中。解決方法就是使用領導選舉算法，選舉一個唯一的提議者。
實現
在具體實現中，算法需要選舉一個領導作為唯一提議者和特殊學習者。要使用容錯的穩定存儲來記錄接受者需要記住的信息。
MultiPaxos
Paxos每次只達成一個值的共識，如果我們要實現狀態機就需要一條日誌，做法就是在每條日誌項上運行一次Paxos，然而這樣做的代價是巨大的，將Paxos應用到日誌上需要處理以下技術點。
新項
新的日誌項需要加到從頭開始第一個值沒有被選中的日誌槽中。
服務器可以並行處理添加表項，但是應用到狀態機的時候必須是有序的。
提高效率
- 領導選舉：多個提議者容易造成衝突，降低性能，索性選舉一個領導負責提議，領導選舉可以採用最大ID等選舉算法；
- 單次準備：將領導任期內的所有選中表項都使用一個編號（前提是插入位置的後面沒有其他被選中的日誌槽），這樣每個領導任期之內只需要一次準備，後續添加表項直接使用接收請求（直到被拒絕為止）；
備份和應用
算法還面臨兩個問題。
問題一：如何將日誌備份到全部節點？
在後臺不斷嘗試發送接受請求確保全部節點響應。
問題二：如何讓其他節點知道日誌項被選中？
首先約定將選中的日誌槽的編號設為無窮acceptedProposal[i] = ∞，記錄第一個未選中日誌槽的位置firstUnchosenIndex。
- 提議者告知接收者：在請求RPC中包含firstUnchosenIndex，接收者將所有滿足i < request.firstUnchosenIndex和acceptedProposal[i] == request.proposal的日誌槽i標記為選中；
- 處理舊領導添加的日誌項：接受者在回應中包含firstUnchosenIndex，如果提議者的firstUnchosenIndex大於接收者的firstUnchosenIndex，提議者發送Success RPC。
接收者收到RPC Success(index, v)之後，設置acceptedValue[index] = v和acceptedProposal[index] = ∞，返回firstUnchosenIndex。
閱讀更多 sandag 的文章
