A store allocating from fixed-size blocks had its small values purged and replaced with much larger ones; far fewer entries now fit in the same total — why?
answer
- free space has a size, not just a total
- the block, not the value, is charged
- released blocks return to their own class
- the waste hides inside the store's total
- re-cut the region, or restart
basics
~20 sFree space belongs to the block size it was cut for. Blocks released by the purged small values can only take values that fit them, so the larger values must come from the classes that serve their size — and the memory freed elsewhere is present, free, and unusable.
solid answer
~60 sUnder fixed-size allocation classes, memory is carved into blocks of predetermined sizes, and a value goes into the smallest block that fits, with the remainder of that block wasted. Free blocks do not float; they return to the class they were cut for. When the workload's value sizes shift, the free blocks left by the old sizes cannot serve the new ones — that is **class trapping**, and it is why capacity appears to vanish without anything being deleted or leaked. Two things make it hard to spot. First, the store counts a whole block as used when it hands one out, so this waste sits **inside** its own reported total rather than in the gap between its total and the process's resident size; the ratio a general-purpose store would expose it with looks healthy here. Second, it is not a defect and nothing reclaims it on its own. It resolves when the sizes shift back, when the store can re-cut a region for another class if it supports that, or on a restart.
go deeper
The takeaway is that free memory has a shape. Where a store hands out blocks of fixed sizes, space freed by small values cannot simply be handed to a large one, so free bytes and usable bytes are different totals.
Explain the routing: the smallest block that fits is charged in full, released blocks go back to their own class, and a shift in value sizes leaves a class holding free blocks nobody wants while another class starves.
Recognise it from evidence other than the usual ratio — the reported total unchanged while fewer entries fit, payloads far below the total, and a coincidence with a size change rather than a volume change — and know that only re-cutting or a restart rebalances it.
Treat it as an argument about what belongs in one keyspace. Values differing by an order of magnitude in size share a tier badly, and the allocation strategy underneath is a property to design for rather than a setting to discover during an incident.
## Two ways to carve memory Stores in this class do not all allocate the same way, and the difference decides the whole shape of this failure. | | General allocator | Fixed-size allocation classes | |---|---|---| | How a value is placed | A block of roughly the requested size is carved out | The smallest predetermined block that fits is handed over | | Waste per value | Rounding up to the allocator's next step | The remainder of the block, which can be large | | Where free space goes | Back to general free lists, usable by many sizes | Back to the class it was cut for, usable by that size only | | Where the waste is counted | Mostly outside the store's own total, in the gap | Inside the store's own total — it counts whole blocks | Neither is wrong. Fixed-size classes buy predictability and a very cheap allocation path; a general allocator buys flexibility across sizes. The cost of the first arrives exactly when the workload's sizes change. ## The mechanism Memory is divided into regions, each region cut into blocks of one size, with a ladder of sizes covering the range of values the store expects. A write is routed to the class whose block size is the smallest that will hold it. 1. While the workload's sizes are stable, this is efficient: each class stays roughly as full as its share of the traffic. 2. When the small values are purged, their blocks are released **to their own class**. That class now has a large pool of free blocks and no demand. 3. The new, larger values are routed to a different class, which has no free blocks and must get memory from somewhere. 4. If no unused region is left to cut for that class, writes of the new size cannot be satisfied even though a large share of the store's bytes is free. That is class trapping: memory that is free inside a class that the current workload's sizes can no longer use. ## Why the usual diagnostic misses it The standard tell for wasted memory is the gap between what the store attributes to its entries and what the operating system says the process occupies. Class trapping does not show up there. The store counted the blocks as used when it handed them out, and it keeps counting the whole region it owns, so its own total stays high and the ratio against resident size stays narrow. Every number you would normally read says the store is holding what it says it is holding. The evidence is elsewhere: - **Entries fit that did not fit before, or stop fitting** for no change in the reported total. - **The payloads do not account for the total.** The entry count multiplied by the current average value size comes out far below what the store says it is holding. - **The change coincides with a size shift**, not with a change in volume — a migration that rewrote every value, a field that grew, a serialisation format that was swapped. ## What resolves it - **The workload shifting back.** If the small sizes return, their class has plenty of room and nothing needed doing. - **Re-cutting a region for another class.** Some stores can take a region whose class is idle and reassign it to a class that needs blocks; others cannot, and where they cannot the trapped space stays trapped for the life of the process. - **A restart.** A fresh process cuts its regions against the traffic it sees now, so the ladder matches the current sizes from the first write. It is the blunt remedy, and it costs whatever the tier held with no other copy. - **Not mixing sizes in one keyspace.** The design-level answer: values whose sizes differ by an order of magnitude and whose lifecycles differ are a poor fit for one store, and separating them removes the mechanism rather than managing it. ## The same workload on a general allocator Run the identical purge-and-refill against a store using a general allocator and you get a different picture, not a clean one. The freed small blocks go back to general free lists; some of them are too small or too scattered to satisfy the larger requests, so the process asks the operating system for more memory, and the freed space shows up as a **widened gap** between the store's total and resident size rather than as capacity that mysteriously vanished inside it. Same cause — a shift in value sizes against memory laid out for the old ones — with the evidence in the opposite place. That contrast is worth stating explicitly in an interview, because asserting either signature as "what in-memory stores do" is wrong about half of them.
- Why does the data-size-to-resident-size ratio stay healthy while this is happening?Because the store charged itself for the whole block when it handed one out, and it keeps charging itself for the regions it owns. The waste was already counted inside its own total, so nothing moves into the gap against resident size. The ratio that would expose the same waste under a general allocator is simply looking in the wrong place here.
- Does this ever fix itself?Only if the workload's sizes shift back, or the store can reassign an idle region to a class that needs blocks. Not every store in this class can do the second, and where it cannot, the trapped space persists for the life of the process. Nothing about time alone resolves it, which is what distinguishes it from a transient gap after a purge.
- How would the same purge-and-refill look on a store using a general allocator?The freed blocks go back to general free lists, but many are too small or too scattered for the new, larger values, so the process requests more memory from the operating system. The waste then appears as a widened gap between the store's entry total and resident size, rather than as capacity vanishing inside the store's own total.
A car park striped for compact cars. Emptying half the compact bays does nothing for the vans queuing at the gate, and the attendant's board still reads full — because the space is there, it is just the wrong shape and it was counted as occupied the moment it was striped.
saying these in an interview costs you the question
- Assumes free space in one size class can serve a larger value.
- Looks only at the gap against resident size to find wasted memory.
- Calls trapped capacity a leak in the store.
- Asserts fixed-size blocks as how in-memory stores allocate.
- Expects the trapped space to be reclaimed automatically over time.