[[334877]]

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

分布式一致性

分布式一致性，簡(jiǎn)單的說(shuō)就是在一個(gè)或多個(gè)進(jìn)程提議了一個(gè)值后，使系統(tǒng)中所有進(jìn)程對(duì)這個(gè)值達(dá)成一致。

為了就某個(gè)值達(dá)成一致，每個(gè)進(jìn)程都可以提出自己的提議，最終通過(guò)分布式一致性算法，所有正確運(yùn)行的進(jìn)程學(xué)習(xí)到相同的值。

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

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

Paxos

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

Prepare階段的作用：

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

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

Multi-Paxos

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

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

Raft

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

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

Raft與Multi-Paxos的不同：

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

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

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

EPaxos

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

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

EPaxos無(wú)Leader選舉開(kāi)銷(xiāo)，一個(gè)副本不可用可立即訪問(wèn)其他副本，具有更高的可用性。各副本負(fù)載均衡，無(wú)Leader瓶頸，具有更高的吞吐量?？蛻舳丝蛇x擇最近的副本提供服務(wù)，在跨AZ跨地域場(chǎng)景下具有更小的延遲。

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

從圖論的角度看，日志是圖的結(jié)點(diǎn)，日志之間的順序是圖的邊，EPaxos對(duì)結(jié)點(diǎn)和邊分別達(dá)成一致，然后使用拓?fù)渑判?，決定日志的順序。圖中也可能形成環(huán)路，EPaxos需要處理循環(huán)依賴(lài)的問(wèn)題。

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

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

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

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

對(duì)比分析

從Paxos到Raft再到EPaxos，背后的技術(shù)是怎么樣演進(jìn)的，我們可以從算法本身來(lái)做個(gè)對(duì)比，下面主要從可理解性、效率、可用性和適用場(chǎng)景等幾個(gè)角度進(jìn)行對(duì)比分析。

1 可理解性

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

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

2 效率

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

負(fù)載均衡

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

消息復(fù)雜度

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

Pipeline

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

并發(fā)處理

Multi-Paxos沿用Paxos的策略，一旦發(fā)現(xiàn)并發(fā)沖突則回退重試，直到成功;Raft則使用強(qiáng)Leader來(lái)避免并發(fā)沖突，F(xiàn)ollwer不與Leader競(jìng)爭(zhēng)，避免了并發(fā)沖突;EPaxos則直面并發(fā)沖突問(wèn)題，將沖突依賴(lài)也做為一致性問(wèn)題對(duì)待，解決并發(fā)沖突。Paxos是沖突回退，Raft是沖突避免，EPaxos是沖突解決。Paxos和Raft的日志都是線性的，而EPaxos的日志是圖狀的，因此EPaxos的并行性更好，吞吐量也更高。

3 可用性

EPaxos任意副本均可提供服務(wù)，某個(gè)副本不可用了可立即切換到其它副本，副本失效對(duì)可用性的影響微乎其微;而Multi-Paxos和Raft均依賴(lài)Leader，Leader不可用了需要重新選舉Leader，在新Leader未選舉出來(lái)之前服務(wù)不可用。顯然EPaxos的可用性比Multi-Paxos和Raft更好，但Multi-Paxos和Raft比誰(shuí)的可用性更好呢。

Raft是強(qiáng)Leader，F(xiàn)ollower必須等舊Leader的Lease到期后才能發(fā)起選舉，Multi-Paxos是弱Leader，F(xiàn)ollwer可以隨時(shí)競(jìng)選Leader，雖然會(huì)對(duì)效率造成一定影響，但在Leader失效的時(shí)候能更快的恢復(fù)服務(wù)，因此Multi-Paxos比Raft可用性更好。

4 適用場(chǎng)景

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

思考

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

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

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

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