信道编码之纠删码编码

简介

随着数据的存储呈现出集中化（以分布式存储系统为基础的云存储系统）和移动化（互联网移动终端）的趋势，数据可靠性愈发引起大家的重视。集群所承载的数据量大大上升，但存储介质本身的可靠性进步却很小，这要求我们必须以更加经济有效的方式来保障数据安全。

副本与纠删码都是通过增加冗余数据的方式来保证数据在发生部分丢失时，原始数据不发生丢失。但相较于副本，纠删码能以低得多的存储空间代价获得相似的可靠性。比如3副本下，存储开销为3，因为同样的数据被存储了三份，而在10+3（将原始数据分为10份，计算3份冗余）的纠删码策略下，存储开销为为1.3。采用纠删码能够极大地减少存储系统的存储开销，减少硬件、运维和管理成本，正是这样巨大的收益驱使各大公司纷纷将纠删码应用于自己的存储系统，比如Google、Facebook、Azure、EMC等等国际巨头，在国内以淘宝、华为、七牛云等为代表的公司也在自己的存储系统上应用了纠删码。

最典型的纠删码算法是里德-所罗门码（Reed-Solomon码，简称RS码）。RS码最早应用于通信领域，经过数十年的发展，其在存储系统中得到广泛应用，比如光盘中使用RS码进行容错，防止光盘上的划痕导致数据不可读；生活中经常使用的二维码就利用了RS码来提高识别的成功率。近年RS码在分布式存储系统中的应用被逐渐推广，一方面是分布式存储系统存储的存储容量和规模增大的需求；另一方面是由于纠删码编码速度在近年得到迅猛提升。随着对高性能纠删码引擎在实际系统中应用需要，也催生了对纠删码在具体系统中实现的各种优化手段。并为相关的决策者带来了困扰——究竟什么样的编码引擎才是高效的呢？

我们将以这个问题展开对纠删码技术的剖析，帮助企业更全面，深入的了解纠删码在存储系统中的应用并更好地做出技术选型。本系列文章将从纠删码的基本原理开始，随后引出如何判断编码引擎优劣这个问题，接下来将深度分析代码实现，帮助开发者顺利完成定制开发。

一、纠删码编码原理

在展开分析之前，我们先来看一看RS码是如何工作的。

编码：
为了计算冗余数据，首先我们需要选举出一个合适的编码矩阵。编码矩阵的上部为一个单位矩阵，这样保证了在编码后原始数据依然可以直接读取。通过计算编码矩阵和原始数据的乘积，可以到最终的结果。

解码：
当数据块发生丢失，在编码矩阵中去掉相应行，等式仍然保持成立。这为我们接下来恢复原始数据提供了依据。
为了恢复数据，首先我们求剩余编码数据的逆矩阵，等式两边乘上这个逆矩阵仍然保持相等。与此同时，互逆矩阵的乘积为单位矩阵，因此可以被消掉。那么所求得的逆矩阵与剩余块的数据的乘积就是原始数据了。

文章后面会给出具体的编码解码计算示例；这里只做理论说明；

数据编码以字节为单位，如果将被编码数据看做一个「数组」，「数组」中每个元素是一个字节，数据按照字节顺序被编码。编码过程是计算编码矩阵中元素和「数组」的乘积过程。为保证乘积的运算结果仍旧在一个字节大小以内（即0-255），必须应用到有限域。有限域上的算术运算不同于通常实数的运算规则。我们通常事先准备好乘法表，并在算术运算时对每一次乘法进行查表得到计算结果。早期的编码引擎之所以性能不佳，是因为逐字节查表的性能是非常低的。倘若能一次性对多字节进行查表以及相应的吞吐和运算，引擎的工作效率必将大幅度提升。

许多CPU厂商提供了包含更多位数的寄存器（大于64位），这类寄存器和相应支持的运算使得用户程序可以同时对大于机器位数的数据进行运算，支持这类寄存器和运算的指令称之为SIMD（SingleInstructionMultipleData）指令集，比如Intel支持的SSE指令集最大支持128bits的数据运算，AVX2指令集最大支持512bits的数据运算。它们为我们对一个「数组」数据分别执行相同的操作，提高了数据运算的并行性。目前，市面上所有高性能的纠删码引擎均采用了该项技术以提高编解码性能。

1. 数学理论工程化

以RS码为例，纠删码实现于具体的存储系统可以分为几个部分：编码、解码和修复过程中的计算都是在有限域上进行的；编码过程即是计算生成矩阵（范德蒙德或柯西矩阵）和所有数据的乘积；解码则是计算解码矩阵（生成矩阵中某些行向量组成的方阵的逆矩阵）和重建数据的乘积。

