張 健，汪 洋，劉丹丹

(1.武漢大學 計算機學院，武漢 430072； 2.武漢大學 軟件工程國家重點實驗室，武漢 430072)(*通信作者電子郵箱943629628@qq.com)

分布式一致性算法Yac

張 健1，汪 洋1*，劉丹丹2

(1.武漢大學 計算機學院，武漢 430072； 2.武漢大學 軟件工程國家重點實驗室，武漢 430072)(*通信作者電子郵箱943629628@qq.com)

傳統(tǒng)靜態(tài)拓撲主從模型分布式一致性算法存在嚴重負載不均及單點性能瓶頸效應，且崩潰節(jié)點大于集群規(guī)模的50%時算法無法正常工作。針對上述問題，提出基于動態(tài)拓撲及有限表決思想的分布式一致性算法(Yac)。算法動態(tài)生成參與一致性表決的成員子集及Leader節(jié)點并時分遷移，形成統(tǒng)計負載均衡；去除要求全體多數(shù)派成員參與表決的強約束，使算法具備更高的失效容忍性；并通過日志鏈機制重新建立算法安全性約束，同時證明了算法的正確性。實驗結果表明，改進算法的單點負載集中效應顯著低于主流靜態(tài)拓撲主從模型分布式一致性算法Zookeeper；改進算法失效容忍性優(yōu)于Zookeeper，且最壞情況下與Zookeeper算法保持持平；同等集群規(guī)模下，改進算法比Zookeeper擁有更高吞吐量上限。

分布式一致性；Paxos算法；表決團；日志鏈；負載均衡

0 引言

分布式計算技術的發(fā)展平衡了日益膨脹的應用計算性能需求與單機性能瓶頸之間的矛盾，一致性問題是保證分布式系統(tǒng)正確性與可靠性的核心問題。

Lamport等[1]于1998年首次提出拜占庭問題，并對非拜占庭模型下分布式一致性問題給出了形式化討論與證明，同年還提出了近乎公理化的分布式一致性算法Paxos[2]。持續(xù)多年的研究和改進之后，文獻[3]進一步重構和完善了Paxos的算法理論。經(jīng)典Paxos算法存在活鎖問題，這是由于經(jīng)典Paxos算法中沒有主節(jié)點，提案基于P2P模型表決，導致成員節(jié)點間可能產(chǎn)生無休止的競爭。針對此問題，文獻[4-5]提出并完善了基于經(jīng)典Paoxos的變種算法Fast-Paxos，首次引入主節(jié)點以消除活鎖，并通過樂觀鎖降低Paxos算法延遲。2013年Google研究院發(fā)表公開了其對Paxos應用研究成果，其證實采用基于主從模型的Multi-Paxos算法工程化實現(xiàn)的分布式鎖服務Chubby[6]支撐了Google公司全球系統(tǒng)基礎設施的運行。

此后，斯坦福大學的Diego Ongaro等[7]提出的Raft算法，還有文獻[8-10]中所描述的始于Apache基金會Hadoop項目子項目的Zookeeper分布式一致性服務，共同推動分布式一致性算法進入以主從模型為主流的發(fā)展時代。

基于主從模型的一致性系統(tǒng)雖然消除了活鎖問題，也較P2P模型擁有更低的平均延遲，但也由于Leader節(jié)點的存在，產(chǎn)生了嚴重的單點性能瓶頸問題。此外，Leader節(jié)點如果崩潰，那么重新選舉Leader節(jié)點引起的系統(tǒng)震蕩也降低了系統(tǒng)的穩(wěn)定性。因此，一部分學者也嘗試尋找新方法提高主從分布式一致性模型的吞吐量。有研究人員嘗試改良分布式一致性算法拓撲結構。文獻[11]提出了Ring-Paxos算法，在成員節(jié)點間構建邏輯環(huán)執(zhí)行鏈式表決，有效降低消息傳播數(shù)量，削弱瓶頸帶來的影響。文獻[12]提出的HT-Paxos算法犧牲了時延性能指標，在執(zhí)行分布式表決前通過被稱為disseminators的節(jié)點集群完成分布式一致性請求的預處理，最大限度剝離Leader節(jié)點的職能 。文獻[13]提出的S-Paxos算法在執(zhí)行分布式?jīng)Q策的Paxos層下建立一個消息擴散層以代替主節(jié)點擴散廣播消息，一定程度上抑制了Leader節(jié)點的消息傳遞開銷。文獻[14]提出了法定集(Quorum)租約機制，在犧牲部分寫時延及失效容忍性基礎上大幅度提高狀態(tài)讀取速度。上述的研究工作都取得了一定成果，但未能夠完全解決Leader節(jié)點存在的單點效應問題。

