Memory grants and reservations

Why is a reservation not usage?

What goes wrong without grants

A memory grant is a promise: "this operator may use up to X bytes, and nobody else will take them." Suppose there are no grants. Each of c queries allocates memory whenever it wants. The system fails when the sum of all footprints Σ Fᵢ becomes larger than the memory M at any instant. Three properties of this failure make it unacceptable. Each one alone is enough reason to build a better mechanism.

1. It strikes the wrong party. The victim is whoever allocates last, not whoever holds the most. A trivial lookup dies because a hash join filled the pool. (This is Dmitri's first puzzle.)
2. It strikes at the worst moment. The failure lands at an arbitrary point in the run. That point is, by construction, the point of maximum accumulated work.
3. It is not reproducible. The outcome depends on how the queries interleave, so you cannot debug it. You can only survive it.

So the claim moves before the work. The operator states a requirement. The memory manager either grants it or queues the query. Now failure happens at admission, where it costs nothing and where it is exactly attributable to the query that asked for too much.

The grant is a point on a curve, not a yes/no

Every spillable operator (one that can write data to disk when memory is short; Degradation explains how) has three things: a minimum below which it cannot run at all, a point above which more memory buys nothing, and a curve in between. The external merge sort shows the shape of that curve clearly.

Reminder of the algorithm. An external merge sort sorts data that is bigger than memory. Step 1: read memory-sized chunks, sort each chunk in memory and write it to disk as a sorted run. Step 2: merge many runs at once into one sorted output, reading a small buffer (size B) from each run. With N bytes of data and M bytes of memory, you produce N/M runs and need

(a pass reads and writes all the data once; ⌈x⌉ means "round up"). Memory M appears as the base of a logarithm. So the curve of cost against memory is not a slope. It is a staircase with one huge first step:

• M ≥ N: no spill at all.
• M just large enough for a single merge pass: about 2× the I/O of the no-spill case.
• Below that: 2 passes, 3 passes, and so on. In each region, doubling memory typically does not change the number of passes.

Going from 128 MB to 512 MB (4× more memory) saves nothing. Going from 64 MB to 128 MB (2× more) removes a whole pass over 1 TB of data.

Therefore grants should be quantized to pass boundaries. Granting 1.5× the memory needed for a one-pass merge is pure waste. Granting 0.9× of it costs an entire extra pass over the data. A memory manager that hands out bytes on a smooth continuum is optimizing a variable that the operator consumes in steps.

Reservation is not usage, and the gap is the whole inefficiency

A grant is a promise of exclusivity. The bytes may sit untouched for the whole life of the query. The classic symptom is the RESOURCE_SEMAPHORE wait in SQL Server: queries queue for memory on a server whose memory is mostly idle, because the grants were sized from estimates that were about ten times too high. (That is Dmitri's second puzzle: the stricter cluster. The cause is entirely upstream, in Where the grant number comes from: the most important item in this article.)

The reservation is against the peak

The reservation covers the operator's peak, and it is held for the operator's whole life, even though the peak occurs only during a build or sort phase. So every mechanism from Ownership that raises the peak turns directly into lost concurrency: an arena that keeps its high-water mark until it is reset, a columnar buffer pinned by a slow consumer, a dictionary that never shrinks. In Ownership these looked like small local waste. Here they set the concurrency limit of the whole system.

Asymmetric preemption: the frame confirmed

Spark's unified memory manager lets execution memory (working memory for joins, sorts, aggregations) evict storage memory (cached data blocks), but never the reverse. This is the preemption-cost argument in action. Cached blocks are recomputable: preempting them costs a recompute. Execution state is not: preempting it costs the query. The system is allowed to preempt only the side that is cheap to preempt.

The numbers in Spark 2.4: spark.memory.fraction = 0.6 of the usable heap is shared between execution and storage. spark.memory.storageFraction = 0.5 of that is the portion that storage may hold safely, immune from eviction. Within the execution pool, each of N active tasks is entitled to between 1/2N and 1/N of the pool.

Look carefully at that last rule. It is a fixed fair share, not a negotiation. It is the cheapest possible arbitration. Its price appears in Memory pressure signalling and operator cooperation.

One-line compression: a grant moves failure from an arbitrary point in execution, where it destroys the most work, to admission, where it costs nothing, and it pays for the move in memory that is reserved and never touched.