Spark框架并行度推断算法

分布式计算集群Spark宽依赖并行度取决于用户设定参数，对于不同的作业类型或数据集，硬编码的并行度参数设定难以发挥集群的最大计算能效。针对这一问题，首先对Spark作业执行方式进行深入分析，建立作业调度模型，提出宽依赖计算代价、资源空置率和溢写概率的定义；然后分析任务并行度对作业执行时间的影响，证明并行度取值具有合理区间，提出并行度推断算法的优化目标。最后根据模型定义进行目标求解，设计批处理内存计算框架的并行度推断算法（parallelism deduction algorithm，PDA），通过构建的数据总量、执行区预留比、操作闭包集合、资源表等多个基础数据，计算符合资源需求表且具有最大资源利用率和最小开销的任务并行度；PDA算法在作业的各个Stage中迭代执行，根据计算环境优化调度方案提高性能。实验表明，PDA算法提高了Spark框架的作业执行效率，针对不同类型作业均具有良好的普适性。

Parallelism Deduction Algorithm for Spark

Inappropriate parallelism parameter may result in the performance degradation on in-memory computing framework. For this issue, we analyze the execution mechanism of Spark jobs, establish job scheduling model, and give the definition of the computing cost, resource idle rate and spill probability. Based on the analysis of the relationship between parallelism parameter and job execution efficiency, the optimization objective of algorithm is given. To solve the problem of optimizing, a parallelism deduction algorithm (PDA) for in-memory computing framework is proposed. Firstly, PDA calculates the best parallelism of job execution by size of input data, worker computing resource and additional overhead of spill, and thus enhances the resource utilization of cluster and speeds up the state synchronization of job execution. The algorithm optimizes the task scheduling for each Stage, accelerates the job execution and improves the calculation efficiency. Experiment results demonstrate that the proposed algorithm can improve the computational efficiency of in-memory computing framework and accelerate data-intensive and compute-intensive applications.