李 鑫，孫 蓉,2*，劉景偉

(1.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2.華僑大學(xué) 廈門(mén)市移動(dòng)多媒體通信重點(diǎn)實(shí)驗(yàn)室，福建 廈門(mén) 361021)

0 引言

在當(dāng)前云計(jì)算時(shí)代，全球流量快速增長(zhǎng)，互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、移動(dòng)終端、安全監(jiān)控和金融等領(lǐng)域的數(shù)據(jù)量呈現(xiàn)出“井噴式”增長(zhǎng)態(tài)勢(shì)。存儲(chǔ)在云服務(wù)器中數(shù)據(jù)的增長(zhǎng)速率甚至超越了摩爾法則，云存儲(chǔ)系統(tǒng)成為云計(jì)算的關(guān)鍵組成部分之一。數(shù)據(jù)的飛速增長(zhǎng)對(duì)存儲(chǔ)系統(tǒng)的性能和擴(kuò)展性提出了更苛刻的挑戰(zhàn)。傳統(tǒng)的存儲(chǔ)系統(tǒng)采用集中式的方法存儲(chǔ)數(shù)據(jù)，使得數(shù)據(jù)的安全性和可靠性均不能保證，不能滿足大數(shù)據(jù)應(yīng)用的需求。分布式存儲(chǔ)系統(tǒng)以其巨大的存儲(chǔ)潛力、高可靠性和易擴(kuò)展性等優(yōu)點(diǎn)成為大數(shù)據(jù)存儲(chǔ)的關(guān)鍵系統(tǒng)并被推廣應(yīng)用到降低存儲(chǔ)負(fù)荷、疏通網(wǎng)絡(luò)擁塞等業(yè)務(wù)領(lǐng)域上，且其以高吞吐量和高可用性成為云存儲(chǔ)中的主要系統(tǒng)。目前Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System,HDFS)作為谷歌文件管理系統(tǒng)(GFS)[1]的開(kāi)源實(shí)現(xiàn)已成為最主流的分布式系統(tǒng)，它被應(yīng)用于許多大型企業(yè)，如Facebook，Yahoo，eBay，Amazon等。

為了應(yīng)對(duì)海量數(shù)據(jù)的存儲(chǔ)需求，該類(lèi)存儲(chǔ)系統(tǒng)的規(guī)模往往非常龐大，一般包含幾千到幾萬(wàn)個(gè)存儲(chǔ)節(jié)點(diǎn)不等。早在2014年，中國(guó)互聯(lián)網(wǎng)百度公司單個(gè)集群的節(jié)點(diǎn)數(shù)量就超過(guò)了10 000[2]。近兩年，騰訊云的分布式調(diào)度系統(tǒng)VStation管理和調(diào)度單集群的節(jié)點(diǎn)數(shù)量可達(dá)100 000。然而數(shù)量龐大的節(jié)點(diǎn)集群經(jīng)常會(huì)產(chǎn)生如電源損壞、系統(tǒng)維修及網(wǎng)絡(luò)中斷等故障致使節(jié)點(diǎn)失效頻發(fā)。據(jù)一些大型分布式存儲(chǔ)系統(tǒng)的統(tǒng)計(jì)數(shù)據(jù)表明，平均每天都會(huì)有2% 左右的節(jié)點(diǎn)發(fā)生故障[3]。在過(guò)去一年中，迅速發(fā)展的云計(jì)算市場(chǎng)不斷涌出如谷歌云、亞馬遜AWS、微軟Azure及阿里云等主流云服務(wù)器大型宕機(jī)事件[4]。

由此可見(jiàn)，全球的云服務(wù)器發(fā)生故障導(dǎo)致數(shù)據(jù)丟失的情況時(shí)有發(fā)生。顯然，能夠可靠存儲(chǔ)數(shù)據(jù)并有效修復(fù)失效數(shù)據(jù)的容錯(cuò)技術(shù)對(duì)分布式存儲(chǔ)系統(tǒng)的重要性不言而喻。因此如何及時(shí)有效地修復(fù)失效節(jié)點(diǎn)，確保數(shù)據(jù)能被正常地讀取和下載就顯得非常重要。據(jù)統(tǒng)計(jì)，在一個(gè)有3 000個(gè)節(jié)點(diǎn)的Facebook集群中，每天通常至少會(huì)觸發(fā)20次節(jié)點(diǎn)修復(fù)機(jī)制。具有節(jié)點(diǎn)修復(fù)能力的數(shù)據(jù)容錯(cuò)技術(shù)是通過(guò)引入冗余的方式來(lái)保證分布式存儲(chǔ)系統(tǒng)的可靠性，存儲(chǔ)系統(tǒng)能夠容忍一定數(shù)量的失效節(jié)點(diǎn)，即提高了系統(tǒng)的數(shù)據(jù)容錯(cuò)能力。

為了保證用戶訪問(wèn)數(shù)據(jù)的可靠性、維持分布式存儲(chǔ)系統(tǒng)的容錯(cuò)性，需要及時(shí)修復(fù)失效節(jié)點(diǎn)。良好的容錯(cuò)技術(shù)要求存儲(chǔ)系統(tǒng)具有低的冗余開(kāi)銷(xiāo)、低的節(jié)點(diǎn)修復(fù)帶寬、低的編譯碼復(fù)雜度等特點(diǎn)。如何降低失效節(jié)點(diǎn)的修復(fù)帶寬、降低磁盤(pán)I/O、降低存儲(chǔ)系統(tǒng)編譯碼的復(fù)雜度、提高系統(tǒng)的存儲(chǔ)效率成為分布式存儲(chǔ)中研究的熱門(mén)方向，因此，能夠有效彌補(bǔ)多副本機(jī)制和MDS碼不足的分布式存儲(chǔ)編碼應(yīng)運(yùn)而生。

1 傳統(tǒng)的存儲(chǔ)容錯(cuò)

傳統(tǒng)最常見(jiàn)也是最早的存儲(chǔ)容錯(cuò)是多副本機(jī)制和MDS碼。通常，多副本機(jī)制引入冗余簡(jiǎn)單，但其存儲(chǔ)負(fù)載很大，存儲(chǔ)效率非常低,如Google文件系統(tǒng)和Hadoop文件系統(tǒng)等。傳統(tǒng)的最大距離可分(Maximum Distance Separable，MDS)碼結(jié)構(gòu)可以實(shí)現(xiàn)分布式存儲(chǔ)編碼，比如里德-所羅門(mén)(Reed-Solomon，RS)碼，以及Google Colossus，HDFS Raid，Microsoft Azure，Ocean Store等。其存儲(chǔ)成本更低，但是其擁有更高的修復(fù)成本和訪問(wèn)延遲，而且沒(méi)有考慮存儲(chǔ)開(kāi)銷(xiāo)、磁盤(pán)I/O開(kāi)銷(xiāo)等，因此并不適合用于大規(guī)模分布式存儲(chǔ)系統(tǒng)。

1.1 多副本機(jī)制

多副本機(jī)制是產(chǎn)生冗余最基本的方式。為了彌補(bǔ)數(shù)據(jù)失效帶來(lái)的損失，確保存儲(chǔ)系統(tǒng)中數(shù)據(jù)的完整性，將數(shù)據(jù)的副本存儲(chǔ)在多個(gè)磁盤(pán)中，只要有一個(gè)副本可用，就可以容忍數(shù)據(jù)丟失。如圖1所示。如果數(shù)據(jù)以最常見(jiàn)的3副本方式存儲(chǔ)，那么原始數(shù)據(jù)會(huì)被復(fù)制到3個(gè)磁盤(pán)上，因此任何1個(gè)磁盤(pán)故障都可以通過(guò)剩余2個(gè)磁盤(pán)中任意1個(gè)來(lái)修復(fù)。顯然，該3副本機(jī)制有效的存儲(chǔ)空間理論上不超過(guò)總存儲(chǔ)空間的1/3，多副本機(jī)制顯著降低了存儲(chǔ)效率。

圖1 3副本機(jī)制

1.2 MDS碼

