【hadoop】纠删码技术详解

1 纠删码背景

随着大数据技术的发展，HDFS作为Hadoop的核心模块之一得到了广泛的应用。为了数据的可靠性，HDFS通过多副本机制来保证。在HDFS中的每一份数据都有两个副本，1TB的原始数据需要占用3TB的磁盘空间，存储利用率只有1/3。而且系统中大部分是使用频率非常低的冷数据，却和热数据一样存储3个副本，给存储空间和网络带宽带来了很大的压力。因此，在保证可靠性的前提下如何提高存储利用率已成为当前HDFS面对的主要问题之一。Hadoop 3.0引入了纠删码技术（Erasure Coding)，它可以提高50%以上的存储利用率，并且保证数据的可靠性。

2 纠删码简介

纠删码（Erasure Code)本身是一种编码容错技术，最早是在通信行业解决部分数据在传输中损耗的问题，它的基本原理是把传输的信号分段，加入一定的校验再让各段间发生一定的联系，即使在传输过程中丢失掉部分信号，接收端仍然能通过算法把完整的信息计算出来。Erasure Code适时出现，以更低成本和更高技术含量提供了较强的可靠性，就吸引到了众多分布式存储／云存储的厂商和用户。

3 纠删码原理

Reed-Solomon（RS）码是存储系统较为常用的一种纠删码，它有两个参数k和m，记为RS(k，m)。如下图所示，k个数据块组成一个向量被乘上一个生成矩阵（Generator Matrix）GT从而得到一个码字（codeword）向量，该向量由k个数据块和m个校验块构成。如果一个数据块丢失，可以用(GT)-1乘以码字向量来恢复出丢失的数据块。RS(k，m)最多可容忍m个块（包括数据块和校验块）丢失。

4 举例

我们有 7、8、9 三个原始数据，通过与生成矩阵相乘，计算出最终的纠删码。这时原始数据加上校验数据，一共五个数据：7、8、9、50、122，可以任意丢两个，然后通过算法进行恢复。

前面介绍了纠删码parity位的计算过程，由于单位矩阵乘以另外一个矩阵等于矩阵本身，所以data位就是数据本身。矩阵B为最终存储到磁盘的数据。如下所示：

矩阵B中第2行和第5行数据块丢失，需要将GT矩阵对应的第2行和第5行删除，再通过删除后的GT矩阵计算出丢失的数据

根据公式，矩阵乘以该矩阵的逆矩阵等于单位矩阵，单位矩阵乘以任何矩阵等于矩阵本身。根据这个性质，可以通过等式两边同时乘以GT的逆矩阵算出真实的数据。