论文部分内容阅读
随着大数据时代的来临以及大数据概念的普及,人们已经普遍认识到大规模数据信息资源的巨大价值,大数据时代会像互联网时代一样,给人类社会带来巨大的改变和发展机遇。然而,机遇总是伴随着挑战,在大数据分析应用所涉及的存储管理和计算分析等技术环节上,都面临着诸多的技术挑战。在大数据存储管理和查询技术上,传统的关系数据库无法适应大数据环境下的分布式存储管理和查询需求。关系数据库难以进行横向扩展,也难以有效应对非结构化和半结构化数据的高效存储和查询需求。计算机硬件的发展和体系结构的演变,使得数据索引和查询优化方法必须考虑新的硬件性能和体系结构特点。大规模分布式数据存储管理和查询研究受到了国内外研究团队的普遍关注,如最广为接受和使用的HBase系统、Facebook公司的Cassandra等诸多系统为大数据分布式数据管理和查询分析应用提供了良好的支撑。然而,由于现实世界中行业大数据容量巨大、数据形态复杂多样,现有的大数据管理技术与系统在数据的查询管理能力和查询性能上还不能完全满足实际应用的要求,技术上还远未达到完全成熟的地步。例如,HBase虽然较好地解决了高扩展性问题,可以存储管理高达数百亿以上规模的数据记录,然而,HBase只提供了主键索引,对于非主键属性上的数据查询效率低下。分布环境下的大数据存储管理与查询在索引方法、查询性能优化、数据一致性、系统可扩展性等方面,比传统数据库系统面临更多的技术难题和技术挑战,也带来了更多需要研究解决的问题。基于上述问题和背景,本文对大数据的存储管理和查询优化技术进行了一系列的研究。具体而言,本文工作包括以下主要技术内容和贡献:(I)基于热度累积缓存的分层式非主键索引方法HBase只有主键上的索引机制,不支持非主键索引,这导致HBase的非主键数据查询效率低下,难以满足数据实时/准实时查询需求。本文研究提出了一种分层式HBase非主键索引查询模型和方法,包括基于HBase的持久性索引和基于内存的索引热点数据缓存方法。在内存索引缓存层中,提出一种高效的热度累积缓存替换策略,更大程度地减少对HBase持久性存储层中索引表的磁盘访问开销。该方法不仅具有更高的缓存命中率和更快的查询响应时间,也表现出了良好的可扩展性。(2)基于热度自适应数据分片的大数据范围查询优化方法大数据上的范围查询通常具有倾斜特征,倾斜范围查询负载下的数据具有不同程度的相关性。通过面向数据片的方式管理和查询数据,将相关性强的数据划分成数据片,可以从时间和空间效率上优化范围查询。本文研究提出一种面向数据片的跳表索引结构及基于热度自适应数据分片的缓存调度算法,通过跳表索引结构来组织和管理冷热数据片。基于提出的累积热度和平均查询访问占比两个指标,基于热度自适应数据分片的缓存调度算法通过分裂合并方法调整分片的边界和长度,使得数据分片能够快速、持续地捕获查询模式。在缓存空间限定下,该方法通过自适应地调整数据分片来最大化缓存空间利用率和范围查询的缓存命中率,从而提高范围查询的效率。通过控制冷热数据片的分片粒度,将热数据做细粒度分片,而冷数据做粗粒度分片,可以同时获得分片拟合查询分布的精度和算法的空间效率。(3)基于关联感知模型的数据分片优化方法通过研究大数据上范围查询的特征和累积概率分布规律,本文提出了关联感知的数据分片优化模型和基于该模型的范围查询数据分片优化方法。关联感知的数据分片优化模型把倾斜范围查询下的数据分片优化问题转化为一个几何意义上的阶梯曲线拟合问题。基于关联感知模型的范围查询数据分片优化方法以最小化查询代价为优化目标,计算出数据分片优化方案。在获得最优分片的前提下,本文致力于提高分片算法的效率,研究提出并证明了如下结论:范围查询上符合查询累积概率分布规律的数据分片切分位置一定会落在范围查询边界上。据此结论,本文提出了基于动态规划的范围查询边界分片优化算法,在确保获得最优数据分片方案的条件下,大幅降低算法的时间复杂度,提高分片算法的效率。继而又提出了自底向上合并的范围查询边界分片优化算法,用合并分片替代检索分片位置的方法,算法的分片效率得到了进一步提高。(4)基于上述关键技术方法,本文在HBase上设计实现了相应的完整系统。其中,基于分层式非主键索引的查询系统HiBase己经成为中兴通讯公司的产品,并在国内多家银行得到大规模的实际推广应用,取得显著的推广应用效果。进一步,基于热度自适应调整数据分片和基于关联感知模型的数据分片优化方法也在HiBase系统中得到集成和实现。实验结果表明,系统对于分布式环境下大数据的查询优化具有显著的提升效果,相比于标准HBase和华为同类的Hindex系统,查询性能都有非常明显的提升。相比于将非主键属性上的范围查询转化为在内存中并行执行批量单值查询的方法,数据分片算法对范围查询的性能提升可以达到两个数量级。