基于迭代填充的内存计算框架分区映射算法
来源：计算机应用杂志2017年第3期北京时间：
作者：卞琛, 于炯, 修位蓉, 英昌甜, 钱育蓉
单位：新疆大学 信息科学与工程学院, 乌鲁木齐 830046
摘要：针对内存计算框架Spark在作业Shuffle阶段一次分区产生的数据倾斜问题，提出一种内存计算框架的迭代填充分区映射算法（IFPM）。首先，分析Spark作业的执行机制，建立作业效率模型和分区映射模型，给出作业执行时间和分配倾斜度的定义，证明这些定义与作业执行效率的因果逻辑关系；然后，根据模型和定义求解，设计扩展式数据分区算法（EPA）和迭代式分区映射算法（IMA），在Map端建立一对多分区函数，并通过分区函数将部分数据填入扩展区内，在数据分布局部感知后再执行扩展区迭代式的多轮数据分配，根据Reduce端已分配数据量建立适应性的扩展区映射规则，对原生区的数据倾斜进行逐步修正，以此保障数据分配的均衡性。实验结果表明，在不同源数据分布条件下，算法均提高了作业Shuffle过程分区映射合理性，缩减了宽依赖Stage的同步时间，提高了作业执行效率。
关键词：内存计算,数据均衡,扩展式分区,迭代式映射
基金资助：国家自然科学基金资助项目（61262088，61462079，61363083，61562086）；新疆维吾尔自治区高校科研计划项目（XJEDU2016S106）。
