簡(jiǎn)介：?EPaxos（Egalitarian Paxos）作為工業(yè)界備受矚目的下一代分布式一致性算法，具有廣闊的應(yīng)用前景。但縱觀業(yè)內(nèi)，至今仍未出現(xiàn)一個(gè)EPaxos的工程實(shí)現(xiàn)，甚至都沒(méi)看到一篇能把EPaxos講得通俗一點(diǎn)的文章。EPaxos算法理論雖好，但由于其實(shí)在晦澀難懂，工程實(shí)現(xiàn)上也有很多挑戰(zhàn)，實(shí)際應(yīng)用落地尚未成熟。本文將用通俗易懂的語(yǔ)言介紹EPaxos算法，由淺入深、一步一步的讓只有Paxos或Raft等分布式一致性算法基礎(chǔ)的同學(xué)都能輕易看懂EPaxos，真正將晦澀難懂的EPaxos，變的平易近人，帶入千萬(wàn)家。

作者 | 祥光（嚴(yán)祥光）
來(lái)源 | 阿里技術(shù)公眾號(hào)

引言

EPaxos（Egalitarian Paxos）作為工業(yè)界備受矚目的下一代分布式一致性算法，具有廣闊的應(yīng)用前景。但縱觀業(yè)內(nèi)，至今仍未出現(xiàn)一個(gè)EPaxos的工程實(shí)現(xiàn)，甚至都沒(méi)看到一篇能把EPaxos講得通俗一點(diǎn)的文章。EPaxos算法理論雖好，但由于其實(shí)在晦澀難懂，工程實(shí)現(xiàn)上也有很多挑戰(zhàn)，實(shí)際應(yīng)用落地尚未成熟。

本文旨在通俗易懂地介紹EPaxos算法，由淺入深、一步一步的讓只有Paxos或Raft等分布式一致性算法基礎(chǔ)的同學(xué)都能輕易看懂EPaxos，真正將晦澀難懂的EPaxos，變的平易近人，帶入千萬(wàn)家。

在《一文了解分布式一致性算法EPaxos》中，從Paxos的問(wèn)題引出EPaxos，介紹了EPaxos的基本概念與直觀理解，相信讀者已經(jīng)對(duì)EPaxos有了整體的印象。

本文將從Paxos與EPaxos對(duì)比的角度，介紹EPaxos核心協(xié)議流程。上一篇文章最后留下的思考題，相信在閱讀完本文后，都能找到答案。閱讀本文需要一些Paxos或Raft等分布式一致性算法背景。

一 EPaxos基本思想

EPaxos是一個(gè)Leaderless的一致性算法，無(wú)需選舉Leader，任意副本均可發(fā)起提議。

Leaderless也可以看作每個(gè)副本都是Leader，從Multi-Paxos或Raft的角度看，如果使用多Group，將每個(gè)Leader劃分到不同的Group，每個(gè)副本擔(dān)任一個(gè)Group的Leader，同時(shí)擔(dān)任其它所有Group的Follower，好像也可以做到類(lèi)似Leaderless的效果。

使用多Group實(shí)現(xiàn)的Leaderless，每個(gè)Group獨(dú)立的對(duì)一系列Instance達(dá)成一致，每個(gè)Group產(chǎn)生一條Instance序列，不同Group產(chǎn)生的Instance彼此獨(dú)立，不能確定先后順序。因此跨Group的一致性是一大問(wèn)題，在一致性層面無(wú)法解決，往往需要在上層使用分布式事務(wù)來(lái)解決。

EPaxos解決了這個(gè)問(wèn)題，實(shí)現(xiàn)了真正的Leaderless。EPaxos通過(guò)跟蹤Instance之間的依賴關(guān)系，確定不同Group產(chǎn)生的Instance的相對(duì)順序，然后通過(guò)排序?qū)⒍郍roup產(chǎn)生的多條Instance序列合并成一條全局的Instance序列，實(shí)現(xiàn)了跨Group的一致性，也即實(shí)現(xiàn)了真正的Leaderless。

