Placement Ranks, Rescue Hashes, and Why They Differ
Deciding where a new machine goes and deciding who rescues a dead host's machines look like the same problem. They are not, and Pilots answers them with different algorithms on purpose.
Two questions that sound identical:
Where should this new machine go?
Who takes this machine now that its host is gone?
Both are "pick a host for a machine". I implemented the second one first and then tried to use it for the first one, which was a mistake worth writing down, because the difference between them is not about scheduling quality. It is about who is available to ask.
Rescue has nobody to ask, so it computes
When a host dies, the host that knew about its machines is the one that died. There is no authority left, and every survivor is in the same position: same replicated rows, no coordinator, and a need to agree about who does what without talking.
A deterministic hash is the only thing that works. Every survivor computes hash(machine_id) mod live_hosts, takes the slice where the answer is its own index, and the partition is exact. No overlap, no gaps, nobody in charge.
What it does not do is care whether the host it picked is a good choice. The hash may hand a memory-hungry machine to a host that is nearly full. That is the price of agreeing with nobody, and for a rescue it is the right price: a suboptimal placement that happens immediately beats an optimal one that needs a conversation with a host that might also be dead.
A create has the whole fleet available, so it ranks
A create is different in one decisive way: everybody involved is alive.
So it ranks. The host that received the request scores the live fleet from rows it already has locally, which are the live set, each host's capacity, and which builds each host has cached. No network calls, because that state is all in the local replica.
Two hosts ranking two creates differently at the same moment is completely fine. The ranker proposes. The target disposes: it admits the machine against its own free memory or refuses with a 507, and the ranker moves to the next candidate. After three refusals it serves the machine locally and lets its own admission control answer.
That is how placement is safe without reservations or locks. The only authority on whether a host can hold a machine is that host.
Highest headroom, never tightest fit
The ranking rule is the one I would defend hardest, because it is the opposite of what a scheduler paper would tell you.
Bin-packing maximises utilisation. It is also how a fleet ends up with every host at 95 percent and no room anywhere to absorb the next burst, at which point a create fails not because the fleet is full but because it is evenly full. Spreading keeps the next create from failing.
So the winner is the highest headroom after placement, not the tightest fit.
There is one bounded bonus: a host that already holds every build the create needs scores a little higher, because a cached build is the difference between a restore and a download. It can only break a near-tie. It can never move a machine onto a host that cannot comfortably hold it, because the fast path is not worth an admission failure.
Exact ties fall back to the same deterministic owner function the rescue uses, which means the answer does not depend on the order rows happened to arrive in this host's replica. Two hosts with identical state pick the same winner.
Reclaimable memory is capacity
This one changed the shape of what a host will accept, and it came from watching hosts refuse creates while holding gigabytes nobody was using.
A host counts, beside its free memory, the memory held by running machines that are idle enough for the idle monitor to suspend anyway. A create that fits within free plus reclaimable is admitted, and the host suspends the idlest machines until it fits.
The reasoning is that those machines were going to be suspended within the minute regardless. Refusing a create to protect memory that is about to be released is a refusal with no benefit. And suspending is cheap and reversible here: a suspended machine holds no memory and runs no process, and the next request to it holds and wakes.
Suspended machines are not counted, because there is nothing to reclaim. Suspend already killed the Firecracker process, so a suspended machine's memory is not held in the first place.
Admission control was the actual bug
Before all of this, nothing on the create path read free memory at all. Placement double-booking was prevented in theory by hosts being the final authority on their own capacity, and in practice by nothing, because that authority was never consulted.
It is worth being precise about what was wrong. The architecture was right. The sentence "hosts are the final authority on their own capacity" was in the design doc and everyone agreed with it. There was simply no code where a host said no.
Now there is. A host admits or refuses against its own numbers, the refusal is a 507 with a reason, and the ranker treats it as information rather than as an error to retry into.
The general lesson I took from it: an invariant that nothing checks is a sentence in a document. The ones that survive are the ones with a line of code that can refuse.
Where the capacity numbers come from
One last detail, because it has bitten a fleet before. A host with a reserved hugepage pool must count its free memory from HugePages_Free rather than MemAvailable, since the reserved pool is excluded from the latter.
A host that counts the wrong one believes it is full. It advertises no capacity, refuses every create, and refuses every rescue sent its way. That last part is what makes it serious: the failure is invisible during normal operation and shows up exactly when another host has died and the fleet needs this one to take its machines.
Every note, or install the CLI and try the thing this one is about.