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

发布时间：2020-05-21 15:57

【摘要】：日益增长的海量数据的有效管理已经成为科学研究、工程以及信息服务等领域的巨大挑战性问题。海量数据对大规模网络存储环境提出了巨大的需求,使得现有的大规模网络存储技术在可扩展性、高性能、并发、综合效能、分布管理、安全可用、数据一致性以及可靠性等方面已经不能满足分布海量数据管理应用的需要。因而,研究大规模网络存储技术具有重大的意义。本文对大规模网络存储环境涉及的数据布局、查询优化以及元数据负载均衡等关键技术进行深入研究,提出了有效的解决方案和算法,主要的研究工作和创新点如下: (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可以在元数据服务器之间均衡地分布负载,根据负载的变化自适应地调整负载的分布,具有很好的容错性,而且可以很快地定位元数据服务器。
【图文】：

特性图,冗余度,存储设备,容错特性

图 2.8 RSEDP 和 RR 的冗余度性特性来表示失效存储设备上的副本在其他存备失效时，其他存储设备上存储了该存储设定位到其他存储设备上。容错特性可以反映9 显示了存储设备 16 失效时，其副本在其他以看出，RSEDP 可以将存储设备 16 上的负2.9(b)表示 CD 将存储设备 16 的负载分散到了 RR 的容错特性，高柱子表示对应的存储低柱子表示相应存储设备上有较少的失效存RSEDP 的容错特性远远好于 CD，同时比 R

存储设备,副本,分布情况,容错特性

图 2.8 RSEDP 和 RR 的冗余度2.3.2 容错特性我们使用容错特性来表示失效存储设备上的副本在其他存储设备上的分布情况。当一个存储设备失效时，其他存储设备上存储了该存储设备的副本，，则该存储设备上的负载被定位到其他存储设备上。容错特性可以反映存储设备失效时负载均衡情况。图 2.9 显示了存储设备 16 失效时，其副本在其他存储设备上的分配情况。从图 2.9(a)可以看出，RSEDP 可以将存储设备 16 上的负载公平地分配到其他存储设备上。图 2.9(b)表示 CD 将存储设备 16 的负载分散到相邻的 4 个存储设备上。图 2.9(c)显示了 RR 的容错特性，高柱子表示对应的存储设备上有较多失效存储设备上的负载，低柱子表示相应存储设备上有较少的失效存储设备上的负载。从图 2.9 可以看出，RSEDP 的容错特性远远好于 CD，同时比 RR 好。
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：TP333

【相似文献】