余春雷，劉篤晉，朱華偉，楊佳蓉

（1.四川文理學院智能制造學院，四川 達州 635002；2.政務數(shù)據(jù)安全達州市重點實驗室，四川 達州 635002；3.長安大學信息工程學院，陜西 西安 710064）

0 引 言

當今社會是一個互聯(lián)網(wǎng)高速發(fā)展的時代［1］，近年來，我國數(shù)字經(jīng)濟創(chuàng)新發(fā)展逐年上升，人工智能、大數(shù)據(jù)、信息技術(shù)的快速發(fā)展給數(shù)據(jù)的存儲帶來了新的挑戰(zhàn)。隨著大數(shù)據(jù)應用的爆發(fā)性增長［2］，此前傳統(tǒng)的存儲系統(tǒng)設計已經(jīng)無法滿足大數(shù)據(jù)應用的需要。如何保證數(shù)據(jù)的可靠性和穩(wěn)定性［3-4］等問題出現(xiàn)在存儲廠商的面前。應用設備智能互聯(lián)、數(shù)字化轉(zhuǎn)型、高性能存儲和云計算等技術(shù)的發(fā)展加速了大數(shù)據(jù)相關(guān)技術(shù)的進步［5］，而作為實現(xiàn)大數(shù)據(jù)價值的關(guān)鍵環(huán)節(jié)，數(shù)據(jù)存儲與管理技術(shù)也日新月異，引領(lǐng)著大數(shù)據(jù)技術(shù)的變革［6-7］。

目前，大數(shù)據(jù)存儲涉及介質(zhì)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)連接控制等關(guān)鍵技術(shù)，存儲機制正由集中式向分布式存儲系統(tǒng)方向轉(zhuǎn)變［8］。HDFS（Hadoop Distributed File System）是目前典型的分布式存儲系統(tǒng)［9］，HDFS 架構(gòu)如圖1所示。

圖1 HDFS架構(gòu)

受大數(shù)據(jù)特征和應用場景影響，大數(shù)據(jù)存儲與管理技術(shù)發(fā)展多樣化且具有針對性，多基于分布式存儲系統(tǒng)。分布式存儲架構(gòu)通過橫向擴展，將分散的存儲資源構(gòu)成虛擬存儲設備，具備多副本高可用、低成本大容量等優(yōu)勢［10］，多副本經(jīng)常采用的技術(shù)是三副本［11-12］。多副本存在的缺陷是存儲開銷大［13］，為了降低存儲開銷，糾刪碼策略被應用到分布式存儲系統(tǒng)中，使系統(tǒng)具有更好的容錯性［14］。典型的糾刪碼有里所（Reed-Solomon，RS）碼和磁盤陣列碼［15-17］，它們都可以保證數(shù)據(jù)的可靠性，完成對故障的數(shù)據(jù)快速修復。糾刪碼通過少量的存儲開銷保證系統(tǒng)的冗余性，但是增加了其修復帶寬開銷。

針對多副本策略和糾刪碼策略等局限性［18-19］，文獻［20］提出了再生碼（Regenerating Codes）的編碼方式。再生碼是一類特殊的糾刪碼，經(jīng)證明修復故障節(jié)點時，只需要連接相應節(jié)點就可以修復數(shù)據(jù)，但是再生碼在處理數(shù)據(jù)中心的分層性質(zhì)方面的效果仍然有限［21］；同時修復局部性高［22］，因為修復時需要連接多個節(jié)點。目前，再生碼的研究包括最小存儲再生MSR（Minimum Storage Regenerating）碼和最小帶寬再生MBR（Minimum Bandwidth Regenerating）碼［23-25］。