如果系統(tǒng)編碼設(shè)計(jì)的目標(biāo)是在不犧牲磁盤(pán)故障容忍度的前提下最大化存儲(chǔ)效率，那么存儲(chǔ)系統(tǒng)采用MDS碼來(lái)儲(chǔ)存數(shù)據(jù)，因?yàn)樗梢詾橄嗤拇鎯?chǔ)開(kāi)銷(xiāo)提供更高的可靠性。也就是說(shuō)MDS碼是一種能提供最優(yōu)儲(chǔ)存與可靠性權(quán)衡的糾刪碼。在一個(gè)分布式存儲(chǔ)方案中，原始文件首先被分成k個(gè)數(shù)據(jù)塊，接著它們編碼生成n個(gè)編碼塊并存儲(chǔ)在n個(gè)節(jié)點(diǎn)中。訪問(wèn)任意l(l≥k)個(gè)節(jié)點(diǎn)，通過(guò)糾刪碼的譯碼就可恢復(fù)出原始文件，如果l=k，該碼就滿足MDS性質(zhì)，最多能夠容忍(n-k)個(gè)節(jié)點(diǎn)的失效。如圖2所示，原始文件被MDS碼編碼生成5個(gè)數(shù)據(jù)塊并放置到5個(gè)磁盤(pán)中。任意某個(gè)磁盤(pán)損壞，都能通過(guò)訪問(wèn)其他4個(gè)幸存磁盤(pán)中的3個(gè)來(lái)修復(fù)。

圖2 (5,3)MDS碼修復(fù)失效磁盤(pán)

MDS碼的3個(gè)主要缺點(diǎn)阻礙了它在分布式存儲(chǔ)系統(tǒng)中的推廣。首先，為了讀取或?qū)懭霐?shù)據(jù)，系統(tǒng)需要對(duì)數(shù)據(jù)進(jìn)行編譯碼，由于CPU限制會(huì)導(dǎo)致高延遲和低吞吐量。根據(jù)調(diào)研，即使Facebook存儲(chǔ)系統(tǒng)的集群中用MDS碼只編碼一半數(shù)據(jù)，修復(fù)流量也會(huì)使集群中的網(wǎng)絡(luò)鏈路接近飽和。其次，MDS碼修復(fù)失效節(jié)點(diǎn)時(shí)必須訪問(wèn)多個(gè)編碼塊，而訪問(wèn)的這些編碼塊足以得到所有的原始數(shù)據(jù)，這樣的修復(fù)代價(jià)也太大了。最后，托管在云存儲(chǔ)中的應(yīng)用程序?qū)Υ疟P(pán)I/O性能很敏感，且由于大多數(shù)數(shù)據(jù)中心引入鏈路超額配置；因此帶寬始終是數(shù)據(jù)中心內(nèi)的有限資源，使得MDS碼的節(jié)點(diǎn)修復(fù)在帶寬開(kāi)銷(xiāo)和磁盤(pán)I/O開(kāi)銷(xiāo)方面都非常昂貴。

圖3 采用MDS編碼的分布式儲(chǔ)存模型

2 分布式存儲(chǔ)編碼及性能比較

為了降低修復(fù)故障節(jié)點(diǎn)的帶寬開(kāi)銷(xiāo)，有幾種分布式存儲(chǔ)編碼，即再生碼[6](Regenerating Codes，RGC)、局部可修復(fù)碼[7](Locally Repairable Codes，LRC)和MDS陣列碼等被提出來(lái)，它們都有各自的優(yōu)缺點(diǎn)。如RGC和LRC的修復(fù)帶寬較小，但由于它們?cè)谛迯?fù)過(guò)程中有大量的矩陣運(yùn)算，計(jì)算復(fù)雜度很高，因此構(gòu)造過(guò)程非常復(fù)雜；Piggybacking編碼的研究還處在起步階段，有很多理論和實(shí)際應(yīng)用還不太完善；MDS陣列碼如EVENODD，B-code，X-code，RDP，STAR，Zigzag碼等，它們的編譯碼過(guò)程基本都是構(gòu)建在低階域的簡(jiǎn)單運(yùn)算之上，復(fù)雜度低。但受限于陣列碼的構(gòu)造過(guò)程，它們所設(shè)計(jì)的冗余節(jié)點(diǎn)很少，導(dǎo)致其容錯(cuò)能力有限，修復(fù)能力一般都比較弱，修復(fù)效率較低。目前，在容錯(cuò)技術(shù)中存儲(chǔ)和修復(fù)性能更勝一籌的分布式存儲(chǔ)編碼主要有 3類(lèi)：① 注重存儲(chǔ)與修復(fù)開(kāi)銷(xiāo)平衡的RGC；② 面向優(yōu)化磁盤(pán)I/O開(kāi)銷(xiāo)的LRC，③ 不改變系統(tǒng)節(jié)點(diǎn)分布結(jié)構(gòu)的Piggybacking編碼。

2.1 RGC

為了降低MDS碼的節(jié)點(diǎn)修復(fù)帶寬，Dimakis等人受網(wǎng)絡(luò)編碼的啟發(fā)將編碼數(shù)據(jù)的修復(fù)建模為信息流圖，從而提出了再生碼，其約束條件是維持容忍磁盤(pán)故障的能力[6]?；诖四Ｐ蛠?lái)表征存儲(chǔ)與帶寬之間的最優(yōu)權(quán)衡，即給定磁盤(pán)上存儲(chǔ)的數(shù)據(jù)量大小，可以得到修復(fù)過(guò)程中需要傳輸數(shù)據(jù)量的最優(yōu)下界。

2.1.1 RGC原理

在信息流圖中，所有的服務(wù)器可以分為源節(jié)點(diǎn)、存儲(chǔ)節(jié)點(diǎn)和數(shù)據(jù)收集器，其中源節(jié)點(diǎn)表示數(shù)據(jù)對(duì)象產(chǎn)生的服務(wù)器。圖4為RGC信息流圖。

圖4 RGC信息流圖

MDS碼節(jié)點(diǎn)的數(shù)據(jù)恢復(fù)是要新生節(jié)點(diǎn)接收來(lái)自服務(wù)器(數(shù)據(jù)提供者)的k個(gè)數(shù)據(jù)塊后，在新生節(jié)點(diǎn)上進(jìn)行編碼產(chǎn)生節(jié)點(diǎn)新數(shù)據(jù)。但再生碼是在數(shù)據(jù)提供者和新節(jié)點(diǎn)上都能進(jìn)行編碼，即數(shù)據(jù)提供者(存儲(chǔ)節(jié)點(diǎn))有不止一個(gè)編碼段。當(dāng)需要修復(fù)節(jié)點(diǎn)時(shí)，提供者先發(fā)送自己編碼段的線性組合，新節(jié)點(diǎn)將接收到的編碼段再次編碼重構(gòu)新的節(jié)點(diǎn)。如圖5所示，假定任意2個(gè)磁盤(pán)都足以恢復(fù)原始數(shù)據(jù)的MDS碼，即k=2，每個(gè)磁盤(pán)存儲(chǔ)一個(gè)包含2個(gè)編碼段的編碼塊。對(duì)MDS碼而言，恢復(fù)故障磁盤(pán)至少需要給新磁盤(pán)發(fā)送2個(gè)編碼塊(4個(gè)編碼段)。但數(shù)據(jù)經(jīng)提供者編碼后再發(fā)送給新磁盤(pán)的數(shù)據(jù)量可減少至1.5個(gè)編碼塊(3個(gè)編碼段)，這樣就能減小數(shù)據(jù)的傳輸量，降低25%的帶寬消耗。

圖5 RGC基本原理圖

Dimakis等人利用信息流圖計(jì)算最小割界得到失效節(jié)點(diǎn)修復(fù)帶寬的下限曲線，再生碼就是在存儲(chǔ)開(kāi)銷(xiāo)α和修復(fù)帶寬γ的最優(yōu)曲線上。該曲線上存在最小存儲(chǔ)和最小修復(fù)帶寬這2個(gè)極值點(diǎn)。達(dá)到存儲(chǔ)最小的極值點(diǎn)的編碼稱為最小存儲(chǔ)再生碼(Minimum Storage Regenerating Codes，MSR)[7]，達(dá)到修復(fù)帶寬最小極值點(diǎn)的編碼稱為最小帶寬再生碼(Minimum Bandwidth Regenerating Codes，MBR)[8]。

MSR的節(jié)點(diǎn)存儲(chǔ)大小和節(jié)點(diǎn)修復(fù)帶寬可以表示為：

