PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Scheduling Algorithms for Data Processing Clusters

Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, Mohammad Alizadeh

arXiv:1810.01963v4cs.LGstat.ML

TL;DR

Cluster schedulers often use general heuristics that ignore workload-specific DAG structure and parallelism because manual customization is costly. Decima uses reinforcement learning and neural networks to learn scheduling policies from high-level objectives, achieving substantial completion-time reductions over existing heuristics on Spark clusters.

  • Problem

    Existing cluster schedulers use generalized heuristics and often ignore workload structure, while manually developing workload-specific policies requires substantial expertise and effort.

  • Method

    Decima trains a neural-network scheduling policy with reinforcement learning using simulated workload experiments, while introducing representations and training methods for complex DAGs and continuous stochastic arrivals.

  • Results

    At least 21% lower average job completion time was achieved for TPC-H query mixes on a 25-node Spark cluster, with up to 2× improvement during high cluster load.

  • Takeaways & Limitations

    Decima demonstrates that reinforcement learning can automatically learn flexible and efficient scheduling policies for complex cluster workloads.

  • Takeaways & Limitations

    When trained only on batched arrivals, Decima can starve large jobs under continuous arrivals and underperform tuned weighted-fair scheduling above 65% load.

Abstract

from arXiv · show

Efficiently scheduling data processing jobs on distributed compute clusters requires complex algorithms. Current systems, however, use simple generalized heuristics and ignore workload characteristics, since developing and tuning a scheduling policy for each workload is infeasible. In this paper, we show that modern machine learning techniques can generate highly-efficient policies automatically. Decima uses reinforcement learning (RL) and neural networks to learn workload-specific scheduling algorithms without any human instruction beyond a high-level objective such as minimizing average job completion time. Off-the-shelf RL techniques, however, cannot handle the complexity and scale of the scheduling problem. To build Decima, we had to develop new representations for jobs' dependency graphs, design scalable RL models, and invent RL training methods for dealing with continuous stochastic job arrivals. Our prototype integration with Spark on a 25-node cluster shows that Decima improves the average job completion time over hand-tuned scheduling heuristics by at least 21%, achieving up to 2x improvement during periods of high cluster load.

1 Introduction

Decima automatically learns workload-specific scheduling policies from high-level objectives, addressing the impracticality of manually designing such policies. Its scalable neural architecture and RL training methods handle complex DAGs and continuous stochastic job arrivals, improving completion time over existing heuristics.

  • Current schedulers favor generality and simplicity, often ignoring job structure and efficient parallelism because workload-specific policies require costly expert design and validation.This effort may be unavailable or uneconomic for many organizations.
  • Decima uses monitoring information and workload logs to learn scheduling policies from a high-level objective such as minimizing average job completion time.It can learn resource shares and job-specific parallelism levels rather than relying on rigid fair sharing.
  • Decima reduces average job completion time of TPC-H query mixes by at least 21% on a 25-node Spark cluster and improves completion time by up to 2× under high load.It also improves average completion time by 32–43% in multi-resource CPU-and-memory scheduling.
  • Decima combines a scalable neural network design for arbitrary DAGs with RL techniques for unbounded stochastic job-arrival sequences.These contributions address the scale and streaming-arrival challenges of cluster scheduling.
  • Decima is presented as an RL-based scheduler for complex data-processing jobs that learns workload-specific policies without human input beyond a high-level objective.The paper includes a prototype implementation and evaluation against state-of-the-art scheduling heuristics.

2 Motivation

Data-processing jobs expose complex dependency structures and workload-dependent parallelism, but existing schedulers largely ignore this information. Decima learns policies that combine these dimensions and improves average completion time in a mixed TPC-H workload.

  • Data-parallel jobs are represented as DAGs whose stages have different task counts, durations, and input/output sizes.These heterogeneous nodes create complex data-flow structures in systems such as Spark.
  • Designing optimal schedules across arbitrary DAG combinations is intractable, so existing schedulers often enqueue newly available tasks or order stages arbitrarily.These approaches do not fully exploit dependency structure.
  • 2.2 Setting the right level of parallelism: Q9 on 100 GB gains speedup up to 40 parallel tasks, whereas Q2 on 100 GB has marginal returns beyond 20 tasks and Q9 on 2 GB needs no more than 10 tasks.The appropriate parallelism level depends on both query characteristics and input size.
  • 2.2 Setting the right level of parallelism: Existing schedulers commonly leave parallelism choices to users or coarse auto-scaling heuristics and may divide resources without considering execution efficiency.Additional parallelism beyond a job’s sweet spot yields diminishing gains.
  • 2.3 An illustrative example on Spark: 45% lower average JCT than Spark FIFO and 19% lower than a fair scheduler were achieved by Decima on ten random TPC-H queries with 50 task slots.Five jobs completed in the first 40 seconds in this illustrative workload.
  • Decima automatically learns workload-specific policies from a high-level goal instead of requiring general-purpose heuristics to encode every scheduling dimension.The approach is intended to exploit DAG structure, parallelism, and job-size information together.