為了解決修復分布式存儲系統(tǒng)故障節(jié)點出現(xiàn)的修復過程復雜的問題，部分重復（Fractional Repetition，F(xiàn)R）碼［26］的概念在基于MBR 碼的基礎上被提了出來。外部最大距離可分（Maximum Distance Separable，MDS）碼和內(nèi)部重復碼是FR 碼的構(gòu)造算法的核心過程。 FR 碼無需進行有限域運算，同時也可以降低節(jié)點存儲開銷［27］。因此，部分重復碼被廣泛研究。本文提出一種基于Petersen 圖邊染色［28］（Petersen Edge Coloring Based FR）碼的構(gòu)造算法，稱為PECBFR 碼。PECBFR 碼可以隨機訪問模式下的系統(tǒng)存儲容量，達到理論上的最優(yōu)。此外，與分布式存儲系統(tǒng)中的里所碼以及簡單再生碼（Simple Regenerating Codes，SRC）相比，在系統(tǒng)修復故障節(jié)點時，提高了故障節(jié)點修復效率，保障了數(shù)據(jù)的可靠性和穩(wěn)定性。

1 基礎知識

1.1 系統(tǒng)模型

本文分布式存儲系統(tǒng)用（n，k，d）來表示，其中分布式存儲系統(tǒng)的節(jié)點總數(shù)用n表示，重構(gòu)原文件所需最少節(jié)點數(shù)用k表示，修復一個失效節(jié)點所需的可用節(jié)點數(shù)用d表示，并且在分布式存儲系統(tǒng)（n，k，d）中滿足k≤d≤n-1。當系統(tǒng)中出現(xiàn)節(jié)點失效時，系統(tǒng)需要從其他存活節(jié)點下載數(shù)據(jù)對失效節(jié)點進行修復，下載的數(shù)據(jù)量β=1。同時，修復模型采用確定性修復方式。因此，修復完成以后節(jié)點的存儲容量保持不變還是為d。在這種系統(tǒng)模型的修復方式下，分布式存儲系統(tǒng)的存儲容量用CMBR表示，存儲容量表示任意選擇k個分布式存儲系統(tǒng)中存活節(jié)點能獲得的最大文件大小。當從每個存活節(jié)點下載數(shù)據(jù)β=1 時系統(tǒng)的存儲容量為：

1.2 邊染色

把圖G的邊集劃分成m個非空子集，即，i，j= 1，2，…，m，Ei∩Ej= ?，i≠j，把Ei中的邊用第i種顏色上色就是圖G邊染色。無環(huán)非空圖G中邊的r染色（edge r-coloring）中π是指r種顏色1，2，…，r對邊集E（G）中元素的一種分配，使得相鄰2 條邊所染顏色不同。換句話說，G中邊的r染色是映射：

使得對每個i(i= 1，2，…，r)，π-1(i)是匹配或者空集。若令：

1.3 部分重復碼

定義1在（n，k，d）系統(tǒng)中，（n，d，θ，ρ）部分重復碼可以由n個子集的集合N={N1，…，Nn}表示［29］，ρ是數(shù)據(jù)塊的重復度，每個子集中的符號均屬于符號集[n]={ 1，2，…，θ}。該（n，d，θ，ρ）部分重復碼的構(gòu)造過程滿足如下條件：

1）每個節(jié)點存儲d個數(shù)據(jù)塊，即

2）[n]中的每個元素都出現(xiàn)于N中ρ個不同的子集。

在（n，d，θ，ρ）FR 碼的構(gòu)造過程中，其中參數(shù)滿足θρ=nd。首先將原文件分割為m個數(shù)據(jù)塊，如圖2 所示，分別為數(shù)據(jù)塊m0～m8，其次通過MDS 碼對m0～m8進行編碼，產(chǎn)生m0～m8、P9等編碼數(shù)據(jù)塊，P9為校驗塊數(shù)據(jù)塊，保護數(shù)據(jù)的可靠性。然后采用復制策略，對m0～m8、P9等編碼數(shù)據(jù)塊復制ρ份，最后通過部分重復碼的內(nèi)部構(gòu)造算法把所有的數(shù)據(jù)塊存儲在n個節(jié)點里?？梢钥闯觯跇?gòu)造的FR 碼中，任意選擇2 個存儲節(jié)點相同的數(shù)據(jù)塊只有一個。隨機連接3 個存儲節(jié)點，可以獲得的不同數(shù)據(jù)塊是9 個，根據(jù)定義可知該FR 碼率為9。此外，由式（1）可計算出該分布式存儲系統(tǒng)的存儲容量為9，因此在（n，k，d）系統(tǒng)中所構(gòu)造的FR碼是最優(yōu)的。

