張 基，謝在鵬，毛鶯池，徐媛媛，朱曉瑞，李博文

（河海大學(xué)計(jì)算機(jī)與信息學(xué)院，南京 211100）

0 概述

容錯(cuò)技術(shù)是分布式系統(tǒng)的重要組成部分，確保了發(fā)生故障時(shí)的系統(tǒng)連續(xù)性和功能性［1］。近年來(lái)，隨著分布式系統(tǒng)規(guī)模的不斷擴(kuò)大、分布式架構(gòu)和計(jì)算復(fù)雜度的日益增加［2］以及廉價(jià)商業(yè)硬件的廣泛使用，使得計(jì)算任務(wù)發(fā)生故障的概率持續(xù)增加，例如在Google 生產(chǎn)集群中平均每天會(huì)有數(shù)十個(gè)節(jié)點(diǎn)發(fā)生故障［3］。瞬態(tài)故障尤其是軟錯(cuò)誤［4］會(huì)導(dǎo)致計(jì)算機(jī)系統(tǒng)的異常行為，這類(lèi)故障會(huì)損壞數(shù)據(jù)的完整性，引起分布式節(jié)點(diǎn)的計(jì)算失效［4-5］。在一些大型分布式系統(tǒng)中平均每天會(huì)有1%～2%的節(jié)點(diǎn)發(fā)生失效［6］，因此容錯(cuò)技術(shù)可在保證部分節(jié)點(diǎn)失效的情況下，使分布式系統(tǒng)仍能繼續(xù)運(yùn)行且得到正確結(jié)果［7-9］。在基于MapReduce［10］的分布式計(jì)算中，數(shù)據(jù)洗牌（shuffle）階段較高的通信開(kāi)銷(xiāo)嚴(yán)重影響了分布式計(jì)算性能，例如在Facebook 的Hadoop 集群中，33%的任務(wù)執(zhí)行總時(shí)間用于數(shù)據(jù)洗牌階段［11］。針對(duì)基于MapReduce 分布式計(jì)算框架的多副本容錯(cuò)算法通信開(kāi)銷(xiāo)較大的問(wèn)題，本文提出一種結(jié)合分布式編碼計(jì)算的容錯(cuò)算法CTMR，使基于MapReduce 的分布式計(jì)算系統(tǒng)在發(fā)生瞬態(tài)故障的情況下仍能繼續(xù)運(yùn)行且得到正確結(jié)果，同時(shí)能有效降低容錯(cuò)計(jì)算過(guò)程中的通信開(kāi)銷(xiāo)。

1 相關(guān)工作

基于多副本冗余技術(shù)［12-15］的分布式容錯(cuò)算法于1962年由IBM提出，但在現(xiàn)代分布式系統(tǒng)中仍然被廣泛采用［16-17］。這類(lèi)算法的主要思想是：在含有n個(gè)節(jié)點(diǎn)的分布式系統(tǒng)中，如果每個(gè)節(jié)點(diǎn)要容忍f個(gè)故障，那么該節(jié)點(diǎn)可以使用（f+1）個(gè)獨(dú)立的副本，顯然存儲(chǔ)和運(yùn)行這些副本需要消耗大量的空間和其他資源。此外，由于多副本之間的一致性使得基于副本冗余技術(shù)的容錯(cuò)算法更易于設(shè)計(jì)，同時(shí)副本的維護(hù)和恢復(fù)成本較低。三模冗余（Triple Modular Redundancy，TMR）是軟件和硬件系統(tǒng)中常用的基于副本的容錯(cuò)算法［18-19］，使用3 個(gè)實(shí)現(xiàn)功能相同的模塊同時(shí)進(jìn)行操作，系統(tǒng)使用投票機(jī)制選出最終輸出。由于3 個(gè)模塊相互獨(dú)立，同時(shí)有2 個(gè)模塊出現(xiàn)相同錯(cuò)誤的概率非常小，因此可大幅提高系統(tǒng)可靠性，掩蔽故障模塊的錯(cuò)誤。文獻(xiàn)［20］提出一種優(yōu)化的副本虛擬機(jī)放置算法，動(dòng)態(tài)設(shè)置k個(gè)副本虛擬機(jī)并將其作為備份來(lái)提高云服務(wù)的可靠性。在基于MapReduce的分布式計(jì)算［10］中，每個(gè)任務(wù)被分配到多個(gè)節(jié)點(diǎn)以確保在某個(gè)節(jié)點(diǎn)出現(xiàn)故障的情況下系統(tǒng)仍能繼續(xù)運(yùn)行。文獻(xiàn)［21］提出面向分布式流體系結(jié)構(gòu)的多副本容錯(cuò)技術(shù)，該技術(shù)通過(guò)比較多個(gè)副本的數(shù)據(jù)進(jìn)行檢錯(cuò)，采取三取二的邏輯判斷方式選擇多數(shù)相同的結(jié)果，并對(duì)錯(cuò)誤的數(shù)據(jù)進(jìn)行糾錯(cuò)以防止錯(cuò)誤進(jìn)一步傳播，但當(dāng)數(shù)據(jù)量較大時(shí)通信開(kāi)銷(xiāo)會(huì)成為容錯(cuò)過(guò)程中的性能瓶頸。文獻(xiàn)［18］提出一種兩階段三模冗余（two-stage TMR）容錯(cuò)算法，該算法將每個(gè)任務(wù)備份3 份并分配給3 個(gè)節(jié)點(diǎn)，先指定2 個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算，當(dāng)2 個(gè)節(jié)點(diǎn)執(zhí)行完畢后進(jìn)行結(jié)果比較，如果比較結(jié)果不一致，則指定第3 個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算，最終通過(guò)投票選出多數(shù)一致的結(jié)果。該算法在故障率較低的情況下可以有效節(jié)省系統(tǒng)資源，但當(dāng)錯(cuò)誤率較高時(shí)，重新執(zhí)行第3 份備份任務(wù)不僅增加了計(jì)算工作量并且大幅降低了系統(tǒng)實(shí)時(shí)性能。

