Scheduling sandbox bursts: why 50 creates land on one host

I'm Ajay; I build PandaStack, a Firecracker microVM platform, and this is a post about a bug I shipped, watched happen in production, and then fixed. It is one of the most boringly reproducible failures in distributed systems, and it wears a disguise: the scheduler was not broken. It was working perfectly. That is precisely why it emptied a burst of fifty sandbox creates onto a single host while eleven other hosts sat there with free memory.

The shape is general. If you have ever written a load balancer that picks the least-loaded backend, a connection pool that picks the least-busy connection, or a Kubernetes-style scheduler that scores nodes by free resources, you already own this bug. It just has not been triggered yet, because nothing has arrived fast enough.

The scorer that looks obviously correct

Here is roughly the placement function we ran. Every host agent heartbeats into Postgres every ten seconds with its capacity: total and used vCPU, total and used memory, whether it can do streaming (UFFD) snapshot restore. The scheduler reads that table, scores each host, and picks the maximum. There is a cache in front of the query because otherwise every create pays a database round trip.

// scheduler.go -- the version that is correct exactly once per interval.

type Agent struct {
	ID            string
	CPUTotal      float64
	CPUUsed       float64
	MemMBTotal    int64
	MemMBUsed     int64
	StreamRestore bool      // can page vm.mem from object storage on demand
	HeartbeatAt   time.Time
}

// The whole policy, and it fits on a napkin. Free capacity, weighted.
// Every create takes the same snapshot-restore path on any host that has
// the seed, so there is nothing to optimize for except spreading load.
func score(a Agent) float64 {
	freeCPU := a.CPUTotal - a.CPUUsed
	freeMemGB := float64(a.MemMBTotal-a.MemMBUsed) / 1024
	s := 0.6*freeCPU + 0.3*freeMemGB
	if a.StreamRestore {
		s += 5.0 // boots without downloading the whole memory file first
	}
	return s
}

func (s *Scheduler) Pick(ctx context.Context) (string, error) {
	// 30s cache over a table written every 10s. Two staleness sources,
	// stacked, and neither one is a bug on its own.
	agents, err := s.cache.Agents(ctx)
	if err != nil {
		return "", err
	}

	now := time.Now()
	best, bestScore := "", math.Inf(-1)
	for _, a := range agents {
		if now.Sub(a.HeartbeatAt) > 30*time.Second {
			continue // stale heartbeat: treat as dead, not as idle
		}
		if sc := score(a); sc > bestScore {
			best, bestScore = a.ID, sc
		}
	}
	if best == "" {
		return "", ErrNoCapacity
	}
	return best, nil
}

Read that function with one request in mind and it is unimprovable. Read it with fifty simultaneous requests in mind and it is a funnel. `Pick` is a pure function of `s.cache.Agents(ctx)`. Fifty callers inside the same cache window get the same slice, run the same arithmetic, and get the same string back. Not "usually the same". The same, deterministically, every time, until the cache expires.

Determinism is normally a virtue. Here it is the weapon.

We want schedulers to be deterministic. Deterministic placement is testable, explainable, and reproducible in an incident review — you can replay the inputs and get the decision back. Nobody wants to debug a scheduler that shrugs.

But determinism converts a bias into a sweep. If the scorer were noisy, the least-loaded host might win fifteen of the fifty creates, the runner-up twelve, and so on — lumpy, imperfect, survivable. With a deterministic function over a frozen input set, the winner takes all fifty. The distribution collapses from skewed to degenerate. Same policy, same intent; the difference between a hot host and a dead one is entirely down to whether the function had any entropy in it.

A deterministic scheduler over a stale view does not make one bad decision. It makes the same bad decision as many times as you ask it to.

The feedback loop is longer than the burst

The second half of the bug is timing. A placement does not affect the score until the host notices the new VM, includes it in a heartbeat, that heartbeat lands in Postgres, and the scheduler's cache expires and re-reads. With a 10s heartbeat and a 30s cache, the worst case is about forty seconds from "we placed a VM" to "the scheduler can see we placed a VM."