MDS碼的存儲(chǔ)開(kāi)銷(xiāo)最小，而MSR碼節(jié)點(diǎn)的儲(chǔ)存開(kāi)銷(xiāo)就等于傳統(tǒng)MDS碼的節(jié)點(diǎn)大小，因此可以被當(dāng)做MDS碼。當(dāng)d=n-1時(shí)，則上式變?yōu)椋?/p>

當(dāng)n趨于無(wú)窮大時(shí)，其修復(fù)帶寬等于一個(gè)編碼塊大小，但MDS碼的修復(fù)帶寬為k倍的編碼塊大小，因此MSR碼節(jié)省很大的修復(fù)帶寬。

MBR的節(jié)點(diǎn)存儲(chǔ)大小和節(jié)點(diǎn)修復(fù)開(kāi)銷(xiāo)可以表示為：

當(dāng)d=n-1時(shí)，則上式變?yōu)椋?/p>

從上式可以看出，MBR碼的節(jié)點(diǎn)存儲(chǔ)大小和修復(fù)開(kāi)銷(xiāo)一致，存儲(chǔ)和修復(fù)帶寬大小比一個(gè)編碼塊稍微大些，因此其修復(fù)帶寬非常小。

2.1.2 RGC發(fā)展現(xiàn)狀

分布式存儲(chǔ)網(wǎng)絡(luò)中一個(gè)重要的性能指標(biāo)是它的安全性。RGC除了數(shù)據(jù)存儲(chǔ)容錯(cuò)外，還可以應(yīng)用在信息安全上。它是一種用于提供數(shù)據(jù)可靠性和可用性的分布式存儲(chǔ)網(wǎng)絡(luò)編碼，能實(shí)現(xiàn)高效的節(jié)點(diǎn)修復(fù)和信息安全[9]。其中竊聽(tīng)者可能獲得存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)，也可能訪問(wèn)在修復(fù)某些節(jié)點(diǎn)期間下載的數(shù)據(jù)(如果竊聽(tīng)者發(fā)現(xiàn)添加到系統(tǒng)中的新節(jié)點(diǎn)替換了失效的節(jié)點(diǎn)，那么它就可以訪問(wèn)修復(fù)期間下載的所有數(shù)據(jù)，這嚴(yán)重威脅了數(shù)據(jù)的安全和隱私)。在這種不利環(huán)境下，Dimakis提出了RGC的準(zhǔn)確構(gòu)造從而實(shí)現(xiàn)了信息保密，即在不向任何竊聽(tīng)者透露任何信息的情況下，可以安全存儲(chǔ)并向合法用戶提供最大的數(shù)據(jù)量，同時(shí)得到了一般分布式存儲(chǔ)系統(tǒng)保密容量的上限，并證明了這個(gè)界對(duì)于帶寬受限的系統(tǒng)來(lái)說(shuō)是緊密的，這在點(diǎn)對(duì)點(diǎn)分布式存儲(chǔ)系統(tǒng)中是有用的[10]?？紤]用分散數(shù)據(jù)保護(hù)一個(gè)分布式存儲(chǔ)系統(tǒng)的問(wèn)題，研究了節(jié)點(diǎn)間交互在減少總帶寬方面的作用[11]。當(dāng)節(jié)點(diǎn)相互獨(dú)立，交互是沒(méi)有用的，并且總是存在一個(gè)最優(yōu)的非交互方案。除此之外，RGC在信息安全保密方面也有研究[12]。

RGC按照故障節(jié)點(diǎn)的修復(fù)特點(diǎn)可分為功能性修復(fù)和準(zhǔn)確性修復(fù)。功能性修復(fù)是指恢復(fù)新節(jié)點(diǎn)后使系統(tǒng)仍具有MDS性，以維持對(duì)故障節(jié)點(diǎn)的容忍度，一般的再生碼都是功能性修復(fù)。準(zhǔn)確性修復(fù)是指新生節(jié)點(diǎn)中的數(shù)據(jù)與被修復(fù)失效節(jié)點(diǎn)中的數(shù)據(jù)相同。因此在前期研究基礎(chǔ)上出現(xiàn)了準(zhǔn)確RGC的概念，當(dāng)節(jié)點(diǎn)失效后能進(jìn)行準(zhǔn)確修復(fù)，這意味著系統(tǒng)形式的編碼結(jié)構(gòu)可以結(jié)合準(zhǔn)確重構(gòu)節(jié)點(diǎn)來(lái)實(shí)現(xiàn)與多副本機(jī)制一樣低的訪問(wèn)延遲。常用的方法是干擾對(duì)齊技術(shù)，把不需要的向量對(duì)齊到相同的線性子空間以達(dá)到消除的目的[13]。

目前大多數(shù)關(guān)于RGC的研究都集中在單一節(jié)點(diǎn)的恢復(fù)上，但是在大型分布式存儲(chǔ)系統(tǒng)中同時(shí)看到2個(gè)或更多的節(jié)點(diǎn)故障是很常見(jiàn)的。為了充分利用好修復(fù)多個(gè)故障節(jié)點(diǎn)的契機(jī)，一種協(xié)同修復(fù)機(jī)制應(yīng)運(yùn)而生，即修復(fù)節(jié)點(diǎn)之間可以相互共享數(shù)據(jù)。此類(lèi)RGC被稱為合作RGC[14]，它的出現(xiàn)使得用更低的帶寬來(lái)修復(fù)多個(gè)故障節(jié)點(diǎn)成為可能。

縱然RGC達(dá)到了存儲(chǔ)與帶寬開(kāi)銷(xiāo)之間的最優(yōu)權(quán)衡，但因?yàn)槠湫枰爆嵉臄?shù)學(xué)參數(shù)和復(fù)雜的編碼理論基礎(chǔ)，實(shí)現(xiàn)過(guò)程很難。目前RGC大多在有限域GF(2q)上進(jìn)行多項(xiàng)式運(yùn)算。加法在計(jì)算機(jī)上處理較為簡(jiǎn)單，然而乘法和除法卻相對(duì)復(fù)雜，更有甚者需要用到離散對(duì)數(shù)和查表才能處理。這使得RGC的編譯碼復(fù)雜度很高，因而很難滿足分布式存儲(chǔ)系統(tǒng)對(duì)計(jì)算復(fù)雜度的要求。RGC作為MDS碼的改進(jìn)版，擁有良好的理論基礎(chǔ)，但是現(xiàn)有的絕大部分RGC編譯碼復(fù)雜度很高且碼率低，所以迫切地提出高碼率且編譯碼復(fù)雜度低的RGC，這具有積極的現(xiàn)實(shí)意義。若同時(shí)結(jié)合磁盤(pán)I/O、數(shù)據(jù)存儲(chǔ)安全和網(wǎng)絡(luò)結(jié)構(gòu)等方面構(gòu)造，能進(jìn)一步推廣RGC的應(yīng)用范圍。

2.2 LRC

與通過(guò)犧牲磁盤(pán)I/O開(kāi)銷(xiāo)來(lái)節(jié)省帶寬消耗的RGC不同， LRC具有較少的磁盤(pán)訪問(wèn)數(shù)量。它是通過(guò)強(qiáng)制一個(gè)失效節(jié)點(diǎn)中的數(shù)據(jù)只能通過(guò)某些特定的存儲(chǔ)節(jié)點(diǎn)來(lái)進(jìn)行修復(fù)，從而減少需要讀取和下載的數(shù)據(jù)量來(lái)降低修復(fù)帶寬。雖然這種方式犧牲了對(duì)節(jié)點(diǎn)故障的容忍度(LRC的理論可譯性：能夠修復(fù)信息理論上可譯的故障模式，即LRC不具有MDS性質(zhì))，以犧牲少量存儲(chǔ)開(kāi)銷(xiāo)為代價(jià)(增加了額外的局部校驗(yàn)塊)，但會(huì)顯著降低磁盤(pán)I/O開(kāi)銷(xiāo)。眾所周知，磁盤(pán)I/O開(kāi)銷(xiāo)越大，使用壽命就越短。因此LRC在數(shù)據(jù)容錯(cuò)技術(shù)中的地位不容小覷。

2.2.1 LRC的原理