本文針對主從式分布式算法特性，在Raft、Zookeeper的體系架構基礎上提出了改良，采用時域哈希方法，使作為負載中心Leader節(jié)點隨時間序列動態(tài)轉(zhuǎn)移，實現(xiàn)統(tǒng)計上的負載均衡；同時為降低一致性表決廣播數(shù)量和提高可用性，提出有限表決思想，舍棄傳統(tǒng)一致性表決實例中的半數(shù)以上成員參加的強約束，任意一次表決僅要求有限成員子集參與，并通過Log Chain機制杜絕集群狀態(tài)分支，形成了新的高性能分布式一致性框架。本文對新算法的CAP(Consistency, Availability and Partition tolerance)[15]特性進行了分析闡明，同時還對算法的負載均衡性、吞吐量、時延等關鍵技術指標進行了實驗驗證。根據(jù)實驗結果，新型分布式一致性算法在克服單點性能瓶頸的負載均衡性、可用性、吞吐量、重度負載情形下請求處理時延等指標上都具備較好的表現(xiàn)。

1 Yac分布式一致性算法

1.1 一致性問題模型與分布式副本狀態(tài)機

分布式一致性問題的數(shù)學模型描述如下：

圖1 日志堆積與狀態(tài)變更

日志視圖與狀態(tài)視圖是等價的，如圖1所演示的狀態(tài)變更日志堆棧中，節(jié)點1和節(jié)點2中初始狀態(tài)為A=1。節(jié)點1的狀態(tài)轉(zhuǎn)移日志為A+2和A-5，節(jié)點2的狀態(tài)轉(zhuǎn)移日志序列為A-5；則最終，節(jié)點1表征的狀態(tài)視圖為A=-2，而節(jié)點2表征的狀態(tài)視圖為A=-4。

可以根據(jù)日志視圖模型進一步將分布式一致性問題描述為下列形式：

定義2 分布式集群成員節(jié)點初始狀態(tài)一致。如果經(jīng)過離散時間序列{Tn}后，集群中分布式副本狀態(tài)機儲存的日志堆棧一致，則集群狀態(tài)一致，反之則集群狀態(tài)不一致。

1.2 傳統(tǒng)主從式分布式一致性算法的問題

傳統(tǒng)主流的主從式分布式一致性算法模型如Zookeeper、Raft等，存在通用的架構形式。

本質(zhì)包含如下幾種主要角色。

1)Leader：全局的唯一的主節(jié)點。具備Sequencer的功能，在分布式一致性表決中裁定議案(Proposal)的偏序，并產(chǎn)生一致性決議。

2)Follower：一致性表決的參與者，可以針對某項決議向Leader發(fā)起投票，通常傳統(tǒng)任何一個一致性表決都要求一半以上成員節(jié)點組成的子集(也稱法定集)參加，這也是傳統(tǒng)分布式一致性算法在半數(shù)以上成員存活時才能正常工作的強約束的由來。

3)Learner：不參加一致性表決，僅學習一致性結果。

上述Leader、Follower和Learner只是邏輯上的角色劃分，有時并不一定有嚴格界限，許多分布式系統(tǒng)中，F(xiàn)ollower和Learner會一體化實現(xiàn)，而也有的分布式系統(tǒng)中，Leader也被允許如Follwer一樣參與投票。

可以抽象出這些主從分布式一致性算法的一般模式，如下。

1)選主：系統(tǒng)初始狀態(tài)下，首先通過特定的選主算法，在全部成員節(jié)點中選出Leader，并且當Leader節(jié)點崩潰后重新執(zhí)行選主過程。

2)一致性請求：客戶端(Client)提交的請求(Request)首先被轉(zhuǎn)發(fā)給Leader，Leader將請求轉(zhuǎn)換成議案(Proposal),并選出一個法定集合(通常為全體成員集合)，將議案廣播給法定集合成員。

3)一致性表決：參與表決的Follower節(jié)點根據(jù)接收到的議案內(nèi)容進行投票(Vote)，并將投票發(fā)送給Leader。

4)提交：Leader節(jié)點統(tǒng)計投票，并將表決結果提交(commit)到整個網(wǎng)絡。

5)讀取：客戶端節(jié)點通過Learner節(jié)點讀取整個網(wǎng)絡的一致性狀態(tài)。

上述傳統(tǒng)主流主從式分布式一致性算法的一般模式中，有兩個問題制約了系統(tǒng)的總體性能上限。

第一個問題為固定Leader節(jié)點的存在：

