这是UC Berkeley的一篇设计分布式系统中的调度的文章，作者是个萌妹纸。本来想贴张照片，想想算了不侵犯人家肖像权，大家自行百度就可以了（偷偷说一句微博上有高清大图）。嗷~~~文章发表在SOSP’13。

###Abstract####

总之就是设计了一个非集中式的，随机采样的方法来实现调度，达到了接近最优的性能。嗯。

为什么说接近最优呢？人家在一个110个机器的集群上进行了测试，表示Sparrow(哦对，这个调度叫Sparrow)的性能能够达到理想的调度算法的12%以内。至于是哪些性能指标，读下去再说吧。

###1 Introduction###

现如今的数据分析集群都跑些越来越短的高扇出的工作。然后就有很多框架做出来满足这些需求（比如Dremel, Spark, Impala等等）。总之就是这些框架的速度越来越快了，作者还给了张图证明了随着时代的发展，数据分析框架的时延越来越低了。人们想了各种方法来使得时延变低，非常辛苦。由于这些系统都是分布式系统，所以调度不能拖后腿啊。于是就有了这篇文章的工作。

Sparrow是一个分布式的调度器，使用了two choices load balancing technique。这种技术调度每个task都探查两个随机的server然后把task交给排队等待任务较少的server。Sparrow使用了以下三种技术来make the power of two choices effective。
Batch Sample: 由于一个job的response time（就是从一个job提交开始到这个job的所有task都完成所使用的时间）与最后一个task的等待时间有关，然而这个等待时间会由于在两个选择之间抉择而变慢，所以对于并行job，two choices的这种做法表现得并不好。Batch Sampling利用了一种multiple choices approach[1]解决了这个问题。
Late Binding: 然而two choices的性能还受到两方面的影响： 首先，server上等待队列的长度并不能很好地反应等待时间。其次，消息会有时延，多个调度器并行工作可能会产生竞争。Late binding能够解决这个问题。具体的做法是延迟task提交到worker的时间直到woker已经准备好为这个task工作。这种做法与只用Batch Sample相比较能够平均减少45%的response time。
Policies and Constraints: Sparrow在每个工作节点上都使用了多个队列用来enforce global policies(这是什么鬼？)还有支持per-job and per-task placement constraints needed by analytics frameworks(这又是什么鬼？)。总之就是这两个功能十分重要就对了。

然后就简要介绍了一些测试和结果。Introduction部分就完了。

###2 Design Goals###

本文关注的是低时延应用的细粒度任务调度。低时延的workloads比批处理的workloads需要更频繁的调度。

Sparrow并没有为每一个task开一个进程，而是假设每一个framework在每一个worker上都有一个都有一个long-running executor process在运行，这样，Sparrow只需要在一个task被launched的时候发送一个short task description（而不是a large binary）就行了。（这是为什么？）这些executor process可以在cluster resource manager(例如YARN, Mesos, Omega)给Sparrow和其他frameworks(例如传统的批处理workloads)分配资源的时候执行？

Sparrow也有一些无法做到的事情。Sparrow无法保证placement constraints(例如，我的job不能被放在User X的工作被运行的worker上)。Sparrow也不支持bin packing和gang scheduling。

但Sparrow也因此变得简单高效。而且对于一些基本的约束Sparrow还是可以支持的。比如per-task constraints(每个task必须跟输入数据共驻主存)，还有per-job constraints(每个task必须被放在有GPU的machine上)。这些特性与Hadoop MapReduce scheduler和Spark scheduler类似。

###3 Sample-Based Scheduling for Parallel Jobs###

一个传统的任务调度算法需要对全局有一个完整的视图，应该知道哪一个task运行在哪一个worker上，然后再对接下来的task分配可用的worker。然而Sparrow用的并不是这种方式：Sparrow并行执行多个schedulers，每一个scheduler并不用维护cluster load的状态。为了调度job的task，schedulers只依赖当前瞬时的load信息。

