MEPaxos：低延遲的共識算法*

趙守月，葛洪偉+

1.輕工過程先進控制教育部重點實驗室（江南大學），江蘇 無錫 214122

2.江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122

1 引言

分布式計算中的一個基本問題是在故障存在的情況下，依然能實現(xiàn)整體系統(tǒng)的可靠性[1]。這通常需要分布式系統(tǒng)中各個節(jié)點（副本）對處理過程中某一數(shù)值達成一致，即取得共識。共識問題是許多商業(yè)分布式系統(tǒng)[2-6]的核心。然而現(xiàn)實世界中，由于各種故障（進程故障、通信鏈路故障等）的存在，解決共識問題十分困難[7]。

FLP不可能定理[8]指出：在存在故障（即使只有一個進程故障）的異步系統(tǒng)中，不存在用于解決共識問題的確定性算法。這說明，解決共識問題的算法必須在安全性（safety）和靈活性（liveness）之間取舍。其中，確保安全性算法中影響最深遠的是Lamport提出的 Multi-Paxos（multi-decree Paxos）算法[9-10]。

Multi-Paxos致力于解決異步分布式系統(tǒng)[11]中非拜占庭故障[12]的共識問題。Multi-Paxos依賴單個領(lǐng)導者處理并發(fā)客戶端發(fā)送的命令，但在廣域網(wǎng)環(huán)境下的分布式系統(tǒng)中，單領(lǐng)導者的設(shè)置給客戶端和系統(tǒng)交互帶來了更大的延遲（和領(lǐng)導者不在同一局域網(wǎng)的客戶端需要更多的時間和領(lǐng)導者通信）。同時，領(lǐng)導者易成為整個系統(tǒng)的性能瓶頸。

針對上述單領(lǐng)導者的缺陷，許多Multi-Paxos算法變種被提出。Fast Paxos[13]允許客戶端將命令發(fā)送給所有副本，但在并發(fā)命令的情況下，會產(chǎn)生沖突（collision），造成延遲性能顯著下降。Generalized Paxos[14]可以按任意順序執(zhí)行可交換的命令，但對于不可交換的命令，延遲性能顯著下降。Mencius[15]通過每個副本輪流當領(lǐng)導者的方式均衡負載，但延遲性能易受到單個較慢副本和客戶端負載不均衡的影響。S-Paxos（scalable Paxos）[16]中副本對客戶端發(fā)送的命令批處理之后發(fā)送給領(lǐng)導者，減輕了領(lǐng)導者的壓力，但在廣域網(wǎng)環(huán)境下，領(lǐng)導者依然是性能瓶頸。EPaxos（egalitarian Paxos）[17]允許客戶端將命令發(fā)送至任意副本（通常是距客戶端最近的副本），但延遲性能易受命令沖突的影響。

以上算法在某種程度上較Multi-Paxos降低了客戶端感知到的延遲，但在負載不均衡、命令沖突增大等情況下，延遲性能會變差。本文基于低延遲的設(shè)計目標，結(jié)合EPaxos和Multi-Paxos，提出了共識算法MEPaxos（modified egalitarian Paxos）。MEPaxos 綜合考慮客戶端的負載情況、并發(fā)客戶端的命令沖突情況以及網(wǎng)絡(luò)的實時情況提出了系統(tǒng)平均延遲的計算方法；接著引入超時機制對二階段提交算法進行改進；最后根據(jù)系統(tǒng)平均延遲計算公式，利用改進的二階段提交算法自動進行算法轉(zhuǎn)換，以獲取最優(yōu)的延遲性能。

2 相關(guān)工作

2.1 Multi-Paxos算法

Multi-Paxos將客戶端發(fā)送的命令復制到2F+1（F為能忍受的最大故障數(shù)）個副本來確保安全性，即：在F+1個（稱為法定人數(shù)）副本無故障的情況下，Multi-Paxos能確保安全性。算法具體過程如圖1所示?？蛻舳藢⒚頒發(fā)送給單個領(lǐng)導者，領(lǐng)導者和所有副本（稱之為接受者）進行一輪信息交流（圖1中Prepare階段，每個領(lǐng)導者只執(zhí)行一輪Prepare消息），確保接受者不再響應(yīng)之前的命令。若收到法定人數(shù)接受者的回復，領(lǐng)導者和接受者再進行一輪信息交流（圖1中Accept階段），請求接受者復制C。若領(lǐng)導者收到法定人數(shù)接受者的回復，確認C被成功提交，發(fā)送確認消息給客戶端和所有副本（稱之為學習者），學習者本地提交C。

