Caching

Some data is expensive to get. A database query, a disk read, a call to another service: each costs time, and the cost repeats every time you ask. A cache is a small, fast memory that sits in front of the slow thing and remembers recent answers. When the same question comes back, the cache answers instantly and the slow thing is never bothered.

The catch is the word small. A cache that held everything would just be the slow thing's twin. Real caches hold a fraction of the data, which forces a decision every time something new arrives and the cache is full: something already inside has to go. The rule for choosing the victim is called an eviction policy, and the figure runs the most common one, least recently used. LRU's bet is simple: the key you touched longest ago is the one you're least likely to need next.

Watch the readouts as the stream plays. A hit means the key was already in the cache, one green flash and no trip below. A miss means the origin gets a visit, and the origin fetches counter is deliberately just the misses counter wearing a different label. That redundancy is the whole economics of caching: every miss is a trip to the slow thing, so hit rate is not a vanity metric, it is a direct measure of how much slow work you avoided. This stream ends at 50%: half the requests never touched the origin.

Then watch what happens when E arrives. The cache is full, and LRU evicts C, its coldest key. Two steps later, C is requested again and has to be re-fetched. A policy that could see the future would have evicted E itself, a one-off that never returns. But the cache cannot see the future; it can only see the past, and recency is its guess about what comes next. Every eviction policy is a guess of this kind, and every policy can be made to guess wrong by the right sequence of requests.

Two honesty notes. The request stream here is hand-built to be instructive: a hot key, some warm ones, two one-offs, arranged so each kind of event appears and the eviction backfires visibly. Real traffic is messier, and hit rates depend on how much repetition your workload actually has. And LRU is one policy among several; least frequently used, first-in-first-out, and randomized policies all make different bets, each with workloads that favor it and workloads that punish it.

The cache in this figure is real: an actual LRU implementation processes each request, and the readouts are computed from its state, not scripted.

Simulating a real LRU cache