通信開(kāi)銷(xiāo)是基于MapReduce 的分布式計(jì)算中的主要性能瓶頸，這是因?yàn)樵跀?shù)據(jù)洗牌階段交換大量中間結(jié)果。為解決該問(wèn)題，文獻(xiàn)［7］提出分布式編碼計(jì)算方法，將map 任務(wù)重復(fù)布置到多個(gè)不同的節(jié)點(diǎn)，通過(guò)增加計(jì)算冗余創(chuàng)建同時(shí)滿(mǎn)足多個(gè)服務(wù)器數(shù)據(jù)需求的編碼數(shù)據(jù)來(lái)降低通信開(kāi)銷(xiāo)。在一個(gè)分布式集群中，node1包含數(shù)據(jù)集{v1，v2}，node2包含數(shù)據(jù)集{v2，v3}，node3包含數(shù)據(jù)集{v1，v3}。node1將本地?cái)?shù)據(jù)集編碼結(jié)果c1（c1=v1⊕v2，⊕表示異或）運(yùn)用廣播發(fā)出。node2接收到編碼數(shù)據(jù)后利用本地?cái)?shù)據(jù)v2即可將收到的編碼結(jié)果解碼得到v1，其中v1=v2⊕c1。同理，node3通過(guò)解碼即可得到v2。在該過(guò)程中，通過(guò)將node1與node2和node3冗余存儲(chǔ)的數(shù)據(jù){v1，v2}進(jìn)行編碼來(lái)創(chuàng)建同時(shí)滿(mǎn)足node2和node3的編碼數(shù)據(jù)，而無(wú)需將v1、v2分別發(fā)送至node2和node3，從而降低通信開(kāi)銷(xiāo)。然而，目前尚未發(fā)現(xiàn)能有效降低分布式容錯(cuò)計(jì)算中通信開(kāi)銷(xiāo)的相關(guān)討論和研究。為降低現(xiàn)有分布式計(jì)算使用多副本容錯(cuò)過(guò)程中產(chǎn)生的通信開(kāi)銷(xiāo)，本文基于副本冗余和分布式編碼計(jì)算技術(shù)，提出一種CTMR 容錯(cuò)算法。

2 CTMR 容錯(cuò)算法

2.1 CTMR 模型