Fig.1 Multi-Paxos process圖1 Multi-Paxos處理過程

2.2 EPaxos算法

EPaxos是近年業(yè)內(nèi)最認可，廣域網(wǎng)環(huán)境下延遲性能綜合最好的Multi-Paxos算法變種。和Multi-Paxos類似，EPaxos將客戶端命令復制到2F+1個副本上確保安全性。算法具體過程如圖2所示。通常情況下，客戶端將命令C發(fā)送給最近的副本（稱該副本為C的領(lǐng)導者）。C的領(lǐng)導者和所有副本進行一輪消息交流（圖2中Fast path階段）。期間，C的領(lǐng)導者將C和本地與C相關(guān)的命令集合一起發(fā)送，副本回復時包含本地與C相關(guān)的命令集合。若C的領(lǐng)導者收到個（稱為Fast path階段法定人數(shù)）相同的回復，發(fā)送確認消息給客戶端和所有副本，所有副本本地提交C。否則，C的領(lǐng)導者和所有副本再進行一輪消息交流（圖2中Slow path階段）。若C的領(lǐng)導者收到F+1個（稱為Slow path階段法定人數(shù)）副本的回復，發(fā)送確認消息給客戶端和所有副本，所有副本本地提交命令C。

Fig.2 EPaxos process圖2 EPaxos處理過程

2.3 Multi-Paxos和EPaxos對比分析

由于Multi-Paxos中每個領(lǐng)導者只執(zhí)行一輪Prepare消息，可忽略不計，故客戶端發(fā)送命令到收到回復大概需要經(jīng)過4次消息交流（圖1中發(fā)送命令，Accept階段，確認提交）；對于EPaxos，若Fast path階段領(lǐng)導者收到法定人數(shù)副本相同的回復，則客戶端發(fā)送命令到收到回復只需經(jīng)過4次消息交流（圖2中發(fā)送命令，F(xiàn)ast path階段，確認提交）；否則，還需進行一輪Slow path，需要6次信息交流。

EPaxos客戶端將命令發(fā)送給最近的副本，而Multi-Paxos客戶端將命令發(fā)送給指定的領(lǐng)導者，因此，EPaxos在4次消息交流提交命令的情況下，延遲性能優(yōu)于Multi-Paxos。而EPaxos在6次消息交流提交命令的情況下，延遲性能通常劣于Multi-Paxos。

3 MEPaxos算法

MEPaxos適用于非拜占庭故障下的異步分布式系統(tǒng)，是一種低延遲的共識算法。觀察到EPaxos存在需要多執(zhí)行一輪Slow path才可提交命令，延遲增加的情況，MEPaxos將EPaxos與Multi-Paxos結(jié)合。首先，MEPaxos提出了系統(tǒng)平均延遲的計算方法，并對二階段提交算法進行改進。接著，每隔時間段t，計算EPaxos和Multi-Paxos系統(tǒng)平均延遲。根據(jù)計算結(jié)果，利用改進的二階段提交算法自動轉(zhuǎn)換到系統(tǒng)平均延遲較小的算法模式，以獲得最優(yōu)的延遲性能。

3.1 命令沖突

為了方便描述EPaxos需要執(zhí)行一輪Slow path才可提交命令，延遲增加的情況，本文提出命令沖突的概念。

定義（命令沖突）如果q個相關(guān)命令（command interference）[17]a1,a2,…,aq同時被提出，且 EPaxos在處理命令ai(i∈[1,q])時，受到其余相關(guān)命令ak1,ak2,…,akn(k1,k2,…,kn∈[1,q])的影響，多執(zhí)行一輪Slow path才可提交，那么說命令ai和命令ak1,ak2,…,akn是沖突的。

