[Binospace] Sparrow(SOSP13)—一种加速短作业的调度方法

背景：

当前大规模数据分析框架的发展朝着两个趋势在变化：

1）任务执行时间更短。

2）更大的任务并行度。

 

因此，在当前分布式计算框架的调度系统中，需要有所改变，以满足如下的需求：

1）更快的任务调度效率，mill-seconds级别。

2）良好的容错，High Availability.

3）较高的吞吐率，High Throughput.

 

分析一下：什么原因会造成多任务的作业执行时间较长？

1）作业内任务分配不合理，在同样的并行层次上，任务执行逻辑和处理的数据量不一致，从而拉长整个作业的执行时间。以MapReduce为例的大数据分析框架中，数据是等分的，并且，处理逻辑是一致的，因此，该问题仅仅出现在以DAG、或者具有Data-Skew的数据逻辑中。

 

2）调度的不均衡性。根据Hadoop作业调度的情况，作业的执行时间由最为执行时间最长的任务决定。例如，Hadoop调度的一个MapTask到负载较高的节点上，从而整个作业的执行时间被拉长。

 

3）中心化的调度效率较低。在当前分布式数据处理框架中，大多数采用Master中心控制的方式来进行调度，例如Mesos/Yarn，需要维护作业和资源两类信息。在调度时，往往花在任务调度上的时间就已经达到秒级，从而很难实现更高的吞吐和更快的作业延迟。除此之外，为了实现高可用性，需要在秒级实现任务状态的复制和迁移，这无疑也给当前的分布式处理系统的设计带来了挑战。

 

设计思路与原理：

Sparrow的设计目标：

1）支持小作业的快速调度。

2）Low latency，High Throughput，High availability

 

Sparrow与通用的资源管理系统(Mesos、Yarn、Omega、vSphere)的区别：

1）不为长作业调度优化，focus on 在短、实时性高的作业；

2)  不做“限制性”调度，例如，Job A的任务调度到Job B任务所在机器上，这种依赖会造成调度的不平衡性；

 

 

核心设计：

 

1、弱化中心化Scheduler的功能，多个更小更快的Scheduler并行执行。

 

 

 

2、Sample-based 调度方法。m个任务随机选择dm个worker(d>1)，部署m个任务到m个queue队列较短的节点。

上图，展示在d=2的情况下，对比单个任务随机选择，与多个任务合并起来随机选择的差异。如上左图，一个作业的Task1 Task2调度过程中，有可能Task1选择的两台Worker任务队列比较长，而Task2选择的2个worker却都较为闲置。从而，因为随机选择的偶然性，造成作业内Task调度等待时间的差异，影响作业的执行延迟。而上右图，一个作业的两个任务，随机选择4个worker，选出两个任务负载较轻的工作节点，降低了Task调度等待时间的差异性的概率。据实验表明，采用batch sampling方法比per-task sampling平均缩短了10%的作业延迟。

 

该方法的缺陷：

1）队列的等待时间的不确定性。该调度方法以队列的长度为选择标准，是建立在队列内的任务执行时间一致的前提下的。在有些情况下，队列多的任务可能是短任务，而队列少的任务可能是长时间任务，仍会造成调度的不平衡性。

然而，预测队列的执行时间的难度是非常大的。

 

2）并发抢占造成的资源竞争。由于多个调度器独立、并发的调度任务，完全有可能多个任务同时被调度到任务负载较轻的工作节点，从而可能造成更长时间的等待。

基于以上两个方面的不足，引入了Virtual Reservation的概念。

 

3、Virtual Reservations

调度器选择一个作业，向dm个worker发送探测信号之后，worker会在队列末尾增加”预留位置(Reservation)”，当worker执行到队列Reservation的位置时，向调度器发送一个可以接受任务的请求，调度器在成功调度了前m个任务之后，会向另外(d-1)m个worker发送一个no-op信号，指示当前的作业的所有任务都已经提交。根据文章作者的实验结果表明，在工作节点上的task执行时间随机分布，且负载在90%的情况下，virtual reservations比batch sampling缩短35%的响应时间，使得执行时间在理论最优响应时间的114%以内。

 

 

 

 

4、由Worker分担大部分调度逻辑。

所有的scheduler对于作业和任务进行统一配置，大部分的有关task-constraints的特性，可以通过增加Worker的逻辑来实现。例如，多队列任务调度，worker内维护多个队列，并且按照作业的属性(priority,perference,feature..etc.)来分配Reservation。这种调度特性逻辑下移到工作节点的做法，有利于提高Scheduler的调度的吞吐，并更容易实现Scheduler以及作业的HA。

 

嵌入计算框架的架构图：

Binos的思考：

使用reservation+worker RPC 反馈scheduler的方式，是在去中心化调度的宗旨下，借鉴了之前中心化调度的交互方式。但是，它相比较传统的调度模型的根本优势在于：

1）调度器无需维护工作节点的状态，是以作业为中心，而不是以工作节点为中心的调度。

2）转变竞争模式。通过高于预期slot的数量占位的方式，原有作业竞争资源变成资源竞争作业，同时提高了调度的平衡性。

3）更简洁的作业容错信息。一般情况下，由于scheduler无需维护工作节点的信息，只需关注提交的作业即可。(ps，类似Twitter-Storm的简洁的调度模式，方便简单可靠地实现系统的高可用)。

 

参考文献：

[1] SOSP13：Sparrow: Scalable Scheduling for Sub-Second Parallel Jobs

[2]Hadoop Fair Scheduler：http://hadoop.apache.org/docs/stable/fair_scheduler.html

[3]Eurosys 13：Omega: Flexible, scalable schedulers for large compute clusters.

[4]Twitter-Storm：http://storm-project.net

声明：

本文章属于Binos_ICT在Binospace个人技术博客原创，原文链接为http://www.binospace.com/index.php/sparrow-sosp13-an-accelerated-short-job-scheduling-method/,未经允许，不得转载。

 

 

From Binospace, post Sparrow(SOSP13)—一种加速短作业的调度方法

文章的脚注信息由WordPress的wp-posturl插件自动生成