分布式数据存储和处理的若干技术研究

论文摘要

在数字信息量激增、网络迅猛发展、软硬件价格低廉、人力成本显著上升这几大背景之下,传统文件系统已经很难满足新形势下的数据管理需求,而“高效的数据管理方式”,“高质量的存储服务”以及“存储优化和自治”广受关注。以这三个发展方向为出发点,本文全面介绍了存储管理系统、海量分布式存储技术、以及存储优化方面的一系列相关工作,总结了这些领域的研究现状和发展趋势,同时指出了现有工作的不足之处。结合相关领域的最新成果,针对其不足之处,本文提出拥有一定自治能力的,分布式数据存储和管理系统框架,研究存储管理系统的体系结构,以及查询检索、分布式存储和系统优化等各方面的关键技术。本文首先给出一种基于数据相关的存储数据模型,定义了对象、相关关系等基本概念,提出基于数据相关的浏览和检索模型,并给出数据检索语言,介绍了查询执行过程。在此基础之上,从分布式存储,查询和检索,相关检测和系统优化这三个子系统详细描述了系统体系结构。在分布式存储方面,结合对等存储技术和对象存储技术,提出一种基于容器的分布式对象存储系统。首先给出基于容器的存储模型,模型以容器作为数据定位和复制的最小单元,把存储空间管理、数据块分配等底层功能交由容器负责,减少系统维护代价,提高系统可伸缩性。介绍了模型中对象、容器、对象池等基本概念,并描述了集群体系架构。接下来介绍了系统的运行时元数据,提出基于对等覆盖网络的自组织元数据维护和容错方案。最后提出了基于动态主本的容器复制技术,给出了基于容器状态的对象访问,以及复本一致性保障和恢复算法。图最短距离索引是存储管理系统查询和检索的核心数据结构之一,然而已有索引方法或者创建时间过长,或者查询效率不足。针对以上不足,创新地提出了具有常数查询时间的索引DIX-C和基于两跳覆盖的索引DIX-2HC,及其无向图变种,并在图索引的基础之上,研究了基于区间编码的相关连接算法。首先,在介绍了一些基本概念和重要数据结构之后,给出并证明了最短距离计算公式。接下来,详细介绍了关键数据结构的计算算法,并描述了各种索引的创建和查询算法。然后,利用距离索引和区间编码,提出了基于树编码的相关连接算法。最后,通过大量实验考察了索引创建性能、查询性能和空间代价,以及相关连接的性能,实验结果表明DIX-C和DIX-2HC算法具有相当的性能优势,相关连接的效率较高。在访问相关检测和系统优化方面,一方面,现有相关检测算法通常依赖支持度保证算法性能,这势必造成大量有价值的访问相关被遗漏,另一方面,现有算法无法检测跨服务器的访问相关,而且性能不足以应用到分布式系统中。针对以上不足,创新性地提出了一系列无支持限制的访问相关挖掘算法,这些算法把相关度（置信度）作为访问相关的主要衡量标准,能够检测支持度较低但是相关度较高的访问相关。首先,给出访问相关的定义和衡量标准。之后,描述了无支持度限制单机挖掘算法HCM和VCM。然后,我们提出了基于k最小随机向量和哈希指纹连接的分布式并行挖掘算法PFC-Miner,实验结果说明本文提出的挖掘算法具有较好的性能和实用性,挖掘出来的访问相关能够大大提高缓存命中率。在内容相关检测和系统优化方面,针对存储系统的关键词匮乏问题,提出一种基于高相似副本的文件关键词自动提取方法PAKE。通过构建一个关键词覆盖网络KON,PAKE从高相似文件副本处提取更多关键词。通过大量实验证明了,相比已有基于相同副本的方法,PAKE更能充分利用资源的冗余性,它能够有效地提高查询准确率、查全率。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 引言
• 1.2 数据相关
• 1.3 研究内容
• 1.4 论文组织
• 第2章 相关工作综述
• 2.1 引言
• 2.2 存储管理系统
• 2.2.1 语义文件系统
• 2.2.2 个人信息管理系统
• 2.2.3 查询和索引
• 2.3 海量分布式存储技术
• 2.3.1 对等存储技术
• 2.3.2 基于智能存储设备的分布式存储技术
• 2.4 数据相关和系统优化
• 2.5 研究趋势和不足之处
• 2.6 本章小结
• 第3章 DDSM:分布式数据存储和管理系统
• 3.1 引言
• 3.2 系统简介
• 3.3 数据模型
• 3.3.1 基本概念
• 3.3.2 数据浏览
• 3.3.3 数据检索
• 3.4 体系架构
• 3.4.1 分布式存储子系统
• 3.4.2 检索子系统
• 3.4.3 相关检测和系统优化
• 3.5 本章小结
• 第4章 CDOS:基于容器的分布式对象存储
• 4.1 引言
• 4.2 基于容器的存储模型
• 4.2.1 相关概念
• 4.2.2 体系结构
• 4.3 自组织运行时元数据维护
• 4.3.1 对等覆盖网络
• 4.3.2 容器索引
• 4.3.3 对象索引
• 4.4 基于状态的对象访问和复本一致性
• 4.4.1 容器复制
• 4.4.2 容器状态
• 4.4.3 对象操作
• 4.4.4 容器恢复
• 4.5 实验和结果分析
• 4.6 与相关工作对比
• 4.7 本章小结
• 第5章 相关检索和图最短路径索引DIX
• 5.1 引言
• 5.2 DIX:有向图最短距离索引
• 5.2.1 生成树和区间编码
• 5.2.2 跳转图和导出树
• 5.2.3 关键数据结构计算算法
• 5.2.4 DIX-C:常数查询时间索引
• 5.2.5 DIX-2HC:基于两跳覆盖的索引
• 5.3 UDIX:无向图最短距离索引
• 5.3.1 无向导出树和最小跳转图
• 5.3.2 索引算法
• 5.4 相关检索
• 5.5 实验和结果分析
• 5.5.1 实验设置
• 5.5.2 结果分析
• 5.6 本章小结
• 第6章 访问相关挖掘和基于相关的数据预取
• 6.1 引言
• 6.2 对象访问相关
• 6.2.1 不同粒度的访问相关
• 6.2.2 基于日志的相关衡量
• 6.3 无支持度限制的单机访问相关挖掘算法
• 6.3.1 横向挖掘算法
• 6.3.2 纵向挖掘算法
• 6.4 无支持度限制的分布式访问相关挖掘算法
• 6.4.1 预处理
• 6.4.2 挖掘算法
• 6.4.3 关于复制
• 6.5 实验及结果分析
• 6.5.1 实验设置
• 6.5.2 挖掘性能
• 6.5.3 分布式挖掘准确率
• 6.5.4 基于相关的预取
• 6.6 本章小结
• 第7章 基于高相似副本的关键词提取和查询改进
• 7.1 引言
• 7.2 系统模型
• 7.3 PAKE关键词自动提取方法
• 7.3.1 用于高相似副本检测的chunk指纹
• 7.3.2 关键词覆盖网络KON
• 7.4 实验和结果分析
• 7.4.1 实验设置
• 7.4.2 衡量指标
• 7.4.3 结果分析
• 7.5 本章小结
• 第8章 总结和展望
• 8.1 本文主要工作概述
• 8.1.1 本文工作
• 8.1.2 本文主要创新点
• 8.2 缺点和不足
• 8.3 未来工作展望
• 参考文献
• 致谢
• 作者简历