[[410758]]

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

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

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

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

一 EPaxos基本思想

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

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

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

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

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

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

二 EPaxos的Instance

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

EPaxos的Instance與Paxos的不同點

Paxos的Instance由全局連續(xù)遞增的InstanceID標識，InstanceID也是Instance的序號，全局唯一，連續(xù)遞增。

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

EPaxos的Instance相對Paxos還有一些額外的屬性：

state標識Instance當前的狀態(tài)，可取值pre-accepted、accepted、committed。因為EPaxos的Instance的狀態(tài)比較多，所以需要專門的state字段標識。
deps為依賴的Instance集合，存放所有依賴的Instance的標識，即要在前面執(zhí)行的Instance。deps保存了Instance之間的相對順序，后續(xù)將基于deps對Instance進行排序。
seq為Instance的序列號，其值為deps中所有Instance的seq的最大值加一，反映Instance提議的順序，后續(xù)排序的時候使用。
EPaxos的Instance的deps和seq屬性與Instance的值一樣，也需要在各副本之間達成一致，后續(xù)各副本將獨立的基于deps和seq對Instance進行排序。因為EPaxos的排序算法是確定性的，各副本基于相同的deps和seq對Instance進行排序，最終會得到一致的全局Instance序列。

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

三 EPaxos共識協(xié)議

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

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

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

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

1 Prepare階段

Prepare階段的作用，EPaxos與Paxos類似，都是為了爭取提議權(quán)，同時學習之前已經(jīng)提議的最新值。在EPaxos中，因為每個副本都擁有各自獨立的Instance空間，在自己的Instance空間上提議，相當于Multi-Paxos的Leader，所以與Multi-Paxos類似，通常情況下可直接跳過Prepare階段，直接從下一階段開始。

2 PreAccept階段

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

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

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

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

3 Accept階段

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

4 Commit階段

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

四 EPaxos排序算法

與Paxos不同，EPaxos的Instance提交后，它們的順序還沒有確定，因此EPaxos需要一個額外的排序過程，對已提交的Instance進行排序。當Instance被提交，并且其依賴集合deps中的所有Instance也都提交后，就可以開始一次排序過程。

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

EPaxos對Instance排序的過程，類似于對圖進行確定性的拓撲排序。但需要注意的是EPaxos的Instance之間的依賴可能形成環(huán)，即圖中可能會有環(huán)路，因此不完全是拓撲排序。

為了處理循環(huán)依賴，EPaxos對Instance排序的算法需要先尋找圖的強連通分量，環(huán)路都包含在了強連通分量中，如果把一個強連通分量整體看作圖的一個頂點，則所有強連通分量構(gòu)成一個有向無環(huán)圖（DAG），然后對所有的強連通分量構(gòu)成的有向無環(huán)圖進行拓撲排序。

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

EPaxos排序算法

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

不同強連通分量中的Instance按照確定性的拓撲順序排序，同一強連通分量中的Instance是并發(fā)提議的，理論上可以按任意確定性規(guī)則排序。EPaxos為每個Instance計算了一個seq序列號，seq的大小反映了Instance提議的順序，同一強連通分量里面的Instance按照seq大小排序。實際seq可能重復，并不能保證全局唯一遞增，EPaxos論文并未考慮到這一點，實際可以使用seq加副本標識排序。

事實上，隨著新的Instance不斷的運行，舊的Instance可能依賴新的Instance，新的Instance又可能依賴更新的Instance，如此下去可能導致依賴鏈不斷延伸，沒有終結(jié)，排序過程一直無法進行，形成活鎖。這也是EPaxos工程應用的一大挑戰(zhàn)。

因為Instance排序算法是確定性的，各副本基于一致的依賴圖對Instance排序后，將得到一致的Instance序列。

五 EPaxos案例

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

EPaxos共識協(xié)議

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

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

1 提議值A(chǔ)

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

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

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

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

2 提議值B

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

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

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

3 提議值C

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

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

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

4 排序

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

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

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

依賴關(guān)系圖中沒有循環(huán)依賴，已經(jīng)是一個有向無環(huán)圖（DAG）。因此頂點A、B、C各自是一個強連通分量，進行確定性的拓撲排序后得到它們的順序：A <— B <— C，如圖如圖（右）所示。

六 EPaxos討論

1 Instance沖突

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

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

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

2 Fast Quorum

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

EPaxos在每個階段，提議者總是本地先持久化成功之后，再廣播消息給其它副本。也就是說提議者總是在Quorum中，因此判斷是否達成Quorum時，提議者總是可以算一票。

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

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

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

七 EPaxos偽代碼

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

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

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

八 總結(jié)

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

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

思考

最后留下幾個思考題，感興趣的同學可以先思考思考：

Instance的seq為什么會重復，什么情況下會重復？
Fast Quorum的取值如何推導？
如果一個Instance的共識協(xié)議流程還未完成，其提議者就宕機了，其它副本該怎么處理這個Instance？