内存数据库并行化查询技术研究

摘要

随着大容量内存的出现和内存价格的逐渐降低，内存数据库开始被广泛使用。内存数据库带来性能提升的同时，也带来了新的挑战。由于内存存取速度的增长难以匹配处理器速度的增长，导致在数据查询中，内存访问延迟已经成为数据库查询的主要代价之一。多核处理器的出现，使得上述问题更加严重。与此同时，数据规模的增大，导致数据处理过程中出现临时错误和数据倾斜的机会增加，查询算法需要一定的纠错能力，避免整个任务的重新执行。多线程并行访问共享Cache造成的访问冲突会给查询执行性能造成负面影响。此外，有限的内存带宽和多核处理器各个核心间的负载不均衡也影响了线程的执行效率。因此，需要充分利用共享Cache多核处理器的处理性能，减少共享Cache访问冲突对内存数据库查询优化。面向多核处理器的此类优化尚有许多问题需要解决。
　　本文针对数据库查询的并行执行进行研究。针对连接查询存在的性能瓶颈，在共享Cache多核处理器环境下进行连接查询的相关优化。主要工作和创新点如下:
　　提出了基于数据划分策略的多线程并行聚集连接算法。针对内存受限的服务器，分别提出了Radix-Join算法和Sort-Merge Join算法的并行算法，并针对多核共享Cache环境下对算法进行了优化。在数据划分阶段，提出了一种自适应的划分策略，使得多线程执行可以随可用内存大小变化策略;在聚集连接阶段，提出了基于数据规模灵活变化的并行连接执行策略，并优化了聚集连接时的内存访问。上述优化技术能够较大减少多线程执行时的共享Cache访问冲突和处理器核心间的负载不均衡，提高了线程的执行效率。
　　针对传统连接算法缺少灵活的调度和必要的容错能力，提出了基于MapReduce的连接并行执行框架。与Radix-Join算法类似，该框架主要分为Map和Reduce两个阶段，适合使用数据划分策略。本文分析了内存连接的各个阶段对Join算法性能的影响，提出了一种可利用MapReduce的动态机制，避免传统并行连接算法实现的数据任务分派不均和容错问题。算法使用MapReduce编程框架，并通过封装分块标记减少MapReduce Join执行过程中标记和排序的计算开销，使算法性能显著提高。实验结果表明，该算法在共享内存体系结构下在性能上相比已有算法有显著提升。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 相关问题的研究现状

1．2．1 面向多核处理器的数据库优化

1．2．2 Cache敏感算法研究现状

1．2．3 MapReduce Join算法研究现状

1．3 本文的主要研究内容和贡献

1．4 本文的组织

第2章 相关背景知识

2．1 计算机存储结构

2．1．1 Cache和内存层次

2．1．2 虚拟内存和地址转换

2．1．3 多核和多线程并行

2．2 MapReduce编程模型

2．2．1 工作原理

2．2．2 模型的不同实现

2．2．3 模型的应用

2．3 内存Hash连接算法

2．3．1 标准Hash连接算法

2．3．2 基于划分的Hash连接

2．3．3 Radix-Join

2．4 本章小结

第3章 面向多核处理器的聚集连接优化

3．1 面向多核的并行聚集连接

3．1．1 面向多核的Hash并行连接

3．1．2 面向多核的Sort-Merge并行连接

3．2 算法的进一步优化

3．2．1 并行MCJoin优化

3．2．2 并行MCSM优化

3．3 实验模拟及结果分析

3．3．1 实验数据

3．3．2 实验设置

3．3．3 实验结果与分析

3．4 本章小结

第4章 基于MapReduce的数据聚集连接

4．1 面向多核结构的MapReduce系统

4．1．1 系统简介

4．1．2 系统的整体框架

4．2 朴素的MapReduce Join算法

4．2．1 数据划分

4．2．2 Map阶段

4．2．3 Reduce阶段

4．3 改进的MapReduce Join算法

4．3．1 数据划分优化

4．3．2 Map阶段优化

4．3．3 Reduce阶段优化

4．4 实验及结果分析

4．4．1 实验设置

4．4．2 实验数据

4．4．3 实验结果及分析

4．5 本章小结

第5章 总结与展望

5．1 本文总结

5．2 将来进一步工作

参考文献

致谢

在读期间发表的学术论文与取得的其他研究成果