黃冬梅，唐春明，亓延峰

(1.西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川 南充 637002；2.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

?

(k+2,k)的Hadamard極小存儲(chǔ)再生碼的明顯修復(fù)方案

黃冬梅1，唐春明1，亓延峰2

(1.西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川 南充 637002；2.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

(k+2,k)的Hadamard極小存儲(chǔ)再生(MSR)碼是一類對(duì)所有的失效單節(jié)點(diǎn)都具有最優(yōu)修復(fù)屬性的高碼率糾刪碼.在已有研究工作的基礎(chǔ)上，本文進(jìn)一步研究一些矩陣的特殊結(jié)構(gòu),并借助Hadamard設(shè)計(jì)的基本性質(zhì)，給出了一些大型矩陣的逆矩陣，獲得了(k+2,k)的MSR碼在單節(jié)點(diǎn)失效時(shí)的明顯修復(fù)方案，從而使得(k+2,k)的MSR碼的更加有效應(yīng)用.

分布式存儲(chǔ)；Hadamard設(shè)計(jì)；糾刪碼；明顯修復(fù)方案；MSR碼

0　引　言

隨著大數(shù)據(jù)時(shí)代的來(lái)臨，各種超大規(guī)模的分布式存儲(chǔ)系統(tǒng)得到迅速發(fā)展.為了維護(hù)數(shù)據(jù)的可靠性和抵抗數(shù)據(jù)丟失的能力，數(shù)據(jù)恢復(fù)是系統(tǒng)必須具備的基本能力，主要是利用數(shù)據(jù)副本和糾刪碼兩種冗余機(jī)制來(lái)維持分布式系統(tǒng)數(shù)據(jù)的修復(fù)能力.由于糾刪碼高效的數(shù)據(jù)存儲(chǔ)效率，一些著名系統(tǒng)采用了基于糾刪碼的存儲(chǔ)，例如Google Colossus(GFS2)[1]、Microsoft Azure[2]、HDFS Raid[3]和OceanStore[4].若分布式系統(tǒng)中節(jié)點(diǎn)數(shù)據(jù)丟失，為了維持系統(tǒng)的冗余水平，必須重構(gòu)該節(jié)點(diǎn)的數(shù)據(jù).有許多指標(biāo)衡量節(jié)點(diǎn)修復(fù)的代價(jià)，例如從磁盤(pán)中總共讀取的信息量，網(wǎng)絡(luò)中總的通信量(修復(fù)帶寬)，或者每次修復(fù)所需的磁盤(pán)數(shù)，其中最重要的是修復(fù)帶寬.文獻(xiàn)[5]給出存儲(chǔ)量和修復(fù)帶寬之間的折中關(guān)系，實(shí)現(xiàn)極小存儲(chǔ)的極大距離可分碼被稱為極小存儲(chǔ)的再生碼(MSR).文獻(xiàn)[6-7]構(gòu)造出低碼率情形下MSR碼.文獻(xiàn)[8-9]在高碼率情形下給出明顯的MSR碼，但只對(duì)系統(tǒng)節(jié)點(diǎn)具有最優(yōu)的修復(fù)性質(zhì).文獻(xiàn)[10]基于Hadamard設(shè)計(jì)給出了一種明顯的(k+2,k)的MSR碼，它對(duì)所有的節(jié)點(diǎn)(系統(tǒng)節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn))都有最優(yōu)的修復(fù)性質(zhì)，稱這種碼為(k+2,k)的Hadamard MSR碼.文獻(xiàn)[11]利用Hadamard設(shè)計(jì)性質(zhì)，改進(jìn)了文獻(xiàn)[10]的修復(fù)策略，大幅度降低單節(jié)點(diǎn)修復(fù)的計(jì)算量.但已有修復(fù)方案需要求解某些大規(guī)模線性方程組，計(jì)算費(fèi)時(shí).本文繼續(xù)使用文獻(xiàn)[11]的Hadamard設(shè)計(jì)的基本性質(zhì)，給出了一些大型矩陣的逆矩陣，并在單節(jié)點(diǎn)失效時(shí)給出了(k+2,k)的MSR碼的明顯修復(fù)方案.

1　預(yù)備知識(shí)

表1　(k+2,k)的Hadamard MSR碼

表1中前k個(gè)系統(tǒng)節(jié)點(diǎn)存儲(chǔ)原始數(shù)據(jù)，第1個(gè)校驗(yàn)節(jié)點(diǎn)存儲(chǔ)原始數(shù)據(jù)的和，第2個(gè)校驗(yàn)節(jié)點(diǎn)存儲(chǔ)原始數(shù)據(jù)的線性組合，相關(guān)系數(shù)為

(1)

為了高效地修復(fù)失效的單節(jié)點(diǎn)，文獻(xiàn)[11]引入了如下幾個(gè)重要的稀疏矩陣.

(2)

2　(k+2,k)的Hadamard極小存儲(chǔ)再生碼的明顯修復(fù)方案

本節(jié)給出一些逆矩陣的結(jié)果，并對(duì)系統(tǒng)節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)給出了明顯修復(fù)方案.下面引理是對(duì)文獻(xiàn)[11]相關(guān)結(jié)果的一個(gè)總結(jié).