傳統(tǒng)主從分布式一致性算法中Leader節(jié)點是固定的，且擔負了過多職責：包括廣播議案、統(tǒng)計投票、決出決議、消息分發(fā)等在內(nèi)，隨著網(wǎng)絡規(guī)模擴大，Leader節(jié)點承擔了數(shù)倍于普通節(jié)點的流量，這對Leader節(jié)點的計算性能和網(wǎng)絡接口帶寬提出了巨大的要求；并且Leader節(jié)點一旦崩潰，集群需要重新進入選主過程，直至Leader上線，集群都會保持無服務狀態(tài)，引發(fā)流量震蕩。這些嚴重制約了傳統(tǒng)主從分布式一致性算法網(wǎng)絡規(guī)模和系統(tǒng)吞吐量上限，這些缺陷在開源系統(tǒng)Zookeeper的應用中表現(xiàn)明顯。

第二個問題為法定集約束的存在：

傳統(tǒng)分布式一致性算法，無論基于P2P模型還是主從模型，都存在必須要求半數(shù)以上節(jié)點存活并參加一致性表決的強約束，也稱法定集約束。這是由于從集合論的角度，不可能存在兩個多數(shù)派成員集合同時投票贊成兩個不同議案，因此從數(shù)學角度確保一致性算法的正確性，這顯著制約了算法的失效容忍性上限。

1.3 Yac分布式一致性算法的相應改進

Yac分布式系統(tǒng)針對上述傳統(tǒng)主流分布式算法中存在的問題提出了改良方法。

對于第一個問題，Yac算法不采用固定Leader節(jié)點，而采用特定的策略動態(tài)生成決策成員集合，該集合在集群成員節(jié)點中隨時域動態(tài)遷移，形成統(tǒng)計負載均衡，作為臨時負載中心的Leader角色也采用共識機制隨上述集合的產(chǎn)生動態(tài)生成。

對于第二個問題，Yac算法放棄采用傳統(tǒng)分布式一致性算法中關于半數(shù)以上成員節(jié)點組成法定集參加表決的強約束，而在特定時間片內(nèi)由映射的角色成員集合參與一致性表決。這破壞了Paxos算法已經(jīng)提供的，對分布式一致性算法正確性的數(shù)學證明，本文建立了一種名為日志鏈的機制，結合算法安全性約束來重新確保Yac分布式一致性算法的正確性。

Yac分布式一致性算法中重新劃分了三種角色，分別為：

1)Leader。臨時Leader節(jié)點，由時域要素計算產(chǎn)生，統(tǒng)計來自一致性表決成員關于某項議案的投票結果，并生成一致性決議通知全網(wǎng)。

2)Elector。臨時的一致性表決參與者，由時域要素計算生成特定時間段內(nèi)的法定一致性表決成員集表決團中的成員，可以針對某項議案進行投票。

3)Follower。普通節(jié)點，執(zhí)行請求與議案的廣播操作，學習Leader節(jié)點的一致性決議。

下面分步闡述表決團和Leader的產(chǎn)生機制，以及如何通過日志鏈機制在有限表決模型下確保一致性決議的唯一性。

1.4 表決團和Leader的生成策略

Yac分布式一致性算法采用哈希方法生成與時間域映射的表決團成員集合。

對于表決團的大小，可以在大于3及小于集群節(jié)點總數(shù)m范圍內(nèi)的奇數(shù)中任意選取。

定義哈希函數(shù)VGen(time_param)，將時域參數(shù)epoch散列映射至上述鍵值對序列的鍵空間中，計算時域要素映射時間段內(nèi)表決團成員集。

1.5 日志鏈機制

日志鏈機制的引入來源于對算法正確性的要求。本文分兩步確保Yac分布式一致性算法的正確性：

1)單次一致性表決正確性：對于單次一致性表決，集群不產(chǎn)生或僅產(chǎn)生唯一一個表決結果。

2)累積一致性表決正確性：經(jīng)過多輪表決后，集群能且僅能確定唯一一個表決結果序列。

針對單次一致性表決正確性，傳統(tǒng)分布式系統(tǒng)采用集合論約束證明正確性；Yac算法由于特殊的表決團生成策略，對于同一個時域參數(shù)epoch，僅可能生成唯一一個表決團，并且在表決團內(nèi)遵循法定集表決約束，因此同樣可以證明正確性。

而針對累積一致性表決的正確性，則通過日志鏈機制來保證。

已知集群中任意一次表決生效產(chǎn)生的集群狀態(tài)變更都可以采用二元組〈epochi，proposali〉唯一描述，其中epochi為時域參數(shù)，proposali為表決的議案。采用遞歸哈希思想，以第五代消息摘要算法(Message Digest algorithm 5th, MD5)對歷史狀態(tài)變更記錄計算累積摘要，生成鏈式數(shù)據(jù)結構Log Chain，如圖2所示。

