如何选择并实现高性能纠删码编码引擎(上）(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.1ISA-L

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

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

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

3.2Jerasure2.0

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

3.3klauspost的ReedSolomon

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

3.4编码速度对比

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

注：

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

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

编码方案：10+4

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

四、自己实现一款引擎

（编辑：ASP站长网）