Omega: flexible, scalable schedulers for large compute clusters
📜 Abstract
Increasing scale and the need for rapid response to changing requirements are hard to meet with current monolithic cluster scheduler architectures. This restricts the rate at which new features can be deployed, decreases efficiency and utilization, and will eventually limit cluster growth. We present a novel approach to address these needs using parallelism, shared state, and lock-free optimistic concurrency control. We compare this approach to existing cluster scheduler designs, evaluate how much interference between schedulers occurs and how much it matters in practice, present some techniques to alleviate it, and finally discuss a use case highlighting the advantages of our approach – all driven by real-life Google production workloads.
✨ Summary
Summary
The paper presents Omega, a cluster-scheduling architecture designed to improve both scalability and extensibility in large, heterogeneous compute clusters. It addresses limitations of monolithic schedulers, including difficult code evolution, limited parallelism, and head-of-line blocking, as well as limitations of two-level schedulers such as pessimistic resource locking and restricted visibility of cluster state.
Omega uses multiple independent schedulers that concurrently access a shared, persistent representation of the entire cluster state. Each scheduler operates on a locally synchronized copy, makes placement decisions independently, and submits an optimistic transaction to commit its changes. Conflicting updates are detected during commit; nonconflicting changes can be retained, while conflicting work is retried. This enables specialized schedulers, full cluster visibility, and parallel scheduling without a central resource-offer allocator.
The evaluation combines a lightweight simulator using synthetic workloads derived from Google traces with a higher-fidelity simulator based on production scheduler code and real workload traces. Compared with monolithic and Mesos-style two-level scheduling, Omega avoids head-of-line blocking and handles long scheduling decisions more effectively. The simulations indicate that interference is generally low at realistic operating points, although conflict rates and scheduler load increase as decision times and workload intensity grow. Incremental transactions perform better than coarse-grained conflict detection or universal gang scheduling; gang scheduling is best applied selectively to jobs that require it.
The authors also demonstrate that Omega supports workload-specific schedulers. A prototype MapReduce scheduler uses global cluster information to allocate otherwise idle resources opportunistically. Depending on the policy and workload, the simulations suggest that 50–70% of MapReduce jobs could benefit, with approximately 3–4× speedups around the 80th percentile under an aggressive resource-allocation policy. The paper notes that these results depend on a simplified performance model.
Influence
Subsequent cluster-scheduling research explicitly cites Omega as an important example of distributed, shared-state scheduling. Microsoft’s Apollo system cites Omega as prior work and develops a related distributed scheduling framework that uses synchronized global cluster information and optimistic coordination, while targeting large production deployments. (usenix.org) Later surveys and taxonomies classify Omega alongside Apollo and other shared-state schedulers, indicating that its architecture became a standard reference point for scalable cluster-resource management. (onlinelibrary.wiley.com) Google’s retrospective treatment of Borg, Omega, and Kubernetes further documents Omega’s place in the evolution of Google’s container-management systems. (studylib.net)