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

大规模网络存储环境中的数据布局与查询优化技术研究

作　者: 陈涛
导　师: 肖侬
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 大规模网络存储数据布局多个top-k查询共享多个聚合查询共享元数据负载均衡
分类号: TP333
类　型: 博士论文
年　份: 2011年
下　载: 67次
引　用: 0次
阅　读: 论文下载

内容摘要

日益增长的海量数据的有效管理已经成为科学研究、工程以及信息服务等领域的巨大挑战性问题。海量数据对大规模网络存储环境提出了巨大的需求,使得现有的大规模网络存储技术在可扩展性、高性能、并发、综合效能、分布管理、安全可用、数据一致性以及可靠性等方面已经不能满足分布海量数据管理应用的需要。因而,研究大规模网络存储技术具有重大的意义。本文对大规模网络存储环境涉及的数据布局、查询优化以及元数据负载均衡等关键技术进行深入研究,提出了有效的解决方案和算法,主要的研究工作和创新点如下:(1)提出了一种面向多副本的自适应数据布局算法RSEDP。大规模存储系统的可靠性和自适应性面临着重大的挑战,需要可靠、自适应以及有效的数据布局算法,现有的研究只能部分满足这些目标。本文首先提出了一种可靠的副本数据布局算法RRDP和一种有效的自适应数据布局算法SEDP,在此基础上,将两种算法相结合,提出了一个面向多副本的自适应数据布局算法RSEDP,从而获得可靠性、自适应性和有效性。RRDP将相同的副本分配在不同的存储设备上,避免相同的副本集中到相邻的存储设备上,获得较高的冗余度和容错能力。SEDP算法将聚类算法与一致hash方法相结合,引入少量的虚拟存储设备,大大减少了算法对存储空间的消耗。可以根据存储设备的权重公平地分布数据,自适应系统的扩展和缩减。为了利用RRDP和SEDP各自的优点,RSEDP根据数据的访问频率将数据划分为热数据和冷数据,热数据采用RRDP布局,冷数据采用SEDP布局。理论和实验结果表明,RSEDP可以获得较高的冗余度和容错能力,按照存储设备的权重公平地分布数据,自适应存储设备的增加和删除,在存储规模发生变化时迁移最优的数据量,并且可以快速地定位数据,对存储空间的消耗较少。(2)提出了一种高效的分层数据布局算法EHDP。目前大部分的布局算法只能适应单层模式,少数的多层模式对存储设备配置有严格的要求,而且无法在常数时间内定位数据,自适应性较差。本文提出了一种新的分层数据布局算法EHDP,首先使用最大最小聚类算法将存储设备集合进行分类,采用分而治之的方法管理大规模的存储设备,支持灵活的存储设备配置;然后使用本文提出的EFAH hash算法在集群间和集群内分布数据。理论和实验结果表明:EHDP可以在常数时间内定位数据,从而减轻元数据服务器的计算量,避免性能瓶颈;同时可以在存储设备之间较公平地分布数据,达到I/O负载均衡的目的;而且在存储设备集合变化时,迁移较少的数据量以满足数据再次分布的公平性,在平衡I/O负载的同时尽可能不影响存储系统对外的服务性能。(3)提出了面向不确定数据流的多个top-k查询优化算法。在大规模网络存储的某些应用中,数据以流的形式存在。由于外在的因素,不确定性是应用数据流的固有特征。不确定数据流上的top-k查询处理越来越重要,如何在多个top-k查询之间共享结果是节省计算开销以及提供实时响应的关键。然而,由于不确定top-k查询处理的复杂语义,在多个top-k查询之间共享结果面临着重大挑战。本文首次对单个top-k查询处理的频率上限进行了定义,对多个top-k查询的共享进行了分类,提出了一个最优的动态规划以及在时空上更有效的贪心算法来解决该共享问题。使用理论分析证明了动态规划与不共享的性能上界,以及贪心算法与动态规划方法的性能下界。实验结果表明,本文提出的贪心算法在多数情况下可以找到最优解,在访问延迟与吞吐量上可以达到与动态规划方法相同的性能;与不共享方法以及组内共享方法相比,动态规划以及贪心算法使得执行查询时的计算开销大大减少,获得高吞吐量和低访问延迟。(4)提出了一种面向数据流的多个聚合查询优化算法。大规模网络存储的很多应用将数据流上的聚合查询注册到系统中,这些查询具有不同的滑动窗口大小以及不同的频率上限,如何在查询中共享计算结果面临着挑战。相关文献首先提出了该问题,使用最早截止时间优先EDF方法。但是该方法没有提出具体的优化算法。本文对具有不同滑动窗口大小和不同频率上限的多个聚合查询的优化问题进行了形式化定义,提出了一个合并规则对查询进行分类。然后,提出有效的共享算法来求解查询的执行计划,只要连续两次执行查询的时间间隔不大于频率上限,则查询可以更频繁地被执行,从而使得更多的查询能够共享计算结果。考虑低载和超载两种情况,本文将共享算法与EDF方法结合。实验结果表明,与不共享方法和EDF方法相比,本文提出的共享算法使得执行查询时扫描的元组数大大减少,得到较高的吞吐量以及较低的访问延迟。(5)提出了一种自适应的分布式元数据负载均衡算法ADMLB。大规模存储环境中元数据的负载均衡对于提高整个系统的I/O性能具有重要的作用。现有的元数据负载均衡策略不能动态地平衡元数据的访问负载,而且自适应性和容错性有待提高。本文首先提出了基本的负载均衡算法(BBLA)和分布式的增量负载均衡算法(IBLA),在此基础上,将两种算法相结合,提出了自适应的分布式元数据负载均衡算法(ADMLB)。采用基本的负载均衡算法(BBLA)按照服务器的性能公平地分布负载,使用分布式的负载均衡算法(IBLA)定时地调整负载的分布。ADMLB可以在元数据服务器之间均衡地分布负载,根据负载的变化自适应地调整负载的分布,具有很好的容错性,而且可以很快地定位元数据服务器。

