论文部分内容阅读
大数据时代背景下，数据的价值受到了前所未有的重视，传统的数据管理与分析技术由于其自身的限制无法应对大数据带来的挑战，亟需新的理论和技术来支撑大数据的分析和处理。连接操作是数据分析处理中最基本，同时也是最耗时的操作之一，且新兴的分布式并行处理框架MapReduce对连接操作的支持度不高，因此连接算法在并行架构的高效处理仍然存在较多问题亟待解决。 本文在综述了并行数据库领域及MapReduce框架连接算法的基础上，围绕连接算法中的数据分布、数据倾斜、两表连接及多表连接等关键问题进行了深入研究。论文的主要研究内容和创新点如下。 (1)提出了并行数据库中一种等宽直方图的分布式并行构造方法。基于Master-slave架构在直方图构建任务开始前在请求发起节点对经RPC协议获取到的工作节点本地最大值、最小值的比较得到数据表的全局最大值、最小值;考虑到并行数据库中带宽资源是极其宝贵的资源，将直方图构建任务划分为多个子任务并行执行，集群中只传输子直方图信息以优化网络带宽的负载;最后在应用请求发起节点对使用全局最大值、最小值构建的子等宽直方图聚合实现直方图任务的构建。算法已成功应用于并行数据库内核为数据分析任务提供数据分布、数据倾斜、数据集连接属性选择率等重要信息，为后文连接算法的优化奠定了基础。 (2)提出了MapReduce架构中基于簇代价分区的两表连接优化算法。MapReduce架构中数据倾斜会导致集群Reducer节点负载失衡从而严重影响连接算法效率，而现有负载均衡算法只关注Reducer节点输入数据量或者连接输出的均衡。针对此问题，在详细分析Reduce端处理流程的基础上，构建了同时考虑Reduce端输入和连接输出的代价模型，然后基于两个连接表的频率分布构建连接矩阵，检测并分割连接矩阵中负载过重连接单元，最后在连接矩阵中的连接单元集合和Reducer节点间建立映射以优化Reduce端的负载，并从理论角度证明了算法优化后集群中负载最重的Reducer节点与Rduce端最优负载的比值不超过2。 (3)提出了MapReduce中基于超方体范围分区的多表连接优化算法。MapReduee架构实现多表连接任务时往往涉及到大量中间结果的读写，从而导致大量的I/O操作和网络传输。针对此问题，算法将集群中Reducer节点组织成超方体形式，将连接表中数据备份多份发送至多个Reducer节点以通过一轮MapReduce任务实现多表连接操作，算法使用范围分区代替基于超方体算法使用的Hash分区以均衡数据倾斜情况下Reduce端的负载失衡问题，基于拉格朗日乘子法的范围分区个数的确定保证了多表连接中网络传输量的最优。算法既能够在一轮MapReduce任务中实现多表连接操作，又能有效的处理多表连接中因数据倾斜导致的Reduce端负载失衡问题。