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

发布时间：2018-11-01 17:27

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

【参考文献】