这篇论文是UC Berkeley AMPLab出的一系列论文之中的一个,AMPLab实验室有一整套大数据处理和分析框架,称为BDAS(the Berkeley Data Analytics Stack),其中比较出名的是Spark。Spark是一个高效的分布式计算系统,性能上要比Hadoop高出100倍。这篇论文主要实现的是一个分布式的,低延迟的调度系统。

大规模的数据分析框架都在朝着小规模任务,多并发的方向发展,因为这样可以提供低延迟。这样一个应用场景之下,一个低延迟,高可用的调度系统就非常重要。Sparrow就是这样一个分布式的,基于随机方法的调度系统。对于一个调度器,主要从四个方面来考虑:1.Millisecond Latency;2.Quality Placement;3.Fault Tolerant;4.High Throughput。传统的中央调度器在多任务高并发的情况下显然是不能满足低延迟,容错和高吞吐量的要求的,唯一能做到的就是第二点,将任务调度到合适的计算节点上。相比较之下,分布式的Sparrow则能达到上述四个要求,唯一在调度效率(Quality Placement)上可能没有传统的中央调度器做得那么好,但是通过采用几种技术也能达到很高的效率。

在任务高并发的情况下,分布式的调度器如果维护一个全局的状态信息将会使得调度过程变得复杂,同时调度的速度也会非常慢,所以Sparrow采取了传统的Random Sampling的方法,就是每次调度的时候选取两个节点,然后选取其中一个排队任务更少的一个计算节点来调度。只是Sparrow在此基础上做了一些改造,使得任务的相应时间变得越来越少。首先是Per-task Sampling,其实就是将一个job拆分成多个task,每次调度task的时候来随机选择,而不是针对整个job来进行调度。这样一种情况下存在的一个问题就是对于两个task,最终选择调度的两个计算节点并非所随机选择的四个节点中最优的两个,这样就引出了Batch Sampling,即对于一个特定的job调度,所有的计算节点采样信息是共享的,这样对于这个job中包含的n个task,就可以在选取的d*n个样本中选择最优的n个节点来调度,避免了前面所说的问题。但是在选择等候队列最短的节点来调度并非就是最优的选择,因为每个task的执行任务时间是不一样的,有可能一个只有一个排队任务的节点比有两个排队任务的节点执行的时间更长。Sparrow采取了一个叫做Late Binding的技术,就是调度器每次在调度一个任务的时候,在计算节点集群中采样的过程中,采样节点并非立即给调度器回复,而是为这样一个采样操作预留一个位置,等其中一个节点上面的其它任务执行完了之后会给调度器一个回复说我这里有资源了,调度器收到之后就会把任务调度到这个节点上,同时给其它的采样节点发送不操作的信息。这样就保证了调度的任务能在最快的时间内完成。论文中有很多关于采用上述技术之后相应时间的对比,就是说明采用了Batch Sampling,Late Binding技术之后响应时间降低了很多。

Sparrow同时还可以处理特殊任务的特殊要求,但是Sparrow只能处理两种类型的限制任务,一种是Per-job的,另外一种是Per-task的。调度的过程中就是采样只针对满足条件的节点进行采样,其它的技术和这个没有什么冲突。在处理容错的过程中,论文中说Sparrow有一个Java的客户端,客户端接受应用的请求中包含一个调度器的列表,客户端会尝试链接列表中的第一个调度器,并和这个调度器保持心跳,如果这个调度器坏掉了,那么客户端会将任务分发到列表中的第二个。

似乎论文中就这么多核心的内容,多数是测试数据的对比,总的来说核心就是采用了Batch Sampling和Late Binding两个技术,同时满足有特定限制的一些任务的调度。

----End----

Comments
Write a Comment