由命令沖突的定義和EPaxos處理步驟[17]可知，EPaxos中，并發(fā)客戶端向同一副本提交相關(guān)命令，命令之間不會產(chǎn)生沖突。只有不同副本處理相關(guān)命令時，命令之間才可能產(chǎn)生沖突。不同副本處的并發(fā)客戶端提出具有相關(guān)性的命令越多，命令沖突也就越多。本文通過系統(tǒng)平均延遲的計算，利用轉(zhuǎn)換算法自動對不同命令沖突下的情況做出反應(yīng)，以取得更優(yōu)的延遲性能。

3.2 系統(tǒng)平均延遲

MEPaxos設(shè)計的主要目標是最小化客戶端感知到的延遲（本文所指的延遲均為提交延遲[17]），給客戶端帶來更好的用戶體驗。本節(jié)考慮整個系統(tǒng)響應(yīng)客戶端的平均延遲，提出系統(tǒng)平均延遲的計算方法。

在MEPaxos中，共有N個副本（N=2F+1，其中F是能容忍的副本最大故障數(shù)）。用Ri表示第i個副本 (i∈[1,N])；tri表示從Rr到Ri所需時間；副本tci表示消息從客戶端到Ri所需的時間。由于客戶端和最近的副本進行交流，因此和同一副本進行交流的客戶端到該副本所需的時間大致相同，這里不進行區(qū)分。

系統(tǒng)平均延遲的計算，主要考慮三個因素：

（1）算法運行過程中客戶端的負載情況，可用算法運行過程中副本處理客戶端提交的命令數(shù)表示。

（2）算法運行過程中并發(fā)客戶端的命令沖突情況，可用副本作為領(lǐng)導者執(zhí)行Slow path的命令數(shù)表示。

（3）算法運行過程中網(wǎng)絡(luò)的實時情況，可用客戶端與副本以及副本與副本之間消息傳輸所需時間表示。

故EPaxos模式下，系統(tǒng)平均延遲ELat可表示為：

其中，Ti表示Ri處理客戶端提交的命令總數(shù)；SCi表示Ri作為領(lǐng)導者執(zhí)行Slow path的命令數(shù)；kmin(i)表示對于r∈[1,N]，第k小的tri，其中k表示Fast path中的法定人數(shù)；pmin(i)表示對于r∈[1,N]，第p小的tri，其中p表示Slow path中的法定人數(shù)。以上數(shù)據(jù)每隔時間段t統(tǒng)計得出。

Multi-Paxos模式下，系統(tǒng)平均延遲MLat可表示為：

其中，Ti表示Ri處理客戶端提交的命令總數(shù)；til表示從副本Ri到領(lǐng)導者Rl的時間；pmin(l)表示對于r∈[1,N]，第p小的trl（EPaxos中Slow path的法定人數(shù)和Multi-Paxos中法定人數(shù)相同）。以上數(shù)據(jù)每隔時間段t統(tǒng)計得出。

3.3 轉(zhuǎn)換算法

MEPaxos在二階段提交算法的基礎(chǔ)上引入超時機制，提出了EPaxos和Multi-Paxos之間的轉(zhuǎn)換算法，具體步驟如下：

（1）算法轉(zhuǎn)換的發(fā)起者RI給各個副本Ri(i∈[1,N])發(fā)送更改算法的通知并設(shè)置超時時間TO。

（2）副本Ri確認收到通知，發(fā)送確認消息以及本地信息LMi給RI，進入轉(zhuǎn)化狀態(tài)（副本在轉(zhuǎn)化狀態(tài)時不會分配新實例，即：對于收到的客戶端命令，放入緩存，在非轉(zhuǎn)化狀態(tài)時再進行處理），同樣設(shè)置超時時間TO。

（3）若RI在TO到達之前收到所有副本的確認消息以及本地信息LMi，則對LMi進行統(tǒng)計，統(tǒng)計結(jié)果記為CLM={LMi|i∈[1,N]}，發(fā)送CLM以及算法轉(zhuǎn)換的執(zhí)行命令給所有副本；否則，發(fā)送算法轉(zhuǎn)換的取消命令給所有副本。

