学位论文 > 优秀研究生学位论文题录展示

大规模分布式存储系统中数据冗余技术研究

作　者: 黄震
导　师: 彭宇行
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 分布式存储纠删码冗余度可靠度
分类号: TP333
类　型: 博士论文
年　份: 2012年
下　载: 96次
引　用: 0次
阅　读: 论文下载

内容摘要

分布式存储系统通过网络通信技术连接分散的存储节点，存储海量数据。其目标为提供高可靠、低开销和高效的存储服务。本文针对大规模分布式存储系统中数据可读性差、数据维护通信量大、数据分配复杂度高以及服务节点选择难等挑战性问题，面向冗余数据读取、冗余数据维护、冗余数据分配以及服务节点选择等方面开展研究，取得了以下成果：针对数据可读性差的问题，本文在分析用户随机访问和顺序访问的概率开销基础上，提出了精确式层次编码方法EHC，达到了下载数据小，解码计算复杂度低和解码速度快的目标。该方法的基本思想是通过多层小组的数据重构技术，减小随机访问的下载数据量和降低解码矩阵的大小；通过映射编码结构为树型结构，采用基于后序遍历的节点优选算法，选择最多的原始数据块和低层编码数据块，以减小解码的等待延迟。与已有的方法相比，EHC方法有效地利用了多层多组结构和低修复度数的特点，采用了后序遍历算法选择低层节点的特性，可以减小下载数据量、降低解码的计算开销和快速解码。针对数据维护通信量大问题，本文在分析系统中数据通信量产生的原因和维护通信技术特点的基础上，提出了再生-层次复合式编码方法ERHC，达到了降低维护通信量的目标。该方法的基本思想是有效应用再生码技术到层次码的复杂结构中，直接分割层次码的数据块为数据片，维持层次码原有的多层多组结构，保持了层次码的高可靠特性，减小了参与修复的节点数，同时减小了用于修复数据块的大小。与已有的方法相比，ERHC方法有效地利用了层次码的小组特性和再生码的信息融合方法，在构建多层多组多数据分片的编码方案基础上，可以在保证数据高可靠和低存储开销的情况下，有效降低数据维护的通信量，并且再生-层次复合式编码方法在各种类型的修复模式下表现稳定，适用广泛，修复的计算复杂度低。针对数据分配复杂度高问题，本文在分析系统中数据分配问题的复杂性基础上，提出了基于生成函数的数据存储分配方法OSA，达到了数据最优存储分配的目标，即在满足给定高可靠度的情况下，最小化了数据的冗余度。该方法的基本思想是采用生成函数将数据可靠度与多个节点存储数据块的组合可靠度关系，映射转化为生成函数与多个因式相乘关系，通过生成函数的推导证明，获得了最优分配方法下的参数关系、简化计算方法以及搜索的终止条件。与已有的方法相比，OSA方法有效地利用了生成函数表示简单易于推导的特性，有效降低了数据的冗余度，同时可以减小最优化搜索的空间和简化计算过程。针对服务节点选择难问题，本文在分析系统中服务节点状态和用户访问特性的基础上，定义了一个基于流行度的二分图顶点覆盖问题，并证明了该问题为NP完全问题，提出了基于数据访问偏斜性的服务节点选择策略SNBS，达到了节省存储开销目标。该方法的基本思想是通过概率分析推导关闭节点的关键性参数，采用了基于访问失效概率的并发贪心算法，在满足用户低访问失效率的情况下，关闭最多的存储节点。与已有的方法相比，SNBS方法，在不做数据迁移的情况下，有效分析了用户访问失效概率及关闭节点对它的影响，利用并发的贪心算法达到了节省服务开销的目标，并且可以有效覆盖数据对象，适应各种不同的系统策略和网络环境。

全文目录