常規(guī)的RGC修復(fù)故障節(jié)點(diǎn)時(shí)，都需要請(qǐng)求幸存節(jié)點(diǎn)將其數(shù)據(jù)的線性組合發(fā)送給新節(jié)點(diǎn)，即RGC僅僅針對(duì)存儲(chǔ)與修復(fù)開(kāi)銷(xiāo)，而沒(méi)能節(jié)省磁盤(pán)I/O。在修復(fù)故障節(jié)點(diǎn)過(guò)程中，RGC最終從幸存節(jié)點(diǎn)讀取的數(shù)據(jù)量將遠(yuǎn)遠(yuǎn)多于寫(xiě)入新節(jié)點(diǎn)的數(shù)據(jù)量，過(guò)多的磁盤(pán)I/O操作會(huì)嚴(yán)重影響數(shù)據(jù)中心的總體磁盤(pán)I/O性能，使得磁盤(pán)I/O開(kāi)銷(xiāo)成為存儲(chǔ)系統(tǒng)中故障節(jié)點(diǎn)恢復(fù)的一個(gè)主要性能瓶頸[15]。磁盤(pán)I/O開(kāi)銷(xiāo)與修復(fù)故障節(jié)點(diǎn)時(shí)訪問(wèn)的幸存節(jié)點(diǎn)數(shù)目(即局部修復(fù)度)成正比，因此訪問(wèn)的幸存節(jié)點(diǎn)數(shù)越少(局部修復(fù)度越小)，磁盤(pán)I/O開(kāi)銷(xiāo)就越少。需要明確的是，寫(xiě)操作發(fā)生在新節(jié)點(diǎn)上，且寫(xiě)操作的數(shù)據(jù)量等于一個(gè)存儲(chǔ)節(jié)點(diǎn)的大小。由于寫(xiě)操作作為重構(gòu)新節(jié)點(diǎn)的最后一步是不可或缺的，因此在實(shí)際修復(fù)過(guò)程中更關(guān)心的是從幸存節(jié)點(diǎn)中讀取的數(shù)據(jù)量。

MDS碼修復(fù)一個(gè)節(jié)點(diǎn)要求讀取k個(gè)編碼塊。從圖5可以看到，RGC中數(shù)據(jù)提供者的編碼操作不能減少讀的數(shù)據(jù)量，只是減少了數(shù)據(jù)的傳輸量，因?yàn)榘l(fā)送編碼后的數(shù)據(jù)是需要讀取節(jié)點(diǎn)內(nèi)整個(gè)編碼塊(所有編碼段)之后再進(jìn)行編碼才生成的。因此，有2種方法可以降低磁盤(pán)I/O開(kāi)銷(xiāo)。第1種，從幸存節(jié)點(diǎn)中選取特定的編碼段，而位于同一節(jié)點(diǎn)中的其他編碼段因?yàn)闆](méi)有參與編碼就不用讀??；第2種，選取少量的特定節(jié)點(diǎn)作為數(shù)據(jù)提供者而不是任意k個(gè)節(jié)點(diǎn)。特別是，LRC采用的是第2種方法。假定任意3個(gè)節(jié)點(diǎn)都足以得到原始數(shù)據(jù)的MDS碼，即k=3。修復(fù)一個(gè)故障節(jié)點(diǎn)，MDS碼和再生碼需要讀取6個(gè)編碼段，而圖6中卻只需要讀取2個(gè)特定的編碼段，所以能降低磁盤(pán)I/O開(kāi)銷(xiāo)。

圖6 訪問(wèn)特定編碼段(或/和特定節(jié)點(diǎn))來(lái)降低磁盤(pán)I/O開(kāi)銷(xiāo)

LRC之所以能通過(guò)選定特定節(jié)點(diǎn)來(lái)修復(fù)失效節(jié)點(diǎn)是因?yàn)樗灶~外的存儲(chǔ)開(kāi)銷(xiāo)為代價(jià)，任意某個(gè)節(jié)點(diǎn)都可以通過(guò)某些特定的編碼塊進(jìn)行修復(fù)，減少了修復(fù)過(guò)程中連接的節(jié)點(diǎn)數(shù)，也減少了磁盤(pán)I/O開(kāi)銷(xiāo)。雖然LRC具有較好的局部修復(fù)特性，但卻無(wú)法擁有像MSR碼和MBR碼等那樣較低的存儲(chǔ)與修復(fù)開(kāi)銷(xiāo)。目前采用LRC編碼的大型系統(tǒng)主要有Facebook的分布式文件系統(tǒng)HDFS和微軟的Azure[11]。且Azure已廣泛應(yīng)用于微軟內(nèi)部的網(wǎng)絡(luò)搜索、視頻服務(wù)、音樂(lè)游戲及醫(yī)療管理等業(yè)務(wù)。LRC的實(shí)現(xiàn)方法主要包括分層編碼(Hierarchical Codes，HC)和簡(jiǎn)單再生碼(Simple Regenerating Codes，SRC)。HC是將原始文件進(jìn)行編碼(一般采用RS碼)之后，進(jìn)行二次編碼得到額外的局部冗余校驗(yàn)塊。當(dāng)需要恢復(fù)一個(gè)失效節(jié)點(diǎn)時(shí)，通過(guò)訪問(wèn)該故障節(jié)點(diǎn)所在分組內(nèi)的幸存節(jié)點(diǎn)和該組內(nèi)編碼產(chǎn)生的局部校驗(yàn)塊即可，而并不需要像MDS碼那樣訪問(wèn)更多的幸存節(jié)點(diǎn)，因此HC可以降低故障節(jié)點(diǎn)的修復(fù)帶寬和磁盤(pán)I/O操作。Papailiopoulos等人將可糾正多個(gè)錯(cuò)誤的RS碼與簡(jiǎn)單的異或運(yùn)算結(jié)合，構(gòu)造出一類(lèi)LRC，即SRC[16]。該方案通過(guò)訪問(wèn)少量幸存節(jié)點(diǎn)來(lái)修復(fù)單節(jié)點(diǎn)故障，利用特定的放置規(guī)則降低了失效節(jié)點(diǎn)的修復(fù)帶寬。

2.2.2 LRC 的發(fā)展現(xiàn)狀

LRC除了有數(shù)據(jù)容錯(cuò)存儲(chǔ)的應(yīng)用外，國(guó)際上已經(jīng)有學(xué)者開(kāi)始嘗試?yán)肔RC解決分布式存儲(chǔ)中的安全問(wèn)題。2016年，Kumar等人為分布式存儲(chǔ)設(shè)計(jì)了一種可修復(fù)噴泉碼(Repairable Fountain Codes，RFC)，在信息安全理論上提出了針對(duì)存儲(chǔ)節(jié)點(diǎn)的竊聽(tīng)模型，應(yīng)對(duì)通過(guò)失效節(jié)點(diǎn)的修復(fù)來(lái)竊取其他幸存節(jié)點(diǎn)數(shù)據(jù)的威脅[17]。Rawat等人通過(guò)平衡LRC的安全性和修復(fù)度，提出了安全性最佳的局部修復(fù)度結(jié)構(gòu)的編碼方案，可有效抵抗監(jiān)聽(tīng)[18]。在2017年，Kadhe等人又通過(guò)內(nèi)碼和外碼的聯(lián)合設(shè)計(jì)，構(gòu)造了一種廣泛的安全存儲(chǔ)碼方案，同時(shí)考慮了MSR碼和LRC這2種分布式存儲(chǔ)編碼。

目前，學(xué)術(shù)上針對(duì)單個(gè)節(jié)點(diǎn)失效LRC的研究主要集中在以下的構(gòu)造方法中：

① 基于二元LDPC碼的構(gòu)造：2016年，Hao等人闡述了一類(lèi)有著多修復(fù)組的LRC與二元LDPC碼的關(guān)系，提出了用正則LDPC碼去構(gòu)造LRC的方法[19]。2017年，Su等人在上述工作基礎(chǔ)上基于循環(huán)置換矩陣和仿射變換矩陣提出了2種二元LRC的構(gòu)造方法，達(dá)到了距離限[20]。

② 基于聯(lián)合信息可用性構(gòu)造：2017年，Kim等人利用聯(lián)合信息的可用性(任何可譯碼的糾刪符號(hào)集可以從任何一組具有小基數(shù)的多個(gè)不相交符號(hào)集進(jìn)行修復(fù))提出了LRC的2個(gè)Alphabet-Dependent限[21]。

