背景介绍
Sparrow的论文收录在SOSP 2013，在网上还可以找到一份作者的talk ppt，值得一提的是作者是位PPMM。她之前发表过一篇The Case for Tiny Tasks in Compute Clusters，这篇文章我没有仔细看过，但是当时在看mesos粗细粒度模式的时候，组里有讨论过这篇论文。再结合她的github上的项目，发现她和AMP实验室里Mesos，spark等项目，在研究方向和合作上还是有很多渊源的。透过Sparrow，结合对Mesos、YARN的一些了解，可以在理论和实际项目中获得更多一些关于资源调度的东西。
适用场景
Sparrow是一个去中心化(分散)的无状态的分布式调度者，为细粒度task提供低延迟的调度。在一个由次秒级的tasks组成的workload里，调度器必须每秒为百万tasks提供毫秒级别延迟的调度决策，同时容忍调度失败。Sparrow主要借助Batch Sampling + Late Binding + Constraints来达到较好的效果。下面会具体介绍Batch Sampling 和 Late Binding，而Constraints是指用户可以对每个job进行一些约束和设定，比如所有tasks必须跑在有GPU的worker上，也就是在选择worker的时候增加一些条件约束。Constraints可能会让用户在使用Sparrow的时候保持更高的好感，而真正的低延迟调度的提速应该还是取决于Batch Sampling + Late Binding的策略。
基础
sparrow假设每个worker针对每个framework已经有一个long-runing的executor进程，最基础的是random，将Job的tasks往随机选择的两个worker上分配，worker自身维护了一个或多个queue(当对用户产生隔离或对优先级有要求的时候会维护多个queue)。
这种最基础的分配task的方法出自The Power of Two Choices in Randomized Load Balancing，让调度器探测两个随机选择的worker，把task分配到queue较短(仅考虑了已存在tasks数目)的worker上。Sparrow基于The Power of Two Choices in Randomized Load Balancing的思想，提出了自己的三个改进的方法，并且给出了一些测试数据，说明了每种特性带来的效果提升。
Sparrow基于random的分配方式，进行的第一种改进是Per-task sampling，即针对每个task都进行一次random操作，由scheduler发送probe(探测器，一个轻量级RPC)到worker上，然后选择一个队列比较短的worker分配task。之后的task重新进行random的work选择。
Batch Sampling
上面的分配方式会让尾部的tasks等待较长的时间，Batch Sampling改进了之前为task单独分配random worker的方式，让scheduler同时为一个job的m个tasks探测m*d个workers(d>1)，为tasks一起监控很多个worker。下图即scheduler为两个task同时探测四个worker。批量取样的性能不会随着job并行化的增加而降级。
Late Binding
之前random模式里提到过，scheduler对worker的选择是从已进行探测的备选worker里选择一个queue长度最短的worker放置新的task，但是有可能造成较长的等待时间，因为没有考虑到已经排队的tasks的执行时间。如果task直接被分配在某个worker上排队，会造成较长的等待时间。
延迟绑定结合上面的批量采样的方式的话，就可以同时监控d*m个worker，只要worker queue空了，就可以把task放置过去进行执行。下图中，承接上面的图示，Scheduler选择了四个worker进行batch sampling，当检测到第一个worker队列空了之后，就可以真正将job的两个tasks中的一个放到该worker上执行了，而另一个task继续由scheduler对四个worker进行监控。
在性能方面，下图展示了各个方法带来的延迟对比，其中黑色的虚线是假设调度器对于worker和task无所不知的情况下可以做出的最优调度，最靠近最优性能的是batch + Late Binding的曲线，从左往右对应的是上面的一个个图示，也证明了Sparrow的改进在百万级别细粒度tasks低延迟调度方面的进步。
Sparrow & Spark
为了证明Sparrow的可用性，作者为Spark加了个sparrow调度插件，将spark的每个stage提交成为一个Sparrow Job，提交给sparrow的schedulers。但是Sparrow由于是无状态的，所以framework使用的scheduler如果fail了，需要自己检测到并且去连接备用scheduler。在测试中client端获得一个scheduler列表，通过发送心跳的方式检测正在使用的scheduler有没有fail，如果fail了，那应对措施也需要针对使用场景而设置，若放弃这次job重新在别的sheduler上启动重新分配tasks去执行的话，要保证幂等。Sparrow同时也不会管worker的fail事件。项目分支地址。
我感觉Sparrow在地位上，比较像Spark LocalScheduler内的LocalTaskSetManager，但是大于它，Sparrow自己有一些schedulers。Sparrow假设每个worker针对每个framework已经有一个long-runing的executor进程，而这个executor可以是跑在mesos上的一个executor process，也可以是spark standalone模式下在各个slave上起的long-running进程，Sparrow做的事情是我给你一个schedulers列表，你用我的scheduler来处理你的job里的tasks怎么调度和分发，具体分发完执行的事情和worker fail了与Sparrow没有关系。
下面图中，在Spark Standalone模式下，Spark不借助于Mesos或者YARN这样的第三方资源调度系统，而是使用自己的调度模块。Spark自己的调度模块里有FIFO pool和FAIR pool，如果换成Sparrow的话，tasks的调度不再是简单的先进先出(FAIR pool内部仍然是先进先出的)，而应该是上面的Batch sampling + lazy binding + constraints的方式来调度到slave上。
(下图是我在阅读Spark源码时画的一张大图的一部分，右下角ClusterScheduler部分接的是mesos调度模块，在SchedulerBackend处可以接粗粒度或者细粒度的mesos scheduler backend，左下方使用的是自己的调度模块LocalScheduler，在0.8里除了之前的FIFO pool外，也新加入了FAIR pool，在我之前的这篇博文里也介绍过。)
类似地，Sparrow也实现了一个优先级队列，还实现了不同user之间的queue隔离性，这种情况下每个worker就维护了多个queue。
(全文完)
------------------------我是补充分割线------------------------
Sparrow vs Mesos/YARN
Sparrow通过自己的scheduler，让job的tasks能在适合workers上得到低延迟的调度，适合细粒度大量tasks的低延迟调度。和mesos、yarn等涉及到资源分配的调度器不一样。我理解Sparrow是mesos/yarn之上的task分发，分发到的workers是实际已经启动了long-running executor并得到资源了的slaves
