基于迭代填充的内存计算框架分区映射算法

发布时间：2018-08-10 22:33

【摘要】：针对内存计算框架Spark在作业Shuffle阶段一次分区产生的数据倾斜问题,提出一种内存计算框架的迭代填充分区映射算法(IFPM)。首先,分析Spark作业的执行机制,建立作业效率模型和分区映射模型,给出作业执行时间和分配倾斜度的定义,证明这些定义与作业执行效率的因果逻辑关系;然后,根据模型和定义求解,设计扩展式数据分区算法(EPA)和迭代式分区映射算法(IMA),在Map端建立一对多分区函数,并通过分区函数将部分数据填入扩展区内,在数据分布局部感知后再执行扩展区迭代式的多轮数据分配,根据Reduce端已分配数据量建立适应性的扩展区映射规则,对原生区的数据倾斜进行逐步修正,以此保障数据分配的均衡性。实验结果表明,在不同源数据分布条件下,算法均提高了作业Shuffle过程分区映射合理性,缩减了宽依赖Stage的同步时间,提高了作业执行效率。
[Abstract]:Aiming at the problem of data skew caused by the primary partition of memory computing framework (Spark) in the stage of job Shuffle, an iterative padding partition mapping algorithm (IFPM).) for memory computing framework is proposed. Firstly, the execution mechanism of Spark jobs is analyzed, the job efficiency model and partition mapping model are established, the definitions of job execution time and assignment inclination are given, and the causal logic relationship between these definitions and job execution efficiency is proved. According to the model and definition, the extended data partition algorithm (EPA) and the iterative partition mapping algorithm (IMA),) are designed to establish one-to-many partition functions at the Map end. After the local perception of the data distribution, the extended region iterative multi-round data allocation is performed. According to the amount of data allocated on the Reduce terminal, the adaptive extended region mapping rules are established, and the data tilt of the native area is modified step by step. In order to ensure the balance of data distribution. The experimental results show that the algorithm improves the rationality of job Shuffle process partition mapping, reduces the synchronization time of wide dependent Stage, and improves the efficiency of job execution under the condition of different data distribution.
【作者单位】：新疆大学信息科学与工程学院;
【基金】：国家自然科学基金资助项目(61262088,61462079,61363083,61562086) 新疆维吾尔自治区高校科研计划项目(XJEDU2016S106)~~
【分类号】：TP333;TP301.6

【相似文献】