摘要  10-12
ABSTRACT  12-14
第一章绪论  14-28
  1.1 分布存储及其冗余技术概述  14-19
    1.1.1 存储的发展历程  14-16
    1.1.2 当前主流的分布式存储系统  16-17
    1.1.3 冗余技术的发展历程  17-19
  1.2 冗余技术的现状、难点和挑战  19-24
    1.2.1 冗余技术的现状  19-21
    1.2.2 冗余技术的难点和挑战性问题  21-24
  1.3 本文工作  24-26
    1.3.1 面向数据可读性的精确式层次编码方法  24-25
    1.3.2 面向数据维护通信量再生-层次复合式编码方法  25
    1.3.3 基于生成函数的数据存储分配方法  25-26
    1.3.4 基于数据访问偏斜性的服务节点选择策略  26
  1.4 论文结构  26-28
第二章相关研究  28-40
  2.1 数据冗余  28-35
    2.1.1 纠删码  28-30
    2.1.2 再生码  30-33
    2.1.3 功能性层次码  33-35
  2.2 数据放置  35-36
  2.3 数据维护  36-37
  2.4 数据分配的生成函数  37-38
  2.5 节点服务  38-39
  2.6 分布式存储系统主要技术方法  39
  2.7 本章小结  39-40
第三章面向数据可读性的精确式层次编码方法  40-52
  3.1 引言  40-42
    3.1.1 数据读取的重要性以及访问模式  40
    3.1.2 主流纠删码方案数据读取的问题  40-41
    3.1.3 精确式层次编码方法  41-42
  3.2 读取开销概率模型  42-45
  3.3 Exact Hierarchical编码  45-48
    3.3.1 精确式层次码  45-46
    3.3.2 低修复度数分析  46-48
    3.3.3 节点优选算法  48
  3.4 性能评估  48-51
  3.5 本章小结  51-52
第四章面向数据维护通信量的再生-层次复合式编码方法  52-86
  4.1 引言  52-54
    4.1.1 数据维护通信量问题和关键点  52
    4.1.2 主流纠删码方案数据维护的问题  52-53
    4.1.3 再生-层次复合式编码方法  53-54
  4.2 评估冗余方案的指标  54-56
    4.2.1 存储空间和网络通信量  54-55
    4.2.2 修复度数  55-56
    4.2.3 可靠度  56
  4.3 ER-Hierarchical编码  56-65
    4.3.1 由层次码起源的ER-Hierarchical编码  57-58
    4.3.2 一个例子  58-62
    4.3.3 ER-Hierarchical编码性质  62-65
    4.3.4 重构和修复  65
  4.4 评估  65-84
    4.4.1 分析性评估  65-67
    4.4.2 实验性评估  67-80
    4.4.3 计算的复杂度  80-84
  4.5 总结  84-86
第五章基于生成函数的数据存储分配方法  86-104
  5.1 引言  86-87
  5.2 存储分配方案  87-100
    5.2.1 数据可靠度  87-89
    5.2.2 模型的属性  89-98
    5.2.3 寻找最优存储分配过程  98-100
  5.3 模型评估  100-103
    5.3.1 分析性评估  100-102
    5.3.2 实验性评估  102-103
  5.4 本章小结  103-104
第六章基于数据访问偏斜性的服务节点选择策略  104-120
  6.1 引言  104-105
    6.1.1 服务节点选择问题  104-105
    6.1.2 服务节点选择策略SNBS  105
  6.2 基于流行度的图覆盖模型  105-113
    6.2.1 一个例子  105-106
    6.2.2 一般模型  106-109
    6.2.3 模型的基本属性  109-113
  6.3 模型评估  113-119
    6.3.1 实验准备  113-115
    6.3.2 实验结果及分析  115-119
  6.4 本章小结  119-120
第七章总结与未来工作  120-123
  7.1 工作总结  120-121
  7.2 研究展望  121-123
附录  123-128
  1 修复存储数据块  123-125
    1.1 新加入者计算系数νi  123-125
    1.2 修复节点计算修复数据片  125
    1.3 新加入者计算(p81, p′82)  125
    1.4 更新矩阵U  125
  2 MBR与ERHC的比较  125-128
    2.1 存储开销  126
    2.2 修复通信量  126-128
致谢  128-130
参考文献  130-142
作者在学期间取得的学术成果  142-143

大规模分布式存储系统中数据冗余技术研究

内容摘要

全文目录

相似论文