③ 基于圖模型的構(gòu)造：2017年，Kim等人還利用具有r個(gè)頂點(diǎn)和t個(gè)邊的超圖構(gòu)造出了有著(r,t)可用性的二元LRC[22]。此前，他還提出過(guò)2個(gè)具有聯(lián)合修復(fù)度的LRC的獨(dú)立上限，并利用簡(jiǎn)單圖模型設(shè)計(jì)出滿足該獨(dú)立上限的LRC，利用簡(jiǎn)單圖設(shè)計(jì)出具有最佳碼率和聯(lián)合信息修復(fù)度的LRC[23]。

④ 基于平均修復(fù)度的構(gòu)造：LRC的平均修復(fù)度，影響著修復(fù)帶寬的大小、磁盤(pán)I/O的開(kāi)銷(xiāo)。Shahabinejad等人提出了一個(gè)適用于任意LRC的平均修復(fù)度的下限，并設(shè)計(jì)出3種LRC。2017年，他們通過(guò)研究信息塊的最佳平均修復(fù)度，得到了一個(gè)更低的下限[24]。

⑤ 基于Matroid理論的構(gòu)造：Westerb等人給出了擬陣與LRC之間的聯(lián)系，通過(guò)線性的或者一般仿射來(lái)使用這些擬陣結(jié)構(gòu)，可以構(gòu)造新的LRC[25]。Tamo等人也通過(guò)擬陣提出了簡(jiǎn)單準(zhǔn)確的LRC構(gòu)造[26]。

⑥ 基于Rank-Metric碼的構(gòu)造：Silberstein等人基于最大秩距離(Maximum Rank Distance，MRD)Gabidulin碼提出了LRC的構(gòu)造方法[27]，采用串行級(jí)聯(lián)編碼的結(jié)構(gòu)，用MDS碼作為外碼，RGC或LRC作為內(nèi)碼，實(shí)現(xiàn)容錯(cuò)存儲(chǔ)。

2.3 Piggybacking編碼

相比于RGC和LRC，Piggybacking編碼以其較低的計(jì)算復(fù)雜度、設(shè)計(jì)靈活等特點(diǎn)開(kāi)始在數(shù)據(jù)容錯(cuò)技術(shù)中占有一席之地。編碼設(shè)計(jì)完成后，它不改變?cè)邢到y(tǒng)的節(jié)點(diǎn)分布結(jié)構(gòu),不產(chǎn)生額外的存儲(chǔ)負(fù)載、在修復(fù)失效數(shù)據(jù)時(shí)將底層碼的譯碼替代為求解與失效數(shù)據(jù)相關(guān)的Piggyback方程。這樣不僅顯著降低了修復(fù)帶寬，還有效降低了修復(fù)復(fù)雜度，為海量數(shù)據(jù)可靠、高效的存儲(chǔ)提供了強(qiáng)有力的保障。

2.3.1 Piggybacking編碼的原理

2013年Rashmi等人首次提出了Piggybacking框架的概念，且將該框架下構(gòu)造的Piggybacking編碼用來(lái)應(yīng)對(duì)存儲(chǔ)系統(tǒng)中頻發(fā)的故障節(jié)點(diǎn)[28]。他們解釋Piggybacking的含義是將MDS碼作為基本碼，將擴(kuò)展后的MDS碼中某些條帶的數(shù)據(jù)符號(hào)通過(guò)精心設(shè)計(jì)好的Piggyback函數(shù)嵌入到其他條帶中形成Piggyback塊的一種設(shè)計(jì)。失效的數(shù)據(jù)符號(hào)可以通過(guò)求解Piggyback方程來(lái)替代傳統(tǒng)的MDS譯碼來(lái)恢復(fù)，這樣能有效降低修復(fù)帶寬。

Piggybacking編碼的框架是在一個(gè)任意的、被稱為基本碼的基礎(chǔ)上操作，目前的基本碼都采用MDS碼。Piggybacking編碼保持了基本碼的很多屬性，比如最小距離和操作域。Piggybacking框架有一個(gè)顯著的特點(diǎn)就是在不改變?cè)写鎯?chǔ)節(jié)點(diǎn)的分布結(jié)構(gòu)下減少了額外的存儲(chǔ)開(kāi)銷(xiāo)，即不需要增加除MDS編碼以外的校驗(yàn)節(jié)點(diǎn)，依舊能保持?jǐn)?shù)據(jù)重建性。另外，Piggybacking編碼滿足MDS性質(zhì)可以實(shí)現(xiàn)高碼率，擁有少的子條帶數(shù)和修復(fù)節(jié)點(diǎn)時(shí)更少的平均數(shù)據(jù)讀取量和下載量等特點(diǎn)。另一個(gè)特別吸引人的點(diǎn)就是Piggybacking編碼支持任意碼長(zhǎng)為n、信息位長(zhǎng)度為k的基本碼(碼參數(shù)的選擇取決于基本碼的需要)。然而有的碼如Rotated-RS碼，當(dāng)校驗(yàn)節(jié)點(diǎn)數(shù)r∈{2,3}和信息節(jié)點(diǎn)數(shù)k≤36時(shí)才存在[29]；EVENODD碼和RDP碼也只在r=2時(shí)才可以實(shí)現(xiàn)。再加上Piggybacking編碼設(shè)計(jì)靈活、復(fù)雜度低和易于系統(tǒng)實(shí)現(xiàn)等特點(diǎn)，目前已經(jīng)應(yīng)用于Facebook Warehouse Cluster，HDFS等系統(tǒng)中[30]。通常Piggybacking編碼采用系統(tǒng)形式，因?yàn)橄到y(tǒng)形式中的信息節(jié)點(diǎn)承載了所有未編碼的原始數(shù)據(jù)。因此用戶通過(guò)直接訪問(wèn)信息節(jié)點(diǎn)就可以得到原始數(shù)據(jù),而不用訪問(wèn)某些校驗(yàn)節(jié)點(diǎn)采用MDS譯碼來(lái)恢復(fù)原始數(shù)據(jù)，這樣不僅降低了獲取原始數(shù)據(jù)的復(fù)雜度，還降低了獲取數(shù)據(jù)的延遲。

圖7 Piggybacking框架

2.3.2 Piggybacking編碼的發(fā)展現(xiàn)狀

作為Piggybacking編碼的鼻祖，Rashmi等人提出了3種Piggybacking設(shè)計(jì)[29]。第1種設(shè)計(jì)是基于較少的子條帶數(shù)量，其中最少的子條帶數(shù)只有2。這類(lèi)設(shè)計(jì)修復(fù)信息節(jié)點(diǎn)時(shí)根據(jù)碼參數(shù)不同可以節(jié)省25%～50%不等的修復(fù)帶寬，且該設(shè)計(jì)也具備修復(fù)校驗(yàn)節(jié)點(diǎn)的能力。經(jīng)計(jì)算表明，當(dāng)整個(gè)Piggybacking框架采用的條帶(例)數(shù)m越大時(shí)，修復(fù)帶寬越低，修復(fù)效率越高。第2種設(shè)計(jì)是由(2r-3)列結(jié)構(gòu)相同的MDS碼組成，并在最后(r-1)列中增加了Piggyback方程。該設(shè)計(jì)要求校驗(yàn)節(jié)點(diǎn)數(shù)r≥3，相比第1種設(shè)計(jì)擁有更高的修復(fù)效率，平均能有效減少約50%的修復(fù)帶寬。這是以犧牲子條帶數(shù)量為代價(jià)：要求最少子條帶數(shù)為(2r-1)，且該設(shè)計(jì)不能有效修復(fù)校驗(yàn)節(jié)點(diǎn)。作者將關(guān)注度從修復(fù)帶寬轉(zhuǎn)移到修復(fù)度上,設(shè)計(jì)了第3種Piggybacking編碼，該碼可以有效修復(fù)最小修復(fù)度可達(dá)k+1的MDS碼中的信息節(jié)點(diǎn)。

