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

作     者：郎贤波 

作者单位：南京邮电大学 

学位级别：硕士

导师姓名：季一木

授予年度：2017年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：大数据 流查询 流连接 流计算平台 

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