1.1有限域运算

有限域是纠删码中运算的基础域，所有的编解码和重建运算都是基于某个有限域的。不止是纠删码，一般的编码方法都在有限域上进行，比如常见的AES加密中也有有限域运算。使用有限域的一个重要原因是计算机并不能精确执行无限域的运算，比如有理数域和虚数域。

此外，在有限域上运算另一个重要的好处是运算后的结果大小在一定范围内，这是因为有限域的封闭性决定的，这也为程序设计提供了便利。比如在RS中，我们通常使用GF(28)，即0～255这一有限域，这是因为其长度刚好为1字节，便于我们对数据进行存储和计算。

在确定了有限域的大小之后，通过有限域上的生成多项式可以找到该域上的生成元，进而通过生成元的幂次遍历有限域上的元素，利用这一性质我们可以生成相应的指数表。通过指数表我们可以求出对数表，再利用指数表与对数表最终生成乘法表。

有了乘法表，我们就可以在运算过程中直接查表获得结果，而不用进行复杂的多项式运算了。同时也不难发现，查表优化将会成为接下来工作的重点与难点。

1.2选择生成矩阵

生成矩阵（GM,generatormatrix）定义了如何将原始数据块编码为冗余数据块，RS码的生成矩阵是一个n行k列矩阵，将k块原始数据块编码为n块冗余数据块。如果对应的编码是系统码（比如RAID），编码后包含了原始数据，则生成矩阵中包含一个k×k大小的单位矩阵和(n−k)×k的冗余矩阵，单位矩阵对应的是原始数据块，冗余矩阵对应的是冗余数据块。非系统码没有单位矩阵，整个生成矩阵都是冗余矩阵，因此编码后只有冗余数据块。通常我们会使用系统码以提高数据提取时的效率，那么接下来我们需要找到合适的冗余矩阵。