3 The DAG Scheduling Problem in Spark

In Spark, jobs are DAGs of dependent stages, and scheduling must allocate executors and choose runnable stages while task-level execution remains delegated to Spark.

  • A Spark job is a DAG whose nodes are stages operating in parallel over input shards, with child stages becoming runnable after parent completion.The number of concurrently running tasks depends on the executors allocated to the job.
  • Spark scheduling decides executor allocation per job, which stage to run next, and which task to run when an executor becomes idle.Stage completion activates dependent child stages and enqueues their tasks.
  • Decima moves executors between job DAGs, focuses on DAG scheduling and executor allocation, and uses Spark’s existing task-level scheduler for identical stage tasks.Its executor-allocation decision controls each job’s degree of parallelism.

4 Overview and Design Challenges

Decima represents scheduling as a neural-network agent trained with reinforcement learning from simulated workloads and rewards tied to a high-level objective. Its design addresses large dynamic states, huge action spaces, and continuous stochastic arrivals.

  • At scheduling events, Decima’s policy network reads the current DAG and executor state and outputs an action assigning executor work to DAG stages.Events include stage completions and job arrivals.
  • Decima trains through many offline simulated experiments, rewarding actions according to objectives such as minimizing average JCT.The reward signal gradually improves the scheduling policy.
  • Figure 3 compares FIFO, shortest-job-first, fair scheduling, and Decima for ten TPC-H queries on 50 task slots using colored query timelines and job-completion markers.Purple regions indicate idle capacity.
  • Decima’s framework is designed to extend across systems, objectives, and resource types, including multi-resource scheduling and makespan optimization.The paper describes qualitatively different policies under different system conditions.
  • The design challenges are scalable processing of hundreds of dynamic DAGs and executors, exploration across exponentially many stage-to-executor mappings, and training under continuous random arrivals.Continuous arrivals create finite-horizon and reward-variance difficulties for conventional RL.

5 Design

Decima addresses scalable DAG scheduling by learning representations and actions with neural networks and reinforcement learning. Its design also handles the high-dimensional decisions and stochastic, continuous job arrivals that make conventional RL difficult to apply.

  • 5 Design: Decima organizes its design around scalable state processing, efficient action encoding, and RL training with continuous stochastic job arrivals.These are the three challenges explicitly structuring the design.
  • 5.1 Scalable state information processing: A graph neural network embeds DAG state into per-node, per-job, and global vectors while learning useful features end-to-end without manual feature engineering.The embeddings summarize stage attributes, dependency structure, individual jobs, and overall cluster load.
  • 5.1 Scalable state information processing: Decima computes node embeddings through child-to-parent message passing and nonlinear transformations that can capture scheduling features such as critical paths.A second nonlinear transformation is reported as critical because it enables features unavailable with the simpler aggregation alone.
  • 5.2 Encoding scheduling decisions as actions: The policy network scores stages using per-node, per-job, and global embeddings, then selects scheduling actions through softmax-based sampling.A separate shared score function evaluates parallelism limits, allowing the same function to serve all jobs and limits.
  • 5.3 Training: Decima assigns rewards from a high-level objective such as average JCT, but training must address poor early policies and reward variance from random job arrivals.Different arrival patterns can produce very different rewards unrelated to the preceding action, adding noise to RL training.

6 Implementation

Decima is implemented as a pluggable scheduling service integrated with Spark through RPC and changes to application and master scheduling interactions. Its offline simulator models several Spark execution effects to support training and evaluation.

  • 6 Implementation: Decima exposes a pluggable scheduling service that parallel data-processing platforms communicate with through an RPC interface.The implementation includes a Python-based training infrastructure and an accurate Spark cluster simulator.
  • 6.1 Spark integration: In Spark, application DAG schedulers query Decima at startup and scheduling events, while the Spark master consults it when jobs arrive and adjusts executor allocation.Decima returns the next stage and parallelism limit, and the master removes executors after stage completion.
  • 6.1 Spark integration: Decima’s node features include remaining tasks, average task duration, current and available executors, and executor locality.The selected statistics depend on available information and the system, and Decima can incorporate additional signals.
  • 6 Implementation: The neural architecture reuses small networks across jobs and parallelism limits, producing a lightweight model with 12,736 parameters and 50KB total size.The shared transformations include graph-embedding functions and policy score functions.
  • 6.2 Training infrastructure: The offline simulator incorporates first-wave slowdowns, 2–3-second executor startup delays, and parallelism-dependent task slowdowns.These effects model pipelining and warmup, JVM launch costs, and wider-shuffle overheads; simulator fidelity is validated against real Spark executions.

