# The Case for Task Sampling based Learning for Cluster Job Scheduling

**Authors:** Akshay Jajoo, Y. Charlie Hu, Xiaojun Lin, Nan Deng  
**arXiv:** [2108.10464](https://arxiv.org/abs/2108.10464)  
**Date:** 2021-08-24  
**Summary page:** https://www.summarizepaper.com/en/paper/2108.10464v2/

## Key points

- Accurately estimating job runtime properties is crucial for effective job scheduling in cluster job scheduling.
- Traditional online cluster job schedulers use history-based learning to estimate runtime properties, but this can lead to inaccurate predictions due to changing technology and user inputs.
- The proposed approach is task-sampling-based, involving proactive sampling and scheduling of a small fraction of tasks from each job.
- This approach exploits the similarity among task runtime properties within the same job, making it immune to changing job behavior.
- The study focuses on two key questions: (1) Can learning in space be more accurate than learning in time? (2) Can delaying the scheduling of remaining tasks until the completion of sampled tasks improve job performance?
- Analytical and experimental analysis demonstrate that learning in space significantly improves accuracy compared to history-based learning.
- Simulation and testbed evaluation show that learning in space reduces average Job Completion Time (JCT) by 1.28x, 1.56x, and 1.32x compared to history-based predictors.
- This research highlights the potential and limitations of real-time learning of job runtime properties through task-sampling-based approaches.
- It provides valuable insights into improving cluster job scheduling by leveraging similarities among task runtime properties within a job while adapting to changing environments.

## Summary

In the field of cluster job scheduling, accurately estimating job runtime properties is crucial for effective job scheduling. Traditional online cluster job schedulers rely on history-based learning, which uses past job execution information to estimate the runtime properties of newly arrived jobs. However, due to the rapid development in cluster technology and changing user inputs, job runtime properties can change over time, leading to inaccurate predictions. To address this issue, this paper proposes a task-sampling-based approach for real-time learning of job runtime properties. This approach involves proactively sampling and scheduling a small fraction of tasks from each job. By exploiting the similarity among the runtime properties of tasks within the same job, this approach is inherently immune to changing job behavior. The study focuses on two key questions: (1) Can learning in space (task-sampling-based learning) be more accurate than learning in time (history-based learning)? (2) If so, can delaying the scheduling of remaining tasks until the completion of sampled tasks compensate for this delay and result in improved job performance? Analytical and experimental analysis using three production traces with different skew and job distribution demonstrates that learning in space can significantly improve accuracy compared to history-based learning. Furthermore, simulation and testbed evaluation on Azure using three production cluster job traces show that despite its online overhead, learning in space reduces the average Job Completion Time (JCT) by 1.28x, 1.56x, and 1.32x compared to the prior-art history-based predictor. Overall, this research highlights the potential and limitations of real-time learning of job runtime properties through task-sampling-based approaches. It provides valuable insights into improving cluster job scheduling by leveraging similarities among task runtime properties within a job while adapting to changing environments.