EPaxos先運(yùn)行共識(shí)協(xié)議，使各副本對(duì)Instance的值和Instance依賴的相對(duì)順序達(dá)成一致，隨后運(yùn)行排序算法，基于前面已經(jīng)達(dá)成共識(shí)的Instance的相對(duì)順序，對(duì)Instance進(jìn)行全局排序，最終得到一致的全局Instance序列。

以上是站在Multi-Paxos或Raft使用多Group實(shí)現(xiàn)Leaderless的角度引出EPaxos的基本思想，實(shí)際Group是一致性算法之外的概念，這里引入Group只是為了方便介紹，實(shí)際EPaxos中并沒(méi)有Group的概念，但與Paxos或Raft類(lèi)似，可以在EPaxos之上實(shí)現(xiàn)多Group。

二 EPaxos的Instance

EPaxos的Instance與Paxos有所不同，Paxos的Instance事先分配序號(hào)，但EPaxos的Instance不事先分配序號(hào)，各副本可以并發(fā)的亂序提交，但跟蹤記錄Instance之間的依賴關(guān)系，最后根據(jù)依賴關(guān)系排序。這里先總結(jié)一下不同點(diǎn)：

EPaxos的Instance與Paxos的不同點(diǎn)

Paxos的Instance由全局連續(xù)遞增的InstanceID標(biāo)識(shí)，InstanceID也是Instance的序號(hào)，全局唯一，連續(xù)遞增。

EPaxos的Instance空間是二維的，每個(gè)副本擁有其中一行，因此由二維的R.i標(biāo)識(shí)，其中R為副本標(biāo)識(shí)，i為副本內(nèi)連續(xù)遞增的整數(shù)，每開(kāi)始一個(gè)新的Instance就加一。副本R擁有的Instance序列為R.1，R.2，R.3，...... R.i，......

EPaxos的Instance相對(duì)Paxos還有一些額外的屬性：

• state標(biāo)識(shí)Instance當(dāng)前的狀態(tài)，可取值pre-accepted、accepted、committed。因?yàn)镋Paxos的Instance的狀態(tài)比較多，所以需要專門(mén)的state字段標(biāo)識(shí)。
• deps為依賴的Instance集合，存放所有依賴的Instance的標(biāo)識(shí)，即要在前面執(zhí)行的Instance。deps保存了Instance之間的相對(duì)順序，后續(xù)將基于deps對(duì)Instance進(jìn)行排序。
• seq為Instance的序列號(hào)，其值為deps中所有Instance的seq的最大值加一，反映Instance提議的順序，后續(xù)排序的時(shí)候使用。

EPaxos的Instance的deps和seq屬性與Instance的值一樣，也需要在各副本之間達(dá)成一致，后續(xù)各副本將獨(dú)立的基于deps和seq對(duì)Instance進(jìn)行排序。因?yàn)镋Paxos的排序算法是確定性的，各副本基于相同的deps和seq對(duì)Instance進(jìn)行排序，最終會(huì)得到一致的全局Instance序列。

將Instance看作圖的頂點(diǎn)，deps就是頂點(diǎn)的出邊，圖的頂點(diǎn)和邊都確定并在各副本之間達(dá)成一致之后，各副本對(duì)圖進(jìn)行確定性的排序，最終得到一致的Instance序列。

三 EPaxos共識(shí)協(xié)議

Paxos提交一個(gè)值需要兩階段，而EPaxos的Instance多了依賴集合deps和序列號(hào)seq，為了確定這些屬性的值，EPaxos比Paxos多了一個(gè)階段。完整的EPaxos有三階段，但并非每個(gè)階段都是必須的，下表將Paxos與EPaxos的協(xié)議流程進(jìn)行對(duì)比：

Paxos與EPaxos的協(xié)議流程對(duì)比

