面向OLAP的大规模分布式内存列式数据库查询引擎

摘要

联机分析处理（On-line Analytical Processing, OLAP）是数据库领域的主要应用，但随着数据量的日益膨胀，如何在海量数据中快速挖掘出数据潜在的价值成为当下数据库领域的一个重大挑战。现有的分布式数据库系统在查询引擎的选择上分为两大类，一类是采用通用计算引擎诸如Map/Reduce或Spark，其最大的缺陷在于，Map/Reduce和Spark在计算模型上仍然属于同步计算模型，在计算上存在同步过程，导致较大的查询延迟，此外基于Spark的分布式数据库系统存在过高的计算内存开销。另一类分布式数据库系统采用专用分布式查询引擎，诸如Impala以及HAWQ等。这类系统将传统数据库查询模型并行化，一定程度上突破了传统数据的计算瓶颈，然而这类数据库依然存在如下不足：1）计算模型沿用传统数据库的volcano模型即按行查询，然而在OLAP业务中，采用按行查询的方式会引入过多的中间数据导致额外的运算开销。2）在分布式计算任务调度上没有很好的调度算法来提升整体的查询速度以及集群资源利用率。
　　本文针对上述系统中存在的缺陷，提出了一种新型的面向OLAP的大规模分布式内存列式数据库查询引擎，该引擎在处理海量数据时拥有较低的查询延迟以及内存开销。论文主要有三方面工作：1）对时下业界热门的分布式数据库查询引擎进行研究与分析，按照通用数据库计算引擎和专用数据库计算引擎对其进行分类，提炼其主要优缺点；将分布式计算任务调度抽象为工作流调度问题（workflow scheduling），研究对比现有的启发式算法，主要包括List Scheduling类算法与遗传算法。2）设计并实现了一套高效的基于列式语义的分布式内存数据库计算引擎，支持从SQL解析到结果数据生成这一完整的查询流程，支持海量数据的实时查询并具有良好的容错性能。3）设计并实现了一套分布式任务调度优化算法，能灵活适应变化的查询场景并快速提供有效的调度优化方案。
　　在系统设计与实现上，本文主要有三点创新：1）采用数据流图表示SQL查询任务，按照列式数据库语义，全异步地推进任务的执行，消除在同步计算模型中因同步过程所带来的计算开销。2）设计并实现高效的列式中间数据结构，具有很好的序列化与反序列化性能并能有效减少内存碎片。3）结合深度增强学习算法与传统启发式调度算法提出了一种新型的分布式任务调度方法来解决工作流调度问题，具有很好的灵活性以及调度结果。
　　最后，本文从查询引擎计算模型的查询性能以及调度优化算法的调度效果两方面对查询引擎进行测试。其中，针对查询性能的测试，本文引入标准的面向OLAP数据库测试集TPC-H对查询引擎进行全面的功能测试以及性能测试；针对调度优化算法，将本文所设计的算法与其他经典的启发式算法调度结果进行对比。测试结果显示，本文所设计的查询引擎在单表扫描语句性能上是Spark-SQL的10倍，是Hive-on-tez的20倍，在Join语句性能上和Spark-SQL持平，在分组聚合语句上性能是Spark-SQL的5倍。在内存开销上本文设计的查询引擎是Spark-SQL的1/8。在调度优化算法上，调度结果要优于其他调度优化算法。

目录

声明

第一章 引言

1.1 研究工作的背景与意义

1.2 国内外研究现状

1.3 本文的主要贡献与创新

1.4 本论文的结构安排

第二章 理论基础及典型系统

2.1 分布式数据库系统查询引擎计算模型

2.2 分布式数据库系统查询引擎调度优化模型

2.3 本章小结

第三章 关键模型与调度优化算法

3.1 基于数据流图的异步分布式数据库列式计算模型

3.2 调度优化代价模型

3.3 基于深度增强学习的调度优化算法

3.4 本章小结

第四章 面向OLAP的分布式内存数据库查询引擎的设计

4.1 应用场景和设计目标

4.2 系统架构设计

4.3 系统关键模块详细设计

4.4 系统主要流程设计

4.5 本章小结

第五章 面向OLAP的分布式内存数据库查询引擎的实现

5.1 基础工具库的实现

5.2 代价模型的实现

5.3 任务调度模块的实现

5.4 计划执行模块的实现

5.5 计算中间数据结构的实现

5.6 本章小结

第六章 系统测试与结果分析

6.1 测试环境

6.2 系统功能测试

6.3 系统性能测试

6.4 本章小结

第七章 总结与展望

7.1 工作总结

7.2 后续工作展望

致谢

参考文献

攻硕期间取得的研究成果