隨著Piggybacking編碼被提出，研究者們正試圖尋找構(gòu)造有效的Piggybacking框架來(lái)修復(fù)失效節(jié)點(diǎn)。Yuan等人提出一種廣義的Piggybacking編碼，并證明了當(dāng)校驗(yàn)節(jié)點(diǎn)數(shù)趨于無(wú)窮大時(shí)，信息節(jié)點(diǎn)的修復(fù)帶寬比率趨近于零，而且非常接近分布式存儲(chǔ)編碼修復(fù)帶寬的理論極限(cut-set bound[31])。Kumar等人針對(duì)信息節(jié)點(diǎn)的修復(fù)設(shè)計(jì)了一種Piggybacking框架，然而該P(yáng)iggybacking結(jié)構(gòu)并沒(méi)有維持MDS性質(zhì)[32]，且當(dāng)B類(lèi)校驗(yàn)節(jié)點(diǎn)數(shù)增加時(shí)，信息節(jié)點(diǎn)的修復(fù)帶寬會(huì)減少，同時(shí)也增加了系統(tǒng)的存儲(chǔ)負(fù)載。Shangguan等人提出了一種Piggybacking編碼用于修復(fù)信息節(jié)點(diǎn)，他們根據(jù)不同Piggyback塊中嵌入的信息符號(hào)數(shù)量的不同將信息節(jié)點(diǎn)進(jìn)行劃分，由此獲得了較低的修復(fù)帶寬[33]。Yang等人保證信息節(jié)點(diǎn)可修復(fù)的同時(shí),為減少校驗(yàn)節(jié)點(diǎn)的修復(fù)帶寬提出了一種Piggybacking框架[34]。

2.3.3 Piggybacking編碼的理論研究、構(gòu)造與應(yīng)用

Piggybacking編碼的研究主要處在理論和構(gòu)造階段，因此從Piggybacking碼的理論研究、構(gòu)造和可能應(yīng)用的這3個(gè)方向?qū)ζ溲芯績(jī)?nèi)容進(jìn)行闡述，其結(jié)構(gòu)如圖8所示。

圖8 Piggybacking編碼的研究方向

2.3.3.1 理論研究

Piggybacking編碼通常是以MDS碼作為基本碼，然而MDS碼的弊端很多，比如：系統(tǒng)中MDS碼的編譯碼操作經(jīng)常會(huì)導(dǎo)致高延遲和低吞吐量的情況，MDS碼的修復(fù)代價(jià)太高，MDS碼修復(fù)度較大，對(duì)磁盤(pán)I/O性能不友好。更加遺憾的是，由于MDS碼的編譯碼復(fù)雜度很高，會(huì)導(dǎo)致Piggybacking編碼的編譯碼復(fù)雜度也不低。因此對(duì)于Piggybacking編碼來(lái)說(shuō)，選擇復(fù)雜度低的基本碼是降低自身復(fù)雜度最快、也是最有效的方法。比如可以考慮將復(fù)雜度較低的類(lèi)LDPC碼來(lái)作為基本碼。

一種Piggybacking編碼性能的好壞，不僅在于其具有較低的修復(fù)帶寬比率，更希望它能有更快的收斂速度，有最小的修復(fù)帶寬比率下界。因此，需要對(duì)該碼的最小修復(fù)帶寬比率的性能界進(jìn)行分析。收斂速度越快，說(shuō)明該碼的最小修復(fù)帶寬比率下降速度越快；最小修復(fù)帶寬比率能達(dá)到的下界越低，說(shuō)明該碼的修復(fù)性能越好。

2.3.3.2 構(gòu)造

理論上基于有限域構(gòu)造，通過(guò)Piggyback塊構(gòu)造后產(chǎn)生的Piggybacking編碼不改變基本碼的有限域，也就是說(shuō)Piggyback函數(shù)設(shè)計(jì)得到的Piggybacking編碼不僅適用于二元域，也同樣適用于多元域Fq(q為素?cái)?shù)冪)。根據(jù)面向修復(fù)節(jié)點(diǎn)特點(diǎn)主要分為單節(jié)點(diǎn)修復(fù)和多節(jié)點(diǎn)修復(fù)，具體如下。

(1)單節(jié)點(diǎn)修復(fù)

在Piggybacking編碼的構(gòu)造階段，也就是設(shè)計(jì)Piggybacking的框架，目前所有研究只是停留在單節(jié)點(diǎn)的修復(fù)設(shè)計(jì)上，而且大部分都是針對(duì)信息節(jié)點(diǎn)的修復(fù)，檢驗(yàn)節(jié)點(diǎn)的非常少，而同時(shí)有效修復(fù)所有節(jié)點(diǎn)的Piggybacking碼就更少。本小節(jié)針對(duì)這3種編碼設(shè)計(jì)，分析構(gòu)造它們所采取的構(gòu)造思路如下：

a.信息節(jié)點(diǎn)的修復(fù)

一種Piggybacking編碼能夠修復(fù)信息節(jié)點(diǎn)，是因?yàn)镻iggyback函數(shù)中嵌入了信息節(jié)點(diǎn)中的原始信息數(shù)據(jù)，然后將這些Piggyback函數(shù)嵌入到不同校驗(yàn)節(jié)點(diǎn)中的不同子條帶(或條帶)中。顯然，當(dāng)信息節(jié)點(diǎn)失效時(shí)，帶有信息節(jié)點(diǎn)中失效信息數(shù)據(jù)符號(hào)的Piggyback函數(shù)存在于沒(méi)有損壞的校驗(yàn)節(jié)點(diǎn)中，通過(guò)這些函數(shù)構(gòu)造的逆過(guò)程即求解Piggyback方程，可得到失效數(shù)據(jù)。但當(dāng)校驗(yàn)節(jié)點(diǎn)失效時(shí)，失效的校驗(yàn)符號(hào)沒(méi)有留下任何與之相關(guān)的Piggyback函數(shù)(塊)，因此該P(yáng)iggybacking編碼就無(wú)法通過(guò)求解Piggyback方程來(lái)恢復(fù)，只能通過(guò)該P(yáng)iggybacking編碼基本碼的MDS性質(zhì)譯出。但這樣的修復(fù)帶寬是大于通過(guò)求解Piggyback方程來(lái)恢復(fù)失效數(shù)據(jù)的修復(fù)帶寬，且當(dāng)基本碼的編碼參數(shù)增大(分布式存儲(chǔ)系統(tǒng)規(guī)模的增大)，通過(guò)MDS性質(zhì)譯出的修復(fù)帶寬是遠(yuǎn)遠(yuǎn)大于通過(guò)求解Piggyback方程的。

對(duì)于不同的Piggybacking編碼而言，其最小修復(fù)帶寬比率(或修復(fù)效率)與修復(fù)帶寬比率的收斂速度均不相同。這與該P(yáng)iggybacking編碼的Piggyback函數(shù)和該P(yáng)iggyback塊放置的位置息息相關(guān)。一般情況Piggybacking編碼的修復(fù)帶寬比率越低，修復(fù)效率越高，其Piggyback函數(shù)構(gòu)造的復(fù)雜度就越高，方法就越巧妙。

通常可以采用整體法和分集法。整體法是將所有信息節(jié)點(diǎn)中的信息數(shù)據(jù)看成一個(gè)大的集合，需要構(gòu)造出一種Piggyback函數(shù)，將這些數(shù)據(jù)按照此編碼規(guī)則統(tǒng)一進(jìn)行嵌入；分集法是將信息節(jié)點(diǎn)進(jìn)行分組(理論分析，一般均分后的性能是最優(yōu)的)，針對(duì)每個(gè)集合需要對(duì)應(yīng)構(gòu)造出一種Piggyback函數(shù)，不合集合之間的函數(shù)不同，將各自集合中的信息數(shù)據(jù)采用與之對(duì)應(yīng)的Piggyback函數(shù)進(jìn)行嵌入。經(jīng)分析，分集法的修復(fù)帶寬比率的收斂速度大于整體法，因此它的修復(fù)效率更高，復(fù)雜度也較高。

b.校驗(yàn)節(jié)點(diǎn)的修復(fù)

