一文了解分布式一致性算法EPaxos
????分布式系統(tǒng)一個核心的問題就是數(shù)據(jù)的一致性。Paxos算法是分布式一致性中的經(jīng)典算法，用來解決一個分布式系統(tǒng)如何就某個值(決議)達(dá)成一致的問題。本文從Paxos的問題引出EPaxos，介紹EPaxos的基本概念與直觀理解。閱讀本文需要一些Paxos或Raft等分布式一致性算法背景。
引言
EPaxos(Egalitarian Paxos)作為工業(yè)界備受矚目的下一代分布式一致性算法，具有廣闊的應(yīng)用前景。但縱觀業(yè)內(nèi)，至今仍未出現(xiàn)一個EPaxos的工程實現(xiàn)，甚至都沒看到一篇能把EPaxos講的通俗一點的文章。EPaxos算法理論雖好，但由于其實在晦澀難懂，工程實現(xiàn)上也有很多挑戰(zhàn)，實際應(yīng)用落地尚未成熟。
本文旨在通俗易懂地介紹EPaxos算法，由淺入深、一步一步的讓只有Paxos或Raft等分布式一致性算法基礎(chǔ)的同學(xué)都能輕易看懂EPaxos，真正將晦澀難懂的EPaxos，變的平易近人，帶入千萬家。
Paxos的問題
一切還要從Paxos說起。Paxos是分布式一致性算法的鼻祖，在2F+1個副本中可以容忍F個副本同時失效。
Paxos正常情況下達(dá)成一次決議需要兩個階段：Prepare階段和Accept階段。
Prepare階段各副本競爭提議權(quán)，Accept階段競爭到提議權(quán)的副本發(fā)起提議，讓議案在各副本間達(dá)成一致。
使用Paxos對一系列值達(dá)成一致的流程如圖1所示。三個副本，以不同顏色標(biāo)識，A、B、C、D是它們提議的值。它們競爭每個Instance，提議自己的值：
?? 
圖1 使用Paxos對一系列值達(dá)成一致
Paxos獨立的決定每個Instance的值。針對每個Instance，運行完整的Paxos兩階段流程，決定該Instance的值。
Paxos達(dá)成一次決議至少需要兩次網(wǎng)絡(luò)來回，在并發(fā)情況下可能需要更多的網(wǎng)絡(luò)來回，極端情況下甚至可能形成活鎖，效率低下。為了解決這些問題，Multi-Paxos應(yīng)運而生。
Multi-Paxos在各副本中選舉一個Leader，提議由Leader發(fā)起，沒有競爭，解決了活鎖問題。提議都由Leader發(fā)起的情況下，Prepare階段可以跳過，將兩階段變?yōu)橐浑A段，提高效率。
使用Multi-Paxos對一系列值達(dá)成一致的流程如圖2所示。三個副本，以不同顏色標(biāo)識，首先進行Leader選舉，綠色副本被選為Leader，然后連續(xù)提議A、B、C、D四個值：
?? 
圖2 使用Multi-Paxos對一系列值達(dá)成一致
Multi-Paxos首先選舉Leader，Leader選出來后Instance的提議權(quán)都?xì)wLeader，無需競爭Instance的提議權(quán)，因此可以省略Prepare階段，只需要一階段。Leader的存在提高了達(dá)成決議的效率，但同時也成為了性能和可用性的瓶頸。
Leader需要處理比其它副本更多的消息，各副本負(fù)載不均衡，資源利用率不高。Leader宕機后系統(tǒng)不可用，直到新Leader被選舉出來，才能恢復(fù)服務(wù)，降低了可用性。
Basic Paxos每個副本都能提議，可用性高，但因為競爭沖突導(dǎo)致效率低下;Multi-Paxos選舉Leader避免沖突，提高效率，但同時又引入了Leader瓶頸，降低了可用性。效率和可用性能否兼顧?EPaxos正是為了解決此問題而提出。不同于Multi-Paxos引入Leader來避免沖突，EPaxos采用另一種思路，它直面沖突，試圖解決沖突問題。
EPaxos的解決方案
EPaxos是一個Leaderless的一致性算法，任意副本均可發(fā)起提議，通常情況下，達(dá)成一次決議需要一次或兩次網(wǎng)絡(luò)來回。
EPaxos無Leader選舉開銷，一個副本不可用可立即訪問其他副本，具有更高的可用性。各副本負(fù)載均衡，無Leader瓶頸，具有更高的吞吐量?？蛻舳丝蛇x擇最近的副本提供服務(wù)，在跨AZ跨地域場景下具有更小的延遲。
不同于Paxos，事先對所有Instance編號，然后再獨立對每個Instance的值一一達(dá)成一致。EPaxos可并發(fā)的處理多個Instance，不事先對Instance編號，而是在運行時動態(tài)決定各Instance之間的順序。
EPaxos不僅對每個Instance的值達(dá)成一致，還對Instance之間的相對順序達(dá)成一致。EPaxos將不同Instance之間的相對順序也作為一致性問題，在各個副本之間達(dá)成一致，因此各個副本可并發(fā)地在不同的Instance中發(fā)起提議，在這些Instance的值和相對順序都達(dá)成一致后，各副本再對它們按照相對順序重新排序，形成一致的順序。
使用EPaxos對一系列值達(dá)成一致的流程如圖3所示：三個副本，以不同顏色標(biāo)識，各副本有自己的Instance空間，在各自的Instance中提議自己的值，A、B、C、D是它們提議的值。每個Instance不僅對值達(dá)成一致，還對與其它Instance之間的相對順序達(dá)成一致。
?? 
圖3 使用EPaxos對一系列值達(dá)成一致
EPaxos的Instance空間是二維的，每個副本擁有二維Instance空間中的一行，無需競爭Instance的提議權(quán)，各副本可并發(fā)的在各自的Instance空間中發(fā)起提議，同時維護Instance之間的相對順序，對Instance的值和相對順序都達(dá)成一致。最后各副本各自按照相對順序?qū)nstance進行確定性的重新排序，即對一系列值達(dá)成一致。
EPaxos引入依賴(deps)的概念，作為Instance的一個屬性，以表示Instance之間的相對順序。A ← B即B依賴A，表示A在B之前。每個Instance都有自己的依賴集合，EPaxos維護Instance之間的依賴，并讓依賴集合與值一起在各副本之間達(dá)成一致，最后各副本按照依賴對Instance重新排序，得到一致的值序列。圖3中的案例，最后各副本達(dá)成一致的一系列值為：A ← B ← C ← D。
將EPaxos的Instance看作圖上的結(jié)點，Instance的依賴集合看作結(jié)點的出邊，Instance的值和依賴集合達(dá)成決議后，圖的結(jié)點和邊就在各副本之間達(dá)成一致，因此各副本會看到到相同的圖。
EPaxos對Instance重新排序的過程，類似于對圖進行確定性的拓?fù)渑判?。但需要注意的是EPaxos的Instance之間的依賴可能形成環(huán)，即圖中可能有環(huán)路，因此不完全是拓?fù)渑判颉?/p>
為了處理循環(huán)依賴，EPaxos對Instance重排序的算法需要先尋找圖的強連通分量，環(huán)路都包含在了強連通分量中，所有強連通分量構(gòu)成一個有向無環(huán)圖(DAG)，然后對強連通分量進行確定性的拓?fù)渑判颉?/p>
EPaxos對Instance重新排序的流程如圖4所示，其中由背景色圈起來的是強連通分量：
?? 
圖4 EPaxos對Instance重新排序流程
尋找圖的強連通分量一般使用Tarjan算法，它是一個遞歸算法，實際壓測發(fā)現(xiàn)遞歸實現(xiàn)很容易爆棧，也給工程應(yīng)用帶來了一定的挑戰(zhàn)。
不同強連通分量中的Instance按照確定性的拓?fù)漤樞蚺判?，同一強連通分量中的Instance是并發(fā)提議的，理論上可按任意確定性規(guī)則排序。EPaxos給出了一種方案，為每個Instance維護了一個seq序列號，seq的大小近似反映了Instance提議的順序，期望全局唯一遞增，同一強連通分量里面的Instance按照seq大小排序。實現(xiàn)的時候測試發(fā)現(xiàn)seq可能重復(fù)，EPaxos論文并未考慮到這一點，后續(xù)文章會更詳細(xì)的介紹此問題與解決方案。
當(dāng)有Instance達(dá)成決議，并且其依賴的所有Instance也都達(dá)成決議后，就可以開始一次排序過程。實際上，隨著新的Instance不斷的運行，舊的Instance可能依賴新的Instance，新的Instance又可能依賴更新的Instance，導(dǎo)致依賴鏈不斷延伸，沒有終結(jié)，排序過程一直無法進行，形成活鎖。這也是EPaxos工程應(yīng)用的一大挑戰(zhàn)。
因為Instance排序算法是確定性的，各副本基于一致的依賴關(guān)系圖對Instance重新排序后，得到一致的Instance序列，即對一系列值達(dá)成一致。
總結(jié)
EPaxos通過引入動態(tài)順序，同時兼顧了效率和可用性，融合了Basic Paxos和Multi-Paxos的優(yōu)點，具有廣闊的應(yīng)用前景。本文粗淺的介紹了EPaxos的基本概念和直觀理解，希望能讓讀者對EPaxos有個整體印象。
思考
最后留下幾個思考題，感興趣的同學(xué)可以思考思考：
EPaxos的Instance沒有事先編號，那Instance如何標(biāo)識?
EPaxos如何確定Instance的依賴集合，又如何讓依賴集合達(dá)成一致?
EPaxos的Instance之間的依賴為什么會形成環(huán)，什么情況下會形成循環(huán)依賴?
【本文為51CTO專欄作者“阿里巴巴官方技術(shù)”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】
