论文研究-基于纠删码的云计算存储备份及恢复策略.pdf

所需积分/C币:31 2019-09-12 07:09:02 531KB .PDF
6
收藏 收藏
举报

如何保障云存储系统中数据的可靠性是云计算领域的热点问题。副本备份技术是保障数据可靠性的重要手段,但是存在占用存储空间大、存储效率低等问题。纠删码能够提供优化的数据冗余度,以防止数据丢失,恰当地使用纠删码可以提高空间的利用效率并获得较好的数据保护效果,在通讯方面已经得到广泛应用。将纠删码引入云存储系统中,代替副本备份策略,以提高云存储系统的性能。实验表明该方案可以有效提高数据可靠性和空间利用率。
016,52(4) Computer Engineering and Applications计算机工程与应用 且这n个数据块中任意k个编码数据均可以重构原来 采用这种系统码方式编码算法进行数据分块时,会 的k个数据。设G=gn(0≤≤n-1.0≤≤k-1),根据公生成较多的分块,这些分块不仅包含了数据分块还有冗 式(1)可得: 尔分块,这样数据分块与冗余分块的数量总和就会大于 F。1「D0 单纯的数据分块。将数据分块与冗余分块视为同等地 位的分块发送给存储结点进行存储,当用户读取文件时 (2) 无论是数据分块还是冗余分块,只要获得了一定数量的 分块就可以重组出文件内谷。由于该算法在生成冗余 即一个(m,k,)线性纠删码可以表示为D=G·F,其中分块时通常都会引入纠错思想,从而极大地避免了恢复 F=(F0,F…,F1是信息数据;D=(DD,…,D,1)是文件与源文件存在差异或无法正常重组的情况。 经过编码的数据,也称为码字( codeword);G是n×k矩 当需要恢复文件时,在所有的r(r≥k)个存活数据块 阼,称作此(mk,)线性纠错码的生成矩阵,形如(3);k中,任意k个数据块就可以将原文件恢复。由于生成矩 与n的比值kn称为此线性纠锆码的编码率,又称码率阵中每个行向量都与一个数据块一一对应,从r个数据 (rate);(n-k)/k称为该编码的冗余度。 块中选取k个数搪块进行解码运算,则这k个数据块对 应的行向量可以组成一个k阶方阵Q,其中k个数据块 0(k-1) 记作为(R0,R1…,R11,Q记作即 gk-)。 g1 G=(g0g1…,8n g1 g-D(3)即Q与原始k个数据块相乘得到了这些存活下来的数 据块,可表示为方程(6) g(m-108(-l…g(m-1(k-1 若G的任意k行组成的子矩阵G'均可逆,则利用 RO 接收到的任意k个数据均可重枃原米的κ个信息数 1_R1 (6) 据。这是研究基于纠删码冗余机制的理论基础。除此 R 之外,引入纠删码的另一个前提是纠删码采用系统码 已知矩阵Q屮任意k个向量线性无关,则矩阵Q ( Sysmatic Code)(系统码就是指信息位和校验位分开 可逆。计算Q的逆矩阵ρ1,用ρ同时乘以编码方程 编码后的码字当中包含信息序列。反之,信息位与校验 位相互交叉称为非系统码)。系统码的采用使得任何生(6)两边,即可得到原始文件F,运算过程如(7)所示 F 成矩阵都可通过运算转化为如式(4)的系统形式,其中 Ro R 是kxk单位矩阵,P是一个(n-k)×k矩阵 =0.2 Q 3.2数据块的恢复 通过上述方法,只要得到编码生成n个数据块中的 (4)任意r(r≥k)个数据块,就可以复原文件F。但在实际 应用中,一旦某个或某些节点失效,文件F的可靠性就 随之下降,而重新对文件编码存储又会造成资源浪费, P 因而能否恢复已经损坏的原有数据块重新存储成为云 在对原来的κ个数据块进行编码时,可表示为式存储系统容错策略选择的另一要求 (5)的数学形式,即生成矩阵G乘以信息数据F。在所 在数据块复原时仍然使用恢复原文件的k个数据块, 得的码字中,其前k位由单位矩阵决定,因此和F中在恢复的过程中分为原始数据块和冗余数据块两种。 各位数据相同。其余的n-k位被称为校验数据,是k3.2.1原始数据块 个原始信息数据的线性组合。 设在恢复文件F过程中根据k.n,生成矩阵创建 0 的解码矩阵为Q,存活下来的用于恢复文件的k个数据 块(R0R…,R),在恢复原始数据块吋,提取¢中 的第i行与完好的k个数据块进行数量积运算将k个 FL D (5)数据块进行数量积运算,所得积再做异或运算,即可得 P1 PI PI 到损坏的原始数据块。公式如下 D D=Q,R=Q1RQ1R…⊙ Q 0≤i≤k (8) 芦欣,刘渊:基于纠删码的云计算存储备份及恢复策略 2016,52(4)5 322冗余数据块 表1不同参数下的副本备份 恢复由原文件生成的冗余数据块(即D4D41…,D,1) 备份数量实验次数文件失效次数文件失效率/% 时,将编码矩阵P中对应行P与k个数据坎进行数量 234 21.5 200 4.0 积运算,所得积做异或运算,即得到损坏的冗余数据块。 D,=P,R=P,RnOP1·R1① P1-1R21(0≤i≤n-k-1) 200 33性能指标 4.3.2基于纠删码备份实验 云存储系统的备份恢复策略的性能可以用编码冗 原文件分块数k=5保持不变,在n=7、8、9、10、11的 余度、数据可用性和存储开销3个指标进行描述。 情况下,各进行200次实验,统计文件失效率,结果如表2 3.3.1缩码冗余度 表2不同n值下的对比数据 采用(n,k,r)纠删码的冗余备份策略,编码冗余度为 实验次数文件失效次数文件失效率/%编码吋间/s解码吋间, n 7200 13.291 1+ (10 k 8200 5.5 15.727 16.294 3.3.2存储开销 200 l8.513 l8.986 采用(n,k,)纠删码的冗余备份策略,每个文件F10200 19.702 20.552 所需要的存储空问为 0 22.584 22.360 F (11) 当n=9时,由分成5块的原文件生成9个数据块如 图冬3 3.3.3数据可用性 采用(n,k,r)纠删码的冗余备份策略,文件F被分 内三工1钟 储系统中共有N个节点当前不可川的节点数M-、Q 割成k个数据块,并编码为n个数据块。假设云存储存 个。文献[15-16给出了系统可用性的计算方法:文件对 象F的可用概率P等于不可用文件块存放在不可用 存储节点上的方法数乘以可用文件块存放在可用存储 福 节点上的方法数再除以所有文件块放在所有存储节点 的方法数所得的值,即 MIN-MIN 上围 (12) 图3数据块生成图 实验结果与分析 4.1实验数据 随机删除4个数据块,川余下的数据块进行数据恢复 操作,假若所除的数据块为 Movie kl.wmv、 Movie k2. 实验中采用一个450MB的视频文件,分块存储时每 wmv、 Movie k5wmv、 Movie n1.wmy,译码后的数据截 个节点存储数据大小为90MB。假设组成云存储系统的图如图4所示。 若十个存储节点的失效率为20%(由于实验条件有限, 不能模拟云存储系统中的大量存储节点,下文计算文件 失效率时采用已存储数据节点失效率为20%计算,计算 结果较上述给出的计算方法偏大),进行基于RS纠删码 和副本备份两种方式的备份和恢复性能的对比试验 4.2实验环境 实验在 Ubuntu13.04系统下,利川Code: Blocks编 译环境进行冗余备份和恢复进行仿真实验。 中细 4.3实验结果 4.3.1副本备份实验 相同实验环境,副本备份数量分别取2、3、4、5、6,各 进行200次实验,统计文件失效率,结果如表1 图4数据块恢复图 016,52(4) Computer Engineering and Applications计算机工程与应用 文件 Movie decoded.wmv为恢复后的文件,Move在较高的4%时,基于纠删码备份可以达到完全恢复的 klrecover wmy Movie k2 recover wmy Movie k5 recover.程度。 wm、 Movie mi recover. wmv分别为采用纠删码恢复 的丢失数据块文件。经检测,通过译码恢复的文件与原5结束语 文件内容完全一致 本文针对云存储数据可靠性问题,提出采用基于纠 4.3.3对比实验 删码的备份方法替代副小备份方法。经过同副本备份 通常情况下,副本备份采用备份数为3,基于纠朋码方式对比的大量实验证实,该方法可以在占用较小存储 的备份方案纠删码的冗余率m不大于2,故采用复本空间的前提下显著提高文件可靠性。同时在恢复原文 备份数为3,n=9,k=5的纠删码进行文件恢复的对比件过程中,可对丢失文件块进行恢复,经检测同丢失数 实验,各进行1000次随机试验,实验结果如表3。 据块完全一致,避免数据块损坏需要恢复文件后重新分 表3常态下文件失效率对比 块再存储的计算开销。在进行大量实验过程中,笔者发 实验次数存储空间MB文件失效次数文件失敚率%现当存储的数据较大时,基于纠删码的备份方式在编码 副本1000 1350 解码过程中,会额外消耗一些时间,如何提高编码解码 纠删码100 19 效率将是以后研究的重点。 为了更好地对比两种数据备份方式对数据可靠性 的保障,采取控制变量法再次进行实验:当备份文件占参考文献 用相同存储空间时(以副本备份数为3时所占用空间为 [1 Schmuck F B, Haskin r l,gpe: a shared. disk file sys 基准,此时n=15.k=5),比较两种方案的文件失效率, tem for large computing clusters[C)/Proceedings of the 实验结果如表4。 Conference on File and Storage Technologies, January 表4占用相同仔储空间时文件失效率对比 28-30,2002:231-244 实验次数文件失效次数文件失效率% [2]Cloudstorageforcloudcomputing[eb/ol].(2009).http:!/ 副木 1000 4.0 ogf. org/Rcsourccs/documents/CloudStoragcForCloud Com 纠删码 10U0 0 puting.pdf. [3]Raluca A P Secure searchable and efficient cloud storage[eB/ 4.4实验结论 Olj.(2010).http://www.usenix.org/event/sec09/techislides/ (1)从表1看出,副本备份方式随着副本份数的增 popa. pdf. 长,所占用存储空间成倍数增长,文件失效率降低速度[4] Cloud storage standards overview and research ideas brain 放缓。 storm[eb/ol].(2009).htTp://www.pdl.cmuedu/sdi/2009/ (2)从表2看出,基于纠删码备份方式,随着n的增 MarkCarlson CloudCMU pdf 长,文件失效率迅速降低,n增长到原始文件分块数目51 Hayes B Cloud computing. Communications of the ACM, 吋,文件失效率趋于稳定,几乎可以保证文件完全恢 2008,51(7):9-11 复。但同时,采用纠删码编码和恢复时,由于纠删码均6 Knorr f, ruman Gi. What cloud computing really means[EB 基于有限域计算,需要进行大量的点积、异或等运算,在 Ol]-[2013-10-19].http://www.infoworld.com/d/cloud-com- 进行大文件编码恢复时需要消耗较长时间,随着冗余块 puting/ what-cloud-computing-rcally-mcans-03 数的增加消耗时间呈线性增长 7 Ghemawat S, Gobioff H, Leung S TThe google file sys tem [J].Operating Systems Review, 2003, 37(5): 29-43 (3)图3、图4表明,采用纠删码可以在某些存储节 [8]黄晓云基于HDFS的云存储服务系统研究[D大连:大连 点失效情况下恢复存储的文件,同吋可以在不恢复原文 海事大学,2010 件重新分块的情况下恢复受损的数据块。 (4)从表3、表4看出,实际应用过程中副本备份方[9]慕建君,路成业,王新梅关于纠删仍的研究与进展[]电子 信息学报,2002,24(9):1276-1281 式文件失效率是基于纠删码的备份恢复方式文件失效 10 Rizzo L Effective erasure codes for reliable computer 率的4.1/1.9=2.158倍。基于纠删码的备份策略在占用 communication protocols J.ACM SIGCOMM Computer 存储空间小的情况下,文件失效率明显降低。而在使 Communication Review, 1997, 27(2): 24-36 用相同存储空间吋,副本备份方式在文件失效率停留 (下转134页)

...展开详情
试读 5P 论文研究-基于纠删码的云计算存储备份及恢复策略.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744435 你的留言是对我莫大的支持
2019-09-12
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-基于纠删码的云计算存储备份及恢复策略.pdf 31积分/C币 立即下载
    1/5
    论文研究-基于纠删码的云计算存储备份及恢复策略.pdf第1页

    试读结束, 可继续读1页

    31积分/C币 立即下载 >