英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries For Storage
（用于存储的开源纠删码库性能评估和测试）
摘要
在过去的五年中，大规模的存储设备需要比RAID-5（只容许单磁盘故障）更高的故障保护，从而导致对用于多磁盘故障的纠删码的一系列研究和开发。各种编码技术的众多开放源码实现可供普通公众使用。在本文中，我们在编码和解码方面对这些实现进行了详细的比较。我们的目标是比较代码和实现, 辨别理论是否与实践相匹配, 并证明参数选择 (特别是与内存有关的) 对代码的性能有重大影响。其他好处是为存储系统设计人员提供设计存储系统时编码性能方面的想法，以及确定以后的纠删码研究中可能产生重大影响的地方。
1 引言
近年来，纠删码已经转移到前台，以防止由多个磁盘组成的存储系统中的数据丢失。Allmydata [1]，Cleversafe [7]，Data Domain [36]，Network Appliance [22]和Panasas [32]等存储公司都开发了使用除RAID-5以外的纠删码来获得数据可用性的产品。学术项目，如LoCI [3]，Oceanstore [29]和Pergamum [31]也是这样做的。同样重要的是，诸如惠普[34]，IBM [12,13]和微软[15,16]等主要技术公司正在积极研究用于存储系统的纠删码。除了一些专有实现的纠删码外，还有许多可供下载的纠删码的开源实现[7,19,23,26,33]。这些项目的主要意图是提供存储系统开发者一个高质量的工具。因此，有必要了解这些代码和实现如何执行。
在本文中，我们比较了五种不同类型纠删码的五种开源实现的编码和解码性能：传统RS码[28]（Classic Reed-Solomon codes），柯西RS码[6]（Cauchy Reed-Solomon codes）奇偶校验码[4]（EVEN-ODD），行对角奇偶校验码[8]（Row Diagonal Parity），低密度RAID-6码[5, 24, 25]（Minimal Density RAID-6 codes），后3种编码在RAID-6系统上支持容双盘错。我们的实验不仅要比较代码，还要了解哪些功能和参数可以实现良好的编码性能。
我们总结的主要结果如下：
特别用途的 RAID-6 代码大大胜过其他的一般用途的代码。RDP以微弱的优势表现的更好在这些编码中；
只要注意生成良好的编码矩阵，柯西RS码明显的比传统RS码表现的更好；
为了在许多代码中实现良好的解码速度，称为特异编码混合重构[14]（Code-Specific Hybrid Reconstruction）的优化是必要的。
参数选择对实现执行的好坏有很大的影响。不仅仅需要考虑计算操作的数量，也需要注意代码与内存层次结构尤其是缓存的交互方式。
有必要达到RAID-6代码针对更高故障数量所显示的改进水平。
在测试的5个库中，Zfec [33]实现了最快的传统RS码，而Jerasure [26]实现了最快的其他码。
2 命名与纠删码
纠删码研究的历史中的一个不幸的后果是没有统一的纠删码命名法。我们主要借用Hafner等人的术语[14]，但在适当的时候尝试遵循更经典的编码术语（例如[5,21]）。
存储系统由n个相同大小的磁盘数组组成，k个保存数据信息，剩余的m个保存从数据中分析出来的奇偶校验信息，我们标记数据磁盘为D0 , . . . , Dk-1和奇偶校验盘C0 , . . . , Cm-1。典型的系统如图1所示。
图1 一个典型的纠删码存储系统
我们关注的是最大可分距离编码（MDS码），它具有这样的性质，即如果任何m个磁盘发生故障，原始数据可能被重建[21]。编码时, 将每个磁盘分区为固定大小的分条。每个奇偶校验分条都使用每个数据磁盘中的一个分条进行编码, 并且将编码在一起的 k m 个分条集合称为条带。因此，如图1所示，可以将每个磁盘视为一个条带的子集，并且可以将整个系统视为条带的集合。条带是独立编码的，因此如果需要在n个磁盘之间轮换数据和奇偶校验以进行负载平衡，可以通过切换每个条带的磁盘身份来实现。
2.1 里德所罗门码（Reed-Solomon (RS) Codes）
RS码有着最悠久的历史。每个分条单元是一个w位的字，w必须足够大以满足n≦2w 1。为了有效地操纵这些字，w通常受到限制，以使字落在机器字边界上：wisin;{8,16,32,64}。然而，只要n≦2w 1，用户可以自己选择w的值。大多数的实现选择w=8，因为用户系统的磁盘数量少于256个，选择w=8可以执行的很好。RS码把每个字看成为0-2w-1之间的一个数字，用伽罗华域算术（GF(2w)）对这些数字进行运算操作，伽罗华域算术定义了这些字的加法，乘法和除法，这样系统就是封闭的并且表现良好。
RS码的编码是简单的线性代数。生成矩阵是从范德蒙矩阵构造的，该矩阵乘以k个数据字以创建由k个数据和m个编码字组成的码字。图2描绘了此过程。
图2 k=4,m=2的RS编码，每个元素是0-2w-1之间的一个数
当磁盘失效时，为了解码出该失效数据分块，所有存活数据对应的剩余生成矩阵的逆矩阵与所有存活数据对应的列向量进行乘法运算，得出原始数据列。这个过程相当于求解一组独立的线性方程组。 从范德蒙矩阵构造GT确保了矩阵求逆总是成功的。
2.2 柯西RS码（Cauchy Reed-Solomon (CRS) Codes）
CRS码[6]以两种方式修改了RS码。首先，其使用了柯西矩阵而不是范德蒙矩阵来构造生成矩阵，其次，其将RS的乘法运算转换成异或运算。此修改将GT从w位字的n*k矩阵转换为wn*wk的位矩阵，和RS码一样，w也需要满足n≦2w 1。
不是操作单个的字，CRS码操作所有的分条。其中，一个分条又被分为w块，这些块可能很大。CRS编码只包含异或操作，一个编码块被构建随着所有的数据块进行了异或运算，图3 描绘了此过程。
图3 k=4,m=2的CRS编码
为了确保异或运算的效率，块的大小必须是机器字的倍数。分条的大小等于w倍的块大小。由于w不在与机器字有联系，w也就不再限制于[8,16,32,64]，而是w可以为任何值只要n≦2w。
CRS解码与RS相类似，删除与失效块有关的GT的所有行并将矩阵转置以获取丢失数据。
2.3奇偶校验码和行对角奇偶校验码（EVENODD and RDP）
EVENODD [4]和RDP [8]是针对RAID-6特殊情况开发的两种代码，即m=2的情况。通常在RAID-6中，第一个奇偶校验驱动标记为P，第二个标记为Q。P驱动和RAID-4系统中的奇偶校验驱动一样，Q驱动由具有不同模式的奇偶方程定义。
虽然它们的原始定义使用不同的术语，但EVENODD和RDP符合与CRS编码相同的范式，每个分条由w个分块组成。在EVENODD中，w被约束成k 1≦w而w 1是一个素数。在RDP中，w 1必须是素数并且k≦w。这两种码当w-k是最小的时候执行的最好。特别是，当k = w或k 1 = w时，RDP实现了最佳编码和解码性能（每编码字执行（k -1）次异或运算）。这两种代码的性能随着w-k的值的增加而下降。
2.4 低密度RAID-6码（Minimal Density RAID-6 Codes）
如果我们对RAID-6用生成位矩阵进行编码，那这个矩阵是很受限制的。特别地，GT的前kw行构成单位矩阵，并且为了P驱动是直接奇偶校验，接下来的w行必须包含k个单位矩阵。RAID-6规范中唯一灵活的是最后w行的组成。对于w的不同值，有三种不同的最小密度码结构：Blaum-Roth码w 1是素数，Liberation码w是素数，Liber8tion码w=8;这些编码有着相同的性能特征，它们编码时需要执行（k-1） (k-1)/2w次异或运算。因此，w越大它们执行的越好。它们的解码性能稍差，需要特异编码混合重构来实现接近最优的性能。
3开源库
我们测试了5种纠删码开源库，这些都是网上免费可用的库，范围从概念验证（例如Luby）到可用于实际系统（例如Zfec）的代码。我们还尝试了Schifra开源库[23]，这是免费的，但没有文档。主要是以下几个开源库：Luby、Zfec、Jerasure、Cleversafe、EVENODD/RDP（其中Jerasure支持特异编码混合重构）。
4编码测试
我们执行两组实验，一个编码，另一个解码。对于编码实验，我们试图测试一个大型数据文件的性能，并将其分割并编码为n = k m个分块，其中每个分块都驻留在不同的磁盘上，使得系统可容忍多达m个磁盘故障。我们的编码器读取数据文件，对其进行编码，并将其写入k m个数据/编码文件，以测量编码操作的性能。
由于内存优化是一个关注点，大型文件超过了多数计算机内存的容量，我们的编码器使用了两个固定大小的缓冲区，一个数据缓冲区被分为k块和一个编码缓冲区被分为m块，编码器从大文件中读取整个数据缓冲区的数据，将其编码到编码缓冲区，然后将两个缓冲区的内容写入k m个单独的文件。重复这个过程，直到文件完全编码，记录总时间和编码时间。处理过程如图4所示。
图4 编码器利用数据缓冲区和编码缓冲区分阶段对大文件进行编码
缓冲器的块被分割成s个分条，并且每个分条被分割成大小为w的字或w个固定大小为PS的块。更具体的说，每个块Di（Cj）被分进了分条DSi,0, . . . ,DSi,s-1（和CSj,0。。。CSj,s-1），中，每个分条的大小为wPS, 因此，数据和编码缓冲区大小取决于各种参数。具体的说，数据缓冲区的大小为kswPS，编码缓冲区的大小为mswPS。
编码是逐条带逐条带完成的，首先，数据分条DS0,0, . . . , DSk-1,0被编码成编码分条CS0,0, . . . , CSm-1,0。这就完成了条带0的编码，如图5所示，s条条带都以这种方式进行编码。
图5 数据和编码缓冲器如何分区与及条带0的编码（数据分条DS0,0, . . . , DSk-1,0被编码成编码分条CS0,0, . . . , CSm-1,0）
因此，编码器允许用户设置多个参数。这些参数是k，m，w（受代码约束），s和PS。
4.1用于测试的机器
我们使用了两台机器进行测试。两台都不是特别高端的产品，但都代表中档产品处理器，它们能够在最快磁盘的I / O速度限制范围内轻松进行编码和解码。第一台是配备32位2GHz Intel Core Duo处理器的Macbook，1GB的RAM，一个32KB的一级缓存和一个2MB的二级缓存。虽然机器有两个内核，但编码器只使用一个内核。作为基准，我们记录了memcpy()方法的速度为6.13GB/s和异或运算速度为2.43GB/s。
第二台机器为Dell工作台，采用运行频率为1.5GHz的英特尔奔腾4 CPU，1GB RAM，8KB一级缓存和256KB二级缓存。操作系统是Debian GNU Linux修订版2.6.8-2-686，这个机器是个32位的机器，memcpy()方法的速度为2.92GB/s和异或运算速度为1.32GB/s。
4.2大文件编码
我们的目的是衡量编码大型视频文件的实际性能。但是，处理大量的I/O导致了在性能时间方面的大量可变性。图6进行了举例说明。这个数据来源于Macbook，我们使用了一个256MB的视频文件用于输入，编码器的工作方式如第4节所述，k = 10和m = 6。但是，我们不执行真正的编码。 相反，我们只需将编码缓冲区的字节写入磁盘之前将其清零即可。 在图中，我们将数据缓冲区的大小从64 KB的小尺寸修改为256 MB视频文件本身的大小。
图6 读一个256MB视频的时间，执行了一个虚拟地编码（k=10,m=6）,并写入了16个数据/编码文件中
在图6中，每个数据点是以随机顺序执行十次的结果。给出了一个tukey图，其中包含最大值和最小值的条形图，包含第一到第三四分位数的框，中值处的散列标记和中值处的一个点。 虽然随着数据缓冲区增长到128 MB，性能有明显的改善趋势，但性能的变化是巨大的：对于许多运行来说，在15到20秒之间。 在文件上运行UNIX的拆分实用程序会显示出类似的可变性。
由于这种可变性，下面的测试将从编码器中删除
全文共8534字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13312]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
