趙守月，葛洪偉+

1.輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室（江南大學(xué)），江蘇 無錫 214122

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

1 引言

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

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

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

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

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

2 相關(guān)工作

2.1 Multi-Paxos算法

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

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

2.2 EPaxos算法

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

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

2.3 Multi-Paxos和EPaxos對(duì)比分析

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

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

3 MEPaxos算法

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

3.1 命令沖突

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 轉(zhuǎn)換算法

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

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

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

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

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

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

3.4 MEPaxos算法步驟

MEPaxos詳細(xì)步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

3.5 MEPaxos性能分析

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

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

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

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

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

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

4 MEPaxos算法保證及其證明

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

4.1 變量說明

在MEPaxos，定義如下表示：T表示MEPaxos算法從開始運(yùn)行到結(jié)束運(yùn)行之間的時(shí)間；Modets表示任意時(shí)刻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是否滿足進(jìn)程保證的函數(shù)，若是，為true，否則為false。

4.2 算法保證描述及證明

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

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

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

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

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

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

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

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

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

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

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

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

證明要證明進(jìn)程保證，只需證明以下公式成立：

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

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

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

故式（17）成立。因此，進(jìn)程保證滿足。 □

5 實(shí)驗(yàn)與分析

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

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

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

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

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

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

5.2 均衡負(fù)載下的延遲

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

副本數(shù)為3時(shí)，無論不同副本處并發(fā)客戶端發(fā)送的相關(guān)命令所占百分比為多少，EPaxos模式下，相關(guān)命令都不會(huì)產(chǎn)生沖突（節(jié)儉模式導(dǎo)致，具體原因詳見參考文獻(xiàn)[17]）。此時(shí)，EPaxos的延遲性能要優(yōu)于Multi-Paxos延遲性能。根據(jù)系統(tǒng)平均延遲計(jì)算結(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í)各副本處客戶端感知到的延遲的中位數(shù)（頂部的線表示99%ile）

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

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

5.3 不均衡負(fù)載下的延遲

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

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

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

6 結(jié)束語

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