圖2 Log Chain數(shù)據(jù)模型

Log Chain保存了數(shù)據(jù)狀態(tài)變更路徑，形成可追溯的集群一致性狀態(tài)變更歷史軌跡，對于鏈中每個Log Entry節(jié)點，都存儲本次狀態(tài)變更記錄及上一個Log Entry的MD5值，這不但包括了對上一次狀態(tài)變更結果的確認，同時還隱式校驗了Log Chain上之前所有狀態(tài)變更記錄的完整性。因此，Log Chain之間可以通過對鏈尾Log Entry節(jié)點的一次比較，檢驗出歷史上所有可能出現(xiàn)過得版本分歧。并且，后面還將說明，Log Chain中所有可能出現(xiàn)的版本分支都是等長的，分支版本與主版本合并算法的復雜度等價于求取分支版本與主版本的最長公共前綴算法，具有線性復雜度。

1.6 安全性約束

為確保算法安全性，即中間不含寫操作的情形下，向集群任意節(jié)點發(fā)起的任意讀請求序列讀取到的狀態(tài)值序列都一致，Yac定義了下列安全性約束：

約束1 如果一個節(jié)點支持一個決議，那么本時間片內(nèi)不再支持任何其他決議。

約束2 表決團是原子的，當且僅當半數(shù)以上的成員支持一項決議，該決議才獲得通過。

約束3 一個時間片內(nèi)僅執(zhí)行一次表決，如果一個時間片內(nèi)，節(jié)點未表決通過或被通知通過一個表決成功的議案，那么節(jié)點生成一個空的Log Entry鏈接到本地Log Chain副本中。

約束4 如果同一時間片內(nèi)，Log Chain的對應Log Entry在集群中同時存在空和非空版本，那么非空Log Entry對應正確的主分支版本。

1.7 算法描述

至此，已可以總結出Yac分布式一致性算法的形式化描述如下。

1)

Algorithm 1: Yac

2)

/*Task for a client*/

3)

Createrequest〈request_id,request_body〉

4)

Sendrequest〈request_id,request_body〉 to serversfrom server_list randomly

5)

Upon not receivingreply〈request_id〉 from serversuntil Δttime

6)

Repeat from step 4)

7)

/*Task for Follower and ALL Server*/

8)

Uponnew_time_slotstart:

9)

Iflast_log_entry_epoch

10)

Appendlog_entry〈last_log_entry_md5,epoch,null,md5〉 Intolog_chain

11)

Setcurrent_epoch++

12)

Letelector_group= VGen(current_epoch)

13)

Letleader=elector_group[0]

14)

Ifthis==leaderThen

15)

Switch to Leader

16)

Else IfthisInelector_groupThen

17)

Switch to Elector

18)

Else

19)

Switch to Follower

20)

Resetcommitted=false,pre_vote_request_id=null

21)

Upon receivingcommit〈epoch,request〉:

22)

AssertcommitIs Validated

23)

Appendlog_entry〈last_log_entry_md5,epoch,request,md5〉 Intolog_chain

24)

Upon receivingrequest〈request_id,request_body〉 from Client c:

25)

Letelector_group=VGen(current_epoch)

26)

Multicastdisseminated_request toelector_group

27)

/*Task for a Elector*/

28)

Upon receivingdisseminated_request〈request_id,

request_body〉

29)

Ifpre_vote_request_id==null Orrequest_id<

pre_vote_request_idThen

30)

Return false

31)

Letelector_group= VGen(current_epoch)

32)

Letleader=elector_group[0]

33)

Sendvote〈current_epoch,disseminated_request〉 Toleader

34)

pre_vote_request_id=request_id

35)

/*Task for a Leader*/

36)

Upon receivingvote〈epoch,request〉

37)

Ifepoch

38)

Return false

39)

Else

40)

Setvote_counter[request_id] ++

41)

Setvote_cache[request_id] =request_body

42)

Ifvote_counter[request_id] >e/2 Then

43)

BroadCastcommit〈epoch,request〉

44)

Letcommitted=true

1.8 節(jié)點崩潰恢復策略

Yac分布式一致性算法可以采用簡單的崩潰恢復策略，當節(jié)點發(fā)生故障后并重新恢復后，首先計算當前epoch，并計算上一個epoch所映射的表決團成員集合，向它們發(fā)送請求同步廣播，將本地Log Chain合并到集群主版本。

1.9 成員變更

