注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

网易杭州 QA Team

务实 专注 分享 做有态度的QA

 
 
 
 
 

日志

 
 

纠删码算法知识普及  

来自崔晓晴   2015-10-16 11:02:08|  分类: 默认分类 |举报 |字号 订阅

  下载LOFTER 我的照片书  |
概述
纠删码(erasure coding,EC)是一种数据保护方法,它将数据分割成片段,把冗余数据块扩展、编码,并将其存储在不同的位置,比如磁盘、存储节点或者其它地理位置。
下图简单阐述了纠删码原理:D1…D10 这10个数据块(甚至可以理解为单个磁盘),P1、P2、P3、P4是对这10个数据块计算出来的纠删码块,这14个块分布在不同的server磁盘上。

纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team


根据10个数据块算出4个校验块,即可以容忍任意4个Block的丢失
存储开销: 1.4x = 14/10
任意一个块损坏,需要通过网络读取10个Block进行恢复

纠删码相对于之前多副本的区别

存储空间降低 :原来3副本需要3倍空间存储一份数据,纠删码只需要1.4倍空间存储一份数据。

可靠性:
3副本允许坏的副本数:2/3
纠删码允许坏的副本数:4/14

额外负担:
计算量(只要有一个坏盘就得通过网络读出n倍的数据并重新计算)
数倍的网络负载

 纠删码算法-Reed-solomon算法原理

基于线性代数(假设n=5,m=3)即5个数据块,通过一定的计算方式(乘上一个(n+m)*n的矩阵,然后得出一个(n+m)*1的矩阵,根据矩阵特点可以知道得出的结果矩阵中前面5个值与原来的五个数据块的值相等,而最后3个则是计算出来的校验块)。这个B矩阵的特点我们稍后再解释。

这个计算校验块的过程则是coding(加码)过程。

纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team

 假设m个节点down机,即丢失了m块数据。那我们如何从剩余的n个节点上的数据(注意,这里剩余的n块可能包含几个数据块+几个校验块,不固定)恢复出来原始的n个数据块呢,就需要通过下面的decoding(解码)过程来实现。
为了解码,第一步,将删掉m个块的(n+m)*1个矩阵变形为n*1矩阵,同时B矩阵也需要删掉对应的m个行得出一个B'的变形矩阵,这个B'就是n*n矩阵。
纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team
纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team

 得到B’以后,需要计算出来B'的逆矩阵,这里稍后讲解逆矩阵的求法,假设已经得出来逆矩阵,如图所示:
纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team
我们知道矩阵*自己的逆矩阵会得到一个线性矩阵(即对角线为1,其他元素都为0),根据这个特性,我们对上面的等式两边都乘以一个B'的逆矩阵,可以得到下面的式子:
纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team
纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team
也就是说通过右边的B'逆矩阵与剩余可用的n块可用元素,就可以得到最原始的D1~D5的n个数据块,至此,完成了一个decoding(解码)过程。

所以,这里的关键有两个问题:

  1. 如何生成计算校验数据块的矩阵B;
  2. 如何高效地计算矩阵的逆矩阵。
计算细节
创建计算矩阵B

将B定义为范德蒙矩阵:

纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team

 


这个矩阵的任意n * n子矩阵均可逆。
如何计算逆矩阵

先简单介绍Gloais域和域上的计算方法:

纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team

该域上的加减法即做简单的XOR运算。

下面我们简单介绍下乘法运算:

乘法运算就是将乘数和被乘数表示成二进制,进而转化成相关多项式,如GF(2^4)域上的15可表示成(1111),进而表示成多项式为x^3 + x^2 + x^1 + 1,而GF(2^4)上的6可表示成(110),可表示成多项式x^2 + x^1。接下来15 * 6计算规则如下:

15 * 6 = (x^3 + x^2 + x^1 + 1) * (x^2 + x^1)
= x^5 + x^4 + x^4 + x^3 + x^3 + x^2 + x^2 + x^1
= x^5 + 2x^4 + 2x^3 + 2x^2 + x^1
= x^5 + x^1(因为在mod2计算时 2 = 0)

由于在GF(2^4)内运算,因此,必须将x^5降级,计算方法是将其除以本原多项式x^4 +x^1 + 1,常用本原多项式如下:

纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team

 因此,将x^5降级方法是

x^5/(x^4+x+1) = x^2 + x = (110) = 3

因此,在GF(2^4)内:

15 * 6 = 3

 RS->LRC

Rs的劣势: 如果仔细分析故障出现的情况,你将很容易发现两个特征:

特征一:所有的故障都将导致同样的重建代价,无论是一个盘,还是M个盘

特征二:单个磁盘故障的几率远远大于多个磁盘同时故障的几率,通常在90%以上

直接出现的对策就是分组,把单个磁盘故障影响范围缩小到各个组内部,出坏盘故障时,该组内部解决,在恢复过程中读组内更少的盘,跑更少的网络流量,从而减小对全局的影响。

LRC(Locally Repairable Codes),局部校验编码,其核心思想为:将校验块(parity block)分为全局校验块(global parity)、局部校验块(local reconstruction parity),故障恢复时分组计算。

以微软Azure的云存储(Windows Azure Storage)实现为例,它采用LRC(12,2,2)编码,将12个数据块为一组编码,并进一步将这12个数据块平均分为2个本地组, 每个本地组包括6个数据块,并分别计算出一个local parity,之后把所有12个数据块计算出2个global parities。 当发生任何一个数据块错误时,只需用本地组内的数据和校验块用于计算,即可恢复出原始数据。而恢复代价(通过网络传输的数据块数量)就由传统RS(12,4)编码的12,变为6,恢复过程的网络I/O开销减半,同时空间冗余率保持不变,仍为(12+2+2)/12 = 1.33

纠删码算法知识普及 - 网易杭州QA - 网易杭州 QA Team

 

总结

纠删码本身是一种比较成熟的算法

纠删码中reed solomon算法是比较早并且已经有开源实现的一种算法,相对引入系统的难度较低。

 
 

 

 

  评论这张
 
阅读(1344)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016