云存储系统中基于纠删码的容错技术研究

摘要

随着计算机和网络技术的发展，云计算正处在迅猛的发展阶段，并会在未来若干年主导着信息产业的市场空间。云存储作为云计算中最核心的基础组件，它通过集群、网格计算和分布式文件系统等技术，将网络中大量异构的存储设备集合起来协同工作，对外提供统一的数据存储、管理和访问等在线服务。由于云存储具有存储成本低、容量大、可扩展性好的特点，所以自从推出后就倍受广大用户的青睐。
　　然而，由于云存储环境的复杂性和开放性，系统会遇到各种各样的问题。应用程序的故障、操作系统的故障、人为操作失误、网络攻击等现象，都有可能造成数据随时失效。在云存储系统中，节点失效被认为是常态事件而不是意外事件，在任何给定时间内都有可能发生某些节点无法工作。为此，容错机制是云存储系统首要考虑的工作任务。
　　现在的云存储容错方案大部分采用了副本复制技术，但随着数据量以超过摩尔定律的速度增长，会给云存储系统带来巨大的存储压力。目前，专家学者们一致认为:为了缓解存储压力，云存储容错方案会逐渐由副本复制向纠删码转变。然而，纠删码是一种典型的以时间换空间的算法，它虽然数据冗余量小，但计算复杂度高，重构效率低，会消耗过多的网络带宽资源。本文从计算性能优化、存储效率优化、故障修复优化、混合冗余优化四个方面出发，对容错纠删码展开研究，主要工作及创新点如下:
　　1.针对传统RS编码在有限域上乘法计算复杂度高的问题，提出了一种自带加速器的RS(Reed-Solomon)编码。
　　RS编码是在伽罗瓦域(Galois Field)GF(2ω)进行运算，加法计算简单，但乘法计算复杂度高。本工作对基于RS编码的存储容错原理进行了详细介绍，并通过实例分析了RS编码进行乘法运算的复杂性，在此基础上，提出了一种自带加速器的RS编码---RSWA(Reed-Solomon Codes with Accelerator)编码，并从理论上将RS编码、柯西RS编码、RSWA编码的复杂度进行了对比。最后，通过实验对RS编码、柯西RS编码、RSWA编码的性能进行了评估。实验结果表明:RSWA编码在单条带编码、整体编码、重构效率方面要优于另外两种编码。
　　2.针对云存储容错系统中数据存储量迅速增长的问题，在基于纠删码的云存储容错系统中提出了一种基于全局布鲁姆过滤器阵列的去重方法。
　　云存储系统中数据量以超过摩尔定律的速度增长，并有超过60％的数据是重复的。在基于纠删码的容错系统中，数据对象分块存储，存储粒度更小，存在的重复数据会更多。在云存储系统的存储空间和网络带宽越来越紧张的情况下，如何提高系统的存储效率成了一个亟待解决的问题。本工作对去重技术的研究现状、布鲁姆过滤器的研究现状、基于布鲁姆过滤器的去重现状进行了介绍，对去重技术、布鲁姆过滤器的基础理论进行了分析。由于布鲁姆过滤器是一种空间高效的随机化数据结构，非常适合于有限空间内的查询比对，所以提出了一种基于全局布鲁姆过滤器阵列的高效去重方法。通过对标准布鲁姆过滤器进行动态的扩容，组建了一个全局动态布鲁姆过滤器阵列(Public Dynamic Bloom Filter Array，PDBFA)，从而有效地控制了系统的误判率。最后，在自组建的Openstack云平台上进行了性能评估，实验结果表明:PDBFA具有去重率高、误判率低、对容错性能影响较小的特性。
　　3.针对RS编码纠错能力强而修复复杂度高的特点，提出了一种面向云存储容错系统的RS再生纠删码。
　　RS编码虽然纠错能力强，但由乘法计算复杂并需要求逆矩阵，所以编译码效率低，不能满足云存储容错系统的特性要求。阵列码虽然计算简单，但一般只能容双错，同样不能满足云存储容错系统的特性要求。本工作在分析了现有的RS编码和RDP阵列码的优缺点后，面向云存储容错系统提出了一种RS再生纠删码。该编码继承了RS编码容多错的可靠性，又能实现扩展RDP编码容三错的高效性。对RS再生码中单节点故障混合修复方法进行了介绍，并求出了混合修复时磁盘读取数的理论下界。从理论上对RS再生码的存储开销、译码效率、修复带宽进行了性能评估。最后，在开源分布式存储系统NCFS中对RS再生码的性能进行了评估实验结果表明:RS再生纠删码比同类纠删码的修复性能有较大的提升，特别是采用混合修复算法以后，系统单故障恢复时间下降20.8％～28.2％。
　　4.针对副本复制技术修复快、占用存储空间多的特点，在云存储容错系统中提出了一种基于复制和纠删码自适应切换的容错策略。
　　基于副本复制技术容错操作简单、故障修复快，但会过多地消耗存储空间，而基于纠删码技术容错可有效节约存储空间，但故障修复时会消耗过多的网络带宽。单一的数据冗余策略无法很好地满足云存储容错系统的特性要求。本工作对副本复制和纠删码两种常用的容错方法进行了对比分析，根据云端文件的访问规律提出一种基于复制和纠删码自适应切换的云存储容错算法，构建了一个相应的云存储容错框架。容错算法根据文件的访问频率和存储大小，自适应地选择容错策略，一方面降低了低访问量文件的存储开销，另一方面提高了高访问量文件的访问时效。实验结果表明:该算法较完全复制节约存储空间40％，而较纠删码的访问时效提升48％，并在这两方面优于同类混合数据冗余算法。
　　综上所述，本文首先从时间优化角度出发，为RS纠删码构造了一个加速器;然后从空间优化的角度出发，提出了一种基于布鲁姆过滤器阵列的去重技术;接着从故障修复优化的角度出发，提出了一种适合于云存储容错系统的RS再生码;最后，结合时间与空间的优化，提出了一种基于副本复制和纠删码自适应切换的容错策略，从而可以构建一个高性能低开销的云存储容错系统。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景与意义

