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

黃冬梅，唐春明，亓延峰

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

?

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

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

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

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

分布式存儲；Hadamard設計；糾刪碼；明顯修復方案；MSR碼

0　引　言

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

1　預備知識

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

表1中前k個系統(tǒng)節(jié)點存儲原始數(shù)據(jù)，第1個校驗節(jié)點存儲原始數(shù)據(jù)的和，第2個校驗節(jié)點存儲原始數(shù)據(jù)的線性組合，相關系數(shù)為

(1)

為了高效地修復失效的單節(jié)點，文獻[11]引入了如下幾個重要的稀疏矩陣.

(2)

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

本節(jié)給出一些逆矩陣的結(jié)果，并對系統(tǒng)節(jié)點和校驗節(jié)點給出了明顯修復方案.下面引理是對文獻[11]相關結(jié)果的一個總結(jié).

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

3　結(jié)束語

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

[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

國家自然科學基金資助項目(11401480)

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

TP309.3

A

1001-9146(2016)05-0082-05