同理，一種Piggybacking編碼能夠修復(fù)校驗(yàn)節(jié)點(diǎn)，是因?yàn)镻iggyback函數(shù)中嵌入了校驗(yàn)節(jié)點(diǎn)中的校驗(yàn)符號(hào)數(shù)據(jù)，將這些Piggyback函數(shù)嵌入到不同校驗(yàn)節(jié)點(diǎn)中的不同條帶(或子條帶)中。與修復(fù)信息節(jié)點(diǎn)的Piggybacking編碼相比不同的是：該P(yáng)iggyback塊也需加到校驗(yàn)節(jié)點(diǎn)上，而不是信息節(jié)點(diǎn)上。通常為了用戶方便有效讀取和下載數(shù)據(jù)，分布式存儲(chǔ)系統(tǒng)一般是系統(tǒng)節(jié)點(diǎn)，也就是當(dāng)系統(tǒng)中信息節(jié)點(diǎn)沒(méi)有損壞時(shí)用戶只需讀取下載信息節(jié)點(diǎn)中自己需要的數(shù)據(jù)即可，無(wú)需進(jìn)行MDS譯碼操作，這樣可以大大降低復(fù)雜度和讀取延遲。只有當(dāng)信息節(jié)點(diǎn)或校驗(yàn)節(jié)點(diǎn)失效時(shí)，才會(huì)動(dòng)用嵌在校驗(yàn)節(jié)點(diǎn)中的Piggyback塊進(jìn)行失效節(jié)點(diǎn)的修復(fù)。

由于修復(fù)校驗(yàn)節(jié)點(diǎn)的校驗(yàn)塊就放在校驗(yàn)節(jié)點(diǎn)上，因此該種Piggybacking編碼就有了一個(gè)與修復(fù)信息節(jié)點(diǎn)Piggybacking編碼不同的設(shè)計(jì)關(guān)鍵：校驗(yàn)節(jié)點(diǎn)的修復(fù)依賴與它相關(guān)的校驗(yàn)節(jié)點(diǎn)，因此必須保證每個(gè)校驗(yàn)節(jié)點(diǎn)的Piggyback塊(用于修復(fù)校驗(yàn)節(jié)點(diǎn))不能嵌入本校驗(yàn)節(jié)點(diǎn)的校驗(yàn)符號(hào)，假如該校驗(yàn)節(jié)點(diǎn)失效后，該節(jié)點(diǎn)中的校驗(yàn)符號(hào)連同與其唯一相關(guān)的Piggyback塊一起丟失，該符號(hào)就無(wú)法通過(guò)Piggyback方程譯出。為了提高Piggyback方程的可解性，即保證每個(gè)數(shù)據(jù)符號(hào)都能被正確恢復(fù)出，要求每個(gè)失效信息節(jié)點(diǎn)里的待嵌入數(shù)據(jù)符號(hào)不能嵌入同一個(gè)Piggyback塊里(避免出現(xiàn)方程式的個(gè)數(shù)少于未知數(shù)個(gè)數(shù)的情況)，因此這些數(shù)據(jù)符號(hào)需要盡可能地散列，當(dāng)然這個(gè)條件對(duì)修復(fù)信息節(jié)點(diǎn)的設(shè)計(jì)也需要滿足。為了設(shè)計(jì)修復(fù)帶寬比率低的用于修復(fù)校驗(yàn)節(jié)點(diǎn)的Piggybacking編碼，除了滿足上面的設(shè)計(jì)要求，還在于Piggyback函數(shù)的巧妙設(shè)計(jì)。也可采用整體法和分集法，分析比較它們之間的修復(fù)效率。

c.所有節(jié)點(diǎn)的修復(fù)

經(jīng)過(guò)對(duì)以上2種節(jié)點(diǎn)修復(fù)方法的簡(jiǎn)單描述，本節(jié)是對(duì)所有節(jié)點(diǎn)的修復(fù)分析方法進(jìn)行闡述。該種Piggybacking編碼的構(gòu)造要求是需要同時(shí)滿足對(duì)信息節(jié)點(diǎn)和校驗(yàn)的有效修復(fù)。用于修復(fù)信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的Piggyback塊都要嵌入校驗(yàn)節(jié)點(diǎn)中。因此， Piggybacking編碼可分為兩大類(lèi)：一類(lèi)是將修復(fù)信息節(jié)點(diǎn)的Piggyback塊和修復(fù)校驗(yàn)節(jié)點(diǎn)的Piggyback塊混合嵌入到校驗(yàn)節(jié)點(diǎn)中；另一類(lèi)是，將這2種Piggyback塊分開(kāi)嵌入校驗(yàn)節(jié)點(diǎn)中。當(dāng)這2種校驗(yàn)塊出現(xiàn)混合嵌入同一個(gè)校驗(yàn)節(jié)點(diǎn)的同一列時(shí)，必須清楚當(dāng)修復(fù)信息節(jié)點(diǎn)或校驗(yàn)節(jié)點(diǎn)時(shí)，用于修復(fù)另一種節(jié)點(diǎn)的Piggyback塊是否會(huì)對(duì)正在修復(fù)節(jié)點(diǎn)的修復(fù)帶寬產(chǎn)生影響，這樣是否會(huì)引入額外的修復(fù)帶寬(相比于單一節(jié)點(diǎn)修復(fù)的Piggybacking編碼)，以及Piggyback函數(shù)的設(shè)計(jì)復(fù)雜度增加的程度。當(dāng)這2種校驗(yàn)塊放置的子條帶沒(méi)有混合時(shí)，無(wú)形中又增加了Piggybacking編碼框架中的校驗(yàn)塊的嵌入子條帶數(shù)，這樣是否會(huì)影響該P(yáng)iggybacking編碼設(shè)計(jì)的參數(shù)(子條帶數(shù))要求。把握好上述2種情況，才能設(shè)計(jì)出復(fù)雜度低、同時(shí)有效修復(fù)2種節(jié)點(diǎn)的Piggybacking編碼。

(2)多節(jié)點(diǎn)修復(fù)

目前所有關(guān)于Piggybacking編碼的研究，針對(duì)失效節(jié)點(diǎn)的修復(fù)都是單節(jié)點(diǎn)修復(fù)。但Piggybacking編碼的多節(jié)點(diǎn)修復(fù)可以類(lèi)似RGC和LRC，且在實(shí)際的分布式存儲(chǔ)系統(tǒng)中有著重要的現(xiàn)實(shí)意義，這對(duì)深入研究Piggybacking編碼有一定的參考價(jià)值。

不同Piggybacking編碼的設(shè)計(jì)框架不同，即針對(duì)其修復(fù)節(jié)點(diǎn)的方法不盡相同。因此，不同Piggybacking編碼的多節(jié)點(diǎn)修復(fù)方法也不同。最重要的是，多節(jié)點(diǎn)的修復(fù)情況相比單節(jié)點(diǎn)更加復(fù)雜，包括3種情況：① 失效的全部都是信息節(jié)點(diǎn)；② 失效的全部都是校驗(yàn)節(jié)點(diǎn)；③ 失效的一部分是信息節(jié)點(diǎn)，一部分是校驗(yàn)節(jié)點(diǎn)。對(duì)于同一種Piggybacking編碼，其信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的修復(fù)帶寬不同，因此以上3種情況的修復(fù)帶寬都不相同，必須分情況討論。最終通過(guò)概率論與數(shù)理統(tǒng)計(jì)的方法求得平均多節(jié)點(diǎn)修復(fù)帶寬比率。另外，需注意的是，多節(jié)點(diǎn)修復(fù)的失效節(jié)點(diǎn)數(shù)以2起步，小于等于校驗(yàn)節(jié)點(diǎn)數(shù)r(其基本碼MDS碼能容忍的最大失效節(jié)點(diǎn)數(shù)為n-k=r)。

多節(jié)點(diǎn)的修復(fù)過(guò)程中會(huì)出現(xiàn)一種權(quán)衡，失效節(jié)點(diǎn)中的失效符號(hào)(需要求解未知數(shù)的個(gè)數(shù))與Piggyback方程個(gè)數(shù)的關(guān)系。顯然，Piggyback方程越多，利用線性方程能求解的未知數(shù)(失效節(jié)點(diǎn)中的符號(hào)數(shù))就越多，則通過(guò)MDS譯碼求解剩余未知數(shù)減少，總的消耗帶寬就小(最差的情況就是所有失效節(jié)點(diǎn)全部用MDS譯碼，即大小等于原始數(shù)據(jù)大小)。所以希望通過(guò)MDS譯碼求解的符號(hào)數(shù)應(yīng)盡量少。但又不能太少，否則Piggyback方程的個(gè)數(shù)少于剩余需要求解符號(hào)數(shù)的個(gè)數(shù)時(shí)，又無(wú)法求解。因此，必須針對(duì)不同的Piggybacking編碼，找到它的修復(fù)帶寬的權(quán)衡，才能求得其最小的多節(jié)點(diǎn)修復(fù)帶寬比率。