This is a control system with dead time. Anyone who has held a shower tap knows the failure mode: you keep turning the knob because nothing has changed yet, and then everything changes at once. Our scheduler turned the knob fifty times in two hundred milliseconds. The correction arrived long after the damage, as a heartbeat reporting with impeccable accuracy that the host we had just buried was now the most loaded machine in the fleet — at which point it fell to the bottom of the ranking and got nothing for the next forty seconds, which is its own kind of wrong.

The counterintuitive part: fast creates make this worse

You would think a platform that provisions quickly would suffer less from placement staleness. The opposite is true, and it took me an embarrassingly long time to see why.

On PandaStack there is no warm pool of idle VMs — every create restores a baked Firecracker snapshot, at roughly 179ms p50 and 203ms p99. So a fifty-VM burst is not a queue that drains over minutes while feedback trickles in. It is fifty machines already running before the first corrective heartbeat is even sent. The burst completes inside the feedback delay, which means there is no moment during the incident at which the scheduler could have known better: the entire incident happened between two observations.

A platform where provisioning takes ninety seconds accidentally has a working feedback loop: by the time create ten begins, creates one through five have long since shown up in the metrics. Slowness is a rate limiter, and rate limiters hide this bug. If you recently made your control plane much faster and started seeing lopsided placement, this is very likely why.

Reproducing it takes about fifteen lines. The trick is that the requests must overlap, not merely follow each other quickly.

# burst.py -- fire 50 creates concurrently and see where they landed.
# Sequential creates will NOT reproduce this. The requests have to be
# in flight at the same time, inside one cache window.
import collections
from concurrent.futures import ThreadPoolExecutor

from pandastack import Sandbox

N = 50


def one(i: int) -> Sandbox:
    return Sandbox.create(
        template="code-interpreter",
        ttl_seconds=300,
        metadata={"burst": "placement-test", "i": str(i)},
    )


with ThreadPoolExecutor(max_workers=N) as pool:
    boxes = list(pool.map(one, range(N)))

# Ask each guest which machine it woke up on. If your platform exposes
# the placement in the API, read it there instead of shelling out.
hosts = collections.Counter()
for sbx in boxes:
    r = sbx.exec("cat /etc/pandastack/host-id 2>/dev/null || hostname")
    hosts[r.stdout.strip()] += 1

for host, n in hosts.most_common():
    print(f"{host:<24} {n:>3}  {'#' * n}")

# A healthy fleet of 12 gives you a ragged 3-6 per host.
# The bug gives you one bar of length 50 and eleven empty lines.

for sbx in boxes:
    sbx.kill()

Fix 1: in-flight reservations (the one that actually works)

The insight is small: the scheduler already knows about the placements it made. It does not need a heartbeat to tell it. It needs to *believe itself* between observations.

So the scheduler keeps a local ledger of placements it has committed but not yet seen confirmed, and subtracts that ledger from the observed capacity before scoring. This is optimistic local accounting, in the same family as an optimistic UI update: assume your own write succeeded, render accordingly, reconcile when the truth arrives.

The part people get wrong is expiry. A reservation is a claim about the future, and futures fail. If a create errors, or the host rejects it, or the process panics between reserving and releasing, that claim must not live forever — otherwise the scheduler slowly convinces itself the fleet is full and returns capacity errors on an empty cluster. That is a worse outage than the one you set out to fix, and it is silent.

// inflight.go -- placements this process has committed but has not yet
// seen reflected in a heartbeat. Optimistic, local, and self-expiring.

type reservation struct {
	cpu       float64
	memMB     int64
	expiresAt time.Time
}

type inflight struct {
	mu      sync.Mutex
	byAgent map[string][]reservation
	ttl     time.Duration // MUST exceed heartbeat + cache TTL, with margin
}

// reserve records a claim and returns a release func. Call release on
// BOTH paths -- success and failure -- and let the TTL catch the cases
// where the process died before it could.
func (i *inflight) reserve(agentID string, cpu float64, memMB int64) func() {
	i.mu.Lock()
	defer i.mu.Unlock()

	r := reservation{cpu: cpu, memMB: memMB, expiresAt: time.Now().Add(i.ttl)}
	i.byAgent[agentID] = append(i.byAgent[agentID], r)

	var once sync.Once
	return func() {
		once.Do(func() {
			i.mu.Lock()
			defer i.mu.Unlock()
			for n, held := range i.byAgent[agentID] {
				if held == r {
					list := i.byAgent[agentID]
					i.byAgent[agentID] = append(list[:n], list[n+1:]...)
					return
				}
			}
		})
	}
}

