论文部分内容阅读
MapReduce是一种并行分布式计算模型，用于大规模数据集的并行运算。它具有良好的可扩展性、容错性、可用性，现在，无论在工业界还是在学术界都得到了广泛的应用。MapReduce比较热门的一个应用领域是处理大型表的连接操作，其中连接操作广泛应用于日志分析、数据分析处理以及联机分析处理等方面。应用MapReduce模型来处理连接操作，可以大幅度提高连接操作的速度，进而提高了数据分析效率和用户满意度。 现有的基于MapReduce的连接算法，按连接表的数量可以分为两表连接和多表连接两种。目前，针对两表连接的研究优化已经相当成熟，而针对多表连接的算法及其优化仍有很大的改进空间。特别是在处理链式多表连接时，现有的基于MapReduce的多表连接算法还存在很多的不足，具体体现在以下两个方面:(1)不能处理多个大表的连接。比如Smart Join算法，它的应用场景只适合于处理两个大表和多个小表之间的连接，并且两个大表之间必须有连接键;(2)需要顺序运行较多的MapReduce任务，效率较低。比如级联连接算法，在连接中排序靠后的表必须等待它前面的所有表完成连接后，再和它们的连接结果进行连接。所以，在应用场景不确定的情况下，采用现有的基于MapReduce的多表连接算法，或是不能有效执行多表链式连接，或是执行连接所需的时间太长不能满足实际需求。 本文提出了一个基于MapReduce的多表连接算法——Pipeline Join算法，该算法有效解决了现有的基于MapReduce的多表连接算法中存在的问题，可以高效地实现任意多个大表的链式连接。对于现有的基于MapReduce的多表连接算法不能处理多个大表的连接的问题，Pipeline Join算法的解决方法是:首先把待连接的表进行切割，然后采用调度器的方式，对来自不同表或不同连接结果集的待连接片段进行调度连接，这样通过切割调度就可以实现多个大表的连接。另外，对于现有的基于MapReduce的多表连接算法需要顺序运行较多的MapReduce任务，效率较低的问题，PipelineJoin算法的解决方法是:采用流水线模型，实现MapReduce任务的流水线式执行，从而有效提高了多表连接的效率。最后，本文在不同规模的数据集上对Pipeline Join算法进行了大量实验，实验结果表明Pipeline Join算法与原有链式多表连接算法相比，可以有效减少连接所需的时间。