基于大数据平台的流连接算法及并行化研究

摘要

近些年来，流式计算（Computing of Stream）作为大数据领域中一个非常重要的研究内容，在学术界和商业界得到了越来越多的关注。在很多实时流数据查询场景中，对流数据处理的时效性要求非常严格。随着数据规模的日渐增大，国内外出现了很多流式计算系统。其中具代表性的有斯坦福大学的STREAM系统以及Twitter的Storm系统，但上述系统对流查询算法的设计过于简单，因此不能满足较为复杂的实时流查询业务需求。流连接作为实时流查询中一个具有代表性的数据处理算法，具有重要的研究意义。随着大数据与云计算的发展，流连接算法在大数据平台上的实现正面临着新的问题和挑战，主要集中体现在以下三个方面：
　　（1）现有的流连接算法如何在大数据平台上进行设计与实现；
　　（2）如何提高流连接算法的效率；
　　（3）如何结合大数据平台上实现并行化连接。
　　本文对以上问题进行了深入的分析和研究，对流数据处理框架及其相关技术进行充分的调研。首先对传统流连接算法的窗口更新方式做了改进，提出了一种针对数据流量不稳定的窗口更新的流连接算法。通过计算连接代价模型，周期性地选择合适的更新周期；同时，针对流连接并行化，通过结合流连接语义本文设计了一种基于一致性Hash的数据流分发策略，该策略首先对连接语义进行分析生成连接计划，选择出最优的连接方案，根据连接关系将流数据分发到相同的节点中进行计算，在大数据平台上实现并行化连接。
　　由于流数据本身具有无限且连续变化的特点，连接算法的时间和空间复杂度急剧增加，不能满足实际的应用需求，本文采用流式计算平台Storm，对流连接算法并行化实现进行了设计，最后通过实验说明算法在结果输出量、实时性等方面有较好的性能。

目录

声明

第一章 绪论

1.2国内外研究现状

1.3论文的主要工作

1.4论文结构

第二章 相关背景知识介绍

2.1大规模批处理系统

2.2流式处理系统

2.3其他相关技术

2.4本章小结

第三章 基于时间滑动窗口改进的流连接算法

3.1基于滑动窗口的流连接算法及代价模型

3.2基于时间滑动窗口改进的流连接算法AT-WJoin

3.3实验结果与分析

3.4本章小结

第四章 基于大数据平台的流连接并行化研究

4.2基于大数据平台的实时连接查询SP-Join框架

4.3本章小结

第五章 基于Storm的流连接算法设计与实现

5.1Storm集群环境搭建

5.2基于Storm的数据流连接算法AT-WJoin

5.3实验结果对比分析

5.4本章小结

第六章 总结与展望

6.2下一步工作

参考文献

附录1 攻读硕士学位期间撰写论文

附录2 攻读硕士学位期间申请的专利

附录3 攻读硕士学位期间参加的科研项目

致谢