Yac分布式一致性算法的將成員變更操作視為分布式一致性決策問題，并保持系統(tǒng)內(nèi)全局狀態(tài)一致。

初始成員集合采用靜態(tài)加載配置文件方式獲取。系統(tǒng)運行時態(tài)，由管理端提出成員變更請求，接入節(jié)點生成成員變更議案，提交當前epoch映射的表決團表決，表決結果由當前Leader廣播至一致性網(wǎng)絡。

1.10 CAP分析

針對可用性(A)指標，傳統(tǒng)的分布式一致性算法，在超過半數(shù)的成員失效時系統(tǒng)就不能正常工作，這是基于法定集的強約束。Yac分布式一致性算法在半數(shù)以上表決團節(jié)點存活時可以提供一致性服務，因此具備比傳統(tǒng)分布式一致性算法更寬的工作區(qū)間。

根據(jù)CAP理論[15]，分區(qū)容忍性(P)與分區(qū)一致性(C)相互沖突， Yac分布式一致性算法嚴格強調(diào)分區(qū)一致性(C)，在分區(qū)容忍性(P)上作出妥協(xié)。

當網(wǎng)絡發(fā)生分區(qū)時，相互隔離的多個分區(qū)無法同時提供服務，因此一定不會產(chǎn)生沖突的值。這是因為表決團是原子的，任一時間片內(nèi)存在且至多存在一個分區(qū)能夠產(chǎn)生具備多數(shù)派的表決團。當分區(qū)恢復聯(lián)通時，借助Log Chain的遞歸Hash特性，任意兩個節(jié)點可在常數(shù)時間內(nèi)檢測出Log Chain之間的版本分歧，只要從樹形日志鏈的根節(jié)點起始進行寬度優(yōu)先遍歷(Breadth First Search, BFS)，遞歸剪除祖先節(jié)點決議為NULL的分支，則可快速將樹形日志鏈重新修整成單一的主鏈，恢復集群的一致性。

1.11 正確性證明

分布式集群狀態(tài)一致等同于各成員節(jié)點的副本日志一致。證明算法正確性，只需證明各成員節(jié)點副本Log Chain之間不會產(chǎn)生無法合并的分支版本。

首先依次證明三個命題：

命題1 各成員節(jié)點副本Log Chain的長度相等。

證明 根據(jù)安全性約束3，每一個時間片內(nèi)，日志鏈產(chǎn)生且至多產(chǎn)生一個空或非空Log Entry節(jié)點，在系統(tǒng)初始化后，各成員節(jié)點經(jīng)歷相同的時間偏序，因此副本Log Chain之間長度相等。

命題2 同一時間片內(nèi)不可能產(chǎn)生兩個決議內(nèi)容不同的非空Log Entry。

證明 采用反證法。假定時間片tk內(nèi)生成了兩個決議內(nèi)容不同的Log Entry，則tk時間片所映射的表決團必定存在兩個多數(shù)派同時支持了不同的提案，而已知任意兩個多數(shù)派存在交集，一定存在節(jié)點在tk時間片內(nèi)支持兩個不同決議，這與安全性約束1矛盾，命題2得證。

命題3 任意時間片都映射一個唯一合法的Log Entry版本。

證明 根據(jù)命題2，任意時間片tk內(nèi)各副本Log Chain所生成的Log Entry僅存在三種情況：①僅存在空Log Entry；②僅存在決議值相同的非空Log Entry；③既存在空Log Entry，也存在決議值相同的非空Log Entry；又根據(jù)安全性約束4，情況①可合并至空Log Entry，情況②③可合并至值唯一的非空Log Entry，因此得證。

綜合上述三個命題的證明，分布式集群中各成員節(jié)點副本Log Chain可以確保版本唯一，由此可以保證分布式集群成員節(jié)點間日志版本一致，進而確保分布式集群狀態(tài)一致。

2 實驗與分析

本文采用Java語言實現(xiàn)了Yac算法，采用RPC作為底層通信技術，開展實驗。為了對比與主流分布式一致性算法的性能差異，本文同時也對Zookeeper開源分布式一致性基礎服務進行了對比測試。課題組采用三臺Xeon E7-8830+64 GB RAM及1 000 M交換機組成的硬件平臺，基于Xen-Server構建的私有云，并在云上部署Docker容器構建實驗集群。分別設計測試負載生成客戶端，對Yac算法集群，生成對測試狀態(tài)變量的隨機四則運算操作并校驗正確性；對Zookeeper算法集群，向ZTree空間中固定路徑中寫入隨機整型變量。為實現(xiàn)可控測試負載，采用Sleep系統(tǒng)調(diào)用動態(tài)調(diào)節(jié)測試請求的生成速率。通過對比實驗，分別從負載均衡指標、失效容忍性、吞吐量與時延特性三個方面對兩種算法進行比較。實驗中的參數(shù)配置上，采用變量m表征集群節(jié)點總數(shù)，采用變量e表征Yac算法表決團大小。

