A cache with limited memory must decide which entries to evict when it's full. Compare LRU (Least Recently Used), LFU (Least Frequently Used), and TTL (Time To Live) eviction policies — how does each decide what to remove, and when would you pick one over another?

## Why the eviction policy matters Every cache has finite memory, so once it fills up, adding a new entry means something existing has to be removed. The **eviction policy** is the rule that decides what to remove, and the choice matters enormously for **hit rate** — the fraction of requests the cache can satisfy without falling through to the slower origin. A poorly chosen policy can leave a cache **thrashing** (constantly evicting and refetching data that's about to be needed again), which erases most of the benefit of caching in the first place. ## Least Recently Used **Least Recently Used (LRU)** evicts whichever entry has gone the longest without being accessed. - **Mechanically, it's usually implemented with a doubly linked list plus a hash map**: every cache read or write moves that entry to the 'most recently used' end of the list, and when the cache is full, the entry at the 'least recently used' end is evicted — both operations are `O(1)`. - **LRU rests on the assumption of temporal locality**: data accessed recently is likely to be accessed again soon, which holds for a huge range of real workloads (a user re-loading their own profile, a web session revisiting the same few pages). - **LRU's well-known weakness** is that a single large sequential scan — for example, a batch job iterating over every row in a table, or a bot crawling every product page once — pushes every genuinely 'hot' entry out of the cache to make room for a flood of one-time-use entries, tanking the hit rate for real traffic right after the scan. - **Variants like LRU-K or 'segmented LRU'** (used in some database buffer pools) mitigate this by requiring an item to be accessed more than once before it's promoted to the protected, hard-to-evict segment. ## Least Frequently Used **Least Frequently Used (LFU)** evicts the entry with the lowest total access count, on the theory that popularity over time is a better predictor of future demand than mere recency. - **This directly fixes the LRU scan problem**: a one-time scan touches each item exactly once, so those items have the lowest possible frequency count and are evicted first, leaving the genuinely popular items untouched. - **The cost is bookkeeping** — LFU needs a counter per entry and (for `O(1)` eviction) a more complex data structure than a simple linked list, such as a frequency-bucketed structure. - **LFU has its own failure mode**: an item that was extremely popular last week but is irrelevant today can retain a high count and squat in the cache, starving newly-popular items — this is sometimes called 'cache pollution' by stale popularity. - **Production LFU implementations** (e.g., Redis's approximated LFU) address this with count decay — periodically halving or aging counters so old popularity fades. ## Time To Live **Time To Live (TTL)** is a different axis entirely: rather than reasoning about usage patterns, it attaches an expiration timestamp to each entry and removes it once that time has elapsed, independent of how often or recently it was accessed. TTL exists to bound staleness, not to manage memory pressure efficiently — an entry can be extremely 'hot' by LRU/LFU standards and still get evicted purely because its TTL expired. This is essential whenever correctness requires a maximum staleness window: a cached currency exchange rate, a feature flag, or a product price might be allowed to be at most 30 seconds old, no matter how popular it is. Pure TTL-based eviction, with no memory-pressure-aware policy at all, risks running out of memory if too many entries are alive simultaneously (unless combined with a max-size limit and a fallback policy). ## Combining the axes in practice In practice, these axes aren't mutually exclusive — most production caches combine them. `Redis`, for example, lets every key carry an optional TTL, and separately configures a memory-pressure eviction policy (`allkeys-lru`, `allkeys-lfu`, `volatile-ttl`, etc.) that decides what to remove once `maxmemory` is reached; a common pattern is to set business-driven TTLs for staleness correctness and let LFU (or LRU) govern which entries survive early eviction under memory pressure. Database buffer pools typically use LRU-family algorithms (MySQL's `InnoDB` uses a modified LRU with a 'young'/'old' sublist split specifically to resist the full-table-scan pollution problem) because query access patterns are strongly recency-biased at the page level. ## The choice, concretely The choice, concretely: 1. **Pick LRU** as a solid, cheap default for general-purpose caching with a recency-biased workload, and be aware of the scan-pollution risk. 2. **Pick LFU** (or a decayed variant) when your workload has a stable, skewed popularity distribution and you specifically need to protect a hot set from being flushed by transient scans or bursts. 3. **Always add a TTL** — even a generous one — whenever staleness has a real-world correctness or compliance cost, since neither LRU nor LFU on its own gives any staleness guarantee at all; an item can stay resident and 'fresh-looking' in the cache indefinitely just because it keeps getting accessed.