（4）若副本Ri在TO到達之前收到CLM以及算法轉(zhuǎn)換的執(zhí)行命令，根據(jù)CLM執(zhí)行相關(guān)命令RCOM。之后跳出轉(zhuǎn)化狀態(tài)，進入要轉(zhuǎn)換的算法模式。否則，副本Ri跳出轉(zhuǎn)化狀態(tài)，返回之前算法模式（副本在一種算法模式下，不會響應(yīng)另一種算法模式下的任何消息）。

其中，LMi和RCOM根據(jù)MEPaxos轉(zhuǎn)換模式的不同，也有所不同，具體如表1所示。

3.4 MEPaxos算法步驟

MEPaxos詳細步驟如下：

（1）MEPaxos進入EPaxos算法模式，處理客戶端提交的命令。

Table 1 DifferentLMiandRCOMunder different change modes表1 LMi和RCOM在不同轉(zhuǎn)換模式下的選取

（2）每隔時間段t，對式（1）所需數(shù)據(jù)進行統(tǒng)計，計算出ELat，并估計MLat。估計方法如下:

（2.1）假設(shè)Ri(i∈[1,N])為領(lǐng)導者，根據(jù)式（2）計算出系統(tǒng)平均延遲RMLati；

（2.2）取MLat=min({RMLati|i∈[1,N]}),領(lǐng)導者為此時的Ri。

（3）若MLat＜ELat，執(zhí)行轉(zhuǎn)換算法，MEPaxos進入Multi-Paxos算法模式處理客戶端提交的命令，轉(zhuǎn)至步驟（4）執(zhí)行；否則，轉(zhuǎn)至步驟（2）繼續(xù)執(zhí)行。

（4）每隔時間段t，對式（2）所需數(shù)據(jù)進行統(tǒng)計，計算出MLat，并估計ELat。估計方法如下：

（4.1）統(tǒng)計時間段t內(nèi)Ri(i∈[1,N])處理客戶端提交的命令中對關(guān)鍵字Km（m∈[1,M]，M表示關(guān)鍵字總數(shù)）操作的命令數(shù)CKim；

（4.2）則Ri處理的對關(guān)鍵字為Km操作的命令中執(zhí)行Slow path的命令數(shù)SCim為：

（4.3）時間段t內(nèi)Ri執(zhí)行Slow path的命令總數(shù)；

（4.4）根據(jù)統(tǒng)計的數(shù)據(jù)以及SCi，按照式（1）算出ELat。

（5）若ELat≤MLat，執(zhí)行轉(zhuǎn)換算法，MEPaxos進入EPaxos算法模式處理客戶端提交的命令，轉(zhuǎn)至步驟（2）執(zhí)行；否則，轉(zhuǎn)至步驟（4）繼續(xù)執(zhí)行。

3.5 MEPaxos性能分析

由MEPaxos算法步驟可知，為實現(xiàn)最優(yōu)化延遲性能的目標，MEPaxos主要進行了以下改進：

（1）算法運行過程中進行系統(tǒng)平均延遲的計算。

（2）根據(jù)改進（1）計算結(jié)果，利用轉(zhuǎn)換算法轉(zhuǎn)換至系統(tǒng)平均延遲較小的算法模式。

在共識算法實際應(yīng)用中，副本之間通常需要定期發(fā)送心跳信息進行交流[18]。計算系統(tǒng)平均延遲所需數(shù)據(jù)可附帶在心跳信息中一起發(fā)送，所需計算資源對整個系統(tǒng)來說可忽略不計，因此改進（1）只需少量可忽略不計的計算資源。

轉(zhuǎn)換算法的引入，使MEPaxos可轉(zhuǎn)換至系統(tǒng)平均延遲較小的算法模式。雖增加了算法的處理過程，但轉(zhuǎn)換后系統(tǒng)的延遲性能更優(yōu)。

MEPaxos做出了增加少量可忽略不計的計算資源以及算法處理過程的權(quán)衡，以實現(xiàn)更優(yōu)的系統(tǒng)延遲性能。

4 MEPaxos算法保證及其證明

和Multi-Paxos、EPaxos類似，MEPaxos提供以下算法保證：非平凡性（nontriviality）、一致性（consistency）以及進展保證（progress guarantee）。本章將對三種算法保證進行詳細介紹并證明MEPaxos可提供這三種算法保證。

