引言
EPaxos（Egalitarian Paxos）作為工業界備受矚目的下一代分布式一緻性算法，具有廣闊的應用前景。但縱觀業内，至今仍未出現一個EPaxos的工程實作，甚至都沒看到一篇能把EPaxos講的通俗一點的文章。EPaxos算法理論雖好，但由于其實在晦澀難懂，工程實作上也有很多挑戰，實際應用落地尚未成熟。
本文旨在通俗易懂地介紹EPaxos算法，由淺入深、一步一步的讓隻有Paxos或Raft等分布式一緻性算法基礎的同學都能輕易看懂EPaxos，真正将晦澀難懂的EPaxos，變的平易近人，帶入千萬家。
Paxos的問題
一切還要從Paxos說起。Paxos是分布式一緻性算法的鼻祖，在2F+1個副本中可以容忍F個副本同時失效。
Paxos正常情況下達成一次決議需要兩個階段：Prepare階段和Accept階段。
Prepare階段各副本競争提議權，Accept階段競争到提議權的副本發起提議，讓議案在各副本間達成一緻。
使用Paxos對一系列值達成一緻的流程如圖1所示。三個副本，以不同顔色辨別，A、B、C、D是它們提議的值。它們競争每個Instance，提議自己的值：
Paxos獨立的決定每個Instance的值。針對每個Instance，運作完整的Paxos兩階段流程，決定該Instance的值。
Paxos達成一次決議至少需要兩次網絡來回，在并發情況下可能需要更多的網絡來回，極端情況下甚至可能形成活鎖，效率低下。為了解決這些問題，Multi-Paxos應運而生。
Multi-Paxos在各副本中選舉一個Leader，提議由Leader發起，沒有競争，解決了活鎖問題。提議都由Leader發起的情況下，Prepare階段可以跳過，将兩階段變為一階段，提高效率。
使用Multi-Paxos對一系列值達成一緻的流程如圖2所示。三個副本，以不同顔色辨別，首先進行Leader選舉，綠色副本被選為Leader，然後連續提議A、B、C、D四個值：
Multi-Paxos首先選舉Leader，Leader選出來後Instance的提議權都歸Leader，無需競争Instance的提議權，是以可以省略Prepare階段，隻需要一階段。Leader的存在提高了達成決議的效率，但同時也成為了性能和可用性的瓶頸。
Leader需要處理比其它副本更多的消息，各副本負載不均衡，資源使用率不高。Leader當機後系統不可用，直到新Leader被選舉出來，才能恢複服務，降低了可用性。
Basic Paxos每個副本都能提議，可用性高，但因為競争沖突導緻效率低下；Multi-Paxos選舉Leader避免沖突，提高效率，但同時又引入了Leader瓶頸，降低了可用性。效率和可用性能否兼顧？EPaxos正是為了解決此問題而提出。不同于Multi-Paxos引入Leader來避免沖突，EPaxos采用另一種思路，它直面沖突，試圖解決沖突問題。
EPaxos的解決方案
EPaxos是一個Leaderless的一緻性算法，任意副本均可發起提議，通常情況下，達成一次決議需要一次或兩次網絡來回。
EPaxos無Leader選舉開銷，一個副本不可用可立即通路其他副本，具有更高的可用性。各副本負載均衡，無Leader瓶頸，具有更高的吞吐量。用戶端可選擇最近的副本提供服務，在跨AZ跨地域場景下具有更小的延遲。
不同于Paxos，事先對所有Instance編号，然後再獨立對每個Instance的值一一達成一緻。EPaxos可并發的處理多個Instance，不事先對Instance編号，而是在運作時動态決定各Instance之間的順序。
EPaxos不僅對每個Instance的值達成一緻，還對Instance之間的相對順序達成一緻。EPaxos将不同Instance之間的相對順序也作為一緻性問題，在各個副本之間達成一緻，是以各個副本可并發地在不同的Instance中發起提議，在這些Instance的值和相對順序都達成一緻後，各副本再對它們按照相對順序重新排序，形成一緻的順序。
使用EPaxos對一系列值達成一緻的流程如圖3所示：三個副本，以不同顔色辨別，各副本有自己的Instance空間，在各自的Instance中提議自己的值，A、B、C、D是它們提議的值。每個Instance不僅對值達成一緻，還對與其它Instance之間的相對順序達成一緻。
EPaxos的Instance空間是二維的，每個副本擁有二維Instance空間中的一行，無需競争Instance的提議權，各副本可并發的在各自的Instance空間中發起提議，同時維護Instance之間的相對順序，對Instance的值和相對順序都達成一緻。最後各副本各自按照相對順序對Instance進行确定性的重新排序，即對一系列值達成一緻。
EPaxos引入依賴（deps）的概念，作為Instance的一個屬性，以表示Instance之間的相對順序。A ← B即B依賴A，表示A在B之前。每個Instance都有自己的依賴集合，EPaxos維護Instance之間的依賴，并讓依賴集合與值一起在各副本之間達成一緻，最後各副本按照依賴對Instance重新排序，得到一緻的值序列。圖3中的案例，最後各副本達成一緻的一系列值為：A ← B ← C ← D。
将EPaxos的Instance看作圖上的結點，Instance的依賴集合看作結點的出邊，Instance的值和依賴集合達成決議後，圖的結點和邊就在各副本之間達成一緻，是以各副本會看到到相同的圖。
EPaxos對Instance重新排序的過程，類似于對圖進行确定性的拓撲排序。但需要注意的是EPaxos的Instance之間的依賴可能形成環，即圖中可能有環路，是以不完全是拓撲排序。
為了處理循環依賴，EPaxos對Instance重排序的算法需要先尋找圖的強連通分量，環路都包含在了強連通分量中，所有強連通分量構成一個有向無環圖（DAG），然後對強連通分量進行确定性的拓撲排序。
EPaxos對Instance重新排序的流程如圖4所示，其中由背景色圈起來的是強連通分量：
尋找圖的強連通分量一般使用Tarjan算法，它是一個遞歸算法，實際壓測發現遞歸實作很容易爆棧，也給工程應用帶來了一定的挑戰。
不同強連通分量中的Instance按照确定性的拓撲順序排序，同一強連通分量中的Instance是并發提議的，理論上可按任意确定性規則排序。EPaxos給出了一種方案，為每個Instance維護了一個seq序列号，seq的大小近似反映了Instance提議的順序，期望全局唯一遞增，同一強連通分量裡面的Instance按照seq大小排序。實作的時候測試發現seq可能重複，EPaxos論文并未考慮到這一點，後續文章會更詳細的介紹此問題與解決方案。
當有Instance達成決議，并且其依賴的所有Instance也都達成決議後，就可以開始一次排序過程。實際上，随着新的Instance不斷的運作，舊的Instance可能依賴新的Instance，新的Instance又可能依賴更新的Instance，導緻依賴鍊不斷延伸，沒有終結，排序過程一直無法進行，形成活鎖。這也是EPaxos工程應用的一大挑戰。
因為Instance排序算法是确定性的，各副本基于一緻的依賴關系圖對Instance重新排序後，得到一緻的Instance序列，即對一系列值達成一緻。
總結
EPaxos通過引入動态順序，同時兼顧了效率和可用性，融合了Basic Paxos和Multi-Paxos的優點，具有廣闊的應用前景。本文粗淺的介紹了EPaxos的基本概念和直覺了解，希望能讓讀者對EPaxos有個整體印象。
思考
最後留下幾個思考題，感興趣的同學可以思考思考：
EPaxos的Instance沒有事先編号，那Instance如何辨別？
EPaxos如何确定Instance的依賴集合，又如何讓依賴集合達成一緻？
EPaxos的Instance之間的依賴為什麼會形成環，什麼情況下會形成循環依賴？