[[410758]]

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

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

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

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

一 EPaxos基本思想

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

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

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

EPaxos解決了這個問題，實現了真正的Leaderless。EPaxos通過跟蹤Instance之間的依賴關系，確定不同Group產生的Instance的相對順序，然后通過排序將多Group產生的多條Instance序列合并成一條全局的Instance序列，實現了跨Group的一致性，也即實現了真正的Leaderless。

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

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

二 EPaxos的Instance

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

EPaxos的Instance與Paxos的不同點

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

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

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

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

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

三 EPaxos共識協議

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

Paxos與EPaxos的協議流程對比

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

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

1 Prepare階段

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

2 PreAccept階段

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

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

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

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

3 Accept階段

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

4 Commit階段

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

四 EPaxos排序算法

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

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

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

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

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

EPaxos排序算法

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

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

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

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

五 EPaxos案例

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

EPaxos共識協議

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

EPaxos核心協議流程案例中Instance的屬性

1 提議值A

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

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

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

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

2 提議值B

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

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

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

3 提議值C

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

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

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

4 排序

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

提議值A、B、C的Instance之間的依賴關系（左），排序之后的順序（右）

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

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

六 EPaxos討論

1 Instance沖突

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

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

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

2 Fast Quorum

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

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

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

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

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

七 EPaxos偽代碼

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

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

EPaxos核心協議流程偽代碼

八 總結

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

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

思考

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

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