分布式存储系统中数据存储研究

作     者：余春雷 

作者单位：长安大学 

学位级别：硕士

导师姓名：王静

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：分布式存储 部分重复码 因子分解 哈夫曼树 

摘      要：随着互联网技术问世以来,推动着各项科学技术的发展,尤其是信息技术的飞速发展。面对信息技术每天产生的大量数据信息,如何高效、可靠地存储是我们当前研究的热点。传统的数据存储一般采用集中式存储,但存在购买设备昂贵而且不易扩展等缺陷,渐渐被分布式存储系统代替。分布式存储系统在存储数据时具有设备价格低廉,而且扩展性好等优势,可以搭载庞大的分布式服务系统。复制策略和纠删码策略通常应用在分布式存储系统中保证数据的可靠性和有效性。复制策略是通过对原始文件复制多份进行存储,通过副本对数据进行有效保护。复制策略简单易实现,但复制策略的存储开销比较大。纠删码策略是通过对原文件分块进行编码产生冗余校验块来对数据进行有效保护,有效的降低了系统的存储开销,但是纠删码策略的修复带宽开销和修复局部性过大,而且修复过程需要解码操作,因而计算复杂度较高。部分重复码（Fractional Repetition,FR）码因在修复故障节点的过程中拥有较低的修复局部性和修复带宽开销,以及能够对故障节点进行无编码快速修复进而得到广泛研究。本文主要针对分布式存储系统中FR码进行研究。本文的主要研究内容如下:（1）针对当前部分重复码构造过程复杂以及对参数的依赖性强,提出一种基于图因子分解的部分重复（Fractional repetition based on graph factorization,FRGF）码的构造算法,能够在很大范围内选择构造参数和数据块的重复度,并且构造方法具有多样性的特点。具体地,首先进行图因子分解,然后利用分解的因子进行部分重复码的构造。根据图的可1因子分解和图的可2因子分解构造不同部分重复码。实验结果表明,与现有的RS码和简单再生码相比,FRGF码拥有更低的修复局部性、修复带宽开销以及修复复杂度,且修复效率高,显著减少了故障节点的修复时间。（2）考虑到分布式存储系统中数据被访问频率的不同,提出一种基于哈夫曼树的可变重复度的异构部分重复（Heterogeneous Variable Fractional Repetition,HVFR）码。具体地,将不同访问频率的数据块作为哈夫曼树带有确定权值的叶子结点,构造哈夫曼树并确定数据块的重复度,进一步利用成对平衡设计（Pairwise Balanced Design,PBD）构造异构FR码,该码能够提高热数据的并行访问速度以及系统存储效率。性能分析和仿真结果表明,与RS码以及简单再生码相比,HVFR码可以显著减少故障节点的修复时间以及修复局部性,提高热数据的并行访问速度,且计算复杂度低、构造更加简单。