Delay scheduling
Matei Zaharia, Dhruba Borthakur, Joydeep Sen Sarma et al. · European Conference on Computer Systems · 2010
As organizations start to use data-intensive cluster computing systems like Hadoop and Dryad for more applications, there is a growing need to share clusters between users. However, there is a conflict between fairness in scheduling and data locality (placing tasks on nodes that contain their input data). We illustrate this problem through our experience designing a fair scheduler for a 600-node Hadoop cluster at Facebook. To address the conflict between locality and fairness, we propose a simple algorithm called delay scheduling: when the job that should be scheduled next according to fairness cannot launch a local task, it waits for a small amount of time, letting other jobs launch tasks instead. We find that delay scheduling achieves nearly optimal data locality in a variety of workloads and can increase throughput by up to 2x while preserving fairness. In addition, the simplicity of delay scheduling makes it applicable under a wide variety of scheduling policies beyond fair sharing.
Cited by 1,393 works. doi:10.1145/1755913.1755940
Authors
References
- MapReduce
- The Google file system
- Analysis and simulation of a fair queueing algorithm
- Analysis and simulation of a fair queueing algorithm
- Dryad
- The Google file system
- Link-sharing and resource management models for packet networks
- Distributed computing in practice: the Condor experience
- A comparison of approaches to large-scale data analysis
- Lottery scheduling: flexible proportional-share resource management