一文了解分布式一致性算法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，提議自己的值：
?? 
圖1 使用Paxos對一系列值達成一致
Paxos獨立的決定每個Instance的值。針對每個Instance，運行完整的Paxos兩階段流程，決定該Instance的值。
Paxos達成一次決議至少需要兩次網絡來回，在并發情況下可能需要更多的網絡來回，極端情況下甚至可能形成活鎖，效率低下。為了解決這些問題，Multi-Paxos應運而生。
Multi-Paxos在各副本中選舉一個Leader，提議由Leader發起，沒有競爭，解決了活鎖問題。提議都由Leader發起的情況下，Prepare階段可以跳過，將兩階段變為一階段，提高效率。
使用Multi-Paxos對一系列值達成一致的流程如圖2所示。三個副本，以不同顏色標識，首先進行Leader選舉，綠色副本被選為Leader，然后連續提議A、B、C、D四個值：
?? 
圖2 使用Multi-Paxos對一系列值達成一致
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之間的相對順序達成一致。
?? 
圖3 使用EPaxos對一系列值達成一致
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所示，其中由背景色圈起來的是強連通分量：
?? 
圖4 EPaxos對Instance重新排序流程
尋找圖的強連通分量一般使用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之間的依賴為什么會形成環，什么情況下會形成循環依賴?
【本文為51CTO專欄作者“阿里巴巴官方技術”原創稿件，轉載請聯系原作者】
