如何选择并实现高性能纠删码编码引擎（下)

《如何选择并实现高性能纠删码编码引擎（下)》要点：
本文介绍了如何选择并实现高性能纠删码编码引擎（下)，希望对您有用。如果有疑问，可以联系我们。

作者介绍：
徐祥曦,七牛云工程师,独立开发了多套高性能纠删码/再生码编码引擎.柳青,华中科技大学博士,研究方向为基于纠删码的分布式存储系统.
前言：

在上篇《如何选择纠删码编码引擎》中,我们简单了解了Reed-SolomonCodes(RS码)的编／解码过程,以及编码引擎的评判标准.但并没有就具体实现进行展开,本篇作为《纠删码技术详解》的下篇,我们将主要探讨工程实现的问题.

这里先简单提炼一下实现高性能纠删码引擎的要点：首先,根据编码理论将矩阵以及有限域的运算工程化,接下来主要通过SIMD指令集以及缓存优化工作来进行加速运算.也就是说,我们可以将RS的工程实现划分成两个基本步骤：

将数学理论工程化

进一步的工程优化

这需要相关研发工程师对以下内容有所掌握：

有限域的基本概念,包括有限域的生成与运算

矩阵的性质以及乘法规则

计算机体系结构中关于CPU指令以及缓存的理论

接下来,我们将根据这两个步骤并结合相关基础知识展开实现过程的阐述.

一理论工程化

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

1.1有限域运算

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

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

在确定了有限域的大小之后,通过有限域上的生成多项式可以找到该域上的生成元[1],进而通过生成元的幂次遍历有限域上的元素,利用这一性质我们可以生成相应的指数表.通过指数表我们可以求出对数表,再利用指数表与对数表最终生成乘法表.关于本原多项式的生成以及相关运算表的计算可以参考我在开源库中的数学工具.[2]

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

1.2选择生成矩阵

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

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

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

1.3矩阵求逆运算

有限域上的求逆方法和我们学习的线性代数中求逆方法相同,常见的是高斯消元法,算法复杂度是O(n^3).过程如下：

在待求逆的矩阵右边拼接一个单位矩阵

进行高斯消元运算

取得到的矩阵左边非单位矩阵的部分作为求逆的结果,如果不可逆则报错

我们在实际的测试环境中发现,矩阵求逆的开销还是比较大的(大约6000ns/op).考虑到在实际系统中,单盘数据重建往往需要几个小时或者更长(磁盘I/O占据绝大部分时间),求逆计算时间可以忽略不计.

二进一步的工程优化

2.1利用SIMD加速有限域运算

从上一篇文章可知,有限域上的乘法是通过查表得到的,每个字节和生成矩阵中元素的乘法结果通过查表得到,图1给出了按字节对原始数据进行编码的过程(生成多项式为x^8+x^4+x^3+x^2+1).对于任意1字节来说,在GF(2^8)内有256种可能的值,所以没有元素对应的乘法表大小为256字节.每次查表可以进行一个字节数据的乘法运算,效率很低.

图 1,按字节对原始数据进行编码

目前主流的支持SIMD相关指令的寄存器有128bit(XMM指令)、256bit(YMM指令)这两种容量,这意味着对于64位的机器来说,分别提供了2到4倍的处理能力,我们可以考虑采用SIMD指令并行地为更多数据进行乘法运算.

但每个元素的乘法表的大小为256Byte,这大大超出了寄存器容纳能力.为了达到利用并行查表的目的,我们采用分治的思想将两个字节的乘法运算进行拆分.

字节y与字节a的乘法运算过程可表示为,其中y(a)表示从y的乘法表中查询与x相乘结果的操作：

y(a)=y*a
我们将字节a拆分成高4位(al)与低4位(ar)两个部分,即(其中⊕为异或运算)：

a=(al<<4)⊕ar

这样字节a就表示为0-15与(0-15<<4)异或运算的结果了.

于是原先的y与a的乘法运算可表示为：

y(a)=y(al<<4)⊕y(ar)

由于ar与al的范围均为0-15(0-1111),字节y与它们相乘的结果也就只有16个可能的值了.这样原先256字节的字节y的乘法表就可以被2张16字节的乘法表替换了.

下面以根据本原多项式x^8+x^4+x^3+x^2+1生成的GF(2^8)为例,分别通过查询普通乘法表与使用拆分乘法表来演示16*100的计算过程.

16的完整乘法表为：

计算16*100可以直接查表得到：

table[100] = 14

16 的低 4 位乘法表,也就是 16 与 0-15 的乘法结果：

lowtable=[0163248648096112128144160176192208224240]

16的高4位乘法表,为16与0-15<<4的乘法结果：

hightable=[02958391161057883232245210207156129166187]

将100(01100100)拆分,则：

100 = 0110 << 4 ⊕ 0100

在低位表中查询0100(4),得：

lowtable[4]=64
在高位表中查询 0110(6),得：

hightable[6]=78

将两个查询结果异或：

result=64^78=1000000^1001110=1110=14

（编辑：ASP站长网）