7 Evaluation

Decima is evaluated against tuned heuristics across Spark-cluster, multi-resource, workload-shift, ablation, and training-performance settings. It consistently improves average job completion time, while its gains depend on workload-aware representations and training procedures.

  • 7.2 Spark cluster: 21% lower average JCT than the closest heuristic, opt. weighted fair, establishes Decima’s advantage across the baseline comparison.Decima prioritizes jobs better, assigns efficient executor shares, and uses job DAG structure.
  • 7.2 Spark cluster: 2× faster job completion during busy hours shows that Decima’s advantage is largest under high cluster load.During hours 7–9, Decima maintains a lower concurrent job count than the tuned heuristic.
  • 7.3 Multi-dimensional resource packing: 32% lower average JCT than Graphene∗ demonstrates Decima’s effectiveness for continuous multi-resource job arrivals.The comparison uses simulated CPU-and-memory scheduling with the optimally tuned weighted-fair heuristic, Tetris, and Graphene∗.
  • 7.3 Multi-dimensional resource packing: 52% lower average JCT than Tetris accompanies memory fragmentation within 4%–13% of Tetris’s level.Decima trades some fragmentation for faster queue clearing by using oversized executors for nearly completed small jobs.
  • 7.4 Decima deep dive: Removing any one major component worsens average JCT beyond the tuned weighted-fair heuristic at high load, while batch-only training fails to generalize to continuous arrivals.The ablations identify parallelism control, graph embedding, variance reduction, and arrival-pattern matching as important to stable learning.
  • 7.4 Decima deep dive: 16% lower average JCT than the best heuristic results when Decima observes interarrival time as a state feature.Mixed workload training improves robustness to workload shifts, and explicit interarrival-time information improves it further.
  • Training and inference performance: Less than 15ms average scheduling delay is small relative to scheduling-event intervals typically measured in seconds.In fewer than 5% of cases, the scheduling interval is shorter than the scheduling delay.

8 Discussion

The discussion extends Decima’s techniques beyond average job duration and identifies robustness, preemption, and broader systems applications as open directions. It emphasizes that these extensions require addressing objective design, workload change, or RL scalability.

  • Robustness and generalization: More drastic workload changes may require adversarial training or online adaptation, but rapidly changing workloads create high model-free RL sample complexity.The paper suggests robust adversarial RL and meta learning as possible approaches.
  • Other learning objectives: Reward shaping could steer Decima toward deadline-aware, tail-latency, or constrained objectives beyond average JCT.The paper gives hard missed-deadline penalties, 90th-percentile duration rewards, and fairness-constrained optimization as examples.
  • Preemptive scheduling: Decima never preempts running tasks and removes executors only after stage completion, limiting scheduling reactivity.Adding fine-grained preemption would enlarge the action space and may require higher decision frequency.
  • Potential networking and system applications: The scalable DAG representation and variance-reduction technique may apply to query optimization, device placement, and systems with stochastic inputs.These applications are presented as broader potential uses of Decima’s learning innovations.

9 Related Work

Related work includes RL schedulers, graph-based learning for combinatorial problems, resource-management systems, and general-purpose cluster managers. Decima differs by targeting dependent-stage jobs and realistic continuous-arrival workloads with scalable graph representations.

  • Learning-based scheduling: DeepRM applies RL to multi-dimensional resource packing but handles single-task jobs in simple simulated environments.Its model lacks DAG-structured job support and its training procedure cannot handle continuous arrivals.
  • Graph-based learning: Decima modifies graph neural network architecture because off-the-shelf graph networks perform poorly for its scheduling problem.Its scalable state representation is inspired by RL and graph-neural-network work on combinatorial optimization.
  • Resource management systems: Paragon and Quasar match workloads to machine types to avoid interference, making their resource-management goal complementary to Decima’s.Tetrisched and Firmament instead use constraint solvers for placement, with explicit constraints or administrative requirements.
  • General-purpose cluster managers: General-purpose managers such as Borg, Mesos, and YARN make workload-specific scheduling policies difficult to apply at that level.The paper suggests Decima could run as a framework atop Mesos or Omega.

10 Conclusion

The conclusion presents Decima as evidence that reinforcement learning can automatically learn complex cluster-scheduling policies. It highlights the resulting policies’ flexibility and efficiency and points to broader applicability of the learning innovations.

  • Conclusion: Decima demonstrates that reinforcement learning can automatically learn complex cluster scheduling policies.The conclusion characterizes the learned policies as flexible and efficient.
  • Conclusion: Decima’s graph embedding and streaming-training innovations may apply to other DAG-processing systems such as query optimizers.The paper states that these techniques may be applicable beyond cluster scheduling.

Appendices Appendices are supporting material that has not been peer reviewed.