EPaxos與Paxos相比，Prepare階段和Accept階段類(lèi)似，但EPaxos多了PreAccept階段，也是EPaxos最關(guān)鍵的一個(gè)階段。正因?yàn)镋Paxos多了PreAccept階段，Instance的狀態(tài)更多了，所以引入專門(mén)的state屬性來(lái)標(biāo)識(shí)Instance當(dāng)前所處的狀態(tài)（pre-accepted、accepted、committed）。沒(méi)有引入Prepare階段的狀態(tài)，是因?yàn)镻repare階段沒(méi)有提議值，可以通過(guò)本地有無(wú)提議值來(lái)與其它狀態(tài)區(qū)分。通常情況下，EPaxos只運(yùn)行PreAccept階段，即可Commit，Prepare階段和Accept階段都能跳過(guò)。

EPaxos與Paxos類(lèi)似，在任意階段如果發(fā)現(xiàn)Instance被搶占，都需要回退到Prepare階段重新開(kāi)始。

1 Prepare階段

Prepare階段的作用，EPaxos與Paxos類(lèi)似，都是為了爭(zhēng)取提議權(quán)，同時(shí)學(xué)習(xí)之前已經(jīng)提議的最新值。在EPaxos中，因?yàn)槊總€(gè)副本都擁有各自獨(dú)立的Instance空間，在自己的Instance空間上提議，相當(dāng)于Multi-Paxos的Leader，所以與Multi-Paxos類(lèi)似，通常情況下可直接跳過(guò)Prepare階段，直接從下一階段開(kāi)始。

2 PreAccept階段

PreAccept階段是EPaxos特有的，其作用是確定Instance的依賴集合deps和序列號(hào)seq，同時(shí)盡量讓提議值、deps和seq在各副本間達(dá)成一致。若PreAccept階段已經(jīng)達(dá)成一致，則直接到Commit階段（Fast Path），否則需要運(yùn)行Accept階段，然后才到Commit階段（Slow Path）。

PreAccept階段是如何確定Instance的依賴集合deps和序列號(hào)seq的呢？其實(shí)比較簡(jiǎn)單，從副本本地已存在的Instance中，收集需要在前面執(zhí)行的Instance，即本地deps集合，本地seq即本地deps中的所有Instance的seq的最大值加一。最終的依賴集合deps取大多數(shù)副本的本地deps集合的并集，最終的序列號(hào)seq則取他們的本地seq的最大值。

各副本并發(fā)提議的時(shí)候，不同副本的本地deps和本地seq都可能不一樣，那么PreAccept階段如何才能達(dá)成一致呢？如果有足夠多的副本（Fast Quorum）的本地deps和本地seq都相同，則已經(jīng)達(dá)成了一致。否則，最終的依賴集合deps取大多數(shù)（Slow Quorum）副本的本地deps的并集，最終的序列號(hào)seq取它們的本地seq的最大值，然后運(yùn)行Accept階段達(dá)成一致。

PreAccept階段的Fast Quorum始終包含提議者，會(huì)在后面討論原因。Fast Quorum的值不小于Slow Quorum。假設(shè)副本總數(shù)為N，可容忍F個(gè)副本同時(shí)失效，N = 2F + 1，則Fast Quorum = 2F，優(yōu)化后的EPaxos可優(yōu)化至F + [ (F + 1) / 2 ]，Slow Quorum = F + 1。Fast Quorum取值的推導(dǎo)這里先不做介紹，會(huì)在后續(xù)文章中詳細(xì)討論，Slow Quorum即大多數(shù)副本，與Paxos的Accept階段相同。

3 Accept階段

Accept階段的作用，EPaxos與Paxos類(lèi)似，但Paxos只將提議值同步到大多數(shù)副本，EPaxos需要將提議值、deps和seq都同步到大多數(shù)副本，一旦形成多數(shù)派則決議達(dá)成。若在PreAccept階段已經(jīng)達(dá)成決議，則可跳過(guò)Accept階段，直接進(jìn)入Commit階段。

4 Commit階段

Commit階段的作用，EPaxos與Paxos類(lèi)似，都是將達(dá)成的決議異步發(fā)送給其它副本，讓其它副本學(xué)習(xí)到?jīng)Q議，不同的是EPaxos的決議不僅包括決議值，還包括deps和seq。

四 EPaxos排序算法

