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

七月 16th, 2013 by klose | Posted under 互联网应用, 海量数据存储与处理.

背景:

当前大规模数据分析框架的发展朝着两个趋势在变化:
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并行执行。
 sparrow1
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%以内。
 sparrow5
spillow-2
4、由Worker分担大部分调度逻辑。
所有的scheduler对于作业和任务进行统一配置,大部分的有关task-constraints的特性,可以通过增加Worker的逻辑来实现。例如,多队列任务调度,worker内维护多个队列,并且按照作业的属性(priority,perference,feature..etc.)来分配Reservation。这种调度特性逻辑下移到工作节点的做法,有利于提高Scheduler的调度的吞吐,并更容易实现Scheduler以及作业的HA。
嵌入计算框架的架构图:
sparrow4

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_ICTBinospace个人技术博客原创,原文链接为http://www.binospace.com/index.php/sparrow-sosp13-an-accelerated-short-job-scheduling-method/,未经允许,不得转载。

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

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





Tags: , , , ,

Comments

One Response to “Sparrow(SOSP13)—一种加速短作业的调度方法”
  1. llc 说道:

    有启发!

Do you have any comments on Sparrow(SOSP13)—一种加速短作业的调度方法 ?