论文部分内容阅读
在移动互联网时代,各行各业所产生的数据已经成为了一种重要的生产要素,其背后蕴藏着巨大的价值。然而,面对持续增长的数据规模和不断产生的分析请求,单机架构下的数据库查询已经无法利用有限的硬件资源来满足低延时、高吞吐的数据分析需求。为此,学术界和工业界开始尝试将数据库查询部署在横向可扩展的分布式架构上,旨在利用分布式架构中充沛的硬件资源来提升数据库查询的性能。由于传统单机架构与分布式架构间的硬件环境差异,传统的查询处理方式往往无法充分利用分布式架构中可观的硬件资源,从而导致较低的性能提升。因此,如何充分地利用分布式架构中可扩展的硬件资源来提升数据库查询的性能便成了一个值得探讨的问题。本文研究分布式架构下数据库查询的并行处理技术,其主要围绕扫描算子、单查询和多查询这三个方面展开,重点关注以下三个问题:首先,对于扫描算子而言,当目标数据聚集在某些节点上时,当前并行扫描策略所产生的多个扫描子任务也会堆积在这些节点上,但却忽视了其它节点上的数据副本,从而无法充分利用分布式架构中多节点间的并行扫描能力。其次,对于单个数据库查询而言,分布式共享内存架构可以将不同节点上的内存资源抽象成为一片共享的内存空间,使得传统单机架构下的查询处理方案能够运行在分布式共享内存之上。但与单机架构相比,分布式共享内存架构仍是一个依赖网络连接的松耦合实现,容易导致查询处理过程中产生大量的网络通信开销,从而影响查询的处理性能。最后,对于多个数据库查询而言,一些类似的查询请求往往有着相同的查询算子,其容易构建出高度重叠的数据结构,导致了分布式架构中计算资源和内存资源的浪费,从而影响了多查询的并行处理性能。基于上述三个关键问题,本文的主要工作和贡献如下:(1)基于分布式共享存储中多副本的并行扫描方案:在共享存储架构中,数据表会被划分成为多个数据分片,存放在不同节点上。因此,当一个扫描算子涉及到多个数据分片时,该算子也可被划分成多个扫描子任务,从而并行地访问这些数据分片。然而,当某些节点拥有较多的数据分片时,扫描子任务也会聚集在这些节点上,从而只能实现有限节点间的并行扫描。基于此,本文提出了一种基于多副本的并行扫描方案,其核心思想是利用副本间的数据并行性,使得针对单个分片的扫描子任务被进一步划分成针对多个分片副本的扫描子任务,从而并行运行在不同节点的不同副本上,进而充分利用了多节点间的并行扫描能力。在多副本并扫描基础之上,本文还提出了一种基于线性规划模型的扫描划分策略,使得不同节点承担着相似的扫描负载。此外,本文还为每个节点设计一套多线程并行调度策略,保证并行扫描过程中节点内多线程间的负载均衡,且尽量降低单个线程内的任务切换开销。(2)分布式共享内存架构下网络敏感的查询处理框架:分布式共享内存架构打破了机器节点间的内存资源隔离,将不同机器节点上的内存暴露在统一的地址空间之下,使得单机架构下的查询处理方案可以快速部署到分布式架构下。但与单机共享内存架构相比,分布式共享内存架构仍是一个借助于网络连接的松耦合实现。因此,当传统的查询处理方案部署在分布式共享内存架构上时,一些普通的读写操作也可能频繁触发跨节点的内存访问,从而带来不菲的网络通信开销。为此,本文提出了一套网络敏感的查询处理框架。为了避免查询处理过程中存在网络带宽瓶颈,本文为该框架设计了一种交错调度策略,使得有着频繁网络通信的查询流水线可以和其它流水线交错处理,从而降低查询处理过程中的网络带宽消耗。此外,为了尽量减少查询处理过程中高时延的跨节点内存访问,本文还为该框架设计了一种基于赋权二部图的流水线子任务分配策略,使得流水线的处理过程有着较高的数据局部性。(3)面向多个哈希连接查询的块状哈希表重用方案:在数据分析场景下,频繁使用的哈希连接查询往往会构建相似的哈希表数据结构,从而浪费了大量的计算资源和内存资源。为此,本文尝试利用分布式架构中的大内存特点,将过往哈希连接查询所构建的哈希表数据结构缓存起来,使得后续查询能够重用这些数据结构,进而降低了多查询并行处理时的资源开销,提升多查询的并行处理性能。不同于已有的缓存重用方案,本文中的哈希表重用方案采用了块状管理机制,使得缓存中的每个哈希表被拆分成多个互不重叠的块状哈希表。因此,后续查询可以根据自身谓词条件来灵活地重用那些较为匹配的块状哈希表,从而提升了复杂谓词条件下的哈希表重用率。此外,本文还提出一种高效的调度策略,其可以同时从查询时延和查询吞吐的角度出发,灵活地选择不同的调度方式来较好地协调块状哈希表重用与缓存更新间的冲突。综上所述,本文深入研究了分布式架构下数据库查询的并行处理方式,从扫描算子、单查询和多查询的角度出发,进一步探讨了并行处理过程中的优化点,并给出了具体的优化方案。