产品产品产品

358篇博客

编辑推荐

网易数帆开源API网关与容器云项目，让云原生生产落地“多快好

网易汪源：统一负载与多云环境的“开放姿态”，才是云原生

网易数帆如何用 Kubernetes“原语”搞定云原生中间件

快手打新挤爆券商系统，网易数帆推出券商稳定性保障方案

探索智慧校园新模式，网易有数在教育行业的实践分享

金融行业大数据治理之路——数据模型篇

纠删码算法知识普及

把生命浪费在美好事物上2018-07-05 12:54

概述

纠删码（erasure coding，EC）是一种数据保护方法，它将数据分割成片段，把冗余数据块扩展、编码，并将其存储在不同的位置，比如磁盘、存储节点或者其它地理位置。

下图简单阐述了纠删码原理：D1…D10 这10个数据块（甚至可以理解为单个磁盘），P1、P2、P3、P4是对这10个数据块计算出来的纠删码块，这14个块分布在不同的server磁盘上。

根据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（加码）过程。

假设m个节点down机，即丢失了m块数据。那我们如何从剩余的n个节点上的数据（注意，这里剩余的n块可能包含几个数据块+几个校验块，不固定）恢复出来原始的n个数据块呢，就需要通过下面的decoding（解码）过程来实现。

为了解码，第一步，将删掉m个块的（n+m）*1个矩阵变形为n*1矩阵，同时B矩阵也需要删掉对应的m个行得出一个B'的变形矩阵，这个B'就是n*n矩阵。

得到B’以后，需要计算出来B'的逆矩阵，这里稍后讲解逆矩阵的求法，假设已经得出来逆矩阵，如图所示：

我们知道矩阵*自己的逆矩阵会得到一个线性矩阵（即对角线为1，其他元素都为0），根据这个特性，我们对上面的等式两边都乘以一个B'的逆矩阵，可以得到下面的式子：

也就是说通过右边的B'逆矩阵与剩余可用的n块可用元素，就可以得到最原始的D1~D5的n个数据块，至此，完成了一个decoding（解码）过程。

所以，这里的关键有两个问题：

如何生成计算校验数据块的矩阵B；
如何高效地计算矩阵的逆矩阵。

计算细节

创建计算矩阵B

将B定义为范德蒙矩阵：

这个矩阵的任意n * n子矩阵均可逆。

如何计算逆矩阵

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

该域上的加减法即做简单的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，常用本原多项式如下：

因此，将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