徐志強(qiáng)，袁德砦，陳 亮

(1.中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都 610041； 2.中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京 100049) (*通信作者電子郵箱hfutsxxzq@163.com)

基于稀疏隨機(jī)矩陣的再生碼構(gòu)造方法

徐志強(qiáng)1,2*，袁德砦1,2，陳 亮1,2

(1.中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都 610041； 2.中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京 100049) (*通信作者電子郵箱hfutsxxzq@163.com)

針對(duì)已有的再生碼編碼方案的運(yùn)算是基于有限域GF(q)、運(yùn)算復(fù)雜度高、效率低的問(wèn)題，提出了一種將GF(2)上的稀疏隨機(jī)矩陣和乘積矩陣框架相結(jié)合的再生碼構(gòu)造方法。首先，將文件數(shù)據(jù)矩陣式排布后根據(jù)編碼矩陣進(jìn)行行異或運(yùn)算；其次，節(jié)點(diǎn)失效后，參與幫助節(jié)點(diǎn)根據(jù)失效節(jié)點(diǎn)的編碼向量編碼本地?cái)?shù)據(jù)并發(fā)送至修復(fù)節(jié)點(diǎn)；最后，修復(fù)節(jié)點(diǎn)根據(jù)接收到的數(shù)據(jù)譯碼出失效節(jié)點(diǎn)原有的數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明修復(fù)帶寬至多只有傳統(tǒng)糾刪碼修復(fù)方案的1/10，相比基于傳統(tǒng)范德蒙編碼矩陣的再生碼，編碼速率提升了70%，譯碼恢復(fù)速率提升了50%，方便了再生碼在大規(guī)模存儲(chǔ)系統(tǒng)中的應(yīng)用。

分布式存儲(chǔ)可靠性；再生碼；稀疏隨機(jī)矩陣；修復(fù)帶寬；節(jié)點(diǎn)失效

0 引言

在分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)失效成為常態(tài)的情況下，設(shè)計(jì)分布式存儲(chǔ)系統(tǒng)時(shí)必須考慮到合適的容錯(cuò)機(jī)制。目前廣泛使用的容錯(cuò)機(jī)制有復(fù)制備份和糾刪碼兩種。復(fù)制備份方案簡(jiǎn)單易行，數(shù)據(jù)恢復(fù)高效；但存儲(chǔ)空間浪費(fèi)明顯，常用的3副本備份機(jī)制需要將同一數(shù)據(jù)塊存儲(chǔ)3份，額外使用了兩倍的存儲(chǔ)空間，而且存在副本一致性難以維護(hù)的問(wèn)題。相比之下，基于糾刪碼[1]的編碼冗余方案不僅能保證高可靠性，同時(shí)可取得高存儲(chǔ)空間利用率，在數(shù)據(jù)量日趨增大的情況下，在很大程度上降低了存儲(chǔ)成本，故而受到了Facebook[2]、Google[3]、Microsoft[4]等公司的重視及廣泛應(yīng)用。其中應(yīng)用最為廣泛的當(dāng)屬里德索羅門(Reed-Solomon, RS)碼[5]等具有極大距離可分(Maximum Distance Separable, MDS)性質(zhì)的糾刪碼，可以達(dá)到最優(yōu)存儲(chǔ)效率。以(n,k)RS碼為例，它首先將原始數(shù)據(jù)文件分成k個(gè)塊，并根據(jù)編碼算法生成共n塊數(shù)據(jù)(n>k)，然后將n個(gè)數(shù)據(jù)塊存儲(chǔ)在不同的節(jié)點(diǎn)上，可以保證不丟失超過(guò)n-k個(gè)數(shù)據(jù)塊時(shí)，均可由剩余的塊根據(jù)譯碼算法恢復(fù)出原始的數(shù)據(jù)文件，但是這種簡(jiǎn)單的修復(fù)方案在節(jié)點(diǎn)失效時(shí)，為維持系統(tǒng)冗余度需要生成丟失節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)，就要從k個(gè)節(jié)點(diǎn)傳輸足夠的數(shù)據(jù)量從而成功譯碼出原始數(shù)據(jù)文件，再編碼生成丟失節(jié)點(diǎn)的數(shù)據(jù)塊，整個(gè)過(guò)程產(chǎn)生大量的網(wǎng)絡(luò)帶寬(這里及后文的修復(fù)帶寬指?jìng)鬏敂?shù)據(jù)量)，從而會(huì)嚴(yán)重影響現(xiàn)有數(shù)據(jù)的讀取速度[6]，因此，設(shè)計(jì)一種能有效降低修復(fù)帶寬的存儲(chǔ)編碼方法對(duì)實(shí)際的大規(guī)模存儲(chǔ)系統(tǒng)來(lái)說(shuō)至關(guān)重要。