The appendices explain reinforcement learning foundations and why policy-gradient methods and average-reward objectives fit Decima’s scheduling setting.

  • Dependency-aware scheduling: A DAG-aware schedule parallelizes dependent branches so the final join can start immediately, whereas a critical-path heuristic takes 29% longer.The heuristic focuses on the branch with more aggregate work but delays the other parent of the join stage.
  • Reinforcement learning: RL agents observe states, take actions, receive rewards, and learn through stochastic environment interactions.The environment transitions after each action, and training proceeds through episodes of state-action-reward observations.
  • Policy representation: Decima’s policy uses a parameterized function approximator because the state-action space is too large for a lookup table.The policy is represented as πθ(sk,ak) with adjustable parameters θ.
  • Policy-gradient methods: Policy-gradient methods update neural-network policy parameters using execution trajectories and estimated returns.REINFORCE adjusts action probabilities in the direction indicated by the policy gradient, scaled by the observed return.
  • Average reward formulation: Average reward is better suited to scheduling than total reward for continuous operation.Decima converts rewards to differential rewards by subtracting a moving average before reusing the policy-gradient update.

C Training implementation details

Decima’s training implementation combines sampled job sequences, parallel experience collection, a faithful Spark simulator, and graph representations capable of expressing critical paths.

  • Training procedure: Decima samples episode lengths and job-arrival sequences, then collects multiple episodes using the same sequence for training.The training procedure uses a baseline computed from the same job sequence to reduce training variance.
  • Training infrastructure: Training uses 16 workers, with each iteration taking roughly 1.5 seconds on a Xeon E5-2640 CPU and Tesla P100 GPU.The implementation uses TensorFlow and parallel episode computation across workers.
  • Evaluation setup: The experiments use test job sequences unseen during training.These include unseen TPC-H combinations and unseen portions of the Alibaba production trace.
  • Simulator fidelity: The Spark simulator closely matches real job runtimes, with mean discrepancy at most ±5% for isolated jobs.Fidelity was evaluated over ten TPC-H runs with jobs running alone and sharing a cluster; modeling first-order Spark effects was crucial.
  • Graph representation: Decima’s two-level nonlinear graph transformation can express the max operation required to compute DAG critical paths.A standard aggregation without the second transformation cannot express this operation, while Decima learns it accurately on unseen DAGs.

G Further analysis of multi-resource scheduling

In multi-resource scheduling, Decima improves job completion and throughput under high load by learning aggressive, selectively fragmented executor allocations.

  • Performance: 32%−43% lower average JCT is achieved by Decima than by state-of-the-art heuristics under continuous arrivals in a multi-resource environment.Decima selectively borrows large executors when doing so helps finish short jobs and increase throughput.
  • High-load behavior: During busy periods, Decima clears queued jobs faster and maintains fewer concurrent active jobs than Graphene∗.It assigns more executors per job, including large executors for some jobs needing smaller ones.
  • High-load behavior: Decima achieves lower JCT and higher cluster throughput when cluster load is high.The result follows the policy’s use of more executors and selective borrowing of large executors.
  • Resource allocation: Decima tends to assign more executors than Graphene∗, accelerating job completion at the cost of unused memory.This trades resource fragmentation against prioritizing small jobs during busy periods.
  • Scope boundary: Continuous memory assignment remains difficult to express with Decima’s finite action space when executor slots could be subdivided.Applying RL with continuous actions to cluster scheduling is identified as future work, assuming sufficient CPU capacity.

H Optimality of Decima

Decima matches or slightly exceeds exhaustive-search performance in a simplified setting, generalizes across workload scales, and remains effective without task-duration estimates, though optimality is not established.

  • Optimality comparison: Exact optimality remains unknown because optimal schedules and tight lower bounds are intractable or unavailable in the evaluated environments.The paper therefore uses simplified settings where brute-force comparisons are possible to estimate closeness to optimality.
  • Optimality comparison: Decima matches or slightly outperforms exhaustive search, achieving 9% better average JCT in the simplified environment.The exhaustive baseline searches all n! job orderings for a batch of ten jobs, while Decima dynamically prioritizes jobs.
  • Optimality comparison: In the simplified setting, exhaustive search improves on shortest-job-first critical-path scheduling by exploiting DAG structure and potential parallelism.SJF-CP focuses strictly on smallest total work, whereas exhaustive search evaluates job orderings against executable parallelism and resource constraints.
  • Generalization: An agent trained with 15× fewer concurrent jobs generalizes to the test workload with a 7% reduced average JCT.An agent trained on a 10× smaller cluster generalizes with a 3% reduction in average JCT.
  • Missing duration estimates: Without task-duration estimates, Decima still outperforms the best heuristic by exploiting graph structure and task-count correlations.This contrasts with heuristics that fundamentally rely on profiling information such as total work.
Loading 1810.01963v4…