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

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

作者介绍：

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

前言：

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

副本与纠删码都是通过增加冗余数据的方式来保证数据在发生部分丢失时,原始数据不发生丢失.但相较于副本,纠删码能以低得多的存储空间代价获得相似的可靠性.比如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、降低修复开销等.

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参数可配置

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!