假設(shè)在分布式集群中有N個(gè)節(jié)點(diǎn)，標(biāo)記為{node1，node2，…，noden}，N個(gè)節(jié)點(diǎn)協(xié)作完成一個(gè)計(jì)算任務(wù)。當(dāng)前集群待處理的數(shù)據(jù)量為M，每份數(shù)據(jù)的冗余度為r，將該數(shù)據(jù)集分配到當(dāng)前集群的N個(gè)map節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)量為M?。map 節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行計(jì)算，將產(chǎn)生的中間結(jié)果使用分布式編碼計(jì)算得到的編碼數(shù)據(jù)發(fā)送到Q個(gè)reduce 節(jié)點(diǎn)，其中編碼壓縮比為c，即將c個(gè)中間結(jié)果通過(guò)編碼得到一個(gè)編碼中間結(jié)果。因此，每個(gè)reduce 節(jié)點(diǎn)將收到其余（N?Q）個(gè)map 節(jié)點(diǎn)的編碼中間結(jié)果，如式（1）所示：

reduce 節(jié)點(diǎn)對(duì)接收到的編碼中間結(jié)果進(jìn)行解碼，通過(guò)校驗(yàn)識(shí)別發(fā)生故障的編碼數(shù)據(jù)包，并利用冗余中間結(jié)果得到M份數(shù)據(jù)最終正確的計(jì)算結(jié)果，如式（2）所示：

因?yàn)楸疚乃惴S機(jī)選取Q個(gè)reduce 節(jié)點(diǎn)均能夠完成所有中間結(jié)果的驗(yàn)證，所以節(jié)點(diǎn)應(yīng)該包含編碼數(shù)據(jù)所有可能的中間結(jié)果，如式（3）所示：

由于TMR 的低復(fù)雜度及高可靠性，因此本文選取r=3、c=2，聯(lián)立式（1）～式（3）解得N=6、M=8，即在含有6 個(gè)節(jié)點(diǎn)的分布式集群中，將待處理的數(shù)據(jù)分成8 個(gè)獨(dú)立的子數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊冗余3 份，每個(gè)節(jié)點(diǎn)包含4 份數(shù)據(jù)，使用故障檢測(cè)與恢復(fù)算法進(jìn)行容錯(cuò)計(jì)算，同時(shí)降低計(jì)算過(guò)程中的通信開(kāi)銷(xiāo)。

在包含N個(gè)節(jié)點(diǎn)的分布式集群中，將每6 個(gè)節(jié)點(diǎn)分為1 個(gè)子集群，共有組子集群。各個(gè)子集群之間相互獨(dú)立，而每個(gè)子集群內(nèi)的節(jié)點(diǎn)在邏輯上是相鄰的，在物理上可以是分散的。將計(jì)算任務(wù)分配到個(gè)子集群上，各個(gè)子集群并行計(jì)算。每個(gè)子集群的數(shù)據(jù)量為，同時(shí)將子集群的數(shù)據(jù)集劃分為8 個(gè)獨(dú)立的子數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊復(fù)制3 份。每個(gè)子集群使用如圖1 所示的CTMR 模型進(jìn)行表示，其中立方體的每個(gè)面表示1 個(gè)節(jié)點(diǎn)，每個(gè)面的4 個(gè)頂點(diǎn)代表當(dāng)前節(jié)點(diǎn)包含的4 個(gè)數(shù)據(jù)集。立方體中的每條棱代表與該棱鄰接的兩個(gè)面所表示的節(jié)點(diǎn)公共冗余數(shù)據(jù)集，而每個(gè)面所表示的節(jié)點(diǎn)數(shù)據(jù)集用Bi表示，例如node1本地?cái)?shù)據(jù)集為B1={b1，b2，b3，b4}。在模型中每個(gè)頂點(diǎn)與3 個(gè)面鄰接，即每份數(shù)據(jù)冗余3 份并存放至3 個(gè)節(jié)點(diǎn)上，例如b3分別存放至node1、node3和node5上。nodek在map 階段對(duì)本地?cái)?shù)據(jù)集的每一個(gè)數(shù)據(jù)塊bi執(zhí)行map 函數(shù)F(bi)得到相應(yīng)的中間結(jié)果集。

圖1 CTMR 模型Fig.1 CTMR model

兩個(gè)鄰近節(jié)點(diǎn)nodek和nodem冗余存儲(chǔ)的數(shù)據(jù)集用Rk，m表示，例如R1，3={b1，b3}。將nodek與nodem冗余存儲(chǔ)的數(shù)據(jù)Rk，m所對(duì)應(yīng)的中間結(jié)果使用分布式編碼計(jì)算得到編碼結(jié)果uk，m，如式（4）所示：