在解码过程中我们要对矩阵求逆，因此所采用的矩阵必须满足子矩阵可逆的性质。目前业界应用最多的两种矩阵是Vandermondematrix(范德蒙矩阵）和Cauchymatrix（柯西矩阵）。其中范德蒙矩阵历史最为悠久，但需要注意的是我们并不能直接使用范德蒙矩阵作为生成矩阵，而需要通过高斯消元后才能使用，这是因为在编码参数（k+m）比较大时会存在矩阵不可逆的风险。

柯西矩阵运算简单，只不过需要计算乘法逆元，我们可以提前计算好乘法逆元表以供生成编码矩阵时使用。创建以柯西矩阵为生成矩阵的编码矩阵的伪代码如下图所示：

     /*
     * 存储系统中的符号约定
     * k:数据块的个数
     * m:校验块的个数（就是code）
     * n:k+m，也就是数据块和校验块的个数总和。
     编码效率：r = k/m
     */
//这里有设定 行数为 rows=(k),cols(=k)为列数,编码生成矩阵为M
//先生成单位矩阵（在线性代数中，n阶单位矩阵，是一个 的方形矩阵，其主对角线元素为1，其余元素为0。 单位矩阵以In表示；如果阶数可忽略，或可由前后文确定的话，也可简记为I。）
for (j = 0; j < cols; j++)
{
    M[j][j] = byte(1);
}

//生成mxk的柯西矩阵，这里的cols=k,row = (k+m)
for(i = cols;  i< rows; i++)
{
     for(j = 0; j < cols; j++)
      {
          d = i ^ j;//这里的i j对应的是预先设定的两个矩阵中对应的元素值
          a = inverseTable[d];// 查乘法逆元表
          M[i][j] = byte(a)
      }
}

1.3矩阵求逆运算
有限域上的求逆方法和我们学习的线性代数中求逆方法相同，常见的是高斯消元法，算法复杂度是O(n3)。过程如下：

1. 在待求逆的矩阵右边拼接一个单位矩阵
   2.进行高斯消元运算
2. 取得到的矩阵左边非单位矩阵的部分作为求逆的结果，如果不可逆则报错

我们在实际的测试环境中发现，矩阵求逆的开销还是比较大的(大约6000ns/op)。考虑到在实际系统中，单盘数据重建往往需要几个小时或者更长（磁盘I/O占据绝大部分时间），求逆计算时间可以忽略不计。需要说明的是，发送端和接收端需要统一生成编码矩阵的算法，否则接收端没有办法根据缺失的包序号生成对应的矩阵，进行求逆运算。
在实际的测试环境中发现，矩阵求逆的开销还是比较大的(大约6000ns/op)。考虑到在实际系统中，单盘数据重建往往需要几个小时或者更长（磁盘I/O占据绝大部分时间），求逆计算时间可以忽略不计。

下面我给出了一个我自己手写的一个简单的计算示例：
假设编码生成矩阵和源数据包如下所示

假设传输过程中丢失了第二个包（这里用8代替，实际计算中按字节计算）和最后一个冗余包（22）丢失，接收端只收到了数据包 4、9、1 和冗余包22，则下面我们一起恢复原始数据包；

二、编码引擎评判标准

我们将从以下几个关键指标来对编码引擎进行分析：

1、高编/解码速度；

2、参数可配置；

3、代码简洁、稳定；

4、降低修复开销等。

2.1 高编/解码速度

无须多言，编/解码性能是最基本也是最重要的指标。对于一款性能优异的引擎来说，应该同时满足以下几个指标：

根据CPU的特性自动选择最优的指令集进行加速。上文提到，依赖于SIMD技术RS码编码性能有了大幅度的提高。其中，我们可以利用多种指令集扩展以供加速，引擎应该能够自主发现最优解

不亚于目前最出色的几款引擎的性能表现（详见第三章著名引擎对比）

通过SIMD加速，性能会有大幅度攀升。我们还可以将逐字节查表（下称基本方法）的编码速度与利用SIMD技术加速的编码速度做对比，两者应该有数倍的差距

编/解码速度稳定，对于不同尺寸的数据块会有相近的性能表现。由于系统缓存的影响，当被编码数据的大小和缓存大小相当时，编码应该具有最快的速度。当编码数据的大小大于缓存大小时，内存带宽成为编码速度的瓶颈，文件大小和编码时间呈现近似线性关系。这样，数据编码时间是可预期的，用户的服务质量也是可保障的。在实际中，我们对于大文件进行定长分块，依次编码，分块大小和缓存大小保持一定关系。

下图展示了在10+4策略下，不同大小的数据块的编码速度变化趋势[2]：

注：

测试平台：MacBookPro(Retina,13-inch,Mid2014)，2.6GHzi5-4278U(3MBL3CacheSize),8GB1600MHzDDR3

编/解码速度计算公式:在k+m策略下，每一个数据块的尺寸计作s,编/解码m个数据块的耗时计作t,则速度=(k*s)/t

测试方法：在内存中生成随机数据，运行若干次编／解码，取平均值

分别执行了avx2指令集,ssse3指令集,基本方法(base)这三种编码方案

被编码文件尺寸指，每一个数据块的尺寸与总的数据块个数的乘积，即原始数据的总大小

作为对比，利用go语言自带的copy函数（copy），对k个数据块进行内存拷贝。copy同样使用了SIMD技术进行加速

另外，解码速度应该大于或等于编码速度（视丢失的数据块数量而定），下图为10+4策略下修复不同数量的原始数据的速度对比[2]：

注：

测试平台与上文的编码测试相同

lostdata=丢失数据块数目（个）

原始数据块每块大小为128KB，总大小为1280KB

2.2 参数可配置

一款合理的纠删码引擎必须能做到编码策略在理论范围内可随意切换，这指的是如果要将编码策略进行变化时，仅需从接口传入不同参数而不需要改动引擎本身。这大大降低了后续的开发和维护所需要的精力。一个可配置参数的编码引擎可以根据数据的冷热程度和数据重要程度选择不同的编码系数，比如可靠性要求高的数据可以选择更多冗余。

2.3 代码简洁、稳定

为了利用SIMD加速我们不得不引入汇编代码或者封装后的CPU指令，因此代码形式并不常见。为了增强可读性可将部分逻辑抽离到高级语言，然而会损失部分性能，这其中的利弊需要根据团队的研发实力进行权衡。

接下来的可维护性也非常重要。首先是接口稳定，不会随着新技术的引入而导致代码大规模重构；另外代码必须经过有合理的测试模块以便在后续的更新中校验新算法。

比如早先的SIMD加速是基于SSE指令集扩展来做的，随后Intel又推出AVX指令集进一步提高了性能，引擎应该能即时跟上硬件进步的步伐。再比方说，再生码[5]（可以理解为能减少修复开销的纠删码）是将来发展的趋势，但我们不能因为算法的升级而随意改变引擎的接口。

2.4 降低修复开销

纠删码的一大劣势便是修复代价数倍于副本方案。k+m策略的RS码在修复任何一个数据块时，都需要k份的其他数据从磁盘上读取和在网络上传输。比如10+4的方案下，丢失一个数据块将必须读取10个块来修复，整个修复过程占用了大量磁盘I/O和网络流量，并使得系统暴露在一种降级的不稳定状态。因此，实际系统中应该尽量避免使用过大的k值。

再生码便是为了缓解数据修复开销而被提出的，它能够极大减少节点失效时所需要的吞吐的数据量。然而其复杂度大，一方面降低了编码速度，另外一方面牺牲了传统RS码的一些优秀性质，在工程实现上的难度也大于传统纠删码。

三、著名引擎对比

目前被应用最广泛并采用了SIMD加速的引擎有如下几款：

1.Intel出品的ISA-L[4]

2.J.S.Plank教授领导的Jerasure[5]

3.klauspost的个人项目（inGolang)[6]

