英语原文共 14 页
A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries For Storage
James S. Plank
Jianqiang Luo agrave;
Catherine D. Schuman
Lihao Xu agrave;
Zooko Wilcox-Orsquo;Hearn
Appearing in:
FAST-09: 7th USENIX Conference on File and Storage Technologies，
San Francisco， CA， February， 2009.
EECS Department
University of Tennessee
Knoxville， TN 37996
- Computer Science Department Wayne State University
AllMyData， Inc.
Contact Author: James S. Plank: plank@cs.utk.edu.
Paper home: http://www.cs.utk.edu/tilde;plank/plank/papers/FAST-2009.html
开源纠删码库在存储方面的性能评估和检验
James S. Plank Jianqiang Luo Catherine D. Schuman
University of Tennessee Wayne State University University of Tennessee
plank@cs.utk.edu
LihaoXu Zooko Wilcox-Orsquo;Hearn
Wayne State University AllMyData, Inc.
摘要
在过去的五年中，大规模的存储装置已经超越RAID-5的故障保护，引起对多个磁盘故障的纠删码的研究和开发。一般公众可以使用各种编码技术的众多开源实现。在本文中，我们在编码和解码方案中对这些实现进行了直接的比较。我们的目标是比较编码和实现，来辨别理论是否与实际相匹配，并演示参数选择（尤其涉及内存参数）如何对编码的性能产生巨大影响。其他好处是让存储系统设计人员能够在设计存储系统时了解编码性能方面的预期，并确定进一步纠删码研究可能产生最大影响的位置。
1 介绍
近年来，纠删码已经发挥作用，用来防止由多个磁盘组成的存储系统中的数据丢失。诸如Allmydata， Cleversafe， Data Domain， Network Appliance和Panasas这样的存储公司都在生产使用超出RAID-5的纠删码的产品，以实现数据可用性。LoCI， Oceanstore和 Pergamum等学术项目也在做同样的事。同样重要的是，像Hewlett Packard ， IBM 和 Microsoft 这些主要的技术公司都在积极研究存储系统中的纠删码。
除了纠删码的专有实现外，还有各种纠删码的众多开源实现可供下载。这些项目中大多数目的是给存储系统开发人员提供高质量的工具。因此，有必要去了解这些代码和实现时如何执行。
在本文中，我们比较五种不同类型纠删码(经典里德-所罗门码，柯西里德-所罗门码，奇偶码，行对角EVENODD (RDP) 和最小密度RAID-6码 )的五种开源实现的编码和解码性能。后三种编码是特定于可以容许两个故障的RAID-6系统。我们的研究不仅要比较编码，还要了解哪些特征和参数会带来好的编码性能。
我们总结主要结果如下：
bull;专用RAID-6码远胜于通用RAID-6码。RDP以微弱的优势在其中表 现最佳。
bull;只要注意生成良好的编码矩阵，柯西-里德-所罗门码会显著优于经典里德-所罗门码。
bull;一种称为特定编码混合重建的优化对在很多编码中实现良好的解码速度是有必要的。
bull;参数选择对实现的执行情况产生巨大的影响。不仅必须考虑计算操作的数量，还要考虑编码如何与内存层次结构(尤其是缓存)交互。
bull;需要达到RAID-6码表现的更高失败次数的改进水平。
在测试的五个库中，最快实现经典里德-所罗门编码，在别的编码中实现最快。
2 命名和纠删码
纠删码研究历史的一个不幸结果是，对于纠删码没有一个统一的命名。我们主要从Hafner等借用术语，但在适当的时候尝试遵循更经典的编码术语(例如图5.21)。
我们的存储系统是由 个硬盘组成。每个磁盘大小相同。它们中的 个磁盘保存数据，剩下的 个磁盘保存编码信息。编码信息通常称为校验，它是根据数据计算的。我们标记数据磁盘 ，校验磁盘 。典型系统如图一所示。
图1:带有纠删码的经典存储系统
我们关注的是极大距离可分码(MDS)，它具有以下特性:假如任意 个磁盘故障，原始数据可能会被重建。编码的时候，把每一个磁盘分成固定大小的条。每个校验条使用来自每个数据磁盘的一个条进行编码，并且一起编码的 个条的集合称为条带。因此，如图1，可以把每一个磁盘视为条的集合，并且可以将整个系统视为条带的集合。每个条带都是独立编码的，因此如果想要在 个磁盘之间轮换数据和校验条以实现负载平衡，只需要通过切换每个条带的磁盘标识。
2.1 里德-所罗门编码
里德-所罗门编码 拥有最久远的历史。条单元是一个 位字，其中 必须足够大以满足 。因此可以有效的操控字， 通常受到约束，使得字落在机器字边界上：。无论如何， 只要 ，就可以根据用户的判断选择 的值。大多数实现选择 ，因为他们的系统包含少于 256 个磁盘，而 表现最佳。里德-所罗门编码将每个单词视为 0 到 ，并使用有限域 对这些数字进行操作，而 对这些词定义了加法、乘法和除法，使得系统闭合并且表现良好。
使用里德-所罗门码进行编码是简单的线性代数。生成矩阵是由范德蒙矩阵构造而成，该矩阵乘以 个数据字以创造由 个数据和 个编码字组成的码字。我们在图2中描述了这个过程(注意，为了使图片更加清晰我们绘制了生成矩阵的转置矩阵)。
图2:对于 和 的里德-所罗门编码。每一个元素是0到 之间的数字。
当磁盘发生故障时，可以通过删除 的行，求逆，将幸存字与逆相乘进行解码。该过程相当于求解一组独立的线性方程。由范德蒙矩阵构造的 的结果确保矩阵求逆总能成功。
在 中，加法等效于按位XOR，乘法更复杂，通常使用乘法表或者离散对数表 实现。因此，里德-所罗门编码被认为是高成本的。有一些里德-所罗门编码的开源实现，我们将在第3节中仔细介绍。
2.2 柯西里德-所罗门编码
CRS编码以两种方式修改了RS编码。首先，它们使用了一种采用柯西矩阵而非范德蒙矩阵的生成矩阵的结构。其次，它们通过将其转换为额外的XOR运算来消除RS码的昂贵的乘法计算。注意，这第二个修改也可以应用于基于范德蒙的RS码。这种修改把GT从一个 位字的 矩阵转换为一个 的位矩阵。与RS编码一样，必须选择 使得 。
CRS码不是对单个字操作而是对整个条进行操作。特别地，条被分成 个包，并且这些包可能很大。编码操作现在仅仅涉及到XOR操作，构建一个编码包作为所有在 的编码包的行有一位的数据包的XOR。图3描述了这个过程，说明了如何构建最后一个编码包作为六个 最后一行识别的数据包的XOR。
图3: 且 的CRS示例
要使XOR高效，包的大小必须为机器字长的倍数。因此条的大小是包的大小的 倍。由于 不再与机器字的大小有关，所以 不必约束为；反言之，只要满足 ， 可以选择任意值。
CRS解码和 RS码类似—所有与故障包相关的的行都被删除，矩阵求逆然后被用于重新计算丢失的数据。
由于CRS编码的性能与中1的个数直接相关，构造柯西矩阵的研究少于原始CRS结构的研究。库使用额外的矩阵变化来进一步改进这些矩阵。此外，在 的特定情况下，库使用先前所有柯西矩阵的枚举结果，来对所有 采用可证明的最佳的矩阵。
2.3 EVENODD和RDP
EVENODD和RDP是两种当 时为RAID-6的特殊情况开发的编码。在传统RAID-6中，第一个EVENODD驱动器标记为P，第二个标记为Q。P驱动器相当于RAID-4系统中EVENODD驱动器，Q驱动器由定义具有不同模式的EVENODD方程式定义。
虽然它们的原始规范使用不同的术语，EVENODD和RDP适合CRS编码相同的范例，条由 个数据包组成。在EVENODD中， 被约束为 ，并且 是一个素数。在RDP中， 必须位素数并且 。两种编码都在 最小的时候性能最佳。特别地，当 或 的时候，RDP实现每个编码字的 个XOR运算的最佳编码和解码性能。两种编码性能都随 的增加而降低。
2.4 最小密度RAID-6编码
如果我们用生成位矩阵对RAID-6进行编码，则矩阵非常受限。特别地，的第一个 行组成单位矩阵，并且为了使P驱动器变为直接的EVENODD，下 行必须包含 个单位矩阵。在RAID-6中唯一的灵活性是最后 行的组成。在中，Blaum and Roth 证明了当 时，剩下的 行必须要有至少 个1来让编码成为MDS。我们把 实现这个最低边界的 MDS 矩阵定义为最小密度编码。
对于 的不同值，最小密度编码有三个不同的结构:
当 为素数时，Blaum – Roth码。
当 为素数时，Liberation码。
当 时，Liber8tion码。
这些编码具有相同性能特征。它们使用每编码字个XOR运算进行编码。因此，当 很大时，它们表现得更好，达到 的渐近最优性。 它们的解码性能稍差，需要一种称为特定于代码的混合重构技术来实现接近最佳的性能。
当修改单个数据时，最小密度编码也可以实现接近最佳的更新性能。 这种性能明显优于EVENODD和RDP，后者的性能大约为1.5。
2.5 Anvin的RAID-6 优化
2007年，Anvin发布了针对RAID-6的RS编码优化。对于此优化，对应于P驱动器的 行包含全部1，因此P驱动器可以是EVENODD。 对应于Q驱动器的行包含列i（零索引）中的 中的数字 ，因此可以通过将驱动器i的数据连续XOR进入Q驱动器并将总和乘以2来计算Q驱动器的内容。 由于乘以2可以比 中的一般乘法快得多地实现，这优化了编码相对于标准RS实现的性能。 解码仍未得到优化。
3.开源库
我们测试了五个开源纠删码库。 这些都是来自互联网上各种来源的免费库，其范围从简短的概念证明（例如）到旨在用于实际系统的调整和支持的代码（例如）。 我们还尝试了Schifra开源库，它是免费的，但没有文档。 我们无法实现编码器和解码器来与其他库进行令人满意的比较。 我们按时间顺序呈现它们。
：CRS编码是在1990年代中期在加利福尼亚州伯克利的ICSI实验室开发的。 作者于1997年发布了他们代码的C版本，可从ICSI的网站获得。 该库支持 ， ，和数据包大小的所有设置。 矩阵采用中的原始结构，这些结构未经优化以最小化1的数量。
：用于纠删码的库自2007年开始开发，但其根源已经存在了十多年。 建立在Rizzo为可靠多播开发的RS编码库之上。该库基于Karn等以前的工作，并且已经广泛使用和调整。 当 时，基于范德蒙矩阵。最新版本（1.4.0）发布于2008年1月。 该库是可编程的，可移植的并且得到作者的积极支持。 它包括C，Python和Haskell中的命令行工具和API。
：是2007年发布的C库，支持各种纠删码，包括RS编码，CRS编码，通用生成矩阵和位矩阵编码，以及最小密度RAID-6编码。RS编码可以基于范德蒙或柯西矩阵， 可以是8，16或32。Anvin的优化包括在RAID-6应用中。对于CRS编码，为RAID-6采用可证明的最佳编码矩阵，并为更大的 值构建优化的矩阵。此外，还支持三个最小密度RAID-6代码。为了提高位矩阵码的性能，尤其是解码性能，包括特定编码的混合重建优化。是在GNU LGPL下发布的。
：2008年
资料编号：[5118]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