// pending sweeps expired claims, then reports what is still outstanding.
// The sweep is the leak prevention: without it, one dropped release
// permanently shrinks a host in this scheduler's eyes.
func (i *inflight) pending(agentID string) (float64, int64) {
	i.mu.Lock()
	defer i.mu.Unlock()

	now := time.Now()
	kept := i.byAgent[agentID][:0]
	var cpu float64
	var memMB int64
	for _, r := range i.byAgent[agentID] {
		if now.After(r.expiresAt) {
			continue // heartbeat has had ample time to tell the truth
		}
		kept = append(kept, r)
		cpu += r.cpu
		memMB += r.memMB
	}
	i.byAgent[agentID] = kept
	return cpu, memMB
}

// Pick, now scoring the world as this process believes it to be.
func (s *Scheduler) Pick(ctx context.Context, req Request) (string, func(), error) {
	agents, err := s.cache.Agents(ctx)
	if err != nil {
		return "", nil, err
	}

	now := time.Now()
	best, bestScore := "", math.Inf(-1)
	for _, a := range agents {
		if now.Sub(a.HeartbeatAt) > 30*time.Second {
			continue
		}
		// Double-counting is fine and self-correcting: once the heartbeat
		// reflects the VM, the reservation expires and stops subtracting.
		// Briefly pessimistic beats durably wrong.
		pc, pm := s.inflight.pending(a.ID)
		a.CPUUsed += pc
		a.MemMBUsed += pm
		if a.MemMBTotal-a.MemMBUsed < req.MemMB {
			continue // would not fit even optimistically
		}
		if sc := score(a); sc > bestScore {
			best, bestScore = a.ID, sc
		}
	}
	if best == "" {
		return "", nil, ErrNoCapacity
	}
	return best, s.inflight.reserve(best, req.CPU, req.MemMB), nil
}

Now the fifty creates interleave properly. Create one reserves 2 GiB on host A and drops A's score. Create two, a millisecond later, reads the same cached heartbeat but a different ledger, and picks B. By create twelve the fleet has been walked in score order, which is exactly the behaviour the original function was trying to express. Under a hundred lines, and it is the change that removed the pile-up for us.

Fix 2: power-of-K choices

The other angle is to break the herd statistically rather than by bookkeeping. Instead of scoring every host and taking the global maximum, sample K hosts uniformly at random and take the best of those. K is usually two.

This is the "power of two random choices" result from the balls-and-bins literature, and the magnitude surprises people. Throw n balls into n bins uniformly at random and the fullest bin holds about log n / log log n balls. Sample two bins per ball and take the emptier one, and the fullest holds about log log n / log 2 — an exponential improvement, from a change so small it barely counts as an algorithm. Going from two choices to three helps again, but only by a constant factor. Two is where the cliff is.

// pickPowerOfK -- stateless herd-breaking. No ledger, no shared state,
// no coordination between scheduler replicas. Just entropy in the input.
func pickPowerOfK(agents []Agent, k int, req Request) (string, error) {
	fit := agents[:0:0]
	now := time.Now()
	for _, a := range agents {
		if now.Sub(a.HeartbeatAt) > 30*time.Second {
			continue
		}
		if a.MemMBTotal-a.MemMBUsed < req.MemMB {
			continue
		}
		fit = append(fit, a)
	}
	if len(fit) == 0 {
		return "", ErrNoCapacity
	}
	if k > len(fit) {
		k = len(fit)
	}

	// Partial Fisher-Yates: shuffle only the k slots we are going to read.
	for n := 0; n < k; n++ {
		j := n + rand.Intn(len(fit)-n)
		fit[n], fit[j] = fit[j], fit[n]
	}

	best, bestScore := "", math.Inf(-1)
	for _, a := range fit[:k] {
		if sc := score(a); sc > bestScore {
			best, bestScore = a.ID, sc
		}
	}
	return best, nil
}

Two properties matter beyond the maths. It holds no state, so it costs nothing to operate and cannot leak. And it is indifferent to how many scheduler replicas you run — four processes sampling independently behave like one process sampling four times as often. Its weakness is that it is probabilistic: it makes the pile-up unlikely rather than impossible, and on a small fleet it will sometimes miss the genuinely best host because it never looked at it.