4.1 變量說明

在MEPaxos，定義如下表示：T表示MEPaxos算法從開始運行到結(jié)束運行之間的時間；Modets表示任意時刻ts，MEPaxos算法所處模式；Modebef表示MEPaxos算法轉(zhuǎn)換前的模式；CM表示算法轉(zhuǎn)換模式；EM表示EPaxos模式；MM表示Multi-Paxos模式；Command表示客戶端提交命令的集合；CT(Commandi)為判定命令Commandi是否被提交的函數(shù)，若是，為true，否則為false；Moi表示命令Commandi以模式Moi被提交；Nontri(Modets)為判定模式Modets是否滿足非平凡性的函數(shù)，若是，為true，否則為false；Consis(Modets)為判定模式Modets是否滿足一致性的函數(shù)，若是，為true，否則為false；Process(Modets)為判定模式Modets是否滿足進程保證的函數(shù)，若是，為true，否則為false。

4.2 算法保證描述及證明

根據(jù)MEPaxos算法步驟，以下公式成立：

根據(jù)文獻[9]和文獻[17]，以下公式成立：

下面將詳細介紹三種算法保證并在以上公式的基礎(chǔ)上，證明MEPaxos算法非平凡性、一致性以及進展保證。

非平凡性只有客戶端提出的命令才能被提交。

證明要證明非平凡性，只需證明以下公式成立：

由式（4）、式（6）、式（7）知，要證明式（12）成立，只需證明：

由式（3）、式（5）、式（6）、式（7）知，式（13）成立。因此，非平凡性滿足。 □

一致性對于同一實例（instance），最多只有一個命令被提交，即對于同一實例，如果副本Rp和副本Rq分別提交了命令Cp和Cq，則Cp和Cq相同。

證明要證明一致性，只需證明以下公式成立：

由式（4）、式（8）、式（9）知，要證明式（14）成立，只需證明：

由式（3）、式（5）、式（8）、式（9）知，式（15）成立。因此，一致性滿足。 □

進程保證在大多數(shù)副本沒有故障并且在接收者超時之前消息能送達的情況下，客戶端的命令最終會被非故障副本提交。

證明要證明進程保證，只需證明以下公式成立：

由式（4）、式（10）、式（11）知，要證明式（16）成立，只需證明：

在CM期間，若存在少數(shù)副本故障且在接收者超時之前消息能送達的情況下，根據(jù)轉(zhuǎn)換算法步驟，MEPaxos會跳出轉(zhuǎn)化狀態(tài)，返回Modebef，根據(jù)式（3）、式（10）、式（11）知，此時式（17）成立。

在CM期間，若無副本故障且在接收者超時之前消息能送達的情況下，根據(jù)轉(zhuǎn)換算法步驟，MEPaxos會進入EM或MM模式，根據(jù)式（10）、式（11）知，此時式（17）成立。

故式（17）成立。因此，進程保證滿足。 □

5 實驗與分析

5.1 實驗環(huán)境與參數(shù)設(shè)置

本文實驗運行在亞馬遜彈性計算云（elastic compute cloud，EC2）平臺，采用實例配置如下：1個2.5 GHz的vCPU，內(nèi)存為1 GB，存儲空間為8 GB，網(wǎng)絡(luò)性能低到中等，64位ubuntu16.04操作系統(tǒng)。采用go語言（1.6.2版本）實現(xiàn)MEPaxos，并將其與EPaxos和Multi-Paxos進行對比分析。

實驗采用節(jié)儉模式[17]：在節(jié)儉模式下，副本將消息發(fā)送給法定人數(shù)副本，而不是全部副本。

參數(shù)設(shè)置：

（1）時間段t。t越大，計算EPaxos和Multi-Paxos系統(tǒng)平均延遲所耗費的副本計算能力以及網(wǎng)絡(luò)帶寬等資源越少，算法的穩(wěn)定性越好，但算法的靈敏度越低。在實際生產(chǎn)實踐中，t的選取可根據(jù)可使用資源的多少，客戶端命令沖突變化情況以及對算法的靈敏度需求決定。本文實驗中t設(shè)置為15 s。