这三款引擎的执行效率都非常高，在实现上略有出入，以下是具体分析：

3.1 ISA-L

intel®-storage-acceleration-library Intel存储加速库，包括两个大类：加密和非加密的。非加密的 crc，izip，erase-code，加密的包括sha512，sha256，md5，sha1等。

核心技术就是使用intel sse/avx/avx2/avx256的扩展指令，并行运算多个流的方法。单线程比openssl要快2～8倍。

现在ISA-L已经开源：

https://github.com/01org/isa-l

https://github.com/01org/isa-l_crypto

---

http://www.zhixing123.cn/computer/57905.html

纠删码作为ISA-L库所提供的功能之一，其性能应该是目前业界最佳。需要注意的是Intel采用的性能测试方法与学术界常用的方式略有出路，其将数据块与冗余块的尺寸之和除以耗时作为速度，而一般的方法是不包含冗余块的。另外，ISA-L未对vandermonde矩阵做特殊处理，而是直接拼接单位矩阵作为其编码矩阵，因此在某些参数下会出现编码矩阵线性相关的问题。好在ISA-L提供了cauchy矩阵作为第二方案。

ISA-L之所以速度快，一方面是由于Intel谙熟汇编优化之道，其次是因为它将整体矩阵运算搬迁到汇编中进行。但这导致了汇编代码的急剧膨胀，令人望而生畏。

另外ISA-L支持的指令集扩展丰富，下至SSSE3，上到AVX512，平台适应性最强。

3.2 Jerasure2.0

不同于ISA-L直接使用汇编代码，Jerasure2.0使用C语言封装后的指令，这样代码更加的友好。另外Jerasure2.0不仅仅支持GF(2⁸)有限域的计算，其还可以进行GF(2⁴)-GF(2¹²⁸)之间的有限域。并且除了RS码，还提供了CauchyReed-Solomoncode（CRS码）等其他编码方法的支持。它在工业应用之外，其学术价值也非常高。目前其是使用最为广泛的编码库之一。目前Jerasure2.0并不支持AVX加速，尽管如此，在仅使用SSE的情况下，Jerasure2.0依然提供了非常高的性能表现。不过其主要作者之一JamesS.Plank教授转了研究方向，另外一位作者Greenan博士早已加入工业界。因此后续的维护将是个比较大的问题。

3.3 klauspost的ReedSolomon

klauspost利用Golang的汇编支持，友好地使用了SIMD技术，此款引擎的SIMD加速部分是目前我看到的实现中最为简洁的，矩阵运算的部分逻辑被移到了外层高级语言中，加上Golang自带的汇编支持，使得汇编代码阅读起来更佳的友好。不过Go并没有集成所有指令，部分指令不得不利用YASM等汇编编译器将指令编译成字节序列写入汇编文件中。一方面导致了指令的完全不可读，另外一方面这部分代码的语法风格是Intel而非Golang汇编的AT&T风格，平添了迷惑。这款引擎比较明显的缺陷有两点：1.对于较大的数据块，编码速度会有巨大的下滑；2.修复速度明显慢于编码速度。

3.4 编码速度对比

我在这里选取了IntelISA-L（图中intel),klauspost的ReedSolomon(图中k),以及自研的一款引擎2这三款引擎进行编码效率的对比,这三款引擎均支持avx2加速。测试结果如下：

注：

编码速度计算公式，测试方法与上一节相同。其中isa-l默认的速度计算方式与公式有冲突，需要修改为一致

测试平台：AWSt2.microIntel®Xeon®CPUE5-2676v3@2.40GHz,Memory1GB

编码方案：10+4

klauspost的引擎默认开了并发，测试中需要将并发数设置为1

参考文章：
高性能纠删码编码
基于柯西矩阵的Erasure Code技术详解

---