Fix 3: jitter and randomised tiebreaks

The cheapest option is to add noise: shuffle the candidate list before scanning so equal scores resolve randomly, or perturb each score by a small random factor before comparing. One line, no state, no risk.

It is also the weakest, and it is worth being honest about why. A randomised tiebreak only helps when scores actually tie, and in a real fleet they rarely do: free memory differs by a few hundred megabytes between hosts, so there is a strict ordering, a single winner, and a tiebreak that never fires. Multiplicative jitter can at least flip near-ties, but sizing it is a trap — small enough to preserve the policy is too small to break a real gap, and large enough to break a real gap means you have replaced your policy with a lottery. Ship it alongside a real fix, never as one.

Fix 4: per-node admission control

Every fix above lives in the scheduler, and the scheduler is exactly the component you cannot trust during an incident. So the last one lives on the host: a semaphore bounding concurrent VM starts, and a fast rejection when it is full.

This is not a placement policy — it spreads nothing. It is a circuit breaker. If forty simultaneous snapshot restores would thrash a host's page cache and turn a 179ms create into a five-second one for everybody, the host should accept eight, refuse the rest with a clear retryable error, and let the scheduler try elsewhere. It protects against every cause of a herd, including the ones you have not diagnosed: a buggy client, a retry storm, a scheduler you did not write.

// On the host agent, not the scheduler. The last line of defence, and
// the only one that still works when the scheduler is the problem.
type starts struct {
	sem chan struct{}
}

func newStarts(limit int) *starts {
	return &starts{sem: make(chan struct{}, limit)}
}

func (s *starts) acquire(ctx context.Context) error {
	select {
	case s.sem <- struct{}{}:
		return nil
	case <-time.After(150 * time.Millisecond):
		// Fail fast and retryable. Queueing here just moves the pile-up
		// from the host's CPU to the caller's timeout budget, and the
		// caller cannot tell the difference between slow and stuck.
		return ErrStartsSaturated
	case <-ctx.Done():
		return ctx.Err()
	}
}

func (s *starts) release() { <-s.sem }

One caveat: the rejection must be distinguishable from a real capacity error, and the scheduler must treat it as "try another host" rather than "this host is dead." Otherwise a brief saturation spike evicts a healthy host from the fleet's view for the next thirty seconds, and you have built a slower, more confusing version of the original bug.

The four fixes, honestly compared

These are complements, not alternatives. We run reservations plus admission control; power-of-K is on the list. Here is how they actually differ.

• Effectiveness against a burst — In-flight reservations: complete within one process; each placement immediately changes the next decision. Power-of-K: statistical, turns a guaranteed pile-up into an unlikely one; max load grows like log log n rather than log n. Jitter: near zero unless scores genuinely tie, which in a real fleet they rarely do. Admission control: does not spread load at all, but hard-caps what any one host will absorb.
• Implementation cost — In-flight reservations: a mutex-guarded map, an expiry sweep, and a release on every exit path including the error ones. Power-of-K: about fifteen lines and a partial shuffle. Jitter: one line. Admission control: a buffered channel on the host, plus a retryable error code the scheduler understands.
• Failure mode when it goes wrong — In-flight reservations: leaked claims shrink the fleet silently until it reports no capacity on an idle cluster. Power-of-K: occasionally skips the genuinely best host; harmless, invisible. Jitter: too much noise and your policy quietly stops being your policy. Admission control: rejections misread as host death evict healthy hosts from the ranking.
• Survives multiple scheduler replicas — In-flight reservations: no, not without shared state; the ledger is per-process, so N replicas give you back a 1/N-sized pile-up. Power-of-K: yes, entirely; replica count does not enter the maths. Jitter: yes, but it was not doing much to begin with. Admission control: yes, and it is the only one enforced at the resource itself rather than upstream of it.

The gotcha: reservations are per-process

This is the part that gets skipped in most write-ups, and it is the part that will bite you in production, because you almost certainly do not run one API replica.