（2）超時時間TO。TO越小，算法轉(zhuǎn)換所需的最大時間越小，客戶端等待的時間越少，但算法轉(zhuǎn)換失敗的概率越大。在實際生產(chǎn)實踐中，TO的選取可根據(jù)客戶端負載情況，所能容忍的算法轉(zhuǎn)換時間以及所需的算法轉(zhuǎn)換成功率確定。本文實驗中TO設(shè)置為1 s。

5.2 均衡負載下的延遲

本節(jié)在副本數(shù)為3和5，客戶端負載均衡的情況下，分別比較MEPaxos、EPaxos和Multi-Paxos的延遲性能。當副本數(shù)為3時，將3個副本部署在加利福尼亞北部（California，CA），弗吉尼亞北部（Virginia，VA）和愛爾蘭（Ireland，IE）；當副本數(shù)為5時，另外兩個副本部署在俄勒岡（Oregon，OR）和東京（Tokyo，TKY）。Multi-Paxos的領(lǐng)導者一直為CA處的副本。在每個副本實例上同時也設(shè)置了10個客戶端，它們同時發(fā)送相同數(shù)量的命令（客戶端發(fā)送命令時，收到前一條命令的回復之后才會發(fā)送后一條命令）。由于命令沖突只在不同副本處理相關(guān)命令時才會發(fā)生，因此副本實例上客戶端的數(shù)量對體現(xiàn)3種共識算法延遲性能差異影響不大，這里設(shè)置為10個客戶端。圖3和圖4分別記錄了各副本處的客戶端從發(fā)送命令到收到回復感知到的中位數(shù)和99%ile延遲（算法后的百分比表示具有相關(guān)性的命令所占的百分比）。

Fig.3 Median commit latency(99%ile indicated by lines atop bars)perceived by clients at each replica when Nis 3圖3 N=3時各副本處客戶端感知到的延遲的中位數(shù)（頂部的線表示99%ile）

副本數(shù)為3時，無論不同副本處并發(fā)客戶端發(fā)送的相關(guān)命令所占百分比為多少，EPaxos模式下，相關(guān)命令都不會產(chǎn)生沖突（節(jié)儉模式導致，具體原因詳見參考文獻[17]）。此時，EPaxos的延遲性能要優(yōu)于Multi-Paxos延遲性能。根據(jù)系統(tǒng)平均延遲計算結(jié)果，MEPaxos一直執(zhí)行EPaxos模式。因此圖3中各副本處，EPaxos延遲性能不受相關(guān)命令所占百分比的影響，優(yōu)于Multi-Paxos延遲性能。MEPaxos客戶端感知到的延遲和EPaxos客戶端感知到的延遲大致相同，小于Multi-Paxos客戶端感知到的延遲。

Fig.4 Median commit latency(99%ile indicated by lines atop bars)perceived by clients at each replica when Nis 5圖4 N=5時各副本處客戶端感知到的延遲的中位數(shù)（頂部的線表示99%ile）

副本數(shù)大于3時，隨著不同副本處并發(fā)客戶端發(fā)送的相關(guān)命令所占百分比的增大，EPaxos模式下，命令沖突數(shù)也增加，延遲性能變差。而Multi-Paxos延遲性能不受并發(fā)客戶端相關(guān)命令百分比的影響。此時MEPaxos根據(jù)ELat和MLat的計算結(jié)果，利用轉(zhuǎn)換算法自動地轉(zhuǎn)換至系統(tǒng)平均延遲較小的算法模式。故在圖4各副本處，EPaxos隨著相關(guān)命令所占百分比的增大，延遲性能變差，Multi-Paxos不受相關(guān)命令所占百分比的影響。當相關(guān)命令所占百分比為0時，MEPaxos客戶端感知到的延遲和EPaxos客戶端感知到的延遲大致相同，小于Multi-Paxos客戶端感知到的延遲；當相關(guān)命令所占百分比為75%和100%時，MEPaxos客戶端感知到的延遲和Multi-Paxos客戶端感知到的延遲大致相同，小于EPaxos客戶端感知到的延遲。副本數(shù)大于5的情況和副本數(shù)為5的情況類似，這里不再贅述。