####3.1 Terminology and job model####

定义一个cluster由worker machines和schedulers组成。一个有着m个tasks的job会把各个task分在这些worker上执行。job可以被任意scheduler调度。woker在固定数量的slots内执行tasks。如果一个woker收到了更多的task但它已经无法并发执行了，就给新task排队，直到有足够的资源供新task执行。

接下来定义了一些时间：

• wait time: 一个task从提交到执行经过的时间
• service time: 一个task的执行时间
• job response time: 一个job从提交到最后一个task完成经过的时间
• delay: 一个job在调度和排队上花费的总时间

本文假设每个job只有一波tasks。就是说，m大于user分配的slots。对于多波task的job，scheduler可以把一些early tasks放在有着longer queueing delay的machines上，这样就不会影响job response time。（这个么看懂）。反正就是测的时候只测一波的就对了。

####3.2 Per-task sampling####

第一段就是说我们要用two choices technique，刚才已经说过了，就是要调度的时候随机选两个woker然后发两个探查（探查是一个lightweight RPC），然后两个worker就会发回复说现在它们这儿排的队有多长，然后scheduler就选短的那个，让这个task去短的woker上排队。这个调度算法就像下图中的(a)一样。这种做法就叫做Per-task sampling。

####3.3 Batch sampling####

由于Per-task sampling的做法太慢了，而且如果探查的两个worker队列都很长（Task1），就会得到非常不好的结果。batch sampling允许对一个job共享探查的结果。每次探查dm个worker，然后选出load最小的m个worker。就像上图中的(b)那样。这个d是可以选择的，上图选择d=2。

####3.4 Problems with sample-based scheduling####

sample-based调度有一些什么缺点呢？

首先，调度要更具worker节点上队列长度来进行。然而队列长度并不能很好地表示等待时间。考虑到有两个队伍，一个队伍有两个50ms的任务，而另一个上面有1个300ms的任务。这时候选后一个队伍就不合适了。然而预测task所需要的时间是非常困难的。

其次，sampling会遇到竞争的情况。当多个不同的schedulers同时探查同一个空闲的worker的时候，由于这个worker是空闲的，它们都倾向于选择这个worker。这样就会造成大家都往同一个worker上放task的情况。

####3.5 Late binding####

Late binding就是为了解决3.4节中提出的竞争问题的，worker并不立即返回探查结果，而是放一个这个task的reservation在队伍的末尾，当这个reservation跑到队头的时候，worker向scheduler发送一个PRC。每个scheduler把job的task提交给最初发回应的m个worker，然后给其它(d-1)m个worker发一个no-op的信号。

这种做法的一个缺点是当worker向scheduler发送一个RPC请求一个新的task的时候，worker是空闲的。这时候可以用一个tradeoff来解决这个问题：当一个worker有足够资源的时候就发RPC？

####3.6 Proactive Cancellation####

（刚看到这个小标题我都傻了，这啥意思啊？主动取消？取消啥？接着看下去~）

当一个scheduler发射了一个job的所有task时，它可以用以下方式处理那些没发过回复的探查（其它worker上的探查，它们太慢了）：可以由scheduler主动向worker发取消请求，或者可以等待worker发回复请求task的时候回复说这个task已经被处理过了。经过他们研究表明前一种做法能够获得更好的结果。

####4 Scheduling Policies and Constraints####

这部分讲的是Sparrow能够支持的两个sheduler policies。这个在第2章的时候曾经提过。

####4.1 Handling placement constriants####

Sparrow能够支持两种约束(constraints)，分别是per-job和per-task constraints。这些约束会被用在一些data-parallel frameworks里，比如需要把task交给硬盘或内存里存有输入数据的机器。

读到这里大概有种感觉，这个调度算法是为spark写的啦~

####4.2 Resource allocation policies####

[1] G. Park. A Generalization of Multiple Choice Balls-into-Bins. In Proc. PODC, pages 297–298, 2011.