任务调度算法优化探讨

Spark中对于任务的调度有两套不同的算法。第一套算法应用于任务集之间的调度，以决定到底应该优先将哪个任务集中的任务分配给集群中的工作节点，在这种情况下，调度的单位是任务集，任务集内的任务被一视同仁；第二套算法应用于任务集内部任务的调度，在给定集群工作节点资源的前提下，根据资源位置信息和任务集中任务的首选位置信息，确定任务被分配到哪一个工作节点的执行器上。下面对两套算法进行介绍。

任务集之间的调度是通过调度池来维护，Spark实现了两类调度算法，分别是FIFO调度和公平调度算法。FIFO调度十分容易理解，即先提交给调度器的任务集（根据阶段ID判断）优先被执行，这就导致一个问题：某些任务集运算量比较大，会长时间占据系统资源，从而导致后面的任务集不能被及时运算，因此Apache Spark引入了公平调度算法，在该算法下，程序会自动构建一棵任务调度树，树的叶子节点都是TaskSetManager对象，可以简单等价理解成一个任务集，其余都是Pool对象，Pool的子节点既可以是Pool，也可以是身为叶子节点的TaskSetManager，公平调度的基本原则是根据Pool/TaskSetManager节点下面运行任务的数目来决定优先级，用户可以设置Pool的最小任务数、任务权重来调整Pool中任务的优先级。在这种模式下，每个任务可以得到粗略相同的集群资源。两种调度算法的相关实现可分别参考FIFOSchedulingAlgorithm类和FairSchedulingAlgorithm类，限于篇幅在此不做过多介绍。

任务集内部任务的调度采用的是基于位置信息的延迟调度（Delay Scheduling）算法，该算法的实现在TaskSetManager类中。延迟调度算法用来决定在给定一个集群资源的情况下，如何挑选一个合适的任务，使得给定资源能够满足任务的首选资源要求，并且尽量保证任务是在本地执行。算法设置了一个位置级别变量allowedLocality，表示任务集中所有任务最大能够接受的位置级别，可选择值定义在TaskLocality类中，从最低级别到最高级别分别是：PROCESS_LOCAL、NODE_LOCAL、NO_PREF、RACK_LOCAL、ANY，限制逐渐宽松。(www.xing528.com)

延迟调度算法通过动态调整allowedLocality的值来适应变化的集群资源，TaskSetManager设置allowedLocality初始值为PROCESS_LOCAL，即要求将任务运行在本地同一执行器中。如果某节点上的执行器TaskSetManager的resourceOffer接口被调用以询问是否有合适的可以运行的任务，TaskSetManager会先判断距离上一次成功分配任务的时间差是否超过了用户指定的阈值，该阈值通过spark.locality.wait.x参数配置，x值可以为空、process、node以及rack，具体可参考官方配置文档。若超过，则将allowedLocality往上升一级，即放宽限制，如果没有超过或者第一次询问，则保持allowedLocality不变。接下来一一遍历TaskSetManager维护的任务集中尚未被执行的任务，检查有没有满足allowedLocality的任务-执行器，满足的意思是主节点与执行器的位置关系不能超出allowedLocality的限制。如果最终找到一个满足allowedLocality并且与执行器最为“接近”的任务，则将allowedLocality收紧到任务-执行器对应的位置限制，否则继续放宽allowedLocality。