針對(duì)糾刪碼的高修復(fù)帶寬問(wèn)題，Dimakis等[7]將網(wǎng)絡(luò)編碼[8]的思想應(yīng)用于分布式存儲(chǔ)中，提出了再生碼的概念。它通過(guò)在每個(gè)節(jié)點(diǎn)多存儲(chǔ)一定量的數(shù)據(jù)，并將數(shù)據(jù)傳送至失效節(jié)點(diǎn)前先在本地進(jìn)行編碼，可以顯著地減少節(jié)點(diǎn)修復(fù)過(guò)程中需要傳輸?shù)臄?shù)據(jù)量，降低了網(wǎng)絡(luò)帶寬消耗。但是Dimakis等[7]僅從理論上證明了再生碼可以達(dá)到存儲(chǔ)開(kāi)銷和修復(fù)帶寬的均衡，且其所給出的線性隨機(jī)網(wǎng)絡(luò)編碼方案[9]完全基于有限域GF(q)上元素的運(yùn)算：一方面計(jì)算開(kāi)銷大，實(shí)現(xiàn)復(fù)雜，另一方面修復(fù)后的數(shù)據(jù)與原節(jié)點(diǎn)的數(shù)據(jù)不一致，只是保證了全部編碼塊整體的冗余能力，故而實(shí)際用途并不大。Suh等[10]基于干擾對(duì)齊的思想提出了精確修復(fù)再生碼的構(gòu)造方法，但構(gòu)造過(guò)程整體上復(fù)雜；Rashmi等[11]基于乘積矩陣的通用性框架給出了可以精確修復(fù)失效節(jié)點(diǎn)數(shù)據(jù)的方案，其中給出的基于范德蒙矩陣或柯西矩陣的乘積矩陣方案，直觀緊湊，容易實(shí)現(xiàn)；但是基于GF(q)上的運(yùn)算，需要比較大的有限域規(guī)模，從而影響了計(jì)算效率，不能適應(yīng)實(shí)際中的使用。

為了提高再生碼的運(yùn)算效率，擺脫有限域GF(q)上的運(yùn)算，本文應(yīng)用陳亮等[12]提出的基于GF(2)上部分隨機(jī)矩陣的隨機(jī)二元可擴(kuò)展碼(Random Binary Extensive Code, RBEC)，并結(jié)合文獻(xiàn)[11]中給出的乘積矩陣思想，提出了一種再生碼的構(gòu)造方案。實(shí)驗(yàn)結(jié)果表明，該方案雖然是概率型的，但其成功概率完全可控(付出一定的冗余將獲得穩(wěn)定的失效恢復(fù)的高概率)，在保證失效恢復(fù)高概率成功的基礎(chǔ)上，相比文獻(xiàn)[11]中被認(rèn)為是基準(zhǔn)的基于范德蒙編碼矩陣的再生碼方案，有更高的編碼速度和失效恢復(fù)速度，從而更加方便了再生碼在大規(guī)模存儲(chǔ)系統(tǒng)中的實(shí)際應(yīng)用。

1 再生碼的基本原理

