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

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

作　者: 余利华
导　师: 董金祥；陈刚
学　校: 浙江大学
专　业: 计算机科学与技术
关键词: 分布式存储语义文件系统个人信息管理系统对象存储对等网络图索引数据挖掘性能优化
分类号: TP311.13
类　型: 博士论文
年　份: 2008年
下　载: 1163次
引　用: 2次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  4-6
ABSTRACT  6-14
第1章绪论  14-21
  1.1 引言  14-16
  1.2 数据相关  16-17
  1.3 研究内容  17-19
  1.4 论文组织  19-21
第2章相关工作综述  21-35
  2.1 引言  21
  2.2 存储管理系统  21-26
    2.2.1 语义文件系统  21-23
    2.2.2 个人信息管理系统  23-25
    2.2.3 查询和索引  25-26
  2.3 海量分布式存储技术  26-30
    2.3.1 对等存储技术  27-29
    2.3.2 基于智能存储设备的分布式存储技术  29-30
  2.4 数据相关和系统优化  30-32
  2.5 研究趋势和不足之处  32-34
  2.6 本章小结  34-35
第3章 DDSM:分布式数据存储和管理系统  35-52
  3.1 引言  35-36
  3.2 系统简介  36-38
  3.3 数据模型  38-42
    3.3.1 基本概念  38-40
    3.3.2 数据浏览  40-41
    3.3.3 数据检索  41-42
  3.4 体系架构  42-50
    3.4.1 分布式存储子系统  43-45
    3.4.2 检索子系统  45-49
    3.4.3 相关检测和系统优化  49-50
  3.5 本章小结  50-52
第4章 CDOS:基于容器的分布式对象存储  52-77
  4.1 引言  52-53
  4.2 基于容器的存储模型  53-57
    4.2.1 相关概念  53-56
    4.2.2 体系结构  56-57
  4.3 自组织运行时元数据维护  57-62
    4.3.1 对等覆盖网络  57-58
    4.3.2 容器索引  58-60
    4.3.3 对象索引  60-62
  4.4 基于状态的对象访问和复本一致性  62-72
    4.4.1 容器复制  62-63
    4.4.2 容器状态  63-66
    4.4.3 对象操作  66-71
    4.4.4 容器恢复  71-72
  4.5 实验和结果分析  72-75
  4.6 与相关工作对比  75-76
  4.7 本章小结  76-77
第5章相关检索和图最短路径索引DIX  77-104
  5.1 引言  77-78
  5.2 DIX:有向图最短距离索引  78-92
    5.2.1 生成树和区间编码  79-80
    5.2.2 跳转图和导出树  80-85
    5.2.3 关键数据结构计算算法  85-88
    5.2.4 DIX-C:常数查询时间索引  88-90
    5.2.5 DIX-2HC:基于两跳覆盖的索引  90-92
  5.3 UDIX:无向图最短距离索引  92-95
    5.3.1 无向导出树和最小跳转图  92-94
    5.3.2 索引算法  94-95
  5.4 相关检索  95-97
  5.5 实验和结果分析  97-103
    5.5.1 实验设置  97-100
    5.5.2 结果分析  100-103
  5.6 本章小结  103-104
第6章访问相关挖掘和基于相关的数据预取  104-131
  6.1 引言  104-105
  6.2 对象访问相关  105-109
    6.2.1 不同粒度的访问相关  105-106
    6.2.2 基于日志的相关衡量  106-109
  6.3 无支持度限制的单机访问相关挖掘算法  109-117
    6.3.1 横向挖掘算法  110-113
    6.3.2 纵向挖掘算法  113-117
  6.4 无支持度限制的分布式访问相关挖掘算法  117-123
    6.4.1 预处理  118-119
    6.4.2 挖掘算法  119-122
    6.4.3 关于复制  122-123
  6.5 实验及结果分析  123-130
    6.5.1 实验设置  123
    6.5.2 挖掘性能  123-125
    6.5.3 分布式挖掘准确率  125-126
    6.5.4 基于相关的预取  126-130
  6.6 本章小结  130-131
第7章基于高相似副本的关键词提取和查询改进  131-144
  7.1 引言  131-132
  7.2 系统模型  132-133
  7.3 PAKE关键词自动提取方法  133-138
    7.3.1 用于高相似副本检测的chunk指纹  134-135
    7.3.2 关键词覆盖网络KON  135-138
  7.4 实验和结果分析  138-142
    7.4.1 实验设置  138-139
    7.4.2 衡量指标  139-140
    7.4.3 结果分析  140-142
  7.5 本章小结  142-144
第8章总结和展望  144-149
  8.1 本文主要工作概述  144-146
    8.1.1 本文工作  144-145
    8.1.2 本文主要创新点  145-146
  8.2 缺点和不足  146-147
  8.3 未来工作展望  147-149
参考文献  149-162
致谢  162-163
作者简历  163-164

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

内容摘要

全文目录

相似论文