其中，⊕表示異或操作。nodek在reduce 階段的函數(shù)為H(v1，v2，…，vi)=rk。

2.2 CTMR 故障檢測(cè)與恢復(fù)

將一個(gè)包含N個(gè)節(jié)點(diǎn)的分布式集群劃分為個(gè)子集群，各個(gè)子集群并行計(jì)算的同時(shí)進(jìn)行檢錯(cuò)和糾錯(cuò)。每個(gè)子集群中的6 個(gè)節(jié)點(diǎn)分別表示為nodek、nodem、nodes、noden、nodep、nodeq，其中nodek和nodem、nodes和noden、nodep和nodeq分別為CTMR模型中的3 組對(duì)面。可以看出，任意一組對(duì)面中的兩個(gè)節(jié)點(diǎn)的本地?cái)?shù)據(jù)集的交集為空，但并集是當(dāng)前子集群數(shù)據(jù)集的全集。每個(gè)節(jié)點(diǎn)map 階段通過(guò)函數(shù)F(bi)計(jì)算本地?cái)?shù)據(jù)集得到相應(yīng)的中間結(jié)果集，例如nodek通過(guò)計(jì)算本地?cái)?shù)據(jù)集Bk得到相應(yīng)的中間結(jié)果集。

隨機(jī)選取一個(gè)節(jié)點(diǎn)nodek，將其在CTMR 模型中的對(duì)面節(jié)點(diǎn)nodem作為校驗(yàn)節(jié)點(diǎn)。nodes、noden、nodep、nodeq為與nodek相鄰的節(jié)點(diǎn)，將其與nodek冗余存儲(chǔ)的數(shù)據(jù)集Rs，k、Rn，k、Rp，k、Rq，k所對(duì)應(yīng)的中間結(jié)果進(jìn)行編碼，得到相應(yīng)的編碼結(jié)果us，k、un，k、up，k、uq，k。將對(duì)應(yīng)的編碼結(jié)果發(fā)送給nodek，然后在nodem上執(zhí)行相同過(guò)程。數(shù)據(jù)塊分發(fā)與中間結(jié)果編碼的偽代碼如算法1 所示。

算法1數(shù)據(jù)分發(fā)與中間結(jié)果編碼算法

nodek和nodem通過(guò)比較接收到的編碼數(shù)據(jù)包與當(dāng)前節(jié)點(diǎn)產(chǎn)生的中間結(jié)果來(lái)驗(yàn)證數(shù)據(jù)的正確性。若式（5）兩個(gè)等式中的任意一個(gè)成立，則表明nodek本地?cái)?shù)據(jù)集的運(yùn)算結(jié)果正確，通過(guò)reduce 函數(shù)可得到當(dāng)前節(jié)點(diǎn)運(yùn)算結(jié)果。

若式（5）中兩個(gè)等式均不成立，而式（6）兩個(gè)等式中的任意一個(gè)成立，則假設(shè)us，k驗(yàn)證成功，即us，k=

若式（7）成立，則表明nodek本地有數(shù)據(jù)計(jì)算錯(cuò)誤，但是收到的其他節(jié)點(diǎn)的編碼數(shù)據(jù)包正確。此時(shí)，通過(guò)reduce 函數(shù)得到當(dāng)前節(jié)點(diǎn)數(shù)據(jù)集的正確結(jié)果為

若us，k、un，k、up，k、uq，k全部驗(yàn)證失敗，則重新選取兩個(gè)校驗(yàn)節(jié)點(diǎn)進(jìn)行上述操作。當(dāng)nodek與nodem均能通過(guò)驗(yàn)證得到正確運(yùn)算結(jié)果時(shí)，利用reduce 函數(shù)便可得到CTMR 模型的最終結(jié)果r=H(rk，rm)。故障檢測(cè)與恢復(fù)的偽代碼如算法2 所示。

算法2故障檢測(cè)與恢復(fù)算法