Dimakis等[7]將分布式存儲(chǔ)系統(tǒng)的數(shù)據(jù)存儲(chǔ)和失效節(jié)點(diǎn)數(shù)據(jù)修復(fù)抽象成經(jīng)典圖論中的信息流圖，利用網(wǎng)絡(luò)編碼中信息關(guān)聯(lián)和信息分散存儲(chǔ)的思想，提出了可以降低節(jié)點(diǎn)修復(fù)帶寬的再生碼方案。下面結(jié)合Dimakis文中所舉的(4,2)再生碼為例，來(lái)說(shuō)明再生碼的基本思想。圖1中待編碼的原始文件大小為2 MB，使用任意一種(4,2)MDS糾刪碼將原文件分成2塊，再編碼成4塊，存儲(chǔ)在不同的節(jié)點(diǎn)上。假設(shè)最后一個(gè)節(jié)點(diǎn)失效導(dǎo)致其存儲(chǔ)的數(shù)據(jù)丟失，那么需要立即啟用一個(gè)新的節(jié)點(diǎn)來(lái)恢復(fù)丟失的數(shù)據(jù)。具體的恢復(fù)過(guò)程如下：剩余存活的3個(gè)節(jié)點(diǎn)分別將自己所存的1 MB大小的數(shù)據(jù)通過(guò)隨機(jī)選擇編碼參數(shù)，先在本節(jié)點(diǎn)內(nèi)部編碼成大小為0.5 MB的編碼塊，再發(fā)送至新啟用的節(jié)點(diǎn)，新啟用的節(jié)點(diǎn)再根據(jù)接收到的3個(gè)編碼塊，譯碼恢復(fù)出失效節(jié)點(diǎn)丟失的數(shù)據(jù)塊。在這個(gè)簡(jiǎn)單的例子中，總共只需要傳輸1.5 MB的數(shù)據(jù)即可完成失效節(jié)點(diǎn)的修復(fù)，同時(shí)文中也指出這是理論上的最小值。當(dāng)然，這個(gè)簡(jiǎn)單例子給出的是一種功能性修復(fù)方案[13]，修復(fù)后的節(jié)點(diǎn)數(shù)據(jù)和原始數(shù)據(jù)不一致，后文主要給出的是準(zhǔn)確修復(fù)方案，保證準(zhǔn)確恢復(fù)出丟失的數(shù)據(jù)。

圖1 (4,2)再生碼的修復(fù)過(guò)程

(1)

(2)

其中，MSR碼本質(zhì)上仍是一種實(shí)現(xiàn)比RS碼的修復(fù)方案更低修復(fù)帶寬的MDS糾刪碼，每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)塊大小和MDS糾刪碼編碼后的每個(gè)數(shù)據(jù)塊大小相同，主要通過(guò)增加參與修復(fù)的節(jié)點(diǎn)個(gè)數(shù)以及在每個(gè)參與修復(fù)節(jié)點(diǎn)本地預(yù)先編碼數(shù)據(jù)塊來(lái)降低修復(fù)帶寬。MBR碼在每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)塊大小大于一般MDS糾刪碼生成的編碼塊，MBR碼通過(guò)在每個(gè)節(jié)點(diǎn)多存儲(chǔ)一定量的數(shù)據(jù)，并在參與修復(fù)的節(jié)點(diǎn)上預(yù)先編碼數(shù)據(jù)塊來(lái)降低修復(fù)帶寬。此外，Rashmi等[15]證明了在準(zhǔn)確地恢復(fù)出失效節(jié)點(diǎn)數(shù)據(jù)的情況下，除MBR和MSR兩種情況外的其他參數(shù)的碼字構(gòu)造都是不能實(shí)現(xiàn)的，因此，本文主要針對(duì)的是MBR和MSR兩種碼字的構(gòu)造方案。

2 RBEC碼的隨機(jī)編碼矩陣

3 基于稀疏隨機(jī)矩陣的MBR和MSR構(gòu)造

再生碼針對(duì)MBR和MSR兩種碼字的一個(gè)關(guān)鍵構(gòu)造參數(shù)是參與節(jié)點(diǎn)修復(fù)的存活節(jié)點(diǎn)數(shù)d。根據(jù)前面給出的γ的公式不難看出，隨著d的增加，修復(fù)帶寬γ不斷下降，在d=n-1時(shí)降至最小，當(dāng)然此時(shí)需要其余n-1個(gè)節(jié)點(diǎn)全部存活，這也就相應(yīng)地降低了碼字的容錯(cuò)能力。不失一般性，下面根據(jù)文獻(xiàn)[14]給出β=1時(shí)的MBR和MSR稀疏隨機(jī)矩陣構(gòu)造方案。當(dāng)β>1時(shí)，編碼和譯碼可簡(jiǎn)單地通過(guò)多次重復(fù)β=1時(shí)的方案來(lái)實(shí)現(xiàn)。兩種方案下采用的編碼矩陣均是RBEC碼使用的稀疏隨機(jī)編碼矩陣，關(guān)鍵的不同之處在于乘積矩陣方案中數(shù)據(jù)塊矩陣的布局方式，數(shù)據(jù)塊矩陣中的每個(gè)元素可以認(rèn)為是一個(gè)個(gè)大小相等的數(shù)據(jù)塊，后文可以看到數(shù)據(jù)塊矩陣的特殊布局方式對(duì)于節(jié)點(diǎn)的成功失效恢復(fù)至關(guān)重要。編碼過(guò)程中，根據(jù)編碼矩陣中0和1的分布，將數(shù)據(jù)塊矩陣中相應(yīng)的行數(shù)據(jù)塊進(jìn)行異或即可得出每個(gè)節(jié)點(diǎn)要存儲(chǔ)的編碼塊。

