Kubernetes / cloud workload placement

The provably optimal pod placement, in milliseconds.

CloudBalance places your pods across nodes so the busiest node is provably as small as it can be — and returns a certificate that proves it. It answers at a million pods in about 13 milliseconds, at a scale where the free exact solvers run out of memory and return nothing.

Try the playground See the measured numbers

~13 ms

Optimal balanced placement at 1,000,000 pods → 100,000 nodes.

gap = 0

Every answer carries a proof it is optimal — or an honest bound when it can't.

56 KB

One dependency-free binary (libc only), air-gapped by construction.

What it does

Two placement problems, both solved to the proven optimum.

CloudBalance is a placement engine you call over a one-line protocol. It covers the two problems a scheduler actually faces — and for both, it returns the provably minimum busiest node together with a certificate you can check.

BALANCED ALLOCATION

Interchangeable nodes

Place N identical pods across K interchangeable nodes so every node's load stays within [min, cap] and inside a balance tolerance, as evenly as possible.

Returns the optimal even layout.
Enumerates every distinct optimal layout, not just one.
Certifies feasibility before it commits.

ELIGIBILITY PLACEMENT

Heterogeneous nodes

When a pod may only run on its eligible subset — a GPU pool, a zone, a taint, a license — find the placement whose busiest node is provably minimal, and certify whether every pod can be placed at all.

Provably minimum makespan (busiest node).
Feasibility certificate: places all, or tells you it can't.
Cost tracks distinct workloads, not raw pod count.

The certificate

A number you can put in an SLA.

Every answer carries feasible / makespan / lb / gap / exact. makespan is a proven upper bound on the busiest node; lb is a proven lower bound; when gap == 0 the placement is proven optimal, and only then is exact set. The engine cannot overclaim — on a hard input it reports the gap instead of pretending.

# the certificate in action — one concentrated 1,040-pod instance
bound path	makespan	lower bound	gap	verdict
cheap global bound	500	58	442	honest, but loose
certified bound	500	500	0	proven optimal — same placement, no extra solve

The placement is identical bit-for-bit in both rows; only the proof got tighter.

Measured, reproducible

The numbers, against the solvers you'd otherwise reach for.

Balanced allocation, wall-clock milliseconds, single-threaded. Compared against the default greedy scheduler, naive exact search, and the two free provably-optimal solvers teams rely on — OR-Tools CP-SAT and CBC. Every figure is reproducible from source.

# balanced allocation — wall-clock ms · DNF = did not finish (>10 s) · OOM = out of memory
pods → nodes	bal	CloudBalance	greedy	brute-force	CBC	CP-SAT
20 → 4	±3	0.067	0.021	0.018	7.14	21.5
100 → 10	±4	0.408	0.021	290.3	6.15	13.1
500 → 50	±2	0.214	0.034	DNF	7.08	36.3
1,000 → 100	±2	0.466	0.040	DNF	11.4	181
5,000 → 500	±2	13.4	0.283	DNF	102	1,833
10,000 → 1,000	±2	65.0	1.05	DNF	245	12,129
100,000 → 10,000	±1	1.47	12.5	DNF	19,685	10,350
1,000,000 → 100,000	±1	13.1	142	OOM	OOM	OOM

The headline: at 1,000,000 pods → 100,000 nodes, both provably-optimal solvers the market relies on (CP-SAT and CBC) run out of memory and return nothing. CloudBalance returns the optimal balanced allocation in about 13 ms — and along the way it enumerates every distinct optimal layout (5 to 501 of them per instance above), which the competitors never return.

13,400×

faster than CBC at 100,000 pods → 10,000 nodes (1.47 ms vs 19,685 ms).

7,050×

faster than CP-SAT at the same scale (1.47 ms vs 10,350 ms).

∞

at 1,000,000 pods both run out of memory; CloudBalance answers in ~13 ms.

Eligibility placement vs CP-SAT — same answer, thousands of times faster

# heterogeneous nodes — both return a provably-optimal makespan
pods → nodes	CloudBalance	CP-SAT	CP-SAT result	speedup
1,000 → 100	0.44 ms	386.5 ms	optimal, makespan 10	~880×
10,000 → 1,000	9.24 ms	39,380 ms	optimal, makespan 10	~4,260×
100,000 → 10,000	315.4 ms	94,042 ms	timed out — returned 11 (worse)	~298×
1,000,000 → 100,000	11,342 ms	—	out of memory, nothing	∞