由以上實驗結(jié)果可以看出，在不同副本處并發(fā)客戶端發(fā)送的相關(guān)命令所占百分比增大時，EPaxos算法延遲性能顯著下降。而MEPaxos能根據(jù)系統(tǒng)平均延遲，自動轉(zhuǎn)換到系統(tǒng)平均延遲較小的算法模式，延遲性能要優(yōu)于EPaxos。

5.3 不均衡負載下的延遲

為了測試在客戶端負載不均衡情況下MEPaxos的性能，在5處CA、VA、IE、OR和TKY分別部署了1個副本；Multi-Paxos的領(lǐng)導者依然為CA處的副本；副本數(shù)為3時，MEPaxos一直執(zhí)行EPaxos算法模式，不進行算法轉(zhuǎn)換，這里不再贅述。在OR和IE處的副本實例上同時設(shè)置了10個客戶端，它們同時發(fā)送相同數(shù)量的命令（客戶端發(fā)送命令時，收到前一條命令的回復之后才會發(fā)送后一條命令）。圖5記錄了OR和IE處的客戶端從發(fā)送命令到收到回復感知到的中位數(shù)和99%ile延遲（算法后的百分比表示具有相關(guān)性的命令所占的百分比）。

Fig.5 Median commit latency(99%ile indicated by lines atop bars)perceived by clients at OR and IE when Nis 5圖5 N=5時OR和IE處客戶端感知到的延遲的中位數(shù)（頂部的線表示99%ile）

如圖5，當只在OR和IE處的實例部署客戶端時，EPaxos隨著不同副本處并發(fā)客戶端相關(guān)命令百分比的增大，命令沖突數(shù)增加，延遲性能變差。Multi-Paxos延遲性能不受并發(fā)客戶端相關(guān)命令百分比的影響。在相關(guān)命令所占百分比為0時，EPaxos延遲性能優(yōu)于Multi-Paxos，MEPaxos一直執(zhí)行EPaxos模式，和EPaxos延遲性能大致相同。在相關(guān)命令所占百分比為75%和100%時，MEPaxos根據(jù)ELat和MLat的計算結(jié)果，自動轉(zhuǎn)換至系統(tǒng)平均延遲較小的算法模式。在轉(zhuǎn)換至Multi-Paxos算法模式時，根據(jù)MEPaxos算法的步驟（2），會選擇使系統(tǒng)平均延遲最小的副本（OR處副本）擔任領(lǐng)導者，故此時，MEPaxos客戶端感知到的延遲要小于Multi-Paxos客戶端感知到的延遲。副本數(shù)大于5的情況和副本數(shù)為5的情況類似，這里不再贅述。

以上實驗在客戶端負載不均衡時，進行EPaxos、Multi-Paxos和MEPaxos算法的對比。實驗結(jié)果表明，在客戶端負載不均衡時，MEPaxos始終能選擇系統(tǒng)平均延遲最小的算法模式，確保了算法的系統(tǒng)平均延遲最優(yōu)。同時，轉(zhuǎn)換至Multi-Paxos算法模式時，能自動選擇最適合當前客戶端負載情況的領(lǐng)導者，延遲性能要優(yōu)于Multi-Paxos。

6 結(jié)束語

本文基于低延遲的設(shè)計目標，提出了共識算法MEPaxos。MEPaxos綜合考慮算法運行過程中客戶端的負載情況、并發(fā)客戶端的命令沖突情況、網(wǎng)絡(luò)的實時情況，提出了系統(tǒng)平均延遲的計算方法，并引入超時機制對二階段提交算法進行改進。MEPaxos可根據(jù)系統(tǒng)平均延遲計算結(jié)果，利用改進的二階段提交算法自動選擇平均延遲較小的算法模式。實驗表明，MEPaxos比當前算法具有更好的延遲性能。由于客戶端環(huán)境的多樣性，未來的研究重點將放在進一步有效加強MEPaxos算法在各種客戶端環(huán)境下的穩(wěn)定性，并將其應(yīng)用到實際生產(chǎn)實踐中。