2.1 負載均衡指標

1)均方差指標

2)單峰指標

其中:均方差指標衡量集群總體負載均衡度，單峰指標用來衡量集群的單點負載集中效應。

圖3、圖4和表1展現(xiàn)了不同集群配置下的兩種算法負載均衡方差指標、單峰指標的對比。其中圖3與圖4中Zookeeper指標變化曲面均與表決團大小無關。由表1可以看出，在集群規(guī)模較小時，如m=15時，Yac算法的負載均衡方差指標較Zookeepr最少低0.2%，隨著集群規(guī)模擴大，Yac的算法的負載均衡方差指標優(yōu)于Zookeeper，m=65時，Yac算法的方差指標至少較Zookeeper高出4.94%；另一方面，對于負載均衡單峰指標，Yac算法顯著優(yōu)于Zookeeper，在集群較小，在m=15且e=7時，Yac算法單峰指標就較Zookeeper高出22.34%，隨著集群規(guī)模擴大，Zookeeper的Leader節(jié)點負載急劇上升；m=65且e=7時，Yac算法的單峰指標已經(jīng)比Zookeeper高出31.3%，顯示出Yac算法統(tǒng)計負載均衡特型在抑制單點負載集中效應上具有明顯優(yōu)勢。

圖3 兩種算法在不同集群配置下的均方差指標比較

圖4 兩種算法在不同集群配置下的單峰指標比較

表1 兩種算法在不同集群配置下負載均衡指標比較

2.2 可用性及失效容忍性

可用性指標IA=(S/R)×100%是統(tǒng)計單位時間片內(nèi)分布式服務可用率的指標，其中S及R分別是單位時間片內(nèi)請求執(zhí)行成功數(shù)以及請求發(fā)起總數(shù)。

通過殺死Docker容器節(jié)點進程的方式，可以模擬分布式集群中節(jié)點崩潰失效事件。Yac算法的失效容忍性與表決團在集群中占比有關，本文依此對Yac算法在不同集群配置、節(jié)點崩潰變化情形下可用性指標及失效容忍性能進行了評估，并與Zookeeper進行了對比分析。

圖5和表2展現(xiàn)了兩種算法在不同集群配置可用性指標變化的對比。圖5中Zookeeper指標變化曲面與表決團在集群中占比無關。由圖5和表2可知：Zookeeper在集群節(jié)點崩潰率小于50%時，可用性指標穩(wěn)定維持在100%；當節(jié)點崩潰率到達50%以上時，集群停止工作，呈階躍特性。

與之相反，Yac算法用性指標表現(xiàn)出與節(jié)點崩潰率的負相關關系。當表決團在集群中占比20%時，節(jié)點崩潰率由10%升高50%過程中，可用性指標由91.56%降低至73.3%；但重點在節(jié)點崩潰率超過50%時，算法仍正常工作，甚至在80%節(jié)點崩潰時，Yac算法可用性仍能保持在35.62%左右，能提供有限服務，在失效容忍上表現(xiàn)了比Zookeeper更大的節(jié)點失效容忍度。當表決團在集群中占比達60%時，算法在相同節(jié)點崩潰率上表現(xiàn)出較表決團在集群中占比20%情形時更高的可用性指標，但失效容忍范圍開始收窄，節(jié)點崩潰率到達60%時僅表現(xiàn)出11.23%的可用性指標。當表決團在集群中占比達100%時，算法失效容忍范圍開始收窄，且可用性指標隨崩潰率變化趨勢近似于Zookeeper表現(xiàn)出的階躍曲線，這與圖5中變現(xiàn)的規(guī)律一致?？芍?，Yac算法可用性表現(xiàn)與表決團在集群中占比呈負相關；表決團在集群中占比為100%時，Yac可用性最差，但此時也與Zookeeper擁有近似失效容忍度及可用性。

圖5 兩種算法在不同集群配置及節(jié)點崩潰率下可用性指標比較

表2 兩種算法在不同集群配置下的可用性指標比較

2.3 時延與吞吐量性能對比分析

時延及吞吐量是分布式一致性算法的重要性能指標，本文在不同集群配置及不同測試負載下對Yac算法與Zookeeper的相關指標進行對比分析。為獲取正確實驗結果，所有Docker容器均綁定CPU核并配置資源限額。