在隨機(jī)選取子集群中的兩個(gè)reduce 節(jié)點(diǎn)后，每次TMR 算法驗(yàn)證都需發(fā)送16 份中間結(jié)果給reduce 節(jié)點(diǎn)，假設(shè)每個(gè)中間結(jié)果大小為τ，那么每個(gè)CTMR 模型在驗(yàn)證過(guò)程中需要發(fā)送16τ的數(shù)據(jù)。在含有N個(gè)節(jié)點(diǎn)的分布式集群中，共需發(fā)送的數(shù)據(jù)量。two-stage TMR 算法在最優(yōu)情況下只需發(fā)送8τ的數(shù)據(jù)量，即最初選擇的兩個(gè)副本對(duì)應(yīng)的中間結(jié)果一致，在最壞情況下所有數(shù)據(jù)最初選擇的兩個(gè)副本的對(duì)應(yīng)中間結(jié)果均不一致，因此需要第3 個(gè)副本進(jìn)行多數(shù)一致表決，共需發(fā)送16τ的數(shù)據(jù)量。在CTMR 算法中，每個(gè)節(jié)點(diǎn)使用分布式預(yù)編碼本地計(jì)算的中間結(jié)果減少通信開(kāi)銷(xiāo)。在最優(yōu)情況下，每個(gè)模型只需8τ的通信量，即模型最初選擇兩個(gè)校驗(yàn)點(diǎn)即可得到正確結(jié)果。在最壞情況下，每個(gè)模型需要16τ的通信量，即在最初選擇兩個(gè)校驗(yàn)節(jié)點(diǎn)后不能得到正確結(jié)果，需更換節(jié)點(diǎn)重新做校驗(yàn)。因此，在包含N個(gè)節(jié)點(diǎn)的分布式集群中，共需發(fā)送的數(shù)據(jù)量。CTMR算法與TMR算法的通信開(kāi)銷(xiāo)之比如式（8）所示，即CTMR算法總能在小于等于TMR 算法通信量的情況下得到正確結(jié)果。

2.3 算法實(shí)例

如圖2 所示，在含有N=6 個(gè)節(jié)點(diǎn)的分布式集群中，輸入系統(tǒng)數(shù)據(jù)量為M=8，將該數(shù)據(jù)集劃分為8 個(gè)數(shù)據(jù)塊{b1，b2，…，b8}。每個(gè)節(jié)點(diǎn)在map 階段計(jì)算本地?cái)?shù)據(jù)集產(chǎn)生相應(yīng)的中間結(jié)果集，例如node2在map 階段針對(duì)本地?cái)?shù)據(jù)集B2={b1，b2，b5，b6}計(jì)算得到相應(yīng)的中間結(jié)果集?？紤]node1在map 階段由于瞬態(tài)故障導(dǎo)致計(jì)算錯(cuò)誤情況下的容錯(cuò)過(guò)程，首先選取node1和node6作為校驗(yàn)節(jié)點(diǎn)，子集群中其余4 個(gè)節(jié)點(diǎn)為node2、node3、node4、node5，將4 個(gè)節(jié)點(diǎn)與node1冗余存儲(chǔ)的數(shù)據(jù)集R2，1、R3，1、R4，1、R5，1所對(duì)應(yīng)的中間結(jié)果分別使用分布式編碼計(jì)算得到相應(yīng)的編碼結(jié)果u2，1、u3，1、u4，1、u5，1發(fā)送給node1，將4 個(gè)節(jié)點(diǎn)與node6冗余存儲(chǔ)的數(shù)據(jù)集R2，6、R3，6、R4，6、R5，6所對(duì)應(yīng)的中間結(jié)果分別使用分布式編碼計(jì)算得到相應(yīng)的編碼結(jié)果u2，6、u3，6、u4，6、u5，6發(fā)送給node6，其中，。

圖2 node1中 和 錯(cuò)誤時(shí)的容錯(cuò)過(guò)程Fig.2 Fault-tolerant process of and incorrect in the node1

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)方案

本文分布式計(jì)算的測(cè)試程序?yàn)門(mén)erasort［22］，CTMR算法的評(píng)價(jià)指標(biāo)為任務(wù)執(zhí)行總時(shí)間、map 和shuffle 階段執(zhí)行時(shí)間以及平均故障修復(fù)時(shí)間（Mean Time to Repair，MTTR），對(duì)比算法為T(mén)MR 和two-stage TMR算法。