On deployment-shaped load, solve cost stops tracking pod count

Real clusters are mostly a handful of deployments of many identical replicas. CloudBalance collapses those to classes and solves the quotient, so cost depends on how many distinct workloads you have — not how many pods they expand to.

# structured load — CloudBalance quotient vs a good greedy packer
total pods	CloudBalance (ms / makespan)	greedy (ms / makespan)	speed
500	0.004 / 1	0.091 / 1	23×
5,000	0.003 / 10	0.914 / 12	317×
50,000	0.003 / 100	6.87 / 122	2,492×
500,000	0.003 / 1,000	71.4 / 1,219	29,098×
5,000,000	0.003 / 10,000	734.5 / 12,188	271,947×

On these instances greedy also runs about 22% over the optimum — so here CloudBalance wins on both speed and quality.

Measured on an 11th-Gen Intel Core i5-1135G7 @ 2.40 GHz, 32 GB, Debian 13, gcc 14.2 -O2, single-threaded; competitors Python 3.13 + OR-Tools 9.15.6755 given all 8 cores and the symmetry-break constraint. Single run per instance; ratios are order-of-magnitude. We benchmark against the free solvers (CP-SAT, CBC) and the default greedy scheduler — we have not benchmarked against commercial solvers and make no claim about them.

Will it work on your load?

Measure your cluster before you commit to a solve.

The whole speed story turns on one question: how much of your load is repeated structure (many identical replicas of a few deployments) versus one-off residue. CloudBalance ships a profiler that answers exactly that in one pass — no solve. Feed it a real export (kubectl get pods plus node labels) and it reports how many distinct workload classes you have, what fraction of the load is structured, the pod-count-independence factor, and which engine you'd get.

# profiler output on modeled workloads — how structured a cluster tends to be
modeled workload	pods	classes	structured	pod ÷ class	routes to
Kubernetes cluster	9,293	130	98.7%	71.5×	compressed exact, gap 0
fully random (worst case)	3,000	3,000	0%	1.0×	flat greedy + certificate

These percentages are synthetic models, not customer telemetry. They come from generators that mimic the shape of real workloads. To get your real split, run the profiler on your own cluster export — that's the first step of a pilot, and it costs nothing. Even the worst case (no structure) still returns a certified answer: with no repeated structure there is no bottleneck to miss, so the cheap certificate is already near-tight.

Live engine

Run it yourself.

These call the real engine over the local gateway — one request line in, one result line out. Demo sizes are kept small so every call is instant; the million-pod figures above are measured results, served as data — not run live here. Start the engine with site/serve.sh, then open this page through the gateway.

Access key — paste the key we gave you to lift the free-trial cap

# the entire integration surface — one line in, one line out
$ printf 'ORBIT_CLOUD 100 10 bal=2\n' | nc -U /tmp/orbit.sock
OK feasible=1 optimal_max_load=10 variance=0.0000 n_placements=6 solve_ms=0.05
    

1 · Profile your load — no solve

One classification pass: how much of a load is repeated structure vs one-off residue, and which engine it routes to. This is the free pre-check — it never solves.

pods (M)

nodes (K)

eligibility (pod:node, comma-separated)

2 · Balanced allocation — interchangeable nodes

Place identical pods across interchangeable nodes as evenly as possible, and enumerate every distinct optimal layout. Runs the full headline instance live — try 1,000,000 pods across 100,000 nodes and it returns in well under a second, the same case OR-Tools and CBC run out of memory on.

pods

nodes

balance (bal)

cap (optional)

3 · Eligibility placement — the certificate

Heterogeneous nodes on the deployment quotient: pod classes with eligibility to node groups. Returns the provably minimum makespan plus the full certificate — and its cost is independent of how many pods the classes expand to.

class counts (comma)

group sizes (comma)

eligibility (class:group)

What it does for you

Lower the busiest node, and prove it.

Provision for the peak you actually need

The busiest node is what you pay to provision. CloudBalance makes it provably as small as possible — a measured 6–22% lower peak node than a good greedy packer. That converts to cost only when a lower peak changes what you provision; we frame it that way on purpose.

