英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
S.Annie Joice, J.Vasanth Wason /International Journal of Engineering Research and
Applications (IJERA) ISSN: 2248-9622 www.ijera.com
Vol. 3, Issue 1, January -February 2013, pp.1797-1807
基于纠删码的云存储文件系统最小化的I/O恢复
S.Annie Joice* J.Vasanth Wason**
(Department of Computer Science and Engineering, M.A.M. College of Engineering and Technology,
Tiruchirappalli-621105)
(Department of Computer Science and Engineering, M.A.M. College of Engineering and Technology,
Tiruchirappalli-621105)
摘要：
云存储是一个网络在线存储模型，其数据被存放在第三方托管的虚拟存储池。为了减少存储开支，云文件系统正从复制转换至纠删码。这篇论文介绍了一个找到任何基于异或纠删码恢复所需要的码字符号的最佳数量和产生使用最小数据量的恢复计划的算法。一些云系采用里德-所罗门码（RS码）由于其普遍性和容忍大量故障的能力。我们定义了一类新的环绕里德-所罗门编码，它能执行比所有已知编码更高效的降级读，除此之外还继承了里德 - 索罗门码的可靠性和性能。
关键字：纠删码，里德-所罗门码，可靠性，复制，虚拟池
- 引言
一个云存储系统由一个存储服务器集组成，它能通过互联网提供长期的存储服务。在第三方云系统存储数据引起了对于数据保密性的严重担忧。所提出的使用纠删码的云文件系统是受微软Azure[10]云系统的启发。它非常满足HDFS修改RAID-6和谷歌冗余码分析。一些云文件系统比如微软Azure系统和谷歌文件系统均使用一个较大的块大小去创建一个只追加写工作量。写积累和缓冲直到块满然后将块封存，被封存的块被纠删编码后分配到存储结点。根据工作量[14,46],后续读取封存块通常访问比块大小更少的数据。当在云文件系上下文中检查纠删码时，两个性能关键操作发生。它们是降级读暂时不可用数据和从单一的故障恢复。尽管纠删码容忍多个同时出现的故障，单一故障占99.75%的恢复率[44]。恢复性能一直很重要,以前的工作包括架构的支持[13,21]和工作量优先恢复[22,48,45]。然而在云上规模尤为严重，大规模系统有频繁的部件故障使恢复成为了常规操作的一部分[16]。在云上不可用的频繁以及临时数据是由于降级读造成的。在故障和恢复期间，读被降级因为它们必须利用纠删码重构不可用存储结点的数据。比读无重构数据更慢的操作是必要的。临时不可用控制磁盘故障，无数据丢失的瞬态错误导致了90%以上的数据中心故障，归因于网络分区，软件问题，或者非磁盘硬件故障，出于这个原因，谷歌延迟了故障存储结点恢复达15分钟。当软件升级使存储结点离线时，临时不可用也会发生。在许多数据中心，软件更新是一个滚动的，连续的进程。只有最近出现的技术减少恢复纠删码的数据需求，最近的两个研究项目已经表明了在RAID-6编码RDP和EVENODD如何可以通过读码字符号的显著较小的子集从单一故障中恢复而不是以前的标准做法即从奇偶校验驱动中恢复[51,49]。恢复性能概括这些结果所有基于异或纠删码，基于恢复性能分析现有代码来区分它们和实验验证，减少在恢复中使用的数据量直接转换为云文件系统改进的性能，但不是典型RAID阵列配置。
一个找到从任意数量的磁盘故障恢复数据所需要的最佳数量的码元的算法，它也能最小化恢复期间数据读数量。这篇论文包括在RAID-6码中单一故障的分析用来表明稀疏码，比如伯劳姆-罗斯[5]，解放码[34]以及八度解放码[35]有最好的恢复性能以及相对于每一行独立地恢复的标准技术减少了约30%的数据。这篇论文也分析了能容忍三个及以上磁盘故障的编码，包括被谷歌[15]和微软Azure[10]使用的里德-所罗门码。
这个算法表明对于云文件系统最小化恢复数据能直接转化为改善I/O性能，在此之前最小化恢复I/O的工作是纯分析的，而我们的工作包含恢复性能测量。
里德-所罗门码对于降级读表现尤其差，因为它们必须读每一个降级读的所有数据磁盘和奇偶校验。由于RS码对于几乎所有编码环境的通用性和适用性导致RS码非常受欢迎，这是有问题的。
回旋里德-所罗门码是一种新类型编码在降级读性能方面超过所有其他编码，除此之外它还具有RS码编码性能和可靠性，回旋RS码在任意数量的磁盘和故障中能被创建。
- 相关工作
性能指标:纠删码一直被用来评价各种指标，比如编解码时CPU影响[3,11,37]，更新少量数据的开支[5,26,52]，无需再编码重配系统的能力[3,7,26]。不同纠删码的CPU性能变化很明显，然而对于所有编码，编码和解码的带宽数量级比磁盘带宽更快，因此当封存数据时决定性因素是写纠删码块到磁盘而不是计算编码。同样，当解码时无论是恢复还是降级读，决定性因素是读数据。
在云文件系统中更新少量数据没关系,追加只写模式和封存块消除整体的小型写入。系统重配置指更改编码参数:改流水线宽度或者增加/减少容错。这种类型的重构性对于云不太重要，因为每一个封存块定义了一个独立的流水线组，在云存储节点之间的传播不同于其他封存块。没有单一磁盘组能被重构，如果需要重构，每一个封存块要独立的被再编码。
在纠删码系统中有一些工作能降低I/O开销，尤其是WEAVER[19]，Pyramid[23]和Stepped
Combination Codes[18]已经被设计去降低恢复时的I/O开销。然而所有这些编码都是非MDS即意味着他们都不具有云存储系统需求的存储效率。REO RAID引擎在纠删码存储系统最小化I/O，但是其重点主要是在小规模存储系统中更新的效果。
云存储系统:在云文件系统中默认的存储策略是三副本，它已经在谷歌文件系统中被实现，在Hadoop中被采用等等。三副本一直很受青睐，因为其易于实现，良好读，恢复性能和可靠性。
三副本存储开销是一个问题，领先的系统设计师考虑把纠删码作为其替代，副本和纠删码的性能权衡被很好的理解，它在很多环境被评估比如对等文件系统[43,50]以及开源代码库[37]。
调查在云文件系统中使用RAID-6（两容错）纠删码表明它们以一个小的开销在可靠性和大型读性能方面将存储开销由200%减少到25%[14]。微软研究进一步探索成本/收益权衡和扩大分析新指标:电源比例和复杂性[53]。由于这些原因，Facebook正在他们的云基础设施中评估RAID-6以及纠删码[47]。
Ford等[15]已经针对谷歌云文件系统开发了可靠性模型，而且已经验证其能应对来自谷歌基础设施的一年工作量以及故障数据。他们的分析得出数据放置策略需要意识到故障分组和突发故障。他们也认为在相关故障情况下，编码需要减少暴露数据丢失才比RAID-6更能容错。他们认为里德-所罗门码能容忍3到4个磁盘故障。Windows Azure 存储因为同样的理由使用里德-所罗门码[10]。我们提出的回旋RS码继承了里德-所罗门码的全部属性以及改善了其降级读。
优先恢复:基于工作量的方法去改善恢复独立于纠删码选择并适用最小化I/O恢复算法以及我们提出的回旋RS码。这些包括:磁盘之间的负载均衡恢复[22]，恢复流行数据首先去减少降级读[48]，只恢复包含活数据的块[45]。同样地，恢复基础架构支持可被应用到我们编码，比如最小化数据拷贝[13]和奇偶去聚的硬件[21]。
减少恢复中使用的数据量最近才成为一个主题,对于EVENODD码[49]，行对角奇偶校验码[51]和RAID-6码第一结果已经给予了最小化恢复时间表。算法定义任意基于异或纠删码的恢复I/O下界和允许多编码在I/O恢复开销方面比较。再生码在存储结点间提供最佳的恢复带宽[12]。这个概念不同于最小化I/O;每个存储结点读所有可用数据以及计算并发送一个线性组合。
由于分布式系统其广域带宽会限制恢复性能，所以再生码被设计。正确的再生码准确的恢复丢失数据（不是一个新的线性数据组合）[39]。为了最小化恢复带宽。这些编码在某些情况下减少恢复I/O。恢复带宽和恢复数据大小的关系仍然是一个悬而未决的问题。
- 背景:纠删码存储
纠删码存储系统增加了容错冗余，尤其是n块磁盘系统被分块成k块数据磁盘和m块保存编码信息的磁盘。编码信息从纠删码数据被计算，对于实际的存储系统，纠删码一般有两种性能。首先它必须最大距离分隔（MDS），这意味着如果任何n块磁盘中的m块故障，它们的内容可以从k块存活的磁盘中重新计算。其次，它必须是系统的，这意味着k块数据磁盘保存未编码数据。
纠删码存储系统被分成多个流水线，它们是来自于n个磁盘的磁盘块的集合。块本身被分成多个码元，并有固定数量的码元为每条流水线的每块磁盘。我们表示这个数量为r，流水线执行编码和解码作为磁盘系统的独立单元。由于相对于数据磁盘，编码磁盘可能需要更大的灵活性，因此为了减轻可能发生的热点，在流水线接着流水线的基础上，磁盘的身份认证可以回旋。
为了达到我们分析的目的，我们关注于单流水线。有k个数据磁盘标记为D0, . . .,Dkminus;1，编码磁盘标记为C0, . . . ,Cmminus;1C0, . . . ,Cmminus;1。在这个流水线上有nr个码元。我们标记在数据磁盘i上的r个码元为di,0, di,1, . . . , di,rminus;1,在编码磁盘j上的r个码元为cj,0, cj,1, . . . , cj,rminus;1。我们描绘在图1的示例系统，在这个示例中，k=6，m=3(因此n=9)和r=4
图1：纠删码存储系统的一条流水线，参数是k=6，m=3和r=4
纠删码通常被定义使得每个码元是一个w比特字，这里的w通常很小，经常是1。然后编码字被定义为数据字的计算。比如，假设纠删码如图1被定义w=1，在这条流水线的每个码元将会由一个单比特组成。同时这简化了纠删码定义，它不直接映射到磁盘系统。它使得在封存块中的每个码元有更大的尺寸说的通，在千兆字节或者万兆字节的量级上，对于每个码元被分成w比特字，它们被编码和并行解码。
3.1 矩阵向量定义
所有纠删码可以以矩阵向量乘积来表示。示例如图2，k=6，m=3以及r=4和图1一样。在这个图纠删码正好被定义，它是一个柯西里德-所罗门码由Jerasure库优化[38].这个字大小，w等于1，因此所有码字被当作比特，算法完全是由异或运算组成。kr个数据码元被组织为kr元素比特向量。它们由nr*kr发生器乘以矩阵GT.1。结果是一个向量被称为编码字有nr个元素。这些是在这个流水线上的所有码元，在这个向量的每个r码元集合被存放在这个系统的不同磁盘。
从GT矩阵的前kr行组成一个认证矩阵，码字中的前kr码元包含数据。剩余mr码元从生成矩阵后mr行数据计算。当达到m块磁盘故障时，标准恢复方法是选择k个存活磁盘并从相对应的生成矩阵的kr行创建一个解码矩阵B。在k个存活磁盘中B-1与码字的结果产生原始数据[6,20,33]。
有许多适用于存储系统的MDS纠删码，里德-所罗门码[40]由k与m的所有值定义，一个里德-所罗门码r=1，w一定是2w_n这样。生成矩阵由范德蒙矩阵构造使得任意k*k范德蒙矩阵的子集是可逆的。有相当多的适用于存储系统[33,36,6,41]的里德-所罗门码的参考资料，加上众多的开源里德-所罗门编码库[42,38,30,31]。
柯西里德-所罗门编码使r=1，wgt;1的里德-所罗门码转化为r=w且w=1的编码。这样做的话，他们消除了伽罗华域昂贵的乘法并且用附加的异或运算代替它。有一个构造柯西里德-所罗门码的生成矩阵方法的指标数，Jerasure
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[146029]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