與Paxos不同，EPaxos的Instance提交后，它們的順序還沒(méi)有確定，因此EPaxos需要一個(gè)額外的排序過(guò)程，對(duì)已提交的Instance進(jìn)行排序。當(dāng)Instance被提交，并且其依賴集合deps中的所有Instance也都提交后，就可以開(kāi)始一次排序過(guò)程。

將EPaxos的Instance看作圖的頂點(diǎn)，Instance的依賴集合deps看作頂點(diǎn)的出邊，Instance的值和依賴集合deps達(dá)成一致后，圖的頂點(diǎn)和邊就在各副本之間達(dá)成一致，因此各副本會(huì)看到相同的依賴圖。

EPaxos對(duì)Instance排序的過(guò)程，類(lèi)似于對(duì)圖進(jìn)行確定性的拓?fù)渑判颉５枰⒁獾氖荅Paxos的Instance之間的依賴可能形成環(huán)，即圖中可能會(huì)有環(huán)路，因此不完全是拓?fù)渑判颉?/p>

為了處理循環(huán)依賴，EPaxos對(duì)Instance排序的算法需要先尋找圖的強(qiáng)連通分量，環(huán)路都包含在了強(qiáng)連通分量中，如果把一個(gè)強(qiáng)連通分量整體看作圖的一個(gè)頂點(diǎn)，則所有強(qiáng)連通分量構(gòu)成一個(gè)有向無(wú)環(huán)圖（DAG），然后對(duì)所有的強(qiáng)連通分量構(gòu)成的有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判颉?/p>

EPaxos排序算法的流程如圖1所示，其中由背景色圈起來(lái)的部分是強(qiáng)連通分量：

EPaxos排序算法

尋找圖的強(qiáng)連通分量一般使用Tarjan算法，它是一個(gè)遞歸算法，實(shí)測(cè)發(fā)現(xiàn)遞歸實(shí)現(xiàn)很容易爆棧，也給工程應(yīng)用帶來(lái)了一定的挑戰(zhàn)。

不同強(qiáng)連通分量中的Instance按照確定性的拓?fù)漤樞蚺判?#xff0c;同一強(qiáng)連通分量中的Instance是并發(fā)提議的，理論上可以按任意確定性規(guī)則排序。EPaxos為每個(gè)Instance計(jì)算了一個(gè)seq序列號(hào)，seq的大小反映了Instance提議的順序，同一強(qiáng)連通分量里面的Instance按照seq大小排序。實(shí)際seq可能重復(fù)，并不能保證全局唯一遞增，EPaxos論文并未考慮到這一點(diǎn)，實(shí)際可以使用seq加副本標(biāo)識(shí)排序。

事實(shí)上，隨著新的Instance不斷的運(yùn)行，舊的Instance可能依賴新的Instance，新的Instance又可能依賴更新的Instance，如此下去可能導(dǎo)致依賴鏈不斷延伸，沒(méi)有終結(jié)，排序過(guò)程一直無(wú)法進(jìn)行，形成活鎖。這也是EPaxos工程應(yīng)用的一大挑戰(zhàn)。

因?yàn)镮nstance排序算法是確定性的，各副本基于一致的依賴圖對(duì)Instance排序后，將得到一致的Instance序列。

五 EPaxos案例

下面使用一個(gè)具體的案例，介紹EPaxos的核心協(xié)議流程，如下圖所示，系統(tǒng)由R1、R2、R3、R4、R5，5個(gè)副本組成，水平方向代表時(shí)間，值A(chǔ)、B、C的提議流程如圖所示。

EPaxos共識(shí)協(xié)議

案例中各Instance的屬性取值如下表所示：

EPaxos核心協(xié)議流程案例中Instance的屬性

1 提議值A(chǔ)

首先R1運(yùn)行PreAccept階段發(fā)起提議值A(chǔ)，它首先獲取自己的本地deps和本地seq，此時(shí)它本地還沒(méi)有任何Instance，所以本地deps為空集，本地seq為初始值1，它持久化提議值A(chǔ)、本地deps和本地seq。