實(shí)驗(yàn)使用多臺(tái)虛擬機(jī)搭建的分布式集群，包括1個(gè)管理節(jié)點(diǎn)和6 個(gè)工作節(jié)點(diǎn)，節(jié)點(diǎn)間的帶寬為100 Mb/s。實(shí)驗(yàn)中動(dòng)態(tài)選擇發(fā)生故障的節(jié)點(diǎn)個(gè)數(shù)，隨機(jī)選取節(jié)點(diǎn)并修改其對(duì)應(yīng)數(shù)據(jù)塊數(shù)值實(shí)現(xiàn)故障注入。假設(shè)系統(tǒng)在單位時(shí)間內(nèi)的故障發(fā)生概率服從泊松分布p(x=k)=，即在單位時(shí)間內(nèi)出現(xiàn)k個(gè)故障的概率為p(k)，本文中λ的取值為2。因此，在滿(mǎn)足泊松分布的條件下，假設(shè)該分布式系統(tǒng)隨機(jī)產(chǎn)生k個(gè)故障。如果各個(gè)故障之間相互獨(dú)立，那么在連續(xù)運(yùn)行的分布式系統(tǒng)中，當(dāng)產(chǎn)生k個(gè)故障時(shí)的無(wú)故障運(yùn)行時(shí)間為tk，則系統(tǒng)平均無(wú)故障運(yùn)行時(shí)間如式（9）所示：

故障修復(fù)時(shí)間為檢測(cè)到故障直至故障修復(fù)的時(shí)間，假設(shè)有k個(gè)故障時(shí)的故障修復(fù)時(shí)間為θk，則平均故障修復(fù)時(shí)間如式（10）所示：

實(shí)驗(yàn)中每個(gè)MapReduce任務(wù)可以分為map、shuffle、check 和reduce 這4 個(gè)階段。在map 階段，管理節(jié)點(diǎn)按照CTMR 算法要求將用戶(hù)輸入數(shù)據(jù)分發(fā)給6 個(gè)工作節(jié)點(diǎn)，同時(shí)指定2 個(gè)校驗(yàn)節(jié)點(diǎn)。每個(gè)工作節(jié)點(diǎn)對(duì)本地?cái)?shù)據(jù)集進(jìn)行排序，得到相應(yīng)的中間結(jié)果集。在shuffle 階段，每個(gè)節(jié)點(diǎn)將其中間結(jié)果編碼，發(fā)送給之前指定的校驗(yàn)節(jié)點(diǎn)。在check 階段，校驗(yàn)節(jié)點(diǎn)將收到的數(shù)據(jù)包進(jìn)行故障檢測(cè)和恢復(fù)，校驗(yàn)成功后得到相應(yīng)結(jié)果。在reduce階段，管理節(jié)點(diǎn)收到校驗(yàn)節(jié)點(diǎn)發(fā)送來(lái)的部分reduce 計(jì)算結(jié)果后執(zhí)行reduce 函數(shù)得到最終輸出結(jié)果。任務(wù)執(zhí)行總時(shí)間Ttotal如式（11）所示：

3.2 實(shí)驗(yàn)結(jié)果

圖3 給出了CTMR、two-stage TMR 以及TMR 算法的任務(wù)執(zhí)行總時(shí)間對(duì)比結(jié)果。可以看出，CTMR算法能有效降低分布式計(jì)算的任務(wù)執(zhí)行總時(shí)間。當(dāng)故障個(gè)數(shù)較少時(shí)，CTMR 算法的執(zhí)行效率遠(yuǎn)高于另外兩種算法。隨著故障個(gè)數(shù)的不斷增加，two-stage TMR 算法由于需要重新執(zhí)行第3 個(gè)副本做驗(yàn)證，而CTMR 算法則需要更換節(jié)點(diǎn)做驗(yàn)證，在該過(guò)程中需要重新發(fā)送編碼數(shù)據(jù)包，因此這兩種算法的任務(wù)執(zhí)行總時(shí)間也會(huì)隨之增加。

圖3 任務(wù)執(zhí)行總時(shí)間對(duì)比Fig.3 Comparison of total task execution time

圖4 給出了CTMR、two-stage TMR 以及TMR 算法在map 階段的執(zhí)行時(shí)間對(duì)比結(jié)果。可以看出，隨著故障個(gè)數(shù)的增加，two-stage TMR 算法由于第1 次投票選擇的2 個(gè)副本對(duì)應(yīng)的中間結(jié)果不同，因此需要進(jìn)行第2 次投票。這時(shí)會(huì)選擇第3 個(gè)副本并執(zhí)行map 任務(wù)，因此map 階段所需時(shí)間隨故障個(gè)數(shù)的增加不斷增加。TMR 和CTMR 算法由于最初都要對(duì)3 個(gè)副本執(zhí)行map 任務(wù)，因此map 階段的執(zhí)行時(shí)間基本保持不變。