類似引理2.2證明，使用引理1.1，同理可證明此引理.

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

本文通過(guò)計(jì)算一些大型矩陣的逆矩陣，并借助Hadamard設(shè)計(jì)的基本性質(zhì)，給出了(k+2,k)的MSR碼在單節(jié)點(diǎn)失效時(shí)的明顯修復(fù)方案，適用于系統(tǒng)節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)，從而使得(k+2,k)的MSR碼更加實(shí)用，在分布式存儲(chǔ)系統(tǒng)中有著重要的應(yīng)用價(jià)值.

[1]QUORA.Google-GFS2Colossus[EB/OL]. [2016-02-09].http://www.quora.com/Colossus-Google-GFS2.

[2]HUANGC,SIMITCIH,XUY,etal.Erasurecodinginwindowsazurestorage[C]//Presentedaspartofthe2012USENIXAnnualTechnicalConference(USENIXATC12), 2012: 15-26.

[3]HADOOPWiki.HDFSRAID[EB/OL]. [2016-02-09].http://wiki.apache.org/hadoop/HDFS-RAID.

[4]KUBIATOWICZJ,BINDELD,CHENY,etal.OceanStore:anarchitectureforglobal-scalepersistentstorage[J].AcmSigplanNotices, 2000, 35(11):190-201.

[5]DIMAKISAG,GODFREYPB,WUY,etal.Networkcodingfordistributedstoragesystems[J].InformationTheory,IEEETransactionson, 2010, 56(9):4539-4551.

[6]SHAHNB,RASHMIKV,KUMARPV,etal.InterferenceAlignmentinRegeneratingCodesforDistributedStorage:NecessityandCodeConstructions[J].InformationTheory,IEEETransactionson, 2010, 58(4):2134-2158.

[7]SUHC,RAMCHANDRANK.Exact-repairMDScodesfordistributedstorageusinginterferencealignment[C]//2010IEEEInternationalSymposiumonInformationTheory.IEEE, 2010: 161-165.

[8]TAMOI,WANGZ,BRUCKJ.Zigzagcodes:MDSarraycodeswithoptimalrebuilding[J],InformationTheory,IEEETransactionson, 2013, 59(3): 1597-1616.

[9]LIJ,TANGX,PARAMPALLIU.Aframeworkofconstructionsofminimalstorageregeneratingcodeswiththeoptimalaccess/updateproperty[J].InformationTheory,IEEETransactionson, 2015, 61(4): 1920-1932.

[10]PAPAILIOPOULOSDS,DIMAKISAG,CADAMBEVR.Repairoptimalerasurecodesthroughhadamarddesigns[J].InformationTheory,IEEETransactionson, 2013, 59(5): 3021-3037.

[11]TANGX,YANGB,LIJ,etal.ANewRepairStrategyfortheHadamardMinimumStorageRegeneratingCodesforDistributedStorageSystems[J].InformationTheory,IEEETransactionson, 2013, 61(10):5271-5279.

Concrete Optimal Repair Strategy for (k+2,k) Hadamard Minimum Storage Regenerating Codes

HUANG Dongmei1, TANG Chunming1, QI Yanfeng2

(1.SchoolofMathematicsandInformation,ChinaWestNormalUniversity,NanchongSichuan637002,China;2.SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

The (k+2,k) Hadamard minimum storage regenerating(MSR) code is a high rate storage code with optimal repair for all single node failures. This paper uses the techniques of Tang et al.’s work and properties of Hadamard designs, gives inverses of some special matrices, and presents concrete, efficient, and optimal repair computation for all the single nodes failures.

distributed storage systems; Hadamard design; erasure codes; optimal repair; MSR codes

10.13954/j.cnki.hdu.2016.05.016

2016-03-09

國(guó)家自然科學(xué)基金資助項(xiàng)目(11401480)

黃冬梅(1980-)，女，湖北荊州人，助教，組合優(yōu)化與編碼.

TP309.3

A

1001-9146(2016)05-0082-05