The in-flight ledger lives in one process's memory. Replica A reserves 2 GiB on host seven; replica B has no idea and cheerfully reserves the same capacity. With two replicas behind a load balancer, a fifty-create burst splits roughly twenty-five each, and each replica spreads its own twenty-five beautifully — across the same ordering, starting from the same host. You get the pile-up back at half amplitude. It looks like the fix partially worked, which is the most expensive kind of result, because it does not force you to keep looking.

There are three honest ways out, and the cheapest one is not the shared-state one.

1. Move the ledger into shared state — a reservations table with expiry, or a Redis key per placement with a TTL. Correct, but every placement decision now carries a network round trip and a new dependency that fails during precisely the traffic spike that made you want it. Make it fail open: a scheduler that cannot reach the store should degrade to power-of-K, not stop scheduling.
2. Lean on the replica-count-independent fixes — power-of-K in the scheduler, a starts semaphore on the host. Neither cares how many schedulers exist, both are stateless, and together they bound the damage without a shared store. This is where I would start.
3. Shard the decision — route creates so a given workspace or template consistently reaches one replica, which makes per-process reservations correct again for that slice. The cost is an affinity requirement in your load balancer and a new question about replica restarts.

Whichever you pick, write the replica count into the test. A placement fix validated against a single process is a placement fix validated against a fleet you do not run.

Stale-host exclusion, and why a cached absence is not a death

The scorer drops hosts whose heartbeat is older than about thirty seconds. This is necessary: a host that has stopped reporting looks, to a free-capacity scorer, like a host with a lot of free capacity, because its last-known usage stopped rising. Without the exclusion, a crashed machine becomes the most attractive destination in the fleet. Least-loaded scoring is drawn to dead things like a moth to a very quiet lamp.

The trap is on the other side. We hit this: the scheduler's cache did not distinguish "this host reported unhealthy" from "this host was not in the result set when I last looked." A cached absence became a cached death, and around one in eight placement attempts returned a capacity error against hosts that were perfectly healthy and heartbeating normally. A cache is a record of what you saw. It is not evidence about what you did not see. Negative conclusions need a fresh read, not a remembered silence.

Two rules have held up for us. Cache positive facts freely and negative facts never — if the cached view has no healthy candidate, re-read the source before returning an error to a customer. And separate the timeouts: the interval at which you stop trusting a heartbeat should be shorter than the one at which you declare a host dead and start evacuating it, because the first is a scheduling hint and the second is irreversible.

What to put on the dashboard

A fleet-wide average hides this bug completely. Mean CPU across twelve hosts looks calm while one of them is on fire; that is arithmetic, not observability.

• Max-to-median host load ratio — the single number that catches a pile-up. Healthy fleets sit near 1.2 to 1.5. A sustained 4 means one host is doing a job that twelve should be sharing.
• Placements per host in a rolling 60-second window — a histogram, not an average. A burst shows up as one tall bar and a row of empty ones, and it is instantly legible even to someone who has never seen your scheduler.
• Outstanding reserved capacity per host — should oscillate and return to zero. A monotonic climb is a leaked reservation, and it will end as a phantom capacity error on an empty cluster.
• Admission rejections per host — near-zero in steady state. A spike is either a real herd or a semaphore sized too small, and both are worth a page.
• Age of the oldest heartbeat used in a placement decision — surfaces cache staleness directly, so you learn how old your worldview was when you committed to it.
• Create latency p99 by host, not fleet-wide — a host absorbing a herd degrades long before it fails, and the fleet-wide p99 hides that until it is far too late.

The general lesson

Network placement was never our binding constraint — each agent pre-allocates 16,384 /30 subnets, so slots are effectively free. Memory and CPU are the real limits, and those are exactly the quantities the scorer was reading out of date. It is a tidy summary of the whole class of bug: the thing you carefully provisioned plenty of was not the thing that ran out.

If you take one idea away, make it this. Any component that chooses by reading a shared observation and applying a deterministic function will, under concurrency, make every caller choose the same thing — whether it is a scheduler, a load balancer, a cache-fill path, or a client library picking the fastest region. The cure always takes one of three shapes: let each decider account for its own outstanding decisions, put entropy in the input so callers stop agreeing, or bound the damage at the resource itself. The bug is not in the scoring function. The bug is that the scoring function is a pure function of something that has not been true for thirty seconds.