然后R1向R2、R3廣播PreAccept(A)消息，消息攜帶提議值A(chǔ)、本地deps、以及本地seq（圖中未標(biāo)示），此時(shí)R1、R2、R3組成Fast Quorum。PreAccept消息可以只廣播給Fast Quorum中的副本，EPaxos論文中將這種優(yōu)化稱為T(mén)hrifty優(yōu)化。

R2、R3收到PreAccept(A)消息后，分別獲取自己的本地deps和本地seq，與R1類(lèi)似，本地deps為空集，本地seq為1，持久化后回復(fù)R1。

R1收到Fast Quorum中的副本的本地deps和本地seq都相同，決議達(dá)成，最終的deps為空集，seq為1，運(yùn)行Commit階段提交。

2 提議值B

接下來(lái)R5運(yùn)行PreAccept階段發(fā)起提議值B，此時(shí)它本地也還沒(méi)有任何Instance，所以本地deps為空集，本地seq為初始值1。R5本地持久化后，向R3、R4廣播PreAccept(B)消息。

R4回復(fù)的本地deps為空集，本地seq為1，R3此時(shí)本地已經(jīng)有了值A(chǔ)的Instance，因此R3回復(fù)的本地deps為{1.1}，也即圖上標(biāo)示的{A}，本地seq為2，即A的Instance的seq加一。

Fast Quorum中的副本的本地deps和seq不都相同，因此需要運(yùn)行Accept階段，最終的deps取大多數(shù)副本的本地deps的并集為{1.1}，也即圖上標(biāo)的{A}，最終的seq取大多數(shù)副本的本地seq的最大值為2，通過(guò)Accept階段，將提議值B、最終的deps、最終的seq達(dá)成多數(shù)派。最后運(yùn)行Commit階段提交。

3 提議值C

最后R1運(yùn)行PreAccept階段發(fā)起提議值C，此時(shí)R1本地已經(jīng)有了值A(chǔ)的Instance，因此本地deps為{1.1}，也即圖上標(biāo)示的{A}，本地seq為3。R1本地持久化后，向R2、R3廣播PreAccept(C)消息。

R2和R3此時(shí)本地已經(jīng)有了值A(chǔ)和值B的Instance，因此R2、R3回復(fù)的本地deps為1.1，5.1}，也即圖上標(biāo)示的{A，B}，本地seq為3，即B的Instance的seq加一。

Fast Quorum中除了提議者R1以外的其它副本的本地deps和seq都相同，因此決議已經(jīng)達(dá)成，最終的deps為{1.1，5.1}，也即{A，B}，seq為3，運(yùn)行Commit階段提交。

4 排序

提議值A(chǔ)、B、C的Instance按照它們的依賴集合deps畫(huà)出的依賴關(guān)系如下圖（左）所示：

提議值A(chǔ)、B、C的Instance之間的依賴關(guān)系（左），排序之后的順序（右）

A的Instance的deps為空集，因此沒(méi)有出邊；B的Instance的deps為{A}，因此有一條出邊指向A；C的Instance的deps為{A，B}，因此有兩條出邊，分別指向A和B。

依賴關(guān)系圖中沒(méi)有循環(huán)依賴，已經(jīng)是一個(gè)有向無(wú)環(huán)圖（DAG）。因此頂點(diǎn)A、B、C各自是一個(gè)強(qiáng)連通分量，進(jìn)行確定性的拓?fù)渑判蚝蟮玫剿鼈兊捻樞?#xff1a;A <— B <— C，如圖如圖（右）所示。

六 EPaxos討論

1 Instance沖突

EPaxos引入Instance沖突（Interfere）的概念（與Parallel Raft類(lèi)似，與并發(fā)沖突不是一個(gè)概念），若兩個(gè)Instance的值之間沒(méi)有沖突（例如訪問(wèn)不同的key），則它們的先后順序無(wú)關(guān)緊要，甚至可以并行處理，因此EPaxos只處理有沖突的日志之間的依賴關(guān)系。

EPaxos的Instance的依賴集合deps，存放的是需要在該Instance之前執(zhí)行的Instance。引入沖突之后，deps中存放的是與該Instance沖突的Instance。

