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