圖6與表3展現(xiàn)了兩種算法在不同集群配置及不同測試負載下的請求處理時延。

圖6 兩種算法在不同集群配置及寫測試負載下請求平均處理時延

其中表3枚舉了不同集群配置及測試負載下兩種算法請求平均處理時延的采樣，圖6(a)與圖6(b)則分別針對不同集群規(guī)模下兩種算法請求平均處理時延隨測試負載變化趨勢進行了可視化分析。從表3中的數(shù)據(jù)可知，在Yac算法測試負載在12×103req/s以下而Zookeeper測試負載在10×103req/s以下時，兩種算法都擁有相對平穩(wěn)的請求處理時延，其中Yac算法的時延采樣均值約為73.74 ms，Zookeeper算法的時延采樣均值約為61.48 ms，Yac算法的請求平均處理時延比Zookeeper高約12.26 ms。隨測試負載增加，算法集群均逐漸達到性能瓶頸，到達瓶頸的節(jié)點因無法及時處理消息和求而導致集群請求處理時延增加。

表3兩種算法在不同負載及集群配置下請求平均處理時延比較ms

Tab. 3 Comparison of average request processing delay of two algorithms under different test load and cluster configuration ms

負載/(103req·s-1)參數(shù)mYace=5e=7e=9Zookeeper359101112131573．3872．5973．4261．273572．6473．2173．3162．361574．1773．5673．4461．883573．6773．3474．0161．251573．3374．7173．7661．363572．2973．3074．3160．741573．1574．6674．1285．583574．2473．9674．5390．711573．9474．2774．15132．943574．3673．6874．83146．5315101．62102．33101．74217．2835109．37108．01110．98241．1415152．61156．44157．68321．8735163．43162．52162．19350．63

圖6(a)與圖6(b)中，Yac算法在測試負載增加到12×103req/s及以上時，時延曲線到達拐點，平均時延開始急劇上升，可認為相應集群配置下Yac算法的吞吐量上限在11×103～12×103req/s；同時，Zookeeper在測試負載到達10×103req/s以上時，時延曲線到達拐點，可認為其吞吐量上限在9×103～10×103req/s。以上分析表明，相同集群規(guī)模下Yac算法在未到達性能瓶頸時請求平均處理時延略高于Zookeeper，但在吞吐量上限比Zookeeper更高。

3 結語

本文通過分析主流靜態(tài)拓撲主從模型分布式一致性算法存在的問題，提出一種具備統(tǒng)計負載均衡特性及高失效容忍性的分布式一致性算法Yac。通過動態(tài)生成表決成員集合改善負載均衡性能，采用共識機制生成的時分切換的Leader節(jié)點抑制單點負載集中效應，采用作用域更小的法定集約束使算法具備更高的失效容忍性，同時通過日志鏈機制重新確保算法安全性。實驗結果表明，同等集群規(guī)模下，Yac算法在解決單點負載集中問題上顯著優(yōu)于Zookeeper，并擁有更高的吞吐量上限；隨表決團在總體成員集中占比降低，Yac算法可擁有比Zookeeper更廣的失效容忍區(qū)間。由于相對更復雜的拓撲及更多的消息傳遞跳數(shù)，Yac算法具有比Zookeeper更高的請求平均處理時延，下一步工作主要是對本文算法進行改進和優(yōu)化，改善時延性能及降低算法復雜度。

References)

