CvxCluster: Solving Large, Complex, Granular Resource Allocation Problems 100–1000x Faster
This page was written by an AI model to give a high-level overview of the paper. Please check the paper for detail: arXiv.
A cluster scheduler places a stream of tasks, each asking for CPU, memory and sometimes GPUs, onto servers with fixed capacities, while honoring policies such as anti-affinity (replicas of one job must land on different servers). Written exactly, this is a multidimensional knapsack problem: servers are bags, resources are dimensions, tasks are objects with a value. The standard optimal formulation is a mixed-integer program (MIP) with one yes/no variable per task-server pair, and it is NP-complete. As clusters and arrival rates grow, the time to make each decision becomes a first-order bottleneck: a slow scheduler forces smaller batches, limits cluster size and adds queueing delay.
Existing approaches trade one problem for another. MIP solvers search a tree of partial solutions (branch-and-bound) and are effective at small scale, but at 3,000 tasks and 250 servers the formulation already has 750,000 binary variables, and the commercial solver Gurobi takes 14.4 s on average, at every scheduling round. Heuristic schedulers, such as the Kubernetes filter-and-score pipeline or Tetris's multi-resource bin packing, are fast but make local decisions without a global view of which resources are scarce. Optimization-based systems such as POP stay fast by simplifying the problem, for example by assuming all servers are interchangeable.
CvxCluster's key idea is to move from a discrete problem to a convex one. In a convex problem any local optimum is also the global optimum, and solvers for it are fast. Letting each placement variable take any value between 0 and 1 turns the MIP into a linear program (LP), which is convex. The LP's answer is not a valid placement, because it splits tasks across servers, so CvxCluster does not use it to place anything. It keeps only the LP's dual variables, or shadow prices: one number per resource per group of servers that says how much the objective would improve with one more unit of that resource. A high CPU price on one kind of machine means CPU is the bottleneck there this round.
The scheduler runs in two stages. Stage 1 sums the capacity of all servers with the same hardware configuration (a shape; a cluster typically has at most tens) into one pool, so the LP's size depends on the number of shapes and tasks, not servers, and reads the shadow prices from the solver. Stage 2 gives each task a net utility on each shape (its priority minus the price of the resources it would use), sorts tasks by their best net utility, and places each on a randomly chosen feasible server of its best shape, falling back to the next-best shape. Discrete rules such as machine labels and anti-affinity are checked in constant time during placement, and the ones that can be written as capacity limits can also be added to the LP so that they get prices of their own.
The evaluation uses the Azure Public Dataset V2 trace. On static placement instances, wherever the Gurobi MIP baseline finishes (up to 250 servers and 10k tasks), CvxCluster is 27 to 586× faster with per-shape prices and 85 to 2,566× faster with one cluster-wide price vector, at a weighted objective 0.7 to 3.1% below the MIP's (this summary's arithmetic from the paper's Table 1). The MIP finds no feasible solution within 600 s at 2,500 servers, while CvxCluster places 1M tasks on 25,000 servers. In simulation with 1 s scheduling rounds, it keeps up with nearly 100,000× the trace's arrival rate on a 785-server cluster, and its solve time grows from 0.8 ms to 43 ms as the cluster grows 128× to 100,480 servers. On a 785-node Kubernetes cluster with simulated nodes, it places pods about 38× faster than DCM, a solver-based scheduler that supports the same constraints.
Key takeaways
- Exact cluster placement is a mixed-integer program with one binary variable per task-server pair; it is NP-complete and too slow to re-solve every scheduling round at scale.
- CvxCluster relaxes it to a linear program, which is convex and fast, and uses the solution only for its shadow prices: the marginal value of each resource on each server shape.
- Pooling servers by shape makes the LP's size independent of cluster size; one cluster-wide price vector (global pricing) is a smaller, faster option.
- A greedy stage ranks tasks by priority minus priced resource cost and places them with constant-time checks for capacity, labels and anti-affinity; constraints expressible as capacity can also be priced in the LP.
- On Azure trace instances: 27 to 2,566× faster than a Gurobi MIP where the MIP finishes, with an objective 0.7 to 3.1% lower (this summary's arithmetic); scales to 1M tasks on 25,000 servers statically and to 100,480 servers in simulation; about 38× DCM's throughput on Kubernetes with simulated nodes.
From a mixed-integer program to shadow prices and a greedy pass
The optimization background, the paper's formulation, the two stages, how constraints fit in, and what the evaluation measures.
1 · Cluster scheduling as an optimization problem
Each round, a scheduler holds a batch of pending tasks, each with demands in several resource dimensions (CPU cores, memory, sometimes GPUs), and a set of servers with fixed capacities in the same dimensions. It must choose which tasks run and where, maximizing some goodness measure (in this paper, priority-weighted placement) without exceeding any server's capacity and while obeying placement rules. In its simplest form this is a multidimensional knapsack problem, which is NP-complete.
The paper groups prior approaches into two families:
- Exact solvers. The standard optimal formulation (used, for example, by POP) is a mixed-integer program with continuous resource quantities and boolean placement variables. MIP solvers explore it with branch-and-bound and cutting planes, repeatedly solving relaxations while searching a combinatorial tree. This works at small scale, but its cost grows quickly with cluster size and arrival rate, which forces smaller batches and less frequent scheduling.
- Heuristics. Kubernetes filters and scores servers in a modular pipeline, Tetris adapts bin-packing heuristics to several resources, and delay scheduling trades a short wait for locality. These are fast but make locally optimal decisions without a global view of resource scarcity across the cluster.
The paper also notes that fast optimization systems often simplify the problem: POP assumes all servers are fungible, while real deployments need constraints such as forcing replicas onto different servers.
2 · Convex optimization in brief
An optimization problem is convex when its objective and feasible region are convex; the property the paper relies on is that any local optimum is then also the global optimum, so solvers can move downhill without searching a combinatorial tree, and convex problems can be solved in polynomial time. A linear program (linear objective, linear inequality constraints, continuous variables) is the simplest convex problem. Adding a requirement that some variables be integers (0 or 1) breaks convexity and gives a mixed-integer program (general knowledge, consistent with the paper's Sections 1 and 2).
- Relaxation. Dropping the integer requirement, here letting a placement variable be any value in [0, 1], turns a MIP into an LP. The LP's optimum is at least as good as the MIP's (general knowledge), but it may be fractional: a task placed 40% on one server and 60% on another (the percentages are illustrative). That is not a valid placement.
- Duality and shadow prices. Solving an LP also yields one dual variable per constraint. For a capacity constraint, the dual variable is the shadow price of that resource: how much the optimal objective would rise per extra unit of capacity (general knowledge; the paper uses the same interpretation). A resource with spare capacity has a price near zero; a contended one has a high price. Modern solvers report dual values as a byproduct of the primal solve.
- Prices as a decomposition. Using dual variables to separate a global coupling constraint (shared capacity) from local decisions is a long-standing technique in networking, control and resource allocation, which the paper cites as its inspiration. CvxCluster applies it so that the LP carries the global reasoning and a simple per-task procedure makes the discrete choices.
3 · The paper's formulation
Section 4.2 gives the exact mixed-integer linear program (MILP) CvxCluster starts from. With t tasks, s servers and r resources:
| Symbol | Shape | Meaning |
|---|---|---|
| T | t × r | Task demand matrix; Tj,k ≥ 0 is task j's demand for resource k |
| S | s × r | Server capacity matrix; Si,k is server i's capacity for resource k |
| A | s × t, entries in {0, 1} | Assignment matrix; Ai,j = 1 if task j is placed on server i |
| p | t | Priority vector; pj > 0 is task j's priority weight |
| ℓg, h(j) | per job group | Anti-affinity limit of job group g; h(j) is the group task j belongs to |
subject to A⊤1 ≤ 1 (2) each task on at most one server
AT ≤ S (3) no server over capacity in any resource
Σj: h(j)=g Ai,j ≤ ℓg ∀g, ∀i (4) anti-affinity
The formulation has t · s binary variables and O(s · r + t + |J| · s) constraints, where |J| is the number of job groups with anti-affinity. At 3,000 tasks, 250 servers, 2 resources and no anti-affinity, that is 750,000 binary variables, and Gurobi takes 14.4 s on average over five random seeds. The cost recurs every scheduling round.
4 · Stage 1: relax, aggregate, read the prices
- Relax. Replace A ∈ {0,1}s×t with A ∈ [0,1]s×t. The result is an LP, which the paper says scales as O(s2 · t) in practice.
- Aggregate by shape. A shape is a hardware configuration (processor type, core count, RAM, GPUs). All servers with the same shape are summed into one capacity pool, so the LP's variables and capacity constraints are defined over m shapes instead of s servers, and the cost becomes O(m2 · t). A datacenter cluster typically has at most tens of shapes. Global pricing goes further and pools the whole cluster into one capacity vector.
- Read the duals. The paper notes two ways to get prices: formulate and solve the dual problem, or solve the primal LP and read the dual values from the solver's output. CvxCluster does the second, which it found simpler and no more costly at the tested sizes. Every server inherits its shape's price vector.
- Interpret. A high CPU price on one shape means CPU is that shape's bottleneck this round. If arriving tasks turn memory-heavy, the memory price on the affected shapes rises, making memory consumption more expensive for the next placements.
5 · Stage 2: greedy placement with prices
- Net utility. For each task and each shape, compute net utility = the task's priority minus the cost of the resources it would consume at that shape's shadow prices. Tasks that use a lot of a scarce resource get lower utility on shapes where it is scarce.
- Rank. Sort all pending tasks in descending order of their best net utility across shapes. This puts higher-priority work first, and steers tasks that do not need a contended configuration away from it.
- Place. For each task in order, find the servers of its best shape that can still satisfy it and pick one uniformly at random. If none can, fall back to the task's next-best shape.
- Check constraints. Each attempt runs constant-time or low-overhead checks: remaining capacity, machine-specific labels or resources, and anti-affinity (an O(1) per-task check of the co-location count for the task's job group on the candidate server).
The paper describes the procedure as intentionally simple: the prices create a near-correct global ordering, and the greedy stage only has to find feasible servers quickly.
6 · Where constraints go
A constraint can live in either stage. Discrete, policy-driven or expensive ones stay in the greedy checks, which can change without touching the pricing stage. Constraints that can be written as per-server capacity limits can also go into the LP, where they get shadow prices of their own that reflect how tight they are, at the cost of more LP rows and a longer stage 1 solve. Anti-affinity is the paper's example (its Figure 2): each job group adds an indicator column to the task demand matrix and a limit column to the server capacity matrix, so the existing capacity constraint AT ≤ S enforces both.
| Task | cpu | mem | Grp 1 | Grp 2 | Server | cpu | mem | Grp 1 | Grp 2 | |
|---|---|---|---|---|---|---|---|---|---|---|
| Task 1 | 4 | 8 | 1 | 0 | Server 1 | 192 | 384 | 1 | 1 | |
| Task 2 | 2 | 2 | 1 | 0 | Server 2 | 192 | 384 | 1 | 1 | |
| Task 3 | 2 | 4 | 0 | 1 | Server 3 | 96 | 768 | 1 | 1 | |
| Task 4 | 8 | 32 | 0 | 1 | ||||||
| Task 5 | 4 | 32 | 0 | 0 |
In this example from the paper, every server has a limit of 1 per group, so at most one task of each group can land on any server. Because only tasks in a group consume its column, the paper argues these extra variables add little complexity.
The GPU extension (Section 5.6) uses the same split. Two GPU shapes are added to the five CPU-only shapes, and a penalty term in the LP objective raises the cost of placing non-GPU tasks on GPU shapes, so the duals reflect that preference. In the greedy stage, GPU-demanding tasks get higher priority so they are placed earlier, and GPU-equipped servers get an extra cost in net utility.
7 · Implementation and evaluation setup
| Item | Setup |
|---|---|
| Software | A discrete-event simulator (about 4,200 lines of C++, single-threaded for deterministic replay) and a Kubernetes custom scheduler (about 3,400 lines of C++), sharing one pipeline: build the LP, extract duals, run greedy placement |
| Solver | Gurobi for CvxCluster's LP and for the MIP baseline (600 s time limit) |
| Workload | Azure Public Dataset V2, a 30-day trace of first-party VM workloads |
| Base cluster | 785 servers drawn uniformly from five AWS machine shapes (96 to 192 vCPUs, 256 to 768 GB), 127,232 vCPUs and 450 TB in total; the smallest cluster that sustains the trace at its original rate without unbounded queue growth |
| Priorities | Four levels (1, 2, 4, 8), with task counts inversely proportional so each level contributes the same total priority (static instances) |
| Scaling | Speed: raise the arrival rate and shorten durations proportionally on a fixed cluster. Size: raise the arrival rate and grow the cluster proportionally |
| Kubernetes | 785 KWOK nodes (simulated nodes and pod lifecycles, no real kubelets) on AWS, compared with DCM, which solves SQL-like constraints with the CP-SAT solver and supports anti-affinity |
8 · Results
Static placement against the MIP (Table 1). All tasks and servers are known up front, which the paper calls the worst case for CvxCluster, since the MIP has complete information.
| Instance | Weighted objective (MIP / shape / global) | Placement rate (MIP / shape / global) |
|---|---|---|
| 25 servers, 1k tasks | 2,019 / 2,004 / 1,989 | 89.6 / 88.1 / 86.6% |
| 250 servers, 10k tasks | 20,457 / 20,096 / 20,006 | 93.6 / 89.2 / 88.4% |
| 25 servers, ~1k tasks, anti-affinity (500 jobs) | 2,077 / 2,036 / 2,012 | 90.1 / 86.1 / 83.8% |
| 250 servers, ~10k tasks, anti-affinity (5k jobs) | 22,063 / 21,565 / 21,545 | 90.8 / 85.9 / 85.7% |
- Quality. The paper summarizes the unconstrained case as shape pricing within about 3% and global pricing within about 4% of the MIP objective. Shape pricing consistently recovers 1 to 2% over global pricing, at the cost of a larger LP. The gap is concentrated at the lowest priority level: high-priority tasks are placed at near-identical rates by all three methods.
- Why the gap sits at low priority. The greedy stage places tasks in decreasing net utility, so low-priority tasks absorb any shortfall. The MIP optimizes all tiers jointly and can pack low-priority tasks more tightly; in some instances it gives up a few large high-priority tasks to fit many small low-priority ones.
- Anti-affinity. With at most one replica per server, the MIP fails to produce a feasible solution beyond 5k jobs, while CvxCluster scales to 500k jobs (~1M tasks) on 25,000 servers, with speedups of 557× (shape) and 1,336× (global) at 5k jobs.
- Where time goes at scale. At 1M tasks, the greedy stage, not the LP, accounts for over 90 s of the 134 s shape-pricing solve.
Speed scaling (Figure 3). On the 785-server cluster with global pricing and a 1 s scheduling interval, the arrival rate is multiplied from 1× to 500,000×, with durations shortened to keep total demand roughly constant. Average solve time is under 1 ms up to 100× and 19 ms at 10,000×. The scheduler sustains nearly 100,000×, placing over 19,000 tasks/s with an average solve of 574 ms (worst case 1.4 s). At 500,000× the average solve is 966 ms (worst case 2.8 s) and the queue grows faster than it drains. Average wait falls from about 1.0 s at 1× to 0.5 s over 250 to 10,000×, then rises to 7.6 s at 100,000× and 13.2 s at 500,000×, where highest-priority tasks wait 3.0 s on average and lowest-priority tasks 15.7 s. At the original rate, the MIP achieves 0.04 s lower average wait, with a 237× slower average solve.
Size scaling (Figure 4). Growing both arrival rate and cluster up to 128× (100,480 servers), per-round solve time rises from 0.8 ms to 43 ms, well within the 1 s interval, and average wait falls from 1.0 s to 0.5 s. The paper attributes the wait improvement to a known bin-packing property: when bins are large relative to objects, almost everything fits into residual capacity.
Kubernetes (Figure 5). At 20× the trace's arrival rate, with job durations capped at 30 s to suit DCM's rate and DCM batching at most 50 pods, CvxCluster places all 7,500 pods in under 500 s, while DCM places about 400 pods in 1,050 s before the run was stopped: about 38× higher throughput. The paper attributes DCM's rate both to its SAT solver taking longer per 50-pod round than CvxCluster takes on far larger batches, and to its extra SQL queries and processing.
GPUs (Table 2). With 50% of tasks given synthetic GPU requirements, CvxCluster matches the MIP's objective exactly at 1k tasks (6,893) and 10k tasks (69,387), solving 14× and 210× faster. At 100k tasks the MIP runs out of memory while CvxCluster completes. The paper suggests that in tightly constrained scenarios like these, the LP relaxation is a closer approximation to the integer program.
9 · Limitations and open directions the paper states
- Rounding gap. Converting the fractional LP into discrete placements loses some quality, which cannot be closed without solving the full integer program. For clusters where every percent of utilization matters, this may not be acceptable.
- Batch model. All queued tasks are placed in one pass per interval. A large queue makes the solve slower; too short an interval leaves too few tasks for the LP to produce useful prices. The fixed 1 s interval is a tuning choice.
- Possible improvements. Iterative rounding (re-solving after placing the top tasks), an adaptive interval based on queue depth, warm-starting the LP across rounds, finer shape groupings (for example by remaining-capacity buckets), and a faster greedy stage (better data structures, parallelism).
- Broader use. The paper argues the price-then-greedy decomposition applies to any allocation problem with capacity constraints and prioritized demands where resources are fungible within groups, such as network bandwidth or storage tiering, and to multi-cluster settings where each cluster is a shape. It also suggests exposing prices to tenants for chargeback or using them as features for learned policies.
FAQ
Q·If the LP's answer is not a valid placement, why solve it at all?▾
For its prices. Solving the LP yields a dual variable for each capacity constraint, which measures how much one more unit of that resource on that shape would improve the objective. Those numbers summarize supply and demand across the whole cluster in a handful of values per shape, and the greedy stage uses them to rank and place tasks. The fractional assignment itself is discarded.
Q·What makes the LP so much faster than the MIP?▾
Two things. An LP is convex, so a solver does not need to search a tree of integer choices: any local optimum is global. And shape aggregation shrinks the LP's server dimension from thousands of servers to the number of shapes (tens at most), so the paper's cost estimate drops from O(s2 · t) to O(m2 · t), independent of cluster size. The MIP keeps one binary variable per task-server pair.
Q·How is this different from POP?▾
The paper describes POP as showing that large granular allocation problems can be solved with optimization, but restricted to fungible resources: it assumes all servers are equivalent. CvxCluster keeps distinct server shapes (each with its own prices) and supports constraints such as anti-affinity and machine labels. The paper's evaluation compares against an exact MIP and against DCM, not against POP.
Q·How does it compare with heuristic schedulers such as the Kubernetes default or Tetris?▾
The paper's argument is qualitative: heuristic pipelines are fast but make local decisions without a global view of scarcity, and they rely on hand-tuned scoring. CvxCluster's greedy stage is also simple, but its ordering comes from prices computed over all pending tasks and all capacity. The evaluation does not include a head-to-head comparison with those heuristic schedulers.
Q·What is the difference between shape pricing and global pricing?▾
Shape pricing pools servers per hardware configuration and produces one price vector per shape. Global pricing pools the whole cluster and produces one price vector for everything. Global pricing gives the smaller LP and usually the faster solve; shape pricing keeps per-shape capacity structure and recovers 1 to 2% of objective over global pricing in the static experiments. The paper presents the granularity as a knob operators can set by latency budget. In the anti-affinity runs at 25,000 servers, shape pricing was the faster of the two (245.0 s vs 377.1 s).
Q·Which tasks lose out compared with the optimal MIP?▾
The lowest-priority ones. Because the greedy stage places tasks in decreasing net utility, high-priority tasks are placed at near-identical rates to the MIP, and low-priority tasks absorb the shortfall. The MIP sometimes does the opposite: it drops a few large high-priority tasks to pack many small low-priority ones, which raises the total objective while inverting priority order.
Q·What happens when a task does not fit on any server of its best shape?▾
Placement falls back to the shape with the task's next-best net utility, and so on. Within a shape, the server is chosen uniformly at random among those that pass the capacity, label and anti-affinity checks. A task that cannot be placed stays in the queue for a later round (inference from the paper's queueing and wait-time results).
Q·How do constraints like anti-affinity fit into a linear program?▾
As extra capacity dimensions. Each anti-affinity group adds a column to the task demand matrix (1 for tasks in the group) and a column to the server capacity matrix (the group's per-server limit), so the ordinary capacity constraint also bounds co-location. Putting it in the LP gives the constraint its own shadow prices; it is always enforced in the greedy stage with an O(1) check either way. Constraints that cannot be written as capacity stay in the greedy checks only.
Q·Does it need a commercial solver?▾
The paper's experiments use Gurobi for both the LP and the MIP baseline, and CvxCluster reads the dual values from the solver's output. It notes that one could instead formulate and solve the dual problem directly. Results with other solvers are not reported.
Q·How are GPUs handled?▾
GPU servers become additional shapes with a GPU resource dimension. Without extra terms, CPU capacity on GPU servers could get the same price as on CPU-only servers, so CPU tasks would use them interchangeably. The paper adds a penalty in the LP objective for placing non-GPU tasks on GPU shapes, raises the priority of GPU-demanding tasks, and adds a cost for GPU servers in the greedy stage. With 50% of tasks given synthetic GPU demands, the objective matched the MIP's exactly at 1k and 10k tasks.
Q·Is there anywhere it does worse or slows down?▾
At the original trace rate, the MIP gets 0.04 s lower average wait, though its average solve is 237× slower. At 500,000× the trace rate on 785 servers, the average solve nears the 1 s interval and the queue grows faster than it drains. At 1M tasks, the greedy stage dominates the solve (over 90 of 134 s with shape pricing), which the paper sees as room for better data structures or parallelism.
Q·Was it run on a real cluster?▾
Partly. The Kubernetes experiment runs a real scheduler against the Kubernetes API on AWS, but the 785 nodes are KWOK nodes, which simulate node and pod lifecycles without running real kubelets. The other dynamic results come from the paper's discrete-event simulator replaying the Azure trace.
Q·What does the evaluation not show?▾
All workloads derive from one trace (Azure Public Dataset V2), and the GPU demands are synthetic because the trace has no GPU requests. The DCM comparison caps job durations at 30 s to suit DCM's scheduling rate. The paper also leaves its suggested improvements (iterative rounding, adaptive intervals, warm starts across rounds, finer shapes) unevaluated.