1．2 云存储容错的发展及面临的挑战

1．3 论文的主要工作

1．4 论文的组织结构

第2章 云存储系统中基于纠删码容错的相关技术

2．1 云存储容错系统的一般架构

2．2 容错纠删码的基本工作原理

2．3 容错纠删码的相关术语

2．4 常见的存储容错纠删码

2．4．1 RS编码

2．4．2 阵列纠删码

2．4．3 LDPC编码

2．5 容错纠删码的主要-I生能指标

2．5．1 容错能力

2．5．2 存储效率

2．5．3 编码效率

2．5．4 重构效率

2．6 云存储中容错纠删码的选择策略

2．6．1 各类纠删码的适用场景

2．6．2 纠删码的选择建议

2．7 小结

第3章 一种自带加速器的Reed-Solomon编码

3．1 引言

3．2 基于RS编码的存储容错方案

3．2．1 RS编码框架

3．2．2 RS校验编码的生成矩阵

3．2．3 RS编码的故障恢复

3．3 一种基于向量矩阵化的RS算法加速器

3．3．1 G(2ω)中乘法计算方法

3．3．2 基于矩阵向量化的乘法计算加速器

3．3．3 RSWA码与RS码计算复杂度对比

3．3．4 RSWA编码的流程

3．4 实验评估

3．4．1 实验环境及流程

3．4．2 实验步骤及结果分析

3．5 小结

第4章 云存储容错系统中纠删码的去重方法研究

4．1 引言

4．2 相关工作

4．2．1 去重技术中查重检测的研究现状

4．2．2 布鲁姆过滤器的研究现状

4．2．3 基于布鲁姆过滤器去重的研究现状

4．3 相关技术的基础理论

4．3．1 纠删码

4．3．2 数据去重技术

4．3．3 标准布鲁姆过滤器

4．4 纠删码中基于布鲁姆过滤器的去重

4．4．1 容错纠删码去重的系统架构

4．4．2 基于标准布鲁姆过滤器阵列的去重方法

4．4．4 纠删码中基于改进布鲁姆过滤器阵列的去重

4．5 实验评估

4．5．1 实验环境

4．5．2 实验步骤及结果分析

4．6 小结

第5章 一种面向云存储容错系统的RS再生纠删码

5．1 引言

5．2 相关工作

5．3 RS编码与RDP编码的生成过程

5．3．1 RS编码的生成过程

5．3．3 RDP编码的生成过程

5．4 RS再生码(RS-ERDP)构造

5．4．1 扩展RDP编码

5．4．2 RS再生码的生成

5．5 RS-ERDP编码中单节点故障修复的读盘优化

5．6 RS-ERDP编码的性能分析

5．6．1 存储开销

5．6．2 译码效率

5．6．3 单节点故障修复带宽

5．6 基于RS-ERDP编码的云存储容错架构

5．7 实验性能评估

5．7．1 实验环境

5．7．2 节点故障修复时间比较

5．7．3 单节点故障修复性能比较

5．8 小结

第6章 云存储容错系统中一种自适应切换的容错策略

6．1 引言

6．2 相关工作

6．2．1 云存储系统中的文件访问规律

6．2．2 混合冗余的容错策略

6．2．3 内存中的页面置换策略

6．3 副本复制和纠删码的分析比较

6．3．1 副本复制容错技术

6．3．2 纠删码容错技术

6．3．3 副本复制和纠删码性能对比

6．4 副本复制和纠删码的自适应切换算法

6．4．1 切换方法的选择

6．4．2 自适应切换算法

6．5 基于副本复制和纠删码动态切换的云存储容错架构

6．6 实验性能评估

6．6．1 实验环境

6．6．2 存储空间对比分析

6．6．3 容错时效对比分析

6．6．4 CPU和内存资源消耗对比分析

6．7 小结

结论

参考文献

致谢

攻读学位期间完成的主要成果

攻读学位期间参与的科研项目