一文了解分布式一致性演算法EPaxos

簡介：分布式系統一個核心的問題就是資料的一致性，Paxos演算法是分布式一致性中的經典演算法，用來解決一個分布式系統如何就某個值（決議）達成一致的問題，本文從Paxos的問題引出EPaxos，介紹EPaxos的基本概念與直觀理解，閱讀本文需要一些Paxos或Raft等分布式一致性演算法背景，

引言

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之間的依賴為什么會形成環，什么情況下會形成回圈依賴？

原文鏈接：https://developer.aliyun.com/article/776580?

著作權宣告：本文內容由阿里云實名注冊用戶自發貢獻，著作權歸原作者所有，阿里云開發者社區不擁有其著作權，亦不承擔相應法律責任，具體規則請查看《阿里云開發者社區用戶服務協議》和《阿里云開發者社區知識產權保護指引》，如果您發現本社區中有涉嫌抄襲的內容，填寫侵權投訴表單進行舉報，一經查實，本社區將立刻洗掉涉嫌侵權內容，