A guarantee you can write down

"Busiest node ≤ X, or the placement is rejected." That is a certificate a heuristic cannot give and CloudBalance can — something you can put in your own SLA to your own customer.

Scale the free exact solvers can't reach

The optimal plan at a million-plus pods, in seconds to milliseconds — where CP-SAT and CBC run out of memory and return nothing at all.

Fast enough for the control loop

Sub-millisecond on structured load means you can re-optimize continuously inside a scheduling loop, instead of on a rare batch schedule.

Trustworthy in production

Built to survive a security audit, not just a benchmark.

Every property below is verified against the shipped binary — for the SRE, platform, finance, and sovereign on-prem buyer who has to defend what runs in the critical path.

Zero dependencies

ldd shows libc only. Nothing transitive to vendor, audit, or patch.

Auditable in an afternoon

A 56 KB binary from 2,206 lines of C. A security team can read all of it.

Air-gapped by construction

Opens an AF_UNIX socket at 0600 only — no network syscalls anywhere, and it writes no files. It cannot phone home.

Deterministic

Integer decision logic, zero floating point anywhere. Same input, same output, on every box — cacheable and sign-off-able.

Flat tail latency

Pure C, no garbage collector, no JIT, no interpreter. No p99 spike from a GC pause or a cold import.

Bounded, tiny memory

On structured load it never materializes the pods — which is exactly why it answers where CP-SAT and CBC hit their memory ceiling.

Self-certifying output

Every response carries its own optimality certificate. Trust the result without re-solving it.

Stateless, one line in / out

No session, no auth handshake, no schema. printf … | nc -U from any language.

A dry-run cost oracle

Profile your real load and see the engine and cost you'll get before spending a solve.

Green, cross-checked test suites

Router 24/24, greedy 20/20 (bit-for-bit standard greedy at the O(E) floor), full flow 8/8, quotient 6/6 plus a 200-instance random fuzz — all cross-checked.

Honest scope

What it proves, and what it doesn't.

Overclaiming here loses the technical buyer, so we state it plainly. Provably optimal applies to unit-demand placement — balanced identical pods, and eligibility. Two neighbouring problems are genuinely hard and out of scope.

Provably optimal

Balanced allocation of identical pods across interchangeable nodes.
Eligibility placement: unit-demand pods restricted to their eligible node subset (GPU pool, zone, taint, license).
Minimum busiest node (makespan) with a feasibility certificate; gap == 0 proves it.

Out of scope — and we say so

Varied indivisible pod sizes (true bin packing) is NP-hard. CloudBalance does not claim optimal there.
Hard anti-affinity (no two of set X co-located) is graph coloring, NP-hard, and out of scope.
On any input it can't prove, the engine reports the gap instead of pretending — exact is never set unless the gap actually closes.

vs alternatives

Straight answers to the obvious objections.

Kubernetes already places pods — why add this?

The default scheduler runs one greedy pass and proves nothing — it can over-pack a node or strand a pod and still report a number. On random load greedy is faster and 6–20% worse; on real deployment-shaped load CloudBalance is both faster and optimal. When the SLA is "busiest node ≤ X or reject," greedy's 10–20% overshoot is the difference between fitting and not.

We use OR-Tools / CP-SAT — isn't that already exact?

So is CloudBalance, on the same instances, hundreds to thousands of times faster. At 100,000 pods CP-SAT can no longer prove optimality inside 90 seconds and hands back a worse answer; at a million it dies with std::bad_alloc while merely building the model. CloudBalance returns the exact optimum there in seconds.

We use a MILP solver like CBC.

CBC scales further than naive search but grows steeply: about 20 seconds at 100,000 pods, and out of memory at a million. On the instance a large cluster actually has, it returns nothing.

We'll just write our own search.

Naive exact backtracking is fine at 20 pods (0.018 ms), burns 290 ms at 100, and doesn't finish inside 10 seconds by 500. That wall is why nobody ships it.

How do I know your answer is right, and how hard is it to integrate?

It's 56 KB of dependency-free C you can read end to end, it can't touch the network, it returns the same answer every time, and every answer carries its own optimality certificate. Integration is one request line in, one result line out.