如何选择并实现高性能纠删码编码引擎案例(上）

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

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

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

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

本文作为系列首篇，我们将一起探讨纠删码的编码原理与如何选择编码引擎这两个问题。

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

下图展示了3+2（3份数据，2份冗余）下对2字节长度的数据进行编码与数据修复过程：

 

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

下面介绍解码过程，当1，2两块数据丢失，即：

当数据块发生丢失，在编码矩阵中去掉相应行，等式仍然保持成立。这为我们接下来恢复原始数据提供了依据。

原始数据的修复过程如下：

为了恢复数据，首先我们求剩余编码数据的逆矩阵，等式两边乘上这个逆矩阵仍然保持相等。与此同时，互逆矩阵的乘积为单位矩阵，因此可以被消掉。那么所求得的逆矩阵与剩余块的数据的乘积就是原始数据了。

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

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

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

1、高编/解码速度；

2、参数可配置；

3、代码简洁、稳定；

4、降低修复开销等。

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

根据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

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

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

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

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

纠删码的一大劣势便是修复代价数倍于副本方案。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]

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

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

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

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

不同于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博士早已加入工业界。因此后续的维护将是个比较大的问题。

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

我在这里选取了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

可能是由于对开源库后续维护问题的担忧，也有可能是现有方案并不能满足企业对某些特定需求和偏好，很多公司选择了自研引擎。那么如何写出高效的代码呢？在上面的简单介绍中，受限于篇幅我跳过了很多细节。比如SIMD技术是如何为纠删码服务的，以及如何利用CPUCache做优化等诸多重要问题。我们会在后续的文章中逐步展开其实现，欢迎大家继续关注。