圖2 部分重復碼構(gòu)造過程

1.4 故障節(jié)點修復方法

確定性修復可以精準地恢復出故障節(jié)點的數(shù)據(jù)［30］，并且修復好的數(shù)據(jù)完好無損，這就是確定修復的特點。功能性修復是對數(shù)據(jù)進行間接修復，修復好的數(shù)據(jù)不是損失的直接數(shù)據(jù)，但是可以通過修復好的數(shù)據(jù)解碼恢復出原來損失的數(shù)據(jù)。功能性修復照樣保證了數(shù)據(jù)可靠性，恢復出來的節(jié)點仍具有修復性質(zhì)，只是需要通過解碼來完成恢復數(shù)據(jù)。

確定性修復與功能性修復如圖3 所示。假設系統(tǒng)中節(jié)點N1出現(xiàn)故障時，這時存儲在N1節(jié)點的數(shù)據(jù)塊A和數(shù)據(jù)塊B失效，如圖3（a）所示，采用確定性修復的方式修復，通過分布式存儲系統(tǒng)中其他的存活節(jié)點如節(jié)點N2、N3、N4提供數(shù)據(jù)塊進行解碼對故障節(jié)點進行修復，修復完成以后，跟N1節(jié)點毀壞前存儲數(shù)據(jù)塊是一樣的，確定性修復可以精準地恢復原來損失的數(shù)據(jù)。如圖3（b）所示，也是對故障節(jié)點進行修復，但采用功能性修復。與確定性修復對比可知，功能性修復修復成功的N0節(jié)點存儲的數(shù)據(jù)跟N1有著很大差別，但是功能性修復也能夠保證系統(tǒng)數(shù)據(jù)穩(wěn)定性和可靠性，系統(tǒng)的容錯能力保持不變。

圖3 確定性修復與功能性修復

2 基于Petersen圖的部分重復碼構(gòu)造

為了提高分布式存儲系統(tǒng)中故障節(jié)點的修復效率，本文提出一種基于Petersen 圖染色的部分重復碼設計，稱PECBFR 碼。PECBFR 碼在分布式存儲系統(tǒng)修復故障節(jié)點時，能夠快速地修復故障節(jié)點。通過染色鏈路構(gòu)造的部分重復碼，在修復局部性、修復復雜度、修復帶寬開銷方面相較于分布式存儲系統(tǒng)中的常見編碼算法都有較大的性能提升。構(gòu)造步驟如下：

步驟1對Petersen 圖的邊進行染色，得到不同顏色的邊e1，e2，…，el(1 ≤l≤μ) 。Petersen 圖中的每個頂點vi(1 ≤i≤n)視為分布式存儲系統(tǒng)中需要存儲的數(shù)據(jù)塊di(1 ≤i≤n)。

步驟2對原始數(shù)據(jù)塊k采用MDS 編碼，總共得到n個數(shù)據(jù)塊，確定分布式存儲系統(tǒng)中FR 碼構(gòu)造過程每個數(shù)據(jù)塊di(1 ≤i≤n)的重復度ρ。

步驟3在染色的Petersen圖中，任意選擇3條顏色不同相鄰的邊組成的鏈路，且滿足每條鏈路通過鏈路Li(1 ≤i≤210 )的集合構(gòu)造部分重復碼的內(nèi)部重復碼。

步驟4把每條鏈路Li(1 ≤i≤210 )視為部分重復碼的存儲節(jié)點Ni，對每條Li鏈路中對應頂點的數(shù)據(jù)塊進行存儲。