3.1 稀疏隨機(jī)矩陣MBR構(gòu)造方案

3.2 稀疏隨機(jī)矩陣MSR構(gòu)造方案

4 基于稀疏隨機(jī)矩陣的MBR和MSR恢復(fù)

(3)

同理，針對(duì)MSR碼，可解方程得到：

此外，因?yàn)闃?gòu)造MBR碼和MSR碼時(shí)采用的編碼矩陣是稀疏隨機(jī)矩陣，為了保證方程組存在唯一解，這里需要保證其系數(shù)矩陣GL×d列滿秩。如第2章所述，可以通過(guò)控制δ的取值保證GL×d以任意高的概率列滿秩，也就保證了方程組可解，從而能成功地恢復(fù)出丟失的數(shù)據(jù)。同時(shí)由于方程組的系數(shù)矩陣稀疏，故而實(shí)際求解時(shí)涉及到數(shù)據(jù)塊矩陣中數(shù)據(jù)塊的異或運(yùn)算次數(shù)就相應(yīng)少，從而可以保證方程組能高效求解。實(shí)質(zhì)上，從上面的恢復(fù)過(guò)程可以看出，這里給出的是δ近似MBR和δ近似MSR的恢復(fù)過(guò)程，這里δ近似的意思是相對(duì)于標(biāo)準(zhǔn)的再生碼參數(shù)，需要額外的δ個(gè)節(jié)點(diǎn)參與恢復(fù)過(guò)程。當(dāng)然，這實(shí)際上犧牲了標(biāo)準(zhǔn)再生碼的一些容錯(cuò)能力，但是在再生碼的參數(shù)取值較大時(shí)，這幾乎可以忽略不計(jì)，不會(huì)帶來(lái)太大的額外開(kāi)銷。

5 稀疏隨機(jī)矩陣再生碼的性能分析

本章主要從數(shù)學(xué)角度來(lái)分析稀疏隨機(jī)矩陣再生碼的存儲(chǔ)開(kāi)銷和編譯碼效率。

5.1 存儲(chǔ)開(kāi)銷

矩陣GL×d的列滿秩與否直接關(guān)系著能否譯碼成功。在這里，L=d+δ，因此n需要滿足n>d+δ，那么碼率r=k/n1+δ/d，這里通常d>δ。針對(duì)MSR碼，參數(shù)d可取值的范圍是2k-2≤d≤n-1，因此，存儲(chǔ)開(kāi)銷為n/k>2+2(δ-2)/(d+2)>2，因此，MSR碼通常比MBR碼有更高的存儲(chǔ)開(kāi)銷。

5.2 編譯碼效率

基于稀疏隨機(jī)矩陣的再生碼的編碼過(guò)程只涉及到數(shù)據(jù)塊之間的異或運(yùn)算，因此，編碼效率取決于生成校驗(yàn)塊需要的異或次數(shù)，而異或次數(shù)又取決于編碼矩陣下半部分中1的個(gè)數(shù)，這里1的個(gè)數(shù)平均為(n-d)×d/2，因此時(shí)間復(fù)雜度為O(nd)。譯碼過(guò)程涉及到矩陣的求逆和數(shù)據(jù)塊之間的異或運(yùn)算，時(shí)間復(fù)雜度為O(d3)。在MBR和MSR的參數(shù)d的取值范圍下，時(shí)間復(fù)雜度為O(k3)。

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

