论文部分内容阅读
伴随网络和云计算技术的飞速发展,全球数据倍增,数据量级已达TB、PB级,形象地被称为海量数据或者大数据。同时,数据背后隐藏的信息的价值也越来越高,不仅能为拥有这些数据的企业提供决策和商机,也能为人类享受更加方便、智能、快捷的服务提供支持。数据的种类越来越多,结构更加复杂,各种结构化、半结构化、无结构数据产生于各种各样的应用环境中,人类迎来了大数据时代。大数据时代背景下,数据的价值受到了前所未有的重视,人们将越来越多的目光投向大数据分析与处理。传统的关系数据管理和分析、并行计算技术由于其自身的限制不能应对大数据带来的挑战,需要新的理论和技术来支撑大数据的分析和处理。MapReduce作为新兴的数据密集型计算编程模型的代表,由于其具备良好的可扩展性,高的容错性和可使用廉价机器代替昂贵的服务器等优势,在大数据分析与处理方面发挥了不可替代的作用,但是它不直接支持连接,增加了分析和处理关系型数据的难度。连接是一种基础的关系代数运算,是分析和处理关系型数据的有效手段。现有的基于MapReduce的连接方法大多只关注等值连接,但是大数据的深度分析工作仅仅靠简单的等值连接是无法完成的,需要MapReduce有效处理更复杂的连接类型,比如叉积、θ-连接等。仅有的关注θ-连接方面的研究,或者描述不够详尽,难于理解和实现,或者不能适应多变的计算环境。基于以上原因,本文提出了一种简单而有效的θ-连接处理方法,简单体现在思想简单易懂,描述详尽;有效体现在能够根据不同输入设置Reducer个数,适应多变的计算环境。该方法命名为Adaptive Share MapReduce Theta(ASMRT),含义为基于MapReduce的可调整份额的θ-连接算法。该算法包括MapReduce Theta(MRT)和Adaptive Share(AS)两部分,AS算法根据各数据集的记录数量,设置合理的权衡因子,求解各数据集的份额和Reducer个数;MRT算法根据各数据集的份额和Reducer个数完成θ-连接。算法的理论模型MRT分区模型采用与连接记录无关的量对数据集进行逻辑划分,既符合MapReduce处理任意连接条件θ-连接的分区逻辑,使得MapReduce处理θ-连接成为可能,又可从本质上避免由于数据集中记录的键值分区不均而引发的数据偏移问题的发生。为验证MRT算法的可行性与AS算法的有效性,本文实现了ASMRT算法,构造有代表性的例子对AS的有效性进行了分析;从关系代数理论分析了MRT算法;结合抽象例子将MRT算法与SRJ算法进行对比分析,结果表明ASMRT能够利用一次MapReduce过程简单而有效地处理任意连接条件的多路θ-连接。