圖4 map 階段執(zhí)行時(shí)間對(duì)比Fig.4 Comparison of the execution time in the map phase

圖5 給出了CTMR、two-stage TMR 以及TMR 算法在shuffle 階段的執(zhí)行時(shí)間對(duì)比結(jié)果。可以看出，CTMR 算法在shuffle 階段所需時(shí)間明顯低于TMR算法，并且相比two-stage TMR 算法有一定程度的減少。本文將shuffle 階段的執(zhí)行時(shí)間作為通信開(kāi)銷(xiāo)的衡量指標(biāo)，當(dāng)系統(tǒng)在單位時(shí)間內(nèi)的故障發(fā)生概率服從泊松分布時(shí)，可以計(jì)算得出發(fā)生k個(gè)故障的概率為p（k），本文中λ的取值為2。根據(jù)式（9）可計(jì)算出CTMR、two-stage TMR 以及TMR 算法在shuffle 階段的執(zhí)行時(shí)間分別為1.90 s、2.21 s 和3.22 s。因此，CTMR 算法在shuffle 階段的執(zhí)行時(shí)間相比TMR 算法降低了41.0%，相比two-stage TMR 算法降低了14.0%。

圖6 給出了CTMR、two-stage TMR 以及TMR 算法在check 階段的執(zhí)行時(shí)間對(duì)比結(jié)果?？梢钥闯?，CTMR 算法在一定的故障個(gè)數(shù)范圍內(nèi)，故障修復(fù)效率明顯優(yōu)于TMR 與two-stage TMR 算法。隨著故障個(gè)數(shù)的不斷增加，TMR 和two-stage TMR 算法均需要對(duì)所有副本進(jìn)行第3 次投票，而CTMR 算法也需要更換節(jié)點(diǎn)進(jìn)行校驗(yàn)，因此3 種算法的故障恢復(fù)時(shí)間不斷增加并最終趨于一致。

圖6 check 階段執(zhí)行時(shí)間對(duì)比Fig.6 Comparison of the execution time in the check phase

當(dāng)系統(tǒng)在單位時(shí)間內(nèi)發(fā)生故障的概率服從泊松分布時(shí)，根據(jù)式（9）分別計(jì)算出CTMR、two-stage TMR 以及TMR 算法在tatal 階段的任務(wù)執(zhí)行總時(shí)間以及map、shuffle 和check 階段的任務(wù)執(zhí)行時(shí)間，結(jié)果如圖7 所示?？梢钥闯?，CTMR 算法的任務(wù)執(zhí)行總時(shí)間相比TMR 算法降低了25.8%，相比two-stage TMR 算法降低了13.2%。根據(jù)式（10），CTMR 算法的平均故障修復(fù)時(shí)間相比TMR 算法降低了18.3%，相比two-stage TMR 算法降低了26.2%。

圖7 故障發(fā)生概率服從泊松分布時(shí)3 種算法的執(zhí)行時(shí)間對(duì)比Fig.7 Comparison of the execution time of the three algorithms when the probability of failure obeys the Poisson distribution

4 結(jié)束語(yǔ)

為降低MapReduce 分布式計(jì)算中容錯(cuò)算法的通信開(kāi)銷(xiāo)，本文結(jié)合副本冗余技術(shù)和分布式編碼計(jì)算技術(shù)，提出一種新的容錯(cuò)算法。實(shí)驗(yàn)結(jié)果表明，CTMR 算法在完成容錯(cuò)計(jì)算的同時(shí)，相比TMR 和two-stage TMR 容錯(cuò)算法，平均降低了41.0% 和14.0%的shuffle 階段的通信開(kāi)銷(xiāo)以及18.3%和26.2%的平均故障修復(fù)時(shí)間，并且提高了分布式系統(tǒng)的可用性和可靠性。但由于本文中的副本數(shù)量固定為3具有一定的局限性，因此下一步將根據(jù)分布式系統(tǒng)的故障發(fā)生概率，通過(guò)動(dòng)態(tài)調(diào)整副本數(shù)量以增強(qiáng)容錯(cuò)算法的靈活性。