為了驗(yàn)證本文給出的基于稀疏隨機(jī)矩陣的再生碼方案的優(yōu)越性，本文選取了不同大小的原數(shù)據(jù)文件和多組編碼參數(shù)(n,k,l)，其中L=d+δ,δ=16。首先，對(duì)MBR碼、MSR碼和RS碼修復(fù)方案(這里的RS碼修復(fù)方案即為引言中提到的方案)的修復(fù)帶寬進(jìn)行了比較；然后，對(duì)比了基于RBEC碼的稀疏隨機(jī)編碼矩陣構(gòu)造的稀疏隨機(jī)最小帶寬再生(Sparse Random-Minimum Bandwidth Regenerating， SR-MBR)碼、稀疏隨機(jī)最小存儲(chǔ)再生(Sparse Random-Minimum Storage Regenerating, SR-MSR)碼和基于范德蒙矩陣構(gòu)造的范德蒙最小帶寬再生(Vandermonde-Minimum Bandwidth Regenerating, Van-MBR)碼、范德蒙最小存儲(chǔ)再生(Vandermonde-Minimum Storage Regenerating, Van-MSR)碼的編碼速率和失效恢復(fù)速率。本章實(shí)驗(yàn)的硬件環(huán)境為Intel Core i3 3.07 GHz CPU、4 GB RAM；軟件環(huán)境為Ubuntu 14.04 64位、Jerasure 2.0、GF-Complete。

6.1 修復(fù)帶寬

本節(jié)中選取的原文件的大小為20 MB和60 MB。針對(duì)再生碼選取了不同的參與修復(fù)節(jié)點(diǎn)數(shù)L={56,116}來(lái)顯示L其對(duì)再生碼修復(fù)帶寬的影響。

從表1中可以看出，針對(duì)20 MB大小的原始文件，參數(shù)為(60,40,56)的MBR碼單節(jié)點(diǎn)數(shù)據(jù)修復(fù)帶寬僅為0.77 MB，遠(yuǎn)遠(yuǎn)小于RS碼修復(fù)方案修復(fù)時(shí)的20 MB。針對(duì)60 MB大小的原文件，(128,100,116)MBR碼修復(fù)帶寬僅為1.1 MB，大約為RS碼修復(fù)方案的1/60。針對(duì)實(shí)際使用的分布式存儲(chǔ)系統(tǒng)，在文件大小達(dá)到更大的量級(jí)時(shí)，將更加體現(xiàn)出MBR碼的低修復(fù)帶寬優(yōu)勢(shì)。

表1 RS碼和MBR碼單節(jié)點(diǎn)修復(fù)帶寬比較

表2給出了不同參數(shù)MSR碼和RS碼修復(fù)方案的單節(jié)點(diǎn)修復(fù)帶寬比較結(jié)果，可以看出針對(duì)20 MB大小的原始文件，(90,36,86)MSR碼的修復(fù)帶寬僅為2.73 MB，大約為RS碼修復(fù)方案的1/10，(180,70,154)MSR碼修復(fù)帶寬為3.83 MB，大約為傳統(tǒng)修復(fù)方法的1/16。這體現(xiàn)了近似MSR碼在獲得近似MDS性質(zhì)的同時(shí)，帶來(lái)相對(duì)RS碼修復(fù)方案明顯的低修復(fù)帶寬優(yōu)勢(shì)。

6.2 編碼和恢復(fù)速率

本節(jié)中選取大小為20 MB、60 MB、100 MB、140 MB的原數(shù)據(jù)文件，比較了在相同編碼參數(shù)(n,k)下基于稀疏隨機(jī)矩陣的再生碼和基于范德蒙矩陣的再生碼的編碼速率和單節(jié)點(diǎn)失效時(shí)的數(shù)據(jù)恢復(fù)速率。

圖3(a)中給出了編碼速率的對(duì)比結(jié)果。從中可以看出，在100 MB文件大小時(shí)，(256,200,216)SR-MBR碼，編碼速率約為29 MB/s，(256,200,200)Van-MBR碼編碼速率約為17 MB/s，提升了大約70%；(256,110,234)SR-MSR碼編碼速率約為34 MB/s，(256,110,218)Van-MSR碼編碼速率約為20 MB/s，提升了大約70%。

表2 傳統(tǒng)RS碼和MSR碼單節(jié)點(diǎn)修復(fù)帶寬比較

圖3 稀疏隨機(jī)矩陣再生碼和范德蒙矩陣再生碼的性能對(duì)比

圖3(b)給出了單節(jié)點(diǎn)失效恢復(fù)速率的對(duì)比結(jié)果。從中可以看出，針對(duì)100 MB大小的文件，(256,200,216)SR-MBR碼恢復(fù)速率約為12.5 MB/s，(256,200,200)Van-MBR碼恢復(fù)速率約為6.5 MB/s，提升了大約一倍；(256,110,234)SR-MSR碼恢復(fù)速率約為3 MB/s，(256,110,218)Van-MSR碼恢復(fù)速率約為2 MB/s，提升了大約50%，因此，SR-MBR碼相比Van-MBR碼以及SR-MSR碼相比Van-MSR碼都有明顯的恢復(fù)速度優(yōu)勢(shì)。

