作者 | 祥光（嚴祥光）
來源 | 阿里技術公眾號
引言
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？
招聘
阿里雲存儲-基礎系統&協同服務團隊，負責自研的飛天分佈式協同基礎服務-女媧，產品支持著阿里雲的計算、存儲、網絡等幾乎所有云產品，支持從單地域到全球化各個規模下的數據協同，持續保持業界先進水平。團隊致力於分佈式系統中最核心的分佈式一致性技術的研發，在這裡，你會獲得實現超大規模分佈式系統核心技術的經驗，在個人專業上成長的同時在中國雲計算的發展史上留下自己的印記。感興趣的童鞋可聯繫[email protected]
技術公開課
《分佈式文件存儲系統技術及實現》
本課程針對分步式文件存儲系統的實現進行講解，首先分析為什麼要使用這種分步式存儲系統，以及這種系統在設計時需要注意的問題，並通過比較常見的分步式存儲系統（HDFS、Ceph等），分享阿里Pangu系統針對其中問題的解決方法，結合Pangu系統說明分步式存儲系統的設計要點。
點擊這裡，開始學習吧~