全文目录

摘要  9-11
Abstract  11-14
第一章绪论  14-38
  1.1 研究背景  14-18
  1.2 相关研究  18-32
    1.2.1 数据的布局  18-28
    1.2.2 数据的多个查询的共享  28-31
    1.2.3 元数据的负载均衡  31-32
  1.3 本文工作  32-35
  1.4 论文结构  35-38
第二章面向多副本的自适应数据布局算法RSEDP  38-58
  2.1 可靠的副本布局算法RRDP  39-43
    2.1.1 RRDP 问题  39-40
    2.1.2 RRDP 的半定规划松弛问题  40-42
    2.1.3 计算开销  42-43
  2.2 有效的自适应数据布局算法SEDP  43-51
    2.2.1 问题的定义  43-44
    2.2.2 有效的自适应数据布局算法SEDP  44-46
    2.2.3 数据的重组织  46-47
    2.2.4 理论分析  47-51
  2.3 实验和结果分析  51-56
    2.3.1 冗余度  52-53
    2.3.2 容错特性  53
    2.3.3 公平性  53-55
    2.3.4 自适应性  55-56
  2.4 小结  56-58
第三章高效的分层数据布局算法EHDP  58-74
  3.1 问题描述  58-59
  3.2 高效的分层数据布局算法EHDP  59-62
  3.3 算法分析  62-66
    3.3.1 高效特性  62-64
    3.3.2 公平性  64-65
    3.3.3 自适应性  65-66
  3.4 实验和结果分析  66-70
  3.5 布局算法的分析与比较  70-71
  3.6 小结  71-74
第四章面向不确定数据流的多个top-k 查询优化算法  74-106
  4.1 引言  75-77
  4.2 具有相同FREQUENCY 和不同k 值的查询之间的共享  77-80
  4.3 共享问题的形式化定义  80-82
  4.4 动态规划方法  82-90
  4.5 贪心算法  90-96
  4.6 实验与结果分析  96-103
    4.6.1 实验设置  96-98
    4.6.2 实验结果  98-103
  4.7 小结  103-106
第五章面向数据流的多个聚合查询优化算法  106-116
  5.1 引言  106-107
  5.2 问题的形式化定义  107-109
  5.3 高效的共享算法SA  109-112
  5.4 共享算法与EDF 的结合算法  112-113
  5.5 实验与结果分析  113-115
    5.5.1 SA 和No-S 的比较  113-114
    5.5.2 Co-SA 和EDF 的比较  114-115
  5.6 小结  115-116
第六章自适应的分布式元数据负载均衡算法ADMLB  116-128
  6.1 模型及相关概念  116-118
  6.2 自适应的分布式负载均衡算法ADMLB  118-121
    6.2.1 基本的负载均衡算法  118-119
    6.2.2 分布式的增量负载均衡算法  119-121
  6.3 ADMLB 算法的特性分析  121-124
    6.3.1 自适应性  121-122
    6.3.2 容错特性  122
    6.3.3 元数据服务器的定位及访问流程  122-124
  6.4 实验与结果分析  124-126
  6.5 小结  126-128
第七章结论与展望  128-132
致谢  132-134
参考文献  134-144
作者在攻读博士学位期间发表的学术论文  144-146
作者在攻读博士学位期间参加的主要科研工作  146

大规模网络存储环境中的数据布局与查询优化技术研究

内容摘要

全文目录

相似论文