Admission control by memory footprint
Why must memory admission count bytes, and what does over-commit bet on?
Why memory admission is unlike every other admission gate
Most admission gates can be approximated by a count: at most 50 concurrent queries, at most 200 connections. That works because the demand per unit is at least bounded. Memory footprints in one workload span eight orders of magnitude. A point lookup wants kilobytes. A hash join over a fact table (the huge central table of a data warehouse) wants hundreds of gigabytes. A concurrency limit controls memory only if you set it for the worst case, and that leaves the machine idle in the common case.
Counting bytes makes it bin packing
Bin packing is the problem of fitting items of different sizes into containers. Here the items are queries (sized by their grants) and the container is the memory pool. It has three consequences.
It is NP-hard, and online it is worse. (NP-hard means no known algorithm solves every case quickly. Online means you must decide as items arrive, without seeing the future.) So every real implementation is greedy plus a queue: admit what fits now, queue the rest. The queue is where the interesting behaviour lives.
Fragmentation returns, one level up. Three nodes with 40 GB free each cannot admit a query that needs 100 GB on one node. The total free memory is 120 GB, but it is in unusable pieces. This is external fragmentation (free space split into pieces too small to use), the same problem as in a heap allocator in Ownership, with a block size of one machine instead of one allocation. Note that fragmentation is scale-invariant: the same mechanism produced unusable bytes in a heap, unusable frames in a buffer pool, and now unusable nodes in a cluster. The cure rhymes each time: either make the units uniform, or add an indirection that lets a request span several units.
Queue order interacts with footprint
| Order | Effect |
|---|---|
| Smallest first | maximizes throughput, but the large query can wait forever (starvation) |
| First in, first out (FIFO) | the large query at the head blocks everything behind it (head-of-line blocking) |
General job scheduling is a big topic of its own and we leave it. What belongs here is that footprint is the variable that makes the problem two-sided (small jobs and giant jobs) in the first place. Also, a memory admission queue without backfill wastes memory. Backfill means: while the large query at the head waits for enough free memory, let smaller queries behind it use the memory that is free now. Without it, memory that the head query cannot use sits idle.
Over-commit is an explicit bet on independence
To over-commit is to admit queries on the assumption that not everyone peaks at the same moment. This is thin provisioning (promising more storage than you have). It is airline overbooking. It is "independence assumed, but false" wearing a business model. The payoff is better utilization on ordinary days.
The cost has the shape of any correlated failure: the bet loses rarely and totally. Whatever makes several queries peak together (a scheduled batch window, a retry storm, a jump in the size of a common upstream dataset) makes all of them peak at once. And the one who pays is the query that arrives last, which is never the query that caused the problem.
One-line compression: memory is the one resource whose admission gate must count bytes rather than admissions, which makes it bin packing, and bin packing at cluster scale is external fragmentation with a very large block size.