可以先對(duì)該P(yáng)iggybacking編碼的2個(gè)失效節(jié)點(diǎn)進(jìn)行分析總結(jié)，找出它的權(quán)衡，再將這種方法推廣到多個(gè)修復(fù)節(jié)點(diǎn)的推算中，難易程度循序漸進(jìn)，且準(zhǔn)確率更高。

2.3.3.3 應(yīng)用

(1)存儲(chǔ)

Piggybacking編碼作為分布式存儲(chǔ)編碼中的新生力量，誕生于大數(shù)據(jù)、云計(jì)算時(shí)代。目前它的主要應(yīng)用是存儲(chǔ)業(yè)務(wù)，并已經(jīng)應(yīng)用到了Facebook Warehouse Cluster，HDFS等系統(tǒng)中。

(2)安全

Piggybacking編碼與同屬于分布式存儲(chǔ)編碼的RGC和LRC一樣，都具有維護(hù)信息理論安全的潛力。因此，可以使Piggybacking編碼既能成為一種執(zhí)行高效、復(fù)雜度低的節(jié)點(diǎn)修復(fù)，同時(shí)還能實(shí)現(xiàn)信息數(shù)據(jù)的安全性。

考慮一個(gè)理論上能應(yīng)對(duì)在存儲(chǔ)節(jié)點(diǎn)的竊聽(tīng)模型，并通過(guò)損壞節(jié)點(diǎn)的修復(fù)得到其他節(jié)點(diǎn)的數(shù)據(jù)。其中的竊聽(tīng)者可能獲得存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)，也可能訪問(wèn)在修復(fù)某些節(jié)點(diǎn)期間下載的數(shù)據(jù)，通過(guò)設(shè)計(jì)安全可靠的Piggyback函數(shù)，既能對(duì)失效節(jié)點(diǎn)進(jìn)行有效修復(fù)，還能使竊聽(tīng)者獲得的數(shù)據(jù)無(wú)法解密譯出，從而確保信息的保密能力。在不向任何竊聽(tīng)者透露任何信息的情況下，可以安全存儲(chǔ)并向合法用戶提供最大的數(shù)據(jù)量。最后通過(guò)證明竊聽(tīng)者和原始數(shù)據(jù)之間的互信息為0，即竊聽(tīng)失敗，證明Piggybacking編碼的安全模型可行?？梢詫?duì)信息理論安全和Piggyback函數(shù)設(shè)計(jì)的復(fù)雜度進(jìn)行權(quán)衡分析，提出理論安全和具有最低Piggyback函數(shù)設(shè)計(jì)的復(fù)雜度二者結(jié)合的Piggybacking編碼方案可抵抗竊聽(tīng)。另外，除了在Piggyback函數(shù)的設(shè)計(jì)(編碼)上考慮，還可以結(jié)合信息安全方面的知識(shí)建立安全模型。

(3)邊緣計(jì)算

如果在分布式存儲(chǔ)系統(tǒng)中完全依賴云中心去修復(fù)失效節(jié)點(diǎn)，不僅會(huì)占用大量的網(wǎng)絡(luò)帶寬，還會(huì)導(dǎo)致整個(gè)系統(tǒng)的性能瓶頸變?yōu)榫W(wǎng)絡(luò)帶寬的瓶頸，因?yàn)樵浦行牡奶幚硭俣纫h(yuǎn)超網(wǎng)絡(luò)中數(shù)據(jù)的傳輸速度。若節(jié)點(diǎn)的修復(fù)計(jì)算能搬移到邊緣節(jié)點(diǎn)，且只向云中心提交處理后的結(jié)果，不僅能降低不必要的帶寬消耗，還能減少修復(fù)延遲，從而進(jìn)一步提高系統(tǒng)性能。另外，就地處理數(shù)據(jù)，可以大大降低數(shù)據(jù)在網(wǎng)絡(luò)傳輸中被竊取的風(fēng)險(xiǎn)，有效進(jìn)行隱私保護(hù)，保障數(shù)據(jù)安全。

協(xié)同邊緣如圖9所示，它連接了多個(gè)在物理位置或網(wǎng)絡(luò)結(jié)構(gòu)中分散的邊緣節(jié)點(diǎn)。邊緣節(jié)點(diǎn)作為一個(gè)將終端用戶和云中心連接具有數(shù)據(jù)處理能力的小型數(shù)據(jù)中心，也是邏輯概念的一部分[35]。實(shí)線箭頭代表云服務(wù)器中心給邊緣節(jié)點(diǎn)下發(fā)任務(wù)，虛線箭頭表示多個(gè)終端用戶將自己產(chǎn)生的數(shù)據(jù)交給具有計(jì)算能力的邊緣節(jié)點(diǎn)進(jìn)行處理。在網(wǎng)絡(luò)邊緣處，節(jié)點(diǎn)不僅可以從云中心請(qǐng)求服務(wù)和內(nèi)容，還可以在本地執(zhí)行計(jì)算卸載、數(shù)據(jù)存儲(chǔ)、緩存和處理以及物聯(lián)網(wǎng)管理等任務(wù)?；谶@些能力，需要對(duì)邊緣節(jié)點(diǎn)進(jìn)行良好設(shè)計(jì)，保證存儲(chǔ)系統(tǒng)中數(shù)據(jù)的可靠、安全和隱私[36]。綜上所述，這些分布式邊緣節(jié)點(diǎn)為終端用戶提供了合作和共享數(shù)據(jù)的機(jī)會(huì)。因此，邊緣計(jì)算具有極大潛力，可以通過(guò)與Piggybacking編碼結(jié)合來(lái)安全高效地解決分布式存儲(chǔ)系統(tǒng)中失效節(jié)點(diǎn)的修復(fù)難題。

圖9 分布式存儲(chǔ)中協(xié)同邊緣計(jì)算范式的結(jié)構(gòu)

2.4 性能比較

表1針對(duì)文中5種存儲(chǔ)容錯(cuò)方式的性能進(jìn)行了簡(jiǎn)單粗略比較(注：從這幾種容錯(cuò)存儲(chǔ)的基本原理來(lái)考慮，并沒(méi)有針對(duì)具體的容錯(cuò)參數(shù)或碼參數(shù))。其中“★”的數(shù)量表示性能的相對(duì)大小程度，即4顆星表示最高，3顆星表示較高，2顆星表示較低，1顆星表示最低。例如多副本機(jī)制的修復(fù)帶寬開(kāi)銷(xiāo)最低，用1顆星表示；其存儲(chǔ)開(kāi)銷(xiāo)最大，用4顆星表示。

表1 幾種存儲(chǔ)容錯(cuò)方式的性能比較

存儲(chǔ)容錯(cuò)修復(fù)帶寬銷(xiāo)存儲(chǔ)開(kāi)銷(xiāo)修復(fù)度計(jì)算復(fù)雜度容錯(cuò)能力多副本機(jī)制★★★★★★★★★★★MDS碼★★★★★★★★★★★★★★RGC★★★★★★★★★★★★★★L(fēng)RC★★★★★★★★★★★★★Piggybacking編碼★★★★★★★★★★★

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

本文簡(jiǎn)單介紹了目前分布式存儲(chǔ)系統(tǒng)中常見(jiàn)的容錯(cuò)技術(shù)，主要分為4部分：① 傳統(tǒng)的容錯(cuò)技術(shù)即最早的多副本機(jī)制和MDS碼；② 基于網(wǎng)絡(luò)編碼的再生碼；③ 著眼于降低磁盤(pán)I/O的局部可修復(fù)碼；④ 不改變存儲(chǔ)結(jié)構(gòu)的Piggybacking編碼。傳統(tǒng)的容錯(cuò)技術(shù)與分布式存儲(chǔ)編碼的容錯(cuò)相比，其基本性能劣勢(shì)比較明顯，慢慢會(huì)被取代。不同的分布式存儲(chǔ)編碼都有自己優(yōu)缺點(diǎn)，具體選擇哪種容錯(cuò)方式要根據(jù)分布式存儲(chǔ)系統(tǒng)的需求來(lái)決定。