[[334877]]

分布式一致性(Consensus)作為分布式系統(tǒng)的基石，一直都是計算機系統(tǒng)領域的熱點。近年來隨著分布式系統(tǒng)的規(guī)模越來越大，對可用性和一致性的要求越來越高，分布式一致性的應用也越來越廣泛。縱觀分布式一致性在工業(yè)界的應用，從最開始的鼻祖Paxos的一統(tǒng)天下，到橫空出世的Raft的流行，再到如今Leaderless的EPaxos開始備受關注，背后的技術是如何演進的?本文將從技術角度探討分布式一致性在工業(yè)界的應用，并從可理解性、可用性、效率和適用場景等幾個角度進行對比分析。

分布式一致性

分布式一致性，簡單的說就是在一個或多個進程提議了一個值后，使系統(tǒng)中所有進程對這個值達成一致。

為了就某個值達成一致，每個進程都可以提出自己的提議，最終通過分布式一致性算法，所有正確運行的進程學習到相同的值。

工業(yè)界對分布式一致性的應用，都是為了構(gòu)建多副本狀態(tài)機模型(Replicated State Machine)，實現(xiàn)高可用和強一致。

分布式一致性使多臺機器具有相同的狀態(tài)，運行相同的確定性狀態(tài)機，在少數(shù)機器故障時整體仍能正常工作。

Paxos

Paxos達成一個決議至少需要兩個階段(Prepare階段和Accept階段)。

Prepare階段的作用：

• 爭取提議權(quán)，爭取到了提議權(quán)才能在Accept階段發(fā)起提議，否則需要重新爭取。
• 學習之前已經(jīng)提議的值。

Accept階段使提議形成多數(shù)派，提議一旦形成多數(shù)派則決議達成，可以開始學習達成的決議。Accept階段若被拒絕需要重新走Prepare階段。

Multi-Paxos

Basic Paxos達成一次決議至少需要兩次網(wǎng)絡來回，并發(fā)情況下可能需要更多，極端情況下甚至可能形成活鎖，效率低下，Multi-Paxos正是為解決此問題而提出。

Multi-Paxos選舉一個Leader，提議由Leader發(fā)起，沒有競爭，解決了活鎖問題。提議都由Leader發(fā)起的情況下，Prepare階段可以跳過，將兩階段變?yōu)橐浑A段，提高效率。Multi-Paxos并不假設唯一Leader，它允許多Leader并發(fā)提議，不影響安全性，極端情況下退化為Basic Paxos。 Multi-Paxos與Basic Paxos的區(qū)別并不在于Multi(Basic Paxos也可以Multi)，只是在同一Proposer連續(xù)提議時可以優(yōu)化跳過Prepare直接進入Accept階段，僅此而已。

Raft

不同于Paxos直接從分布式一致性問題出發(fā)推導出來，Raft則是從多副本狀態(tài)機的角度提出，使用更強的假設來減少需要考慮的狀態(tài)，使之變的易于理解和實現(xiàn)。 Raft與Multi-Paxos有著千絲萬縷的關系，下面總結(jié)了Raft與Multi-Paxos的異同。 Raft與Multi-Paxos中相似的概念：

• Raft的Leader即Multi-Paxos的Proposer。
• Raft的Term與Multi-Paxos的Proposal ID本質(zhì)上是同一個東西。
• Raft的Log Entry即Multi-Paxos的Proposal。
• Raft的Log Index即Multi-Paxos的Instance ID。
• Raft的Leader選舉跟Multi-Paxos的Prepare階段本質(zhì)上是相同的。
• Raft的日志復制即Multi-Paxos的Accept階段。

Raft與Multi-Paxos的不同：

Raft假設系統(tǒng)在任意時刻最多只有一個Leader，提議只能由Leader發(fā)出(強Leader)，否則會影響正確性;而Multi-Paxos雖然也選舉Leader，但只是為了提高效率，并不限制提議只能由Leader發(fā)出(弱Leader)。 強Leader在工程中一般使用Leader Lease和Leader Stickiness來保證：

