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

针对内存计算框架 Spark 在作业 Shuffle 阶段一次分区产生的数据倾斜问题，提出一种内存计算框架的迭 代填充分区映射算法( IFPM) 。首先，分析 Spark 作业的执行机制，建立作业效率模型和分区映射模型，给出作业执行 时间和分配倾斜度的定义，证明这些定义与作业执行效率的因果逻辑关系; 然后，根据模型和定义求解，设计扩展式 数据分区算法( EPA) 和迭代式分区映射算法( IMA) ，在 Map 端建立一对多分区函数，并通过分区函数将部分数据填 入扩展区内，在数据分布局部感知后再执行扩展区迭代式的多轮数据分配，根据 Ｒeduce 端已分配数据量建立适应性 的扩展区映射规则，对原生区的数据倾斜进行逐步修正，以此保障数据分配的均衡性。实验结果表明，在不同源数据 分布条件下，算法均提高了作业 Shuffle 过程分区映射合理性，缩减了宽依赖 Stage 的同步时间，提高了作业执行效率。