從圖3中可以看出，在再生碼的參數(shù)(n,k,d)達(dá)到中等規(guī)模大小時(shí)，稀疏隨機(jī)矩陣再生碼相比范德蒙矩陣再生碼在編碼速率和節(jié)點(diǎn)失效恢復(fù)速率上有明顯的優(yōu)勢(shì)。

7 結(jié)語(yǔ)

本文提出的將RBEC碼的稀疏隨機(jī)矩陣和乘積矩陣方案相結(jié)合的一種再生碼構(gòu)造方案既能保證大幅度降低節(jié)點(diǎn)失效修復(fù)帶寬，同時(shí)相比基于傳統(tǒng)范德蒙編碼矩陣的乘積矩陣方案有更高的編碼速度和失效譯碼恢復(fù)速度。此外，雖然本文提出的再生碼方案的預(yù)期執(zhí)行結(jié)果是概率型的，但其成功的高概率完全可控。進(jìn)一步說(shuō)，真實(shí)的存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)失效的出現(xiàn)情況本來(lái)就是隨機(jī)性的，因此本文這種方案的機(jī)制在本質(zhì)上是符合現(xiàn)實(shí)情況的，并且其數(shù)據(jù)恢復(fù)在實(shí)際使用中的失敗概率完全可以控制在非常小的范圍內(nèi)，由此保證實(shí)用中的可行性和高效性。

本文提出的MBR碼和MSR碼構(gòu)造方案目前僅考慮了單節(jié)點(diǎn)的失效修復(fù)問(wèn)題，多個(gè)節(jié)點(diǎn)的失效修復(fù)在技術(shù)上可以通過(guò)多次單節(jié)點(diǎn)失效修復(fù)過(guò)程的重復(fù)來(lái)完成。盡管如此，修復(fù)過(guò)程的循環(huán)重復(fù)還是會(huì)占用多余的網(wǎng)絡(luò)傳輸帶寬，從而增加修復(fù)時(shí)間，因此，探索針對(duì)多節(jié)點(diǎn)失效修復(fù)的更加直接、更加高效的實(shí)現(xiàn)方案就成了下一步的重要工作方向。

References)

[1] 羅象宏,舒繼武.存儲(chǔ)系統(tǒng)中的糾刪碼研究綜述[J].計(jì)算機(jī)研究與發(fā)展,2012,49(1):1-11.(LUO X L, SHU J W. Summary of research for erasure code in storage system [J]. Journal of Computer Research and Development, 2012, 49(1): 1-11.)

[2] SATHIAMOORTHY M, ASTERIS M, PAPAILIOPOULOS D, et al. XORing elephants: novel erasure codes for big data [J]. Proceedings of the VLDB Endowment, 2013, 6(5): 325-336.

[3] MCKUSICK K, QUINLAN S. GFS: evolution on fast-forward [J]. Communications of the ACM, 2010, 53(3): 42-49.

[4] HUANG C, SIMITCI H, XU Y, et al. Erasure coding in windows azure storage [C]// Proceedings of the 2012 USENIX Conference on Technical Conference. Berkeley: USENIX Association, 2012: 2-2.

[5] REED I S, SOLOMON G. Polynomial codes over certain finite fields [J]. Journal of the Society for Industrial & Applied Mathematics, 1960, 8(2): 300-304.

[6] SUN W, WANG Y, FU Y, et al. A discrete data dividing approach for erasure-code-based storage applications [C]// Proceedings of the 2014 IEEE International Symposium on Service Oriented System Engineering. Piscataway, NJ: IEEE, 2014: 308-313.

[7] DIMAKIS A G, GODFREY P B, WU Y, et al. Network coding for distributed storage systems [J]. IEEE Transactions on Information Theory, 2010, 56(9): 4539-4551.

[8] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[9] HO T, MéDARD M, KOETTER R, et al. A random linear network coding approach to multicast [J]. IEEE Transactions on Information Theory, 2006, 52(10): 4413-4430.

[10] SUH C, RAMCHANDRAN K. Exact regeneration codes for distributed storage repair using interference alignment [EB/OL]. [2016- 12- 20]. https://arxiv.org/pdf/1001.0107.pdf.

