How Swarm Reinforcement Learning Boosts Alibaba’s Sigma Container Scheduling

Background

Alibaba’s 2018 Double‑11 shopping festival generated 213.5 billion CNY in transaction volume, a 360‑fold increase over ten years. The resulting surge in services required the group‑wide container orchestration platform Sigma to coordinate millions of hosts across more than 20 business lines. Efficient scheduling in Sigma is therefore critical for overall system stability and resource utilization.

Problem Definition

When a user requests a container with specific CPU, memory and disk capacities, the scheduler must select a physical machine that satisfies all constraints. This selection can be modeled as a vector bin‑packing problem . If all requests are known beforehand (offline), the problem becomes an integer programming (IP) task. In real‑time operation, requests arrive sequentially, forming a Markov Decision Process (MDP) where the optimal policy could be obtained by value or policy iteration.

Classic heuristics such as First‑Fit (FF) and Best‑Fit (BF) guarantee at most a 1.7‑approximation for one‑dimensional packing, but no similar bounds exist for multi‑dimensional packing, especially when multiple resource dimensions become bottlenecks or when placement constraints (anti‑affinity, disaster‑recovery) are imposed.

Online Scheduling Model

Let p∈P denote the resource vector of a pending container, s∈S the current cluster state, and A⊆A the set of candidate hosts. A scheduling policy is a function π:S×P→A. Deploying a container on host a=π(s,p) incurs an immediate cost r(a). The next state s′ is determined by a transition function L(s,p,a). With discount factor γ∈[0,1], the Bellman equation is:

The optimal policy satisfies:

SwarmRL Algorithm

To overcome the limitations of hand‑tuned heuristics, the Decision‑Intelligence team introduced Swarm Reinforcement Learning (SwarmRL) . The approach uses a population of agents that explore the policy space in parallel and share information to avoid poor local optima while converging quickly.

The high‑fidelity Sigma simulator Cerebro provides state‑value estimates V^π for each candidate policy. The algorithm proceeds as follows:

Randomly initialize a population of agents, each with a distinct policy.

Evaluate every policy in Cerebro, record the globally best policy π_G.

For each agent, update its policy using a velocity‑based rule that combines its local best π_L and the global best π_G:

v ← w·v + C₁·ξ₁·Φ(π_L – π) + C₂·ξ₂·Φ(π_G – π)

where w is the inertia factor, C₁ and C₂ are self‑learning and social‑learning coefficients, ξ₁, ξ₂∈[0,1] are random scalars, and Φ projects the update back into the feasible policy space. The new policy is obtained by applying the updated velocity to the current policy. After each iteration, policies are re‑evaluated in Cerebro, and the global best is refreshed until convergence criteria (e.g., no improvement over several iterations) are met.

State‑value estimation uses multiple sampled cluster snapshots and request sequences. For each sample, the simulator tracks the total cost of the resulting trajectory; the average across samples yields the expected value of a policy.

Experimental Evaluation

Small‑scale benchmark

Scenario: 30 applications, host specification 96 CPU/512 GB, container types 4c8g and 8c16g.

Offline optimal (integer programming) : placement rate 94.44 % using 15 hosts (theoretical upper bound).

Best‑Fit (online) : placement rate 70.83 % using 20 hosts.

SwarmRL (online) : matches the offline optimum—94.44 % placement with 15 hosts.

Large‑scale scenario

Scenario: 3 000 requests generating 5 000 containers. Integer programming is intractable.

SwarmRL reduces host count by 13 hosts (‑4.48 %) and improves placement rate by 4.30 % compared with Best‑Fit.

Compared with manually tuned heuristics, SwarmRL saves 7 hosts (‑2.46 %) and gains 2.36 % in placement rate.

Across 30 random request orderings, SwarmRL’s host‑count variance is 3 hosts, far lower than Best‑Fit (variance = 39) and manual strategies (variance = 84).

Average placement rate: SwarmRL exceeds manual by 13.78 % and Best‑Fit by 3.02 %.

Conclusion and Outlook

SwarmRL consistently achieves higher placement rates and lower resource consumption than traditional heuristics and manual tuning, demonstrating stable performance across varying request orders. The algorithm has already been deployed in Sigma’s production environment, yielding noticeable improvements in resource‑pool utilization.

Future work will extend SwarmRL to multi‑objective scheduling (e.g., load balancing, fragmentation reduction) by leveraging its natural ability to construct Pareto fronts for complex policy optimization.

References

David Simchi‑Levi, Xin Chen and Julien Bramel, The Logic of Logistics , 2014.

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction , 2017.

Hitoshi Iima, Yasuaki Kuroe and Kazuo Emoto, “Swarm reinforcement learning methods for problems with continuous state‑action space,” IEEE ICSMC, 2011.

Yossi Azar et al., “Packing small vectors,” SODA 2016.

Yossi Azar et al., “Tight bounds for online vector bin packing,” STOC 2013.