A store places every value in the smallest of a set of fixed-size blocks — where does the wasted memory come from?

## Blocks of predetermined sizes Some in-memory stores never ask a general-purpose allocator for exactly as many bytes as a value needs. They carve their memory into blocks of a few predetermined sizes — a set of **fixed-size allocation classes** — and place each value into the smallest block it fits in. That turns placement into a lookup. Pick the class, take a free block from it, write the value, done. There is no search for a hole of the right size, no splitting a large hole into a used part and a remainder, and no coalescing of neighbouring free space afterwards. The time to place a value does not depend on what the memory currently looks like, which matters a great deal for a store whose entire promise is an operation measured in microseconds. ## Where the waste is Every value that does not exactly fill its block leaves the rest of that block unused. Nothing else can be put there: the block belongs to this value until the value is gone. The important property is that **the waste is not a fraction of the value**. It is the distance from the value to the top of the block it landed in. Two values a few bytes apart in size can waste wildly different amounts, because one of them is just under a boundary and the other is just over it. Suppose a store's classes were 64, 128 and 256 bytes. These numbers are invented for the illustration and are not any store's: | payload | block it lands in | wasted inside the block | |---|---|---| | 60 bytes | 64 | 4 bytes | | 66 bytes | 128 | 62 bytes | | 130 bytes | 256 | 126 bytes | Six bytes of extra payload between the first row and the second costs about sixty bytes of memory. Nothing about the payload itself tells you which row you are on; only the boundaries do, and they belong to the store. ## The workload that makes it worst A workload whose values cluster just past a boundary is the bad case, and it is common, because value sizes are rarely random — they are produced by one serializer, one schema, one set of field names, so they cluster. - Where the step between classes is large, a value one byte past a boundary wastes close to what it holds: the payload again, give or take. - Where the step is small, the same workload wastes a modest percentage. - The best case is a workload whose values sit just under a boundary, which wastes almost nothing — and which one added field can destroy for every value at once. How large the step is differs by store. Classes usually grow by a ratio rather than by a constant, so the absolute step gets bigger as values get bigger, and some stores let an operator change that ratio. Making the step smaller means more classes: a tighter fit per value, but more partly-filled blocks spread across more classes. ## It is there from the first write This is a placement cost, not the residue of a long-running process. Load a freshly started store once, delete nothing, and the per-block waste is already present and already measurable. That distinguishes it from memory a running process holds that belongs to no entry — a different subject with a different diagnosis. If memory exceeds your payload arithmetic on a store that has done nothing but accept one bulk load, per-block waste is a sufficient explanation on its own. ## Why a store accepts the waste 1. **Placement is constant-time.** No search, so the worst case equals the typical case. 2. **Reclaim is trivial.** A freed block is immediately reusable by the next value of that class, with nothing to merge. 3. **Behaviour is predictable under load.** An allocator that searches can degrade as memory gets busy; one that indexes into classes does not. 4. **The cost is bounded.** The worst per-value waste is capped by the step between adjacent classes, which you can reason about in advance. ## Where stores differ - Some stores use fixed-size classes; others hand each value to a general-purpose allocator, which rounds requests up to steps of its own — usually much finer ones, so the same effect exists but is far smaller. - The number of classes and the step between them differ between stores, and are sometimes an operator's choice. - A store that keeps a compact and a general representation of structured values is attacking the same footprint problem from a different direction, on a different axis. So "an in-memory store rounds each value up into a block and wastes the rest" is true of some designs in this class and not of others. Say which you mean before you use it in a calculation. ## What to do with this - Compare the **distribution** of your value sizes to the boundaries, not the mean of them; a mean sitting comfortably below a boundary tells you nothing about the tail sitting above it. - Treat "the value grew by a few bytes and the memory jumped" as a boundary crossing until something else is proven. - If you can shape the payload — shorter field names, a tighter encoding, one fewer optional field — remember the goal is not to be small. The goal is to be under the next boundary, and a byte is enough. - Measure rather than compute. Payload arithmetic cannot see a boundary it was never told about.