基于分配适应度的Spark渐进填充分区映射算法

Progressive filling partitioning and mapping algorithm for Spark based on allocation fitness degree

分析Spark的作业执行机制,建立了执行效率模型和Shuffle过程模型,给出了分配适应度(AFD,allocation fitness degree)的定义,提出了算法的优化目标。根据模型的相关定义求解,设计了渐进填充分区映射算法(PFPM,progressive filling partitioning and mapping algorithm),通过扩展式分区和渐进填充映射,建立适应Reducer计算能力的数据分配方案,有效缩减Shuffle过程的同步延时,提高集群计算效率。实验表明该算法提高了Shuffle过程数据分配的合理性,优化了并行计算框架Spark的作业执行效率。

The job execution mechanism of Spark was analyzed,task efficiency model and Shuffle model were established,then allocation fitness degree(AFD)was defined and the optimization goal was put forward.On the basis of the model definition,the progressive filling partitioning and mapping algorithm(PFPM)was proposed.PFPM established the data distribution scheme adapting Reducers'computing ability to decrease synchronous latency during Shuffle process and increase cluster the computing efficiency.The experiments demonstrate that PFPM could improve the rationality of workload distribution in Shuffle and optimize the execution efficiency of Spark.