[11] RASHMI K V, SHAH N B, KUMAR P V. Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction [J]. IEEE Transactions on Information Theory, 2011, 57(57): 5227-5239.

[12] 陳亮,張景中,滕鵬國(guó),等.隨機(jī)二元擴(kuò)展碼:一種適用于分布式存儲(chǔ)系統(tǒng)的編碼[EB/OL]. [2016- 12- 10]. http://kns.cnki.net/kcms/detail/11.1826.TP.20160929.1711.012.html.(CHEN L, ZHANG J Z, TENG P G, et al. Random Binary Extensive Code (RBEC): an efficient code for distributed storage system [EB/OL]. [2016- 12- 10]. http://kns.cnki.net/kcms/detail/11.1826.TP.20160929.1711.012.html.)

[13] DIMAKIS A G, RAMCHANDRAN K, WU Y, et al. A survey on network codes for distributed storage [J]. Mathematics, 2010, 99(3): 476-489.

[14] WU Y, DIMAKIS A G, RAMCHANDRAN K. Deterministic regenerating codes for distributed storage [C]// Proceedings of the 2007 Allerton Conference on Control, Computing, and Communication. Monticello: University of Illinois, 2007: 1-5.

[15] SHAH N B, RASHMI K V, KUMAR P V, et al. Distributed storage codes with repair-by-transfer and non-achievability of interior points on the storage-bandwidth tradeoff [J]. IEEE Transactions on Information Theory, 2010, 58(3): 1837-1852.

[16] COOPER C. On the rank of random matrices [J]. Random Structures & Algorithms, 2000, 16(2): 209-232.

[17] 郝杰,逯彥博,劉鑫吉,等.分布式存儲(chǔ)中的再生碼綜述[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,25(1):30-38.(HAO J, LU Y B, LIU X J, et al. Survey for regenerating codes for distributed storage [J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2013, 25(1): 30-38.)

This work is partially supported by Sichuan Science & Technology Support Program (2015GZ0088).

XUZhiqiang, born in 1993, M. S. candidate. His research interests include storage system reliability, network coding.

YUANDezhai, born in 1989, Ph. D. candidate. His research interests include coding theory, information security.

CHENLiang, born in 1990, Ph. D. candidate. His research interests include storage system reliability, Redundant Arrays of Independent Disks (RAID) code.

Regeneratingcodesconstructionmethodbasedonsparserandommatrix

XU Zhiqiang1,2*, YUAN Dezhai1,2, CHEN Liang1,2

(1.ChengduInstituteofComputerApplication,ChineseAcademyofSciences,ChengduSichuan610041,China;2.SchoolofComputerandControlEngineering,UniversityofChineseAcademyofSciences,Beijing100049,China)

Concerning the problem that the calculations of the existing regenerating code schemes is based onGF(q), and it has high computational complexity and low efficiency, a regenerating code construction method based on sparse random matrix overGF(2) and product matrix framework was proposed. Firstly, file data was arranged in a matrix and the row XOR operation was performed according to encoding matrix. Secondly, local data was encoded by helper nodes according to failed node’s encoding vector and sent to repair node. Finally, the failed node’s data was decoded by repair node according to

data. The experimental results show that the repair bandwidth of the proposed method is only one-tenth of traditional erasure code at most, and the encoding rate increases by 70% and decoding recovery rate increases by 50% compared with regenerating code based on conventional Vandermonde matrix, which facilitates the application of regenerating code in massive storage system.

distributed storage reliability; regenerating code; sparse random matrix; repair bandwidth; node failure

TP302.8

:A

2016- 12- 28;

:2017- 03- 07。

四川省科技廳支撐計(jì)劃項(xiàng)目(2015GZ0088)。

徐志強(qiáng)(1993—)，男，河南信陽(yáng)人，碩士研究生，主要研究方向：存儲(chǔ)系統(tǒng)可靠性、網(wǎng)絡(luò)編碼； 袁德砦(1989—)，男，江蘇泰州人，博士研究生，主要研究方向：編碼理論、信息安全； 陳亮(1990—)，男，江西豐城人，博士研究生，主要研究方向：存儲(chǔ)系統(tǒng)可靠性、磁盤(pán)陣列編碼。

1001- 9081(2017)07- 1948- 05

10.11772/j.issn.1001- 9081.2017.07.1948