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.

0 deps

A single pure-C binary, air-gapped by construction — no network, no libraries.

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.
Holds its speed on the largest clusters in production.

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

Same placement 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	∞

Sub-millisecond on production-shaped load, at any scale

Real clusters are mostly a handful of deployments repeated many times. On that shape CloudBalance returns the proven optimum in microseconds — and holds that speed as the cluster grows.

# production-shaped load — CloudBalance 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 — while the competitors (Python 3.13 + OR-Tools 9.15.6755, CP-SAT and CBC) were given all 8 cores and the symmetry-break constraint. Benchmarked against the free solvers and the default greedy scheduler.

Will it work on your load?

Measure your cluster before you commit to a solve.

Before you commit to a solve, CloudBalance profiles your cluster in a single pass — no solve — and tells you the placement quality and speed you'll get on your real load. Feed it a real export (kubectl get pods plus node labels) and it reports what to expect, for free.

# profiler verdict on modeled workloads — what you'd get before any solve
modeled workload	pods	expected result
Kubernetes cluster	9,293	provably optimal, gap 0, in milliseconds
fully random (worst case)	3,000	certified answer with a tight bound

Figures above are illustrative, from workloads modeled on real cluster shapes. To see what your own cluster gets, run the profiler on a real export — it's the first step of a pilot, and it costs nothing. Even the worst case returns a certified answer with a tight bound.

Live engine

Run it yourself.

These call the real engine over your own gateway — one request in, one result 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.

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

# the entire integration surface — one request in, one result out
$ curl -s $CLOUDBALANCE/api/cloud -d '{"pods":100,"nodes":10,"bal":2}'
{"feasible":1,"optimal_max_load":10,"variance":0,"n_placements":6}
    

1 · Profile your load — no solve

One pass that tells you the placement quality and speed you'll get on your real load, before you spend a solve. 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: pods with eligibility to node groups. Returns the provably minimum makespan plus the full certificate, and stays fast even on the largest clusters.

workload counts (comma)

group sizes (comma)

eligibility (workload: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 — so a lower peak lets you provision less.

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 production-shaped 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

A single pure-C binary with no third-party code in the trust boundary — your security team can sign off on the whole thing.

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

It answers at scales where CP-SAT and CBC hit their memory ceiling and return nothing.

Self-certifying output

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

Stateless, one request in / out

No session, no handshake, no schema — a single request 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

Every release ships green across an independent, cross-checked test suite, including randomized fuzzing.

Honest scope

What it proves, and what it doesn't.

We state the boundary 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 optimal, the engine reports the gap honestly — 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 a dependency-free C engine that can't touch the network, returns the same answer every time, and carries its own optimality certificate on every response. Integration is one request in, one result out.