浅谈纠删码如何减少大数据场景下的存储

验“金”室

大数据时代，数据的重要性不言而喻，随着数据越来越多，分布式存储节点也越来越多。庞大的节点数量导致节点异常等情况频发，必须采用一定的容错技术来保证数据的可靠性。保证数据可靠性主要有2种常见的方式：副本策略和纠删码策略。

副本策略和纠删码策略都是通过增加冗余数据的方式来保证在发生部分数据丢失时，原始数据不会丢失。

• 副本策略是将原始数据以倍数存储，如Hadoop默认采用三副本策略有效解决了存储的容错问题，如果需要存储500T的数据，在三副本的容错方案下实际会占用1500T的存储空间。

• 纠删码策略能以较低的存储代价获得相似的容错可靠性，在10+3（将原始数据分为10份，计算3份冗余）的纠删码策略下，500T的数据实际需要存储650T，相比三副本策略压缩了一半。

图1 三副本与纠删码策略存储形式

在大数据场景下，三副本策略所带来的存储成本压力更为明显，因此纠删码技术备受青睐。下面介绍一下纠删码为何能做到如此低的存储开销。

一、技术原理

纠删码技术主要是通过纠删码算法将原始的数据进行编码得到冗余，将数据和冗余一起分块存储起来，以达到容错的目的。基本思想是将n块原始数据通过一定计算，得到m块冗余数据，这个生成冗余数据的过程称为“编码”。对于这n+m块数据，当其中不超过m块数据出错时，均可以任意选取n个正常的数据块通过对应的解码算法恢复出原始的n块数据。

最经典的纠删码算法是里德-所罗门码（Reed-Solomon码，RS码）。下面介绍一下RS码是如何工作的。

1.编码

总数据块（m+n）=原始数据块（n）+冗余数据块（m）。

以5+3的RS码为例说明。图2中的D是原始数据，这里分成了5块。B是编码矩阵，用来将原始数据D进行编码，生成实际要存储的数据块D+C。将编码矩阵B与原始数据矩阵D相乘，便可以得到3个冗余数据块C，这就是编码过程。

图2 编码过程

为了计算冗余数据，首先我们需要选择一个合适的编码矩阵B，这里的编码矩阵B是预先指定的，在RS码算法中要求编码矩阵B是可逆的。为方便数据存储，指定编码矩阵上部是单位矩阵，这样便保证了进行矩阵乘法后，等式右侧上部是原始数据D。下部矩阵可以选择范德蒙德矩阵（如图3所示），从中选择3行5列组成编码矩阵B的下部3行，根据线性代数知识，这样可保证编码矩阵B是可逆的。

图3 范德蒙德矩阵

2.解码

RS码最多能容忍m个数据块丢失，数据恢复的过程如下。

假设丢失了D1、D4、C2数据块。

图4 丢失数据

根据丢失的数据块重组编码矩阵B对应的行和列，可以得到以下等式。

图5 重组B得到B’

等式两边同时左乘新的矩阵B’的逆矩阵B’-1，即可计算出D，也即获得了完整的原始数据。

图6 左乘B’-1

图7 计算出D

有了原始数据D，再根据编码过程，即可恢复出丢失的D1、D4、C2数据块。

二、纠删码的优缺点

1.优点

提供近似三副本的可靠性。

将这n+m个数据块分别存放在n+m个硬盘上，就能最多容忍m个硬盘同时发生故障，大大提高了数据的可靠性。

减小冗余存储。

相比副本策略翻倍的数据存储空间消耗，纠删码策略仅需要在原始数据之外存储部分冗余数据块。

2.缺点

CPU资源消耗高。

数据存储编码时需要进行矩阵乘法，数据丢失解码时需要进行矩阵求逆和矩阵乘法，特别是矩阵求逆的时间复杂度是O(n3)。

磁盘IO和网络负载高。

修复任何一个数据块时都需要n份的其他数据块从磁盘上读取和网络上传输。

三、总结

采用纠删码策略能够极大地减少存储系统的存储开销，减少硬件、运维和管理成本，因此近年来吸引了众多分布式存储/云存储的厂商和用户，微软、谷歌、亚马逊、阿里、华为等知名云服务厂商都已经在自己的产品中采用了纠删码。但是也应该认识到纠删码技术的缺点，选择适合的使用场景以屏蔽它的缺点带来的影响，最大化纠删码技术的价值。

在大数据场景下，采用副本策略和纠删码策略相结合的使用方式，通过合理的架构选择来充分利用纠删码技术的优点，比如在冷数据存储上，大量冷数据长期不会被访问，集群基本稳定，耗资源量少，且在发生节点异常需进行数据恢复时，对集群的资源消耗和数据恢复的时效要求不会对业务造成大的影响，使用纠删码技术就是一个较好的选择。

往期推荐

FCC30+

长按左边二维码

关注我们不迷路