分布式安全存储系统纠删码技术的研究

论文摘要

随着计算机网络技术的迅猛发展,办公自动化和企业信息化的不断普及,人们对数据存储的需求越来越高。单机所包含的磁盘容量己经不能满足人们的日常需要,这就要求有一种可靠的存储系统来连接地域上分散的磁盘空间,提供给各类用户。分布式存储技术对于解决存储系统中存储设备的分散性、I/O的并行性、协议的高效性提供了一种很好的手段。但随着存储规模的扩大,由于硬件故障、人员操作失误、病毒攻击、恐怖袭击、断电、火灾、地震等自然灾害等原因,存储节点失效而导致整个系统发生故障的机率大大提高。为此,系统应具有良好的容错和抗毁功能,保证数据的高可得率和系统运行的高可靠性。基于纠删码技术的冗余容错方法为构造高可用性和高容错性的分布式存储系统提供了一种有效容错机制,因此设计一种纠删能力好、编译码速度快、算法简单、易于软硬件实现的纠删码是分布式存储系统纠删码技术研究最关键问题之一。本文对分布式存储系统中纠删码技术最新研究成果进行了系统、全面的研究和分析,在此基础上,取得了若干创新和成果。本文的主要成果和创新点如下:1.研究总结了目前分布式存储系统中的三种不同类型的纠删码技术:阵列纠删码、RS类纠删码,以及低密度奇偶校验码。针对各类纠删码的不同编码特性,结合分布式存储系统的结构和特点,给出在分布式存储系统中如何选择纠删码实现有效容错机制的原则及其建议。2.首次提出了一类具有最佳编译码特性、平衡特性、同时码长可以为偶数和奇数的纠双错MDS阵列纠删码—V码。从理论上证明了V码的最小列距离为3,即MDS特性。同时,给出了V码纠双列删除错和纠单列突发错两种快速译码算法。并比较分析了V码、EVENODD码,RS码的编译码性能、小写性能以及平衡特性,V码较其它纠双错码而言具有更好的整体性能。3.基于Blaum码,发展了广义EVENODD码,提出一类纠多列错阵列纠删码—（m + p,m）XEOD码。从几何特性上描述了（m + p,m）XEOD码的编码过程,分析了（m + p,m）XEOD码的编码特性。同时给出了其代数编码定义。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 研究背景与课题意义
• 1.2 分布式存储系统中纠删码技术研究现状
• 1.3 本文主要内容和贡献
• 1.4 本文的组织
• 第二章 在分布式存储系统应用的纠删码技术
• 2.1 引言
• 2.2 一般的纠删码原理
• 2.3 阵列纠删码
• 2.3.1 EVENODD码
• 2.3.2 X码
• 2.3.3 B码
• 2.3.4 STAR码
• 2.4 RS类纠删码
• 2.4.1 范德蒙码
• 2.4.2 柯西码
• 2.5 其它纠删码:新思路
• 2.5.1 Tornado码
• 2.5.2 Non-MDS阵列纠删码
• 2.6 在分布式存储系统如何选择一种好的纠删码
• 2.6.1 选择什么样的纠删码
• 2.6.2 选择一种纠删码还是复合纠删码
• 2.7 结论
• 第三章 V码: 一类新的最小列距为3的MDS阵列纠删码
• 3.1 引言
• 3.2 预备知识
• 3.2.1 预备定义
• 3.2.2 预备引理
• 3.3 V码的描述
• 3.4 V码的MDS特性
• 3.5 V码快速译码算法
• 2n+1码的纠双列删除错译码算法'>3.5.1 V_2n+1码的纠双列删除错译码算法
• 3.5.2 纠单列突发错译码算法
• 3.6 V码性能分析
• 3.6.1 存储效率与编译码复杂度
• 3.6.2 更新复杂度和平衡特性
• 3.7 结论
• 第四章 XEOD码:一类有效的纠多列错阵列纠删码
• 4.1 引言
• 4.2 XEOD阵列纠删码编码过程:几何描述
• 4.3 XEOD阵列纠删码代数定义
• 4.3.1 预备定义和引理
• 4.3.2 XEOD阵列纠删码编码过程的代数定义
• 4.3.3 （m + 3,m,4）XEOD码MDS性质
• 4.4 （m + 3,m,4）XEOD码译码算法
• 4.4.1 纠三列信息列删除错译码算法
• 4.4.2 纠三列混合删除错译码算法
• 4.5 （m + 4,m）XEOD码译码算法
• 4.5.1 纠四列信息列删除错译码算法
• 4.5.2 纠四列混合删除错译码算法
• 4.6 （m + p,m）XEOD码译码算法
• 4.7 （m + p,m）XEOD码性能分析
• 4.7.1 （m + p,m）XEOD码存储效率和编译码复杂度
• 4.7.2 （m + p,m）XEOD码更新复杂度
• 4.8 结论
• 第五章 一种有效的范德蒙-阵列纠删码
• 5.1 引言
• 5.2 范德蒙-阵列纠删码
• 5.2.1 范德蒙-阵列纠删码编码过程
• 5.2.2 范德蒙-阵列纠删码生成矩阵G
• 5.2.3 范德蒙-阵列纠删码译码过程
• 5.3 范德蒙阵列纠删码的效率分析
• 5.4 结论
• 第六章 分布式存储系统中纠删码的应用
• 6.1 引言
• 6.2 三类新的纠删码在分布式存储系统中的应用
• 6.2.1 V码在分布式表决技术的应用
• 6.2.2 V码与XEOD码在磁盘阵列中的应用
• 6.2.3 在（n,k）存储系统中三类阵列纠删码的应用
• 6.3 结论
• 第七章 总结与展望
• 附录A 列举范德蒙-阵列码最佳信息拆分矩阵G
• 攻读博士学位期间发表的论文和科研情况
• 简历
• 致谢