具體地，Petersen 圖中邊4 色可染，記χ(G)= min{r：G中邊r色可染}，稱為G的邊色數(shù)（edge chromatic number）。由定義，若χ(G)=r，則G中邊的任何r染色π=（E1，E2，…，Er）中每個Ei都是非空的匹配。換言之，G的邊色數(shù)χ(G)是G中邊不交匹配的最小數(shù)目，即χ(G)≥Δ(G)，所以Petersen 圖中邊4 色可染。根據(jù)邊染色定理，對Petersen 圖中所有的邊進行染色，同時標記出每條邊的顏色。如圖4 所示，每種數(shù)字表示一種顏色。

圖4 Petersen圖的邊4染色

部分重復碼外部采用（10，8）MDS 編碼，即產(chǎn)生2個編碼校驗塊。然后確定部分重復碼數(shù)據(jù)塊的重復度ρ=2。接下來在圖4中任意選擇3條顏色不同相鄰的邊組成的鏈路Li，如表1所示為每條鏈路經(jīng)過的頂點。

表1 Petersen圖鏈路數(shù)據(jù)表

最后把每條鏈路Li（1≤i≤5）視為部分重復碼對應的存儲節(jié)點Ni（1≤i≤5），對每條Li鏈路中對應頂點的數(shù)據(jù)塊進行存儲，這樣一種基于Petersen 圖邊染色的部分重復碼構(gòu)造完成，如圖5 所示。從以上定理可以看出，PECBFR 碼率可以超出系統(tǒng)存儲容量，即Rc（k）＞CMBR。參數(shù)為（5，3，4）分布式存儲系統(tǒng)的FR 碼可以基于Petersen 圖邊染色來進行構(gòu)造，每個數(shù)據(jù)塊的重復度ρ=2。在圖5 構(gòu)造的部分重復碼中，任意選擇3個存儲節(jié)點，可獲取至少9 個不同的編碼數(shù)據(jù)塊，因此，Rc（3）=9。通過公式（1）可知，該系統(tǒng)的容量僅為9。因此，基于Petersen圖邊染色的PECBFR碼算法的系統(tǒng)具有更大存儲容量，存儲效率高。

圖5 FR碼編碼方案

3 性能分析

本章主要對基于Petersen圖邊染色的PECBFR碼算法跟分布式存儲系統(tǒng)中常見的編碼算法進行比較。在存儲開銷、修復局部性、修復復雜度、修復帶寬開銷等性能方面進行比較，如表2 所示。為了量化好比較，具體地文件大小M=1500 Mb，SRC的子文件數(shù)f=5。

表2 編碼方案的性能分析

3.1 修復帶寬開銷

表2 為幾種常見編碼方案在修復帶寬開銷跟修復局部性的性能分析。修復帶寬開銷是：故障節(jié)點的修改過程中下載的數(shù)據(jù)量。當單節(jié)點故障時，（n，k）RS 碼修復時需要靠原文件修復故障節(jié)點，所以帶寬開銷為M，驗證了（n，k）RS 存儲效率高，但是修復帶寬開銷比較大的問題。在（n，k，f）SRC 編碼方案中，修復故障節(jié)點，需要從其他數(shù)據(jù)節(jié)點下載f個數(shù)據(jù)塊，編碼方案中節(jié)點存儲的數(shù)據(jù)塊為f+1，并且數(shù)據(jù)塊的大小是M/fk，因此（n，k，f）SRC 的修復帶寬開銷為（f+1）M/k［13］；可以看出（n，k，f）SRC 犧牲了存儲開銷，減少了修復帶寬開銷?；赑etersen 圖邊染色的PECBFR碼算法，大小為M的文件先被分割為k份，每一份文件大小為M/k，4 個數(shù)據(jù)塊存儲在PECBFR 碼的每個節(jié)點。因此，PECBFR碼修復帶寬開銷為4M/k。PECBFR 碼在存儲開銷跟修復帶寬開銷做出了最優(yōu)的選擇。圖6所示為各種編碼修復帶寬開銷對比。