[1] LAMPORT L, SHOSTAK R, PEASE M. The byzantine generals problem [J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.

[2] LAMPORT L. The part-time parliament [J]. ACM Transactions on Computer Systems, 1998, 16(2): 133-169.

[3] LAMPORT L. Paxos made simple [J]. ACM SIGACT News, 2016, 32(4): 18-25.

[4] LAMPORT L. Fast paxos[J]. Distributed Computing, 2006, 19(2): 79-103.

[5] ZHAO W. Fast paxos made easy: theory and implementation [J]. International Journal of Distributed Systems and Technologies, 2015, 6(1): 15-33.

[6] BURROWS M. The chubby lock service for loosely-coupled distributed systems [C]// Proceedings of the 7th Symposium on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2006: 335-350.

[7] ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm [C]// Proceedings of the 2014 USENIX Annual Technical Conference. Berkeley, CA: USENIX Association, 2014: 305-320.

[8] JUNQUEIRA F, REED B. ZooKeeper: Distributed Process Coordination [M]. Sebastopol, CA: O’Reilly, 2013: 3-42.

[9] JUNQUEIRA F P, REED B C, SERAFINI M. Zab: high-performance broadcast for primary-backup systems [C]// Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks. Piscataway, NJ: IEEE, 2011: 245-256.

[10] HUNT P, KONAR M, JUNQUEIRA F P, et al. ZooKeeper: wait-free coordination for internet-scale systems [C]// Proceedings of the 2010 USENIX Annual Technical Conference. Berkeley, CA: USENIX Association, 2010: 11.

[11] MARANDI P J, PRIMI M, SCHIPER N, et al. Ring Paxos: a high-throughput atomic broadcast protocol [EB/OL]. [2016- 12- 09]. http://www.microsoft.com/en-us/research/wp-content/uploads/2016/06/RingPaxos.pdf.

[12] KUMAR V, AGARWAL A. HT-Paxos: high throughput state-machine replication protocol for large clustered data centers [EB/OL]. [2017- 01- 04]. http://xueshu.baidu.com/s?wd=paperuri%3A%28b741b6286079366bc618b67547ec68f0%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fde.arxiv.org%2Fpdf%2F1407.1237&ie=utf-8&sc_us=11391865198545652672.

[13] BIELY M, MILOSEVIC Z, SANTOS N, et al. S-Paxos: offloading the leader for high throughput state machine replication [C]// Proceedings of the 2012 IEEE 31st Symposium on Reliable Distributed Systems. Washington, DC: IEEE Computer Society, 2012: 111-120.

[14] MORARU I, ANDERSEN D G, KAMINSKY M. Paxos quorum leases: fast reads without sacrificing writes [C]// Proceedings of the ACM Symposium on Cloud Computing. New York: ACM, 2014: 1-13.

[15] GILBERT S, LYNCH N. Perspectives on the CAP theorem [J]. Computer, 2012, 45(2): 30-36.

[16] 許子燦,吳榮泉.基于消息傳遞的Paxos算法研究[J].計算機工程,2011,37(21):287-290.(XU Z C, WU R Q. Research on Paxos algorithm based on messages passing [J]. Computer Engineering, 2011, 37(21): 287-290.)

[17] 楊春明,杜炯.一種基于Paxos算法的高可用分布式鎖服務系統(tǒng)[J].西南科技大學學報,2014,29(2):60-65.(YANG C M, DU J. A highly available distributed lock service system based Paxos algorithm [J]. Journal of Southwest University of Science and Technology, 2014, 29(2): 60-65.)

Yac:yetanotherdistributedconsensusalgorithm

ZHANG Jian1, WANG Yang1*, LIU Dandan2

(1.SchoolofComputerScience,WuhanUniversity,WuhanHubei430072,China;2.StateKeyLabofSoftwareEngineering,WuhanUniversity,WuhanHubei430072,China)

There are serious load imbalance and single point performance bottleneck effect in the traditional static topology leader-based distributed consensus algorithm, and the algorithm is unable to work properly when the number of breakdown nodes is larger than 50% of the cluster size. To solve the above problems, a distributed consensus algorithm (Yac) based on dynamic topology and limited voting was proposed. The algorithm dynamically generated the membership subset and Leader nodes to participate in the consensus voting, and varied with time, achieving statistical load balance. With removal of the strong constraints of all the majority of members to participate in voting, the algorithm had a higher degree of failure tolerance. The security constraints of the algorithm were reestablished by the log chain mechanism, and the correctness of the algorithm was proved. The experimental results show that the load concentration effect of single point in the improved algorithm is significantly lower than that of the mainstream static topology leader-based distributed consensus algorithm Zookeeper. The improved algorithm has better fault tolerance than Zookeeper in most cases and maintains the same as Zookeeper in the worst case. Under the same cluster size, the improved algorithm has higher throughput upper limit than Zookeeper.

distributed consensus; Paxos algorithm; voting group; log chain; load balance

2017- 03- 13;

2017- 05- 07。

國家自然科學基金資助項目(61103216)。

張健(1976—)，男，安徽銅陵人，教授，博士，主要研究方向：云計算、物聯(lián)網(wǎng)； 汪洋(1990—)，男，湖北武漢人，碩士研究生，主要研究方向：云計算、分布式計算； 劉丹丹(1980—)，女，湖北武漢人，副教授，博士，CCF會員，主要研究方向：無線網(wǎng)絡、移動計算。

1001- 9081(2017)09- 2524- 07

10.11772/j.issn.1001- 9081.2017.09.2524

TP301.6

A

This work is partially supported by the National Natural Science Foundation of China (61103216).

ZHANGJian, born in 1976, Ph. D., professor. His research interests include cloud computing, Internet of things.

WANGYang, born in 1990, M. S. candidate. His research interests include cloud computing, distributed computing.

LIUDandan, born in 1980, Ph. D., associate professor. Her research interests include wireless network, mobile computing.