Review for Sparrow

1) Is the problem real?

Now data analytics framework turns to process shorter tasks with high parallelism in order to achieve low latency. Current scheduler cannot achieve millisecond latency guarantee. This is a real problem. It is because the centralized scheduler have too much workload on single node or a few nodes. The paper wants to build up a new scheme that fits for millisecond latency guarantee scheduling.

2) What is the solution’s main idea (nugget)?

The basic idea is to use a distributed and random algorithm called "the power of two choices". That is to randomly probe on two severs and place the task on the sever with fewer tasks.

Sparrow made some modifications to original the power of two choices technique.
Batch sampling: instead of per task sampling, Sparrow place m task sampling together.
Late binding: delay tasks assigning to the workers until workers are ready to run the tasks. Thus it reduces job response time.
policies and constrains: Sparrow uses queues on workers for global polices. And it supports for per-job/task constrains.

3) Why is solution different from previous work?

Previous schedulers are mainly centralized ones. Either with single node or two-level scheduling, there are too much scheduling workloads on the scheduler node/nodes. Therefore, they cannot achieve scheduling with millisecond latency guarantee.

However, different from these centralized schemes, Sparrow is a distributed and randomized scheduling scheme, which could achieve low latency.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 


Even though distributed and randomized scheduling algorithm can achieve low latency, the scheduling could not achieve optimal performance. Although the authors claims the nearly-optimal results, which is a case-by-case evaluation.

5) Do you think the paper will be influential in 10 years? Why or why not?

I do not think so. I think centralized scheduling may still be the main stream. And some centralized scheduler (such as scheduler in spark streaming) has already achieve scheduling latency guarantee within a second.