圖6 修復帶寬開銷對比

3.2 修復局部性

修復局部性指故障節(jié)點修復時需要連接的節(jié)點數(shù)，連接的節(jié)點數(shù)越多，修復局部性就越高，對網(wǎng)絡通信質(zhì)量的要求就高。如表2所示，分別給出了（n，k，f）SRC、（n，k）RS碼、三副本以及PECBFR 碼的修復局部性［13］，可以看出，三副本修復局部性為1，修復局部性最低。（n，k，f）SRC 的修復局部性為10，低于（n，k）RS碼高于三副本跟PECBFR 碼。（n，k）RS 碼的修復局部性是最高的為k，三副本以高昂的存儲開銷換取了較低的修復局部性?；赑etersen 圖邊染色的PECBFR碼算法的修復局部性為4。如圖7 所示，為各種編碼單節(jié)點故障的修復局部性分析圖。PECBFR 碼在存儲開銷跟修復局部性做出了最優(yōu)的選擇。PECBFR碼在修復單節(jié)點故障時的修復局部性比RS碼和SRC都要低。當出現(xiàn)兩節(jié)點故障時，PECBFR 碼與RS 碼和SRC的修復局部性一樣。

圖7 修復局部性比較

3.3 修復復雜度

本節(jié)對于RS 碼、SRC、PECBFR 碼3 種編碼的修復復雜度進行分析。RS碼需要經(jīng)過k2-1次有限域加法運算跟k2+k次有限域乘法運算才能修復故障節(jié)點，因此，O（2k2+k-1）是RS 碼在修復單節(jié)點故障時的修復復雜度。對于SRC，（f-1）（f+1）次異或運算需要被系統(tǒng)運算執(zhí)行才能修復故障節(jié)點，所以修復復雜度為O（f2-1）［29］。對于PECBFR 碼，直接通過復制數(shù)據(jù)就可以進行修復，不需要經(jīng)過其他復雜運算。由此可見，基于Petersen 圖邊染色的PECBFR 碼算法具有較低的修復復雜度，當出現(xiàn)故障節(jié)點時，PECBFR 碼算法能夠快速修復故障節(jié)點。

3.4 節(jié)點修復選擇度

對MDS碼來說，系統(tǒng)可以在n-1個存活節(jié)點中任意選擇k個存儲節(jié)點修復失效節(jié)點。因此，MDS 碼存在種修復方案，本文稱這種可選修復的方案數(shù)為該節(jié)點的修復選擇度。采用PECBFR 碼的編碼方案時，PECBFR 碼中對外部MDS編碼產(chǎn)生的每個編碼數(shù)據(jù)塊復制ρ個副本，然后存儲在不同節(jié)點上。假設PECBFR 碼節(jié)點的存儲容量為T時，采用PECBFR 碼的節(jié)點修復選擇度為（ρ-1）T。如圖8 所示，給出了PECBFR 碼采用重復度ρ=3 時，PECBFR 碼的存儲容量T與節(jié)點修復選擇度之間的關(guān)系?？梢钥闯觯琍ECBFR 碼在故障節(jié)點失效時，存在多種修復方案，并且隨著節(jié)點存儲容量越大，修復方案越多。

圖8 ρ=3時節(jié)點修復選擇度與存儲容量之間的關(guān)系

4 結(jié)束語

本文提出的一種基于Petersen 圖邊染色的PECBFR 碼算法，通過染色鏈路構(gòu)造的部分重復碼，在修復局部性、修復復雜度、修復帶寬開銷等方面相較于分布式存儲系統(tǒng)中的常見編碼算法都有較大的性能提升。除此之外，如果隨著數(shù)據(jù)塊規(guī)模擴大，可以采用本文中多個算法存儲模型對數(shù)據(jù)進行存儲，具有可擴展性，更加具有發(fā)展前景和應用背景。