TL;DR
MACE is a novel reinforcement learning framework designed to schedule streaming data processing jobs—represented as Directed Acyclic Graphs (DAGs)—more efficiently. By explicitly encoding "critical paths" (the bottlenecks of a job) and utilizing a memory mechanism to learn from historical scheduling decisions, MACE reduces average job completion times by up to 9.38% compared to current state-of-the-art models like Decima.
What Problem Does This Paper Address?
In modern distributed systems like Apache Spark or Flink, computational jobs are structured as Directed Acyclic Graphs (DAGs), where nodes are processing stages and edges represent dependencies. Scheduling these jobs is a nightmare: you have to decide which stage to run next and how many resources (parallelism) to give it, all while new jobs arrive continuously in a "streaming" fashion.
The authors identify two major gaps in existing learning-based schedulers:
- Structural Blindness: Most models don't explicitly recognize the "critical path"—the longest sequence of dependent stages that dictates the minimum time a job will take. If you don't prioritize the critical path, the whole job drags on.
- Short-sightedness: Standard neural networks are often "reactive," making decisions based only on the current snapshot of the cluster. They lack a mechanism to remember how previous decisions (like giving a job 20 executors instead of 10) actually impacted performance over time.
Methods
The authors propose MACE (Memory-Augmented reinforcement learning model with Critical structure Encoding), which consists of two primary innovations:
- CSformer (Critical Structure Transformer): This component builds hierarchical embeddings (Stage $\rightarrow$ Job $\rightarrow$ Global). Unlike standard Graph Neural Networks, it uses critical-path-aware positional encodings. It calculates how deep a stage is along the critical path and feeds that into a Transformer. It also uses an extended attention field, allowing stages to "look" at neighbors several hops away to understand long-range dependencies.
- Memory-Augmented Scheduler: This acts as the model's long-term memory. It maintains a fixed-size recurrent state (a memory matrix) for each job. When deciding on parallelism, the scheduler queries this memory using the current job state and the rewards from the previous step. This allows the model to adjust its strategy based on what worked (or didn't) in the recent past.
The entire system is trained end-to-end using the REINFORCE algorithm, a policy gradient method, with the goal of minimizing the average Job Completion Time (JCT).
Datasets
The researchers evaluated MACE using the TPC-H benchmark, a gold standard for data analytics workloads.
- Workload Generation: They simulated a streaming environment where jobs arrive via a Poisson process.
- Scales: They tested across seven data scales ranging from 2GB to 100GB of raw data.
- Baselines: MACE was compared against traditional heuristics (FIFO, SJF-CP, Fair Scheduling, HEFT, SRPT) and the leading RL-based scheduler, Decima.
Key Insights and Ideas
- The Critical Path is the Secret Sauce: The ablation studies revealed that the critical-path-aware positional encoding was the most influential component. Removing it caused a much larger performance drop than removing the memory or the extended attention field.
- Contextual Awareness beats Raw Speed: While heuristic schedulers like FIFO have near-zero decision latency, MACE’s slightly higher latency (~5.5ms) is a drop in the bucket compared to job runtimes (seconds or minutes). The "smarter" decision pays for itself many times over.
- Generalization to the Unknown: MACE showed superior "template-level generalization." When trained on only a few types of queries and tested on entirely new ones, its performance degraded much more slowly than Decima's, likely because it learns the structural motifs of DAGs rather than just memorizing specific job shapes.
Key Results
- Performance Boost: MACE achieved the lowest average JCT in 7 out of 9 test scenarios, outperforming Decima by up to 9.38%.
- Robustness: Under "stress tests"—such as high-load scenarios (frequent job arrivals) or limited resource capacity—MACE maintained a significant lead over both heuristics and other RL models.
- Efficiency: Visualization of scheduling traces showed that MACE packs tasks more densely into available executor slots, leading to earlier job completions and fewer idle "purple regions" in the cluster timeline.
Limitations and Future Work
While MACE is a step forward, the authors note a few areas for improvement:
- Homogeneous Assumptions: The current model assumes all executors (CPUs/Nodes) are identical. In the real world, clusters are often heterogeneous (different RAM, CPU speeds, etc.).
- Communication Costs: The model does not yet explicitly account for the time it takes to move data between executors, which can be a major bottleneck in large-scale shuffles.
- Future Directions: The authors plan to extend MACE to handle these complexities and explore even more diverse, large-scale scheduling environments.
Summary updated