分佈式一致性
分佈式一致性，簡單的說就是在一個或多個進程提議了一個值後，使系統中所有進程對這個值達成一致。
為了就某個值達成一致，每個進程都可以提出自己的提議，最終通過分佈式一致性算法，所有正確運行的進程學習到相同的值。
工業界對分佈式一致性的應用，都是為了構建多副本狀態機模型（Replicated State Machine），實現高可用和強一致。
分佈式一致性使多臺機器具有相同的狀態，運行相同的確定性狀態機，在少數機器故障時整體仍能正常工作。
Paxos
Paxos達成一個決議至少需要兩個階段（Prepare階段和Accept階段）。
Prepare階段的作用：
- 爭取提議權，爭取到了提議權才能在Accept階段發起提議，否則需要重新爭取。
- 學習之前已經提議的值。
Accept階段使提議形成多數派，提議一旦形成多數派則決議達成，可以開始學習達成的決議。Accept階段若被拒絕需要重新走Prepare階段。
Multi-Paxos
Basic Paxos達成一次決議至少需要兩次網絡來回，併發情況下可能需要更多，極端情況下甚至可能形成活鎖，效率低下，Multi-Paxos正是為解決此問題而提出。
Multi-Paxos選舉一個Leader，提議由Leader發起，沒有競爭，解決了活鎖問題。提議都由Leader發起的情況下，Prepare階段可以跳過，將兩階段變為一階段，提高效率。Multi-Paxos並不假設唯一Leader，它允許多Leader併發提議，不影響安全性，極端情況下退化為Basic Paxos。
Multi-Paxos與Basic Paxos的區別並不在於Multi（Basic Paxos也可以Multi），只是在同一Proposer連續提議時可以優化跳過Prepare直接進入Accept階段，僅此而已。
Raft
不同於Paxos直接從分佈式一致性問題出發推導出來，Raft則是從多副本狀態機的角度提出，使用更強的假設來減少需要考慮的狀態，使之變的易於理解和實現。
Raft與Multi-Paxos有著千絲萬縷的關係，下面總結了Raft與Multi-Paxos的異同。
Raft與Multi-Paxos中相似的概念：
- Raft的Leader即Multi-Paxos的Proposer。
- Raft的Term與Multi-Paxos的Proposal ID本質上是同一個東西。
- Raft的Log Entry即Multi-Paxos的Proposal。
- Raft的Log Index即Multi-Paxos的Instance ID。
- Raft的Leader選舉跟Multi-Paxos的Prepare階段本質上是相同的。
- Raft的日誌複製即Multi-Paxos的Accept階段。
Raft與Multi-Paxos的不同：
Raft假設系統在任意時刻最多隻有一個Leader，提議只能由Leader發出（強Leader），否則會影響正確性；而Multi-Paxos雖然也選舉Leader，但只是為了提高效率，並不限制提議只能由Leader發出（弱Leader）。
強Leader在工程中一般使用Leader Lease和Leader Stickiness來保證：
- Leader Lease：上一任Leader的Lease過期後，隨機等待一段時間再發起Leader選舉，保證新舊Leader的Lease不重疊。
- Leader Stickiness：Leader Lease未過期的Follower拒絕新的Leader選舉請求。
Raft限制具有最新已提交的日誌的節點才有資格成為Leader，Multi-Paxos無此限制。
Raft在確認一條日誌之前會檢查日誌連續性，若檢查到日誌不連續會拒絕此日誌，保證日誌連續性，Multi-Paxos不做此檢查，允許日誌中有空洞。
Raft在AppendEntries中攜帶Leader的commit index，一旦日誌形成多數派，Leader更新本地的commit index即完成提交，下一條AppendEntries會攜帶新的commit index通知其它節點；Multi-Paxos沒有日誌連接性假設，需要額外的commit消息通知其它節點。
EPaxos
EPaxos（Egalitarian Paxos）於SOSP'13提出，比Raft還稍早一些，但Raft在工業界大行其道的時間裡，EPaxos卻長期無人問津，直到最近，EPaxos開始被工業界所關注。
EPaxos是一個Leaderless的一致性算法，任意副本均可提交日誌，通常情況下，一次日誌提交需要一次或兩次網絡來回。
EPaxos無Leader選舉開銷，一個副本不可用可立即訪問其他副本，具有更高的可用性。各副本負載均衡，無Leader瓶頸，具有更高的吞吐量。客戶端可選擇最近的副本提供服務，在跨AZ跨地域場景下具有更小的延遲。
不同於Paxos和Raft，事先對所有Instance編號排序，然後再對每個Instance的值達成一致。EPaxos不事先規定Instance的順序，而是在運行時動態決定各Instance之間的順序。EPaxos不僅對每個Instance的值達成一致，還對Instance之間的相對順序達成一致。EPaxos將不同Instance之間的相對順序也做為一致性問題，在各個副本之間達成一致，因此各個副本可併發地在各自的Instance中發起提議，在這些Instance的值和相對順序達成一致後，再對它們按照相對順序重新排序，最後按順序應用到狀態機。
從圖論的角度看，日誌是圖的結點，日誌之間的順序是圖的邊，EPaxos對結點和邊分別達成一致，然後使用拓撲排序，決定日誌的順序。圖中也可能形成環路，EPaxos需要處理循環依賴的問題。
EPaxos引入日誌衝突的概念（與Parallel Raft類似，與併發衝突不是一個概念），若兩條日誌之間沒有衝突（例如訪問不同的key），則它們的相對順序無關緊要，因此EPaxos只處理有衝突的日誌之間的相對順序。
若併發提議的日誌之間沒有衝突，EPaxos只需要運行PreAccept階段即可提交（Fast Path），否則需要運行Accept階段才能提交（Slow Path）。
PreAccept階段嘗試將日誌以及與其它日誌之間的相對順序達成一致，同時維護該日誌與其它日誌之間的衝突關係，如果運行完PreAccept階段，沒有發現該日誌與其它併發提議的日誌之間有衝突，則該日誌以及與其它日誌之間的相對順序已經達成一致，直接發送異步的Commit消息提交；否則如果發現該日誌與其它併發提議的日誌之間有衝突，則日誌之間的相對順序還未達成一致，需要運行Accept階段將衝突依賴關係達成多數派，再發送Commit消息提交。
EPaxos的Fast Path Quorum為2F，可優化至F + [ (F + 1) / 2 ]，在3副本和5副本時，與Paxos、Raft一致。Slow Path 為Paxos Accept階段，Quorum固定為F + 1。
EPaxos還有一個主動Learn的算法，在恢復的時候可用來追趕日誌，這裡就不做具體的介紹了，感興趣的可以看論文。
對比分析
從Paxos到Raft再到EPaxos，背後的技術是怎麼樣演進的，我們可以從算法本身來做個對比，下面主要從可理解性、效率、可用性和適用場景等幾個角度進行對比分析。
1 可理解性
眾所周知，Paxos是出了名的晦澀難懂，不僅難以理解，更難以實現。而Raft則以可理解性和易於實現為目標，Raft的提出大大降低了使用分佈式一致性的門檻，將分佈式一致性變的大眾化、平民化，因此當Raft提出之後，迅速得到青睞，極大地推動了分佈式一致性的工程應用。
EPaxos的提出比Raft還早，但卻長期無人問津，很大一個原因就是EPaxos實在是難以理解。EPaxos基於Paxos，但卻比Paxos更難以理解，大大地阻礙了EPaxos的工程應用。不過，是金子總會發光的，EPaxos因著它獨特的優勢，終於被人們發現，具有廣闊的前景。
2 效率
從Paxos到Raft再到EPaxos，效率有沒有提升呢？我們主要從負載均衡、消息複雜度、Pipeline以及併發處理幾個方面來對比Multi-Paxos、Raft和EPaxos。
負載均衡
Multi-Paxos和Raft的Leader負載更高，各副本之間負載不均衡，Leader容易成為瓶頸，而EPaxos無需Leader，各副本之間負載完全均衡。
消息複雜度
Multi-Paxos和Raft選舉出Leader之後，正常只需要一次網絡來回就可以提交一條日誌，但Multi-Paxos需要額外的異步Commit消息提交，Raft只需要推進本地的commit index，不使用額外的消息，EPaxos根據日誌衝突情況需要一次或兩次網絡來回。因此消息複雜度，Raft最低，Paxos其次，EPaxos最高。
Pipeline
我們將Pipeline分為順序Pipeline和亂序Pipeline。Multi-Paxos和EPaxos支持亂序Pipeline，Raft因為日誌連續性假設，只支持順序Pipeline。但Raft也可以實現亂序Pipeline，只需要在Leader上給每個Follower維護一個類似於TCP的滑動窗口，對應每個Follower上維護一個接收窗口，允許窗口裡面的日誌不連續，窗口外面是已經連續的日誌，日誌一旦連續則向前滑動窗口，窗口裡面可亂序Pipeline。
併發處理
Multi-Paxos沿用Paxos的策略，一旦發現併發衝突則回退重試，直到成功；Raft則使用強Leader來避免併發衝突，Follwer不與Leader競爭，避免了併發衝突；EPaxos則直面併發衝突問題，將衝突依賴也做為一致性問題對待，解決併發衝突。Paxos是衝突回退，Raft是衝突避免，EPaxos是衝突解決。Paxos和Raft的日誌都是線性的，而EPaxos的日誌是圖狀的，因此EPaxos的並行性更好，吞吐量也更高。
3 可用性
EPaxos任意副本均可提供服務，某個副本不可用了可立即切換到其它副本，副本失效對可用性的影響微乎其微；而Multi-Paxos和Raft均依賴Leader，Leader不可用了需要重新選舉Leader，在新Leader未選舉出來之前服務不可用。顯然EPaxos的可用性比Multi-Paxos和Raft更好，但Multi-Paxos和Raft比誰的可用性更好呢。
Raft是強Leader，Follower必須等舊Leader的Lease到期後才能發起選舉，Multi-Paxos是弱Leader，Follwer可以隨時競選Leader，雖然會對效率造成一定影響，但在Leader失效的時候能更快的恢復服務，因此Multi-Paxos比Raft可用性更好。
4 適用場景
EPaxos更適用於跨AZ跨地域場景，對可用性要求極高的場景，Leader容易形成瓶頸的場景。Multi-Paxos和Raft本身非常相似，適用場景也類似，適用於內網場景，一般的高可用場景，Leader不容易形成瓶頸的場景。
思考
最後留下幾個思考題，感興趣的同學可以思考思考：
1）Paxos的Proposal ID需要唯一嗎，不唯一會影響正確性嗎？
2）Paxos如果不區分Max Proposal ID和Accepted Proposal ID，合併成一個Max Proposal ID，過濾Proposal ID小於等於Max Proposal ID的Prepare請求和Accept請求，會影響正確性嗎？
3）Raft的PreVote有什麼作用，是否一定需要PreVote？
