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