An LRU thumbnail cache is bounded by entry count while items range from 2 KB to 2 MB — what breaks?

## Why a count bound is a bad proxy A capacity expressed as "5,000 entries" is really a bet that entries are interchangeable in size. When they are — fixed-width records, small tokens — the bet is fine and counting is cheaper than measuring. When they are not, the bound controls the wrong variable. A thumbnail cache is the canonical case. A tiny avatar variant might be 2 KB; a full-width hero rendering of a panorama might be 2 MB. A 5,000-entry cache is therefore anywhere between roughly 10 MB and 10 GB of resident data, and *which* it is depends on the mix of requests arriving right now. That is the dangerous property: the failure correlates with load. A promotion drives traffic toward large renderings, the cache fills with them at exactly the same entry count it has always held, and the process is pushed into memory pressure precisely when it can least afford it. Nothing in the cache's configuration changed; nothing in the metrics that watch entry count moved. ## Budgeting the resource you actually own Make the capacity a byte budget: 1. Store the entry's size on its node when it is admitted. Never recompute it at eviction time — the payload may be expensive to measure and the node must be able to account for itself when it is dropped. 2. Keep a running total of admitted bytes. 3. On admission, add the new entry's size to the total, then evict from the stale end **while** the total exceeds the budget, subtracting each victim's stored size. 4. On overwrite, subtract the old size and add the new one before running the same loop — an overwrite that grows an entry can push the cache over budget just as an insert can. The eviction loop is the part interviewers probe. A single write can now evict twenty entries, so the *worst-case* cost of one write is no longer constant. The bound that survives is **amortized**: every entry is linked exactly once when admitted and unlinked exactly once when evicted, so across any sequence of n writes the total eviction work is O(n) and the per-write average is constant. That is the same shape of argument as growth-doubling in dynamic arrays, and it carries the same caveat — amortized is a statement about a worst-case *sequence*, not a promise about any individual write. If your service has a tail-latency budget that a twenty-eviction write would blow, the amortized bound is not the answer; you would cap evictions per write and let the cache run transiently over budget, or shed the work to a background trim. ## The oversized-entry guard What happens when a single item is larger than the entire budget? The naive loop admits it, then evicts everything else, then evicts the new item itself, then finds the cache empty and still over budget — and either loops forever against the sentinels or leaves the cache empty after having thrown away every useful entry to make room for something it could not keep. This is a real outage shape, not a theoretical one: one pathological upload flushes a warm cache. The guard is admission control at its simplest: if an item's size exceeds the budget (or some fraction of it, commonly a small percentage, so that no single entry can dominate), do not admit it. Serve it and move on. The cache's job is to hold the many small things well, not to make room for the one thing that cannot fit. A second guard is worth stating: keep a *count* bound too. Byte budgeting alone lets a flood of 200-byte entries accumulate millions of nodes, and each node carries a payload-independent cost — two pointers, the key, the stored size, the map's own per-entry structure. A cache bounded only by payload bytes systematically undercounts its true footprint, sometimes by a large factor for tiny entries. Bounding both count and bytes keeps both failure modes closed. ## What to measure afterwards Entry hit rate stops being the interesting number once entries are heterogeneous. A cache that serves 90% of *requests* from memory but misses on the largest ones may be doing far worse for the resource that hurts — origin bandwidth, rendering CPU, tail latency. Measure hit rate weighted by the cost you are trying to avoid, and track the byte-size distribution of both hits and admissions. The pattern to watch for is a small number of large admissions repeatedly evicting a large number of small hot entries: the byte budget is being spent on entries with poor reuse, and the answer is a size-aware admission rule rather than a bigger budget. ## What does not change The structure itself is untouched. The map still maps keys to nodes, the doubly linked list still orders nodes by recency, reads still relink, and the victim is still the node before the tail sentinel. Weighted capacity changes only the *stopping condition* of eviction, from "one entry over" to "still over budget" — which is exactly the argument for why this composition is worth understanding as a pattern rather than memorising as a single canned design.