• Leader Lease：上一任Leader的Lease過期后，隨機等待一段時間再發(fā)起Leader選舉，保證新舊Leader的Lease不重疊。
• Leader Stickiness：Leader Lease未過期的Follower拒絕新的Leader選舉請求。

Raft限制具有最新已提交的日志的節(jié)點才有資格成為Leader，Multi-Paxos無此限制。 Raft在確認一條日志之前會檢查日志連續(xù)性，若檢查到日志不連續(xù)會拒絕此日志，保證日志連續(xù)性，Multi-Paxos不做此檢查，允許日志中有空洞。 Raft在AppendEntries中攜帶Leader的commit index，一旦日志形成多數(shù)派，Leader更新本地的commit index即完成提交，下一條AppendEntries會攜帶新的commit index通知其它節(jié)點;Multi-Paxos沒有日志連接性假設，需要額外的commit消息通知其它節(jié)點。

EPaxos

EPaxos(Egalitarian Paxos)于SOSP'13提出，比Raft還稍早一些，但Raft在工業(yè)界大行其道的時間里，EPaxos卻長期無人問津，直到最近，EPaxos開始被工業(yè)界所關注。

EPaxos是一個Leaderless的一致性算法，任意副本均可提交日志，通常情況下，一次日志提交需要一次或兩次網(wǎng)絡來回。

EPaxos無Leader選舉開銷，一個副本不可用可立即訪問其他副本，具有更高的可用性。各副本負載均衡，無Leader瓶頸，具有更高的吞吐量。客戶端可選擇最近的副本提供服務，在跨AZ跨地域場景下具有更小的延遲。

不同于Paxos和Raft，事先對所有Instance編號排序，然后再對每個Instance的值達成一致。EPaxos不事先規(guī)定Instance的順序，而是在運行時動態(tài)決定各Instance之間的順序。EPaxos不僅對每個Instance的值達成一致，還對Instance之間的相對順序達成一致。EPaxos將不同Instance之間的相對順序也做為一致性問題，在各個副本之間達成一致，因此各個副本可并發(fā)地在各自的Instance中發(fā)起提議，在這些Instance的值和相對順序達成一致后，再對它們按照相對順序重新排序，最后按順序應用到狀態(tài)機。

從圖論的角度看，日志是圖的結(jié)點，日志之間的順序是圖的邊，EPaxos對結(jié)點和邊分別達成一致，然后使用拓撲排序，決定日志的順序。圖中也可能形成環(huán)路，EPaxos需要處理循環(huán)依賴的問題。

EPaxos引入日志沖突的概念(與Parallel Raft類似，與并發(fā)沖突不是一個概念)，若兩條日志之間沒有沖突(例如訪問不同的key)，則它們的相對順序無關緊要，因此EPaxos只處理有沖突的日志之間的相對順序。

若并發(fā)提議的日志之間沒有沖突，EPaxos只需要運行PreAccept階段即可提交(Fast Path)，否則需要運行Accept階段才能提交(Slow Path)。

PreAccept階段嘗試將日志以及與其它日志之間的相對順序達成一致，同時維護該日志與其它日志之間的沖突關系，如果運行完PreAccept階段，沒有發(fā)現(xiàn)該日志與其它并發(fā)提議的日志之間有沖突，則該日志以及與其它日志之間的相對順序已經(jīng)達成一致，直接發(fā)送異步的Commit消息提交;否則如果發(fā)現(xiàn)該日志與其它并發(fā)提議的日志之間有沖突，則日志之間的相對順序還未達成一致，需要運行Accept階段將沖突依賴關系達成多數(shù)派，再發(fā)送Commit消息提交。

EPaxos的Fast Path Quorum為2F，可優(yōu)化至F + [ (F + 1) / 2 ]，在3副本和5副本時，與Paxos、Raft一致。Slow Path 為Paxos Accept階段，Quorum固定為F + 1。 EPaxos還有一個主動Learn的算法，在恢復的時候可用來追趕日志，這里就不做具體的介紹了，感興趣的可以看論文。

對比分析