沖突是一個(gè)與具體應(yīng)用相關(guān)的概念，引入沖突之后，所有Instance不再是全序的，變成了偏序的，減少了依賴，降低了Slow Path的概率，提高了效率。

2 Fast Quorum

關(guān)于Fast Quorum取值的推導(dǎo)，留待后續(xù)文章介紹，這里先討論下，為什么PreAccept階段的Fast Quorum始終包含提議者。

EPaxos在每個(gè)階段，提議者總是本地先持久化成功之后，再?gòu)V播消息給其它副本。也就是說(shuō)提議者總是在Quorum中，因此判斷是否達(dá)成Quorum時(shí)，提議者總是可以算一票。

在PreAccept階段，提議者將其本地deps和seq包含在了PreAccept消息中，作為其它副本計(jì)算它們本地deps和seq的基礎(chǔ)，使得提議者的本地deps和seq總是包含在最終的deps和seq中，因此PreAccept階段的Fast Quorum始終包含提議者。

EPaxos總是先本地持久化成功之后再?gòu)V播給其它副本，這樣可以減小Fast Quorum，但也導(dǎo)致本地持久化與網(wǎng)絡(luò)消息收發(fā)不能并行進(jìn)行，降低了一些效率，同時(shí)也使得提議者不能容忍本地磁盤(pán)損壞的情況，這些都是EPaxos工程應(yīng)用必須面對(duì)的問(wèn)題。

Fast Quorum的值為什么不會(huì)小于Slow Quorum呢？這里無(wú)需推導(dǎo)Fast Quorum的取值，從直觀上就可以得出這個(gè)結(jié)論。在Paxos中一個(gè)副本提議一個(gè)值，所有副本只會(huì)有兩種結(jié)果，接受或者不接受這個(gè)值。而在EPaxos中每個(gè)副本都可能給出不同的deps和seq，因此需要更多的副本給出相同的結(jié)果才能保證在有副本失效后能恢復(fù)出正確的結(jié)果。

七 EPaxos偽代碼

到這里，相信讀者已經(jīng)可以看懂EPaxos核心協(xié)議流程的偽代碼了。EPaxos核心協(xié)議流程偽代碼如下圖所示，為了簡(jiǎn)單，省略了提議ID（Proposal ID，或者叫Ballot Number，投票編號(hào)）相關(guān)的部分，這部分與Paxos相同。

偽代碼中將日志視為命令（Command），每個(gè)Instance對(duì)一條Command達(dá)成一致，每個(gè)副本使用一個(gè)二維數(shù)組cmds保存收到的Command。

EPaxos核心協(xié)議流程偽代碼

八 總結(jié)

EPaxos通過(guò)顯示維護(hù)Instance之間的依賴關(guān)系，不僅去除了對(duì)Leader的依賴，還使得Instance可以并發(fā)的亂序提交，可以更好的進(jìn)行Pipelining優(yōu)化，同時(shí)顯式維護(hù)依賴也使得亂序執(zhí)行成為可能。EPaxos支持亂序確認(rèn)、亂序提交、亂序執(zhí)行，理論上可以有更高的吞吐量。同時(shí)也可以看到一些EPaxos工程應(yīng)用的挑戰(zhàn)，這些都是EPaxos工程落地要解決的問(wèn)題。

本文從Paxos與EPaxos對(duì)比的角度，介紹了EPaxos核心協(xié)議流程，但EPaxos的內(nèi)容決不僅僅只有這些，特別是Failover場(chǎng)景下，如何保證日志序列的順序性。

思考

最后留下幾個(gè)思考題，感興趣的同學(xué)可以先思考思考：

Instance的seq為什么會(huì)重復(fù)，什么情況下會(huì)重復(fù)？

Fast Quorum的取值如何推導(dǎo)？

如果一個(gè)Instance的共識(shí)協(xié)議流程還未完成，其提議者就宕機(jī)了，其它副本該怎么處理這個(gè)Instance？

原文鏈接
本文為阿里云原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的一文了解EPaxos核心协议流程的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。