《大数据离线分析技术》课件-15.HDFS存储原理-纠删码原理

纠删码原理大数据离线分析教学目标1.了解RAID

2.了解副本、纠删码

3.掌握纠删码原理1.背景近几年，尤其是规模较大的应用场景下，纠删码越来越多的出现在选择的视野范围，成为RAID，副本之外的第三种选择，因此也获得了越来越多的关注。​从传统情况来看，RAID通常用在企业级环境里较多，在几台和十几台存储设备规模的IT系统中，一向是使用稳定可靠历经数十年磨砺的RAID技术。而在数据中心级的大规模部署中，RAID不再受欢迎，大部分的分布式系统都偏好副本模式，看重的是其高可靠性和读性能优化的特点。然而副本带来的成本压力实在是有些吃不消，这时候Erasure

Code适时出现，以更低成本和更高技术含量提供近似可靠性这几点，就吸引到了众多分布式存储／云存储的厂商和用户。2.RAID把相同的数据存储在多个硬盘的不同的地方（因此，冗余地）的方法。因为多个硬盘增加了[平均故障间隔时间（MTBF），储存冗余数据也增加了容错。​RAID技术主要有以下三个基本功能：(1)通过对磁盘上的数据进行条带化，实现对数据成块存取，减少磁盘的机械寻道时间，提高了数据存取速度。(2)通过对一个阵列中的几块磁盘同时读取，减少了磁盘的机械寻道时间，提高数据存取速度。(3)通过镜像或者存储奇偶校验信息的方式，实现了对数据的冗余保护。3.副本、纠删码​HDFS通过多副本机制来保证。在HDFS中的每一份数据都有两个副本，1TB的原始数据需要占用3TB的磁盘空间，存储利用率只有1/3。而且系统中大部分是使用频率非常低的冷数据，却和热数据一样存储3个副本，给存储空间和网络带宽带来了很大的压力。

纠删码技术简称EC，本身是一种编码容错技术​如果严格的区分，实际上按照误码控制的不同功能，可分为检错、纠错和纠删三种类型。（1）检错码：识别错码（2）纠错码：识别错码，纠正错码（3）纠删码：识别错码，纠正错吗，删除超出纠正范围的错码4.纠删码原理Reed-Solomon（RS）码是存储系统较为常用的一种纠删码，它有两个参数k和m，记为RS(k，m)。如图所示，k个数据块组成一个向量D被乘上一个生成矩阵B从而得到一个码字向量，该向量由k个数据块和m个校验块构成。如果一个数据块丢失，可以用(GT)-1乘以码字向量来恢复出丢失的数据块。RS(k，m)最多可容忍m个块（包括数据块和校验块）丢失。以冗余级别为5+3的纠删码为例说明。将n个源数据块D1~Dn按列排成向量D，再构造一个(n+m)n矩阵B（图2），B称为分布矩阵。对矩阵B有一个要求：它的任意n个行向量都是相互独立的，即这n个行向量组成的nn矩阵可逆。(由线性代数知道，对互不相等的实数a1，a2，…，ak(k≥n)，矩阵V的任意n行组成的矩阵都可逆。5.纠删码原理从矩阵V中取出m行，用做分布矩阵B的下部m行，恰好满足对B的要求：任意n行都相互独立。例如冗余级别为5+3纠删码的分布矩阵B可以采用如下形式。6.纠删码原理执行矩阵向量乘B*D，得到m个校验块C1~Cm。小结1.RAID技术通过条带化、多磁盘并行读取和数据冗余保护提高数据存取速度和容错能力2.HDFS通过多副本机制保证数据可靠性，但存储利用率低3.纠删码是一种编码容错技