從Paxos到Raft再到EPaxos，背后的技術是怎么樣演進的，我們可以從算法本身來做個對比，下面主要從可理解性、效率、可用性和適用場景等幾個角度進行對比分析。

1 可理解性

眾所周知，Paxos是出了名的晦澀難懂，不僅難以理解，更難以實現(xiàn)。而Raft則以可理解性和易于實現(xiàn)為目標，Raft的提出大大降低了使用分布式一致性的門檻，將分布式一致性變的大眾化、平民化，因此當Raft提出之后，迅速得到青睞，極大地推動了分布式一致性的工程應用。

EPaxos的提出比Raft還早，但卻長期無人問津，很大一個原因就是EPaxos實在是難以理解。EPaxos基于Paxos，但卻比Paxos更難以理解，大大地阻礙了EPaxos的工程應用。不過，是金子總會發(fā)光的，EPaxos因著它獨特的優(yōu)勢，終于被人們發(fā)現(xiàn)，具有廣闊的前景。

2 效率

從Paxos到Raft再到EPaxos，效率有沒有提升呢?我們主要從負載均衡、消息復雜度、Pipeline以及并發(fā)處理幾個方面來對比Multi-Paxos、Raft和EPaxos。

負載均衡

Multi-Paxos和Raft的Leader負載更高，各副本之間負載不均衡，Leader容易成為瓶頸，而EPaxos無需Leader，各副本之間負載完全均衡。

消息復雜度

Multi-Paxos和Raft選舉出Leader之后，正常只需要一次網(wǎng)絡來回就可以提交一條日志，但Multi-Paxos需要額外的異步Commit消息提交，Raft只需要推進本地的commit index，不使用額外的消息，EPaxos根據(jù)日志沖突情況需要一次或兩次網(wǎng)絡來回。因此消息復雜度，Raft最低，Paxos其次，EPaxos最高。

Pipeline

我們將Pipeline分為順序Pipeline和亂序Pipeline。Multi-Paxos和EPaxos支持亂序Pipeline，Raft因為日志連續(xù)性假設，只支持順序Pipeline。但Raft也可以實現(xiàn)亂序Pipeline，只需要在Leader上給每個Follower維護一個類似于TCP的滑動窗口，對應每個Follower上維護一個接收窗口，允許窗口里面的日志不連續(xù)，窗口外面是已經(jīng)連續(xù)的日志，日志一旦連續(xù)則向前滑動窗口，窗口里面可亂序Pipeline。

并發(fā)處理

Multi-Paxos沿用Paxos的策略，一旦發(fā)現(xiàn)并發(fā)沖突則回退重試，直到成功;Raft則使用強Leader來避免并發(fā)沖突，F(xiàn)ollwer不與Leader競爭，避免了并發(fā)沖突;EPaxos則直面并發(fā)沖突問題，將沖突依賴也做為一致性問題對待，解決并發(fā)沖突。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，F(xiàn)ollower必須等舊Leader的Lease到期后才能發(fā)起選舉，Multi-Paxos是弱Leader，F(xiàn)ollwer可以隨時競選Leader，雖然會對效率造成一定影響，但在Leader失效的時候能更快的恢復服務，因此Multi-Paxos比Raft可用性更好。

4 適用場景

EPaxos更適用于跨AZ跨地域場景，對可用性要求極高的場景，Leader容易形成瓶頸的場景。Multi-Paxos和Raft本身非常相似，適用場景也類似，適用于內(nèi)網(wǎng)場景，一般的高可用場景，Leader不容易形成瓶頸的場景。

思考

最后留下幾個思考題，感興趣的同學可以思考思考，歡迎大家在評論區(qū)留言：

1)Paxos的Proposal ID需要唯一嗎，不唯一會影響正確性嗎?

2)Paxos如果不區(qū)分Max Proposal ID和Accepted Proposal ID，合并成一個Max Proposal ID，過濾Proposal ID小于等于Max Proposal ID的Prepare請求和Accept請求，會影響正確性嗎?

3)Raft的PreVote有什么作用，是否一定需要PreVote?