网易视频云技术分享：ReedSolomon纠删码.docx

网易视频云技术分享：ReedSolomon纠删码.docx网易视频云技术分享:ReedSolomon纠删码网易视频云是网易倾力打造的-款基于云计算的分布式多媒体处理集群和专业音视频技术,为客户提供稳定流畅、低时延、高并发的视频直播、录制、存储、转码及点播等音视频的PASS服务。在线教育、远程医疗、娱乐秀场、在线金融等各行业及企业用户只需经过简单的开发即可打造在线音视频平台。现在,网易视频云转载相关文章,与大家分享一下ReedSolomon纠删码。纠删码是存储领域常川的数据冗余技术,相比多副本复制而言,纠删码能够以更小的数据冗余度获得更高数据可靠性。ReedSolomonCoding是存储领域常用的一种纠删码,它的棊本原理如卜「:给定n个数据块d1,d2,...,dn,n和一个正整数m,RS根据n个数据块生成m个校验块,c1, cnrio对于任意的n和m,从n个原始数据块和m个校验块中任取n块就能解码出原始数据,即RS最多容忍m个数据块或者校验块同时丢失(纠删码貝能容忍数据丢失,无法容忍数据篡改,纠删码正是得名与此)。编码原理RS编码以word为编码和解码单位,大的数据块拆分到字长为w的word(字长w取值一般为8或者16位),然后对word进行编解码。所以数据块的编码原理与word编码原理没什么差别,为论述方便,后文中变量Di,Ci将代表一个wordo首先,把输入数据视为向量D=(D1,D2,Dn),编码后数据视为向量(D1,D2,...,Dn,C1,C2,..,Cm),RS编码可视为如图1所示矩阵运算。下图最左边是编码矩阵,矩阵上部是单位阵(n行n列),下边是Vandermonde矩阵B(m行n列),vandermode炬阵如图2所示,第i行,第j列的氐数值为j^(i-1)oZ所以采用Vandermonde矩阵的原因是,RS数据恢复算法要求编码矩阵任意n*n子矩阵可逆。♦图1:RS纠删码编码运算数据恢复原理RS最多能容忍m个删除错谋。数据恢复原理的过程如下:(1)从编码矩阵屮删去丢失数据块和丢失编码块对应行。假设D1、C2丢失,根据图1所示RS编码运算等式,我们得到如FB'以及等式。T[DI00000DI000000DB”BnB”B刖B理B対B,Bjs♦'S—T—T—T—1016一巧瓦-9『一zivllrv=s图2:vandermode矩阵(2)由于B,是可逆的,两边乘上B'逆矩阵。oR"Survivors(3)得到如下原始数据D的计算公式(4)对D重新编码,得到丢失的校验码矩阵求逆采川高斯消元法,需要进行实数加减乘除四则运算,无法作川丁-字长为w的二进制数据。为了解决这个问题,RS采用伽罗华群GF(2八w)中定义的四则运算法则。GF(2^w)域有"w个值,毎个值都对应一个低于w次的多项式,这样域上的四则运算就转换为多项式空间的运算[2]。GF(2八w)域中的加法就是XOR,乘法比较特殊,需要维护两个大小为2^w-1的表格:log表gflog,反log表gfilog。乘法公式:a*b=gfilog(gflog(a)+fglog(b))%(2八w-1)CRS(CauchyReedSolomon)RS纠删码的计算代价较高,瓶颈在