Keeping an exact removal order over millions of entries costs work on every access; what do stores buy instead, and what does it cost?

## What exact order would actually cost A policy that removes *the* least recently touched entry, or *the* least frequently accessed one, implies a total order over every resident entry, kept correct at all times. Concretely that means: - **Per-entry structure.** Links or an index position, stored alongside every entry. On a tier whose entries are small, that overhead competes with the entries themselves for the same ceiling. - **Work on every access, including reads.** The order changes when an entry is touched, so a read must repair the order. A read path that mutates shared state is a different thing from a read path that does not. - **A contention point.** Where the server handles requests on more than one thread, one global ordering structure is the hottest shared object in the process, and every request wants to modify it. The price is paid on every access forever, to improve a decision that is made only when memory is tight. That is a bad trade, and most stores decline it. ## What they buy instead At the moment a write needs memory, the store does something bounded and local: 1. Draw a **small sample** of resident entries — cheap, because it needs no maintained ordering, only the ability to reach arbitrary entries. 2. Score each sampled entry on the criterion the configured family names: how long since it was touched, how popular it is, how much lifetime remains. 3. Remove the best candidate in the sample. 4. Optionally **carry good candidates forward**: keep the strongest few in a small pool between rounds, so a later round compares new samples against survivors rather than starting from nothing. That makes successive removals better than independent draws without ever materialising a global order. The sample size is a design choice, and different stores choose differently; a larger sample gives a better victim and spends more time inside the write that provoked it. ## What the approximation costs The removed entry is drawn from a sample, so it is usually close to the worst but is not guaranteed to be the worst — that guarantee is exactly what was not paid for. Two consequences matter: - **Quality**: a genuinely warm entry can be removed while a colder one survives, simply because the colder one was not in the sample. Carrying candidates forward reduces how often this happens; it does not eliminate it. - **Blast radius**: the severity of a near-miss depends entirely on what the entries are. If the entry is a copy of something durable, the cost is one refetch. If the entry is a lease, a deduplication record or a half-built aggregate, the store just destroyed the wrong irreplaceable thing, and no policy quality would have made removal safe — only eligibility or a bigger ceiling would. ## The cost lands on the caller that triggered it Removal happens inside a write that could not otherwise be served, so sampling work is latency the caller experiences. A store under sustained pressure removes repeatedly, which is why a tier sitting hard against its ceiling often shows a latency change, not just a memory number. This is also why sample size is bounded: it is a knob between removal quality and write latency at the worst possible moment. ## Where implementations diverge - Some stores keep an exact order within a narrow scope where it is affordable — for example among entries sharing one fixed-size block class — and no global order at all. - Some sample and carry candidates forward; some sample afresh each time. - Some maintain an approximate age marker of reduced precision rather than a true last-touch time, trading resolution for bytes. - A store that allocates from fixed-size blocks is not asking *which entry in the keyspace is worst* at all; it is asking *which entry in the block size I need is worst*, which is a different and much smaller question. So the defensible framing is: exact order is a cost, not a feature that better stores buy. The interesting question is what the store does instead and whether the resulting near-miss is acceptable for the population held. ## What a strong answer sounds like It names the three costs of exact order, describes sampling as bounded work done at removal time rather than continuous work done at access time, states that the removed entry is a good candidate rather than the true worst, and then splits the consequence by what the entries are — because that split is the whole reason this matters on a store rather than only on a cache.