You've felt this before: you restart a service, or open your laptop after the weekend, and everything is sluggish for the first few minutes. Every page load feels like it's dragging. Then, without you doing anything, it speeds back up. Nothing changed in your code. What changed is that the cache went cold, and it just warmed back up.

Almost every system that makes this speed-up possible Redis, your browser, your database, even a function that "remembers" its last few results is solving the exact same problem underneath: it has limited room, so when that room runs out, it has to decide what to throw away first. The answer nearly all of them land on is the same one: throw away whatever hasn't been touched in the longest time. That policy has a name Least Recently Used, or LRU and the way it's actually built is one of the more satisfying "two weak pieces make one strong piece" stories in software.

The problem neither obvious answer solves

Say you want to build this yourself: a fixed-size cache that instantly tells you if something is stored, and instantly evicts the "stalest" entry the moment you're full.

Your first instinct might be a plain lookup table a dictionary, a hash map, whatever your language calls it. That gives you instant answers to "is this here?" But a lookup table has no concept of time. It doesn't know that key A was touched ten seconds ago and key B was touched ten minutes ago. To find the stalest entry, you'd have to check everything slow, and it gets slower as the cache grows.

So your second instinct might be a simple ordered list keep every entry in a line, most recently used at the front. That solves the ordering problem. But now finding a specific entry means walking the line from the front until you happen to find it. And worse, once you find it, moving it to the front means pulling it out of the middle of the line which, in a plain list, means shifting everything around it.

Neither piece alone works. One gives you instant lookup with no memory of time. The other gives you a sense of time with no instant lookup.

The fix: don't choose, combine

The actual solution used almost everywhere is to stop treating "look something up" and "track its age" as the same job, and instead let one structure handle each, wired together.

Picture a line of people, ordered by who was served most recently front of the line is "just here," back of the line is "hasn't been seen in ages." That's your time-ordering structure, and because it's a doubly linked line (each person knows who's directly in front of and behind them), pulling anyone out of the middle and moving them to the front is instant you're just relinking a few neighbors, not shuffling the whole line.

Now add a cashier holding a notebook that maps every person's name directly to their exact spot in that line. You don't scan the line to find someone you check the notebook, and it points you straight at them. That notebook is your lookup table, except its entries don't hold the person's information directly they hold a pointer to where that person is standing.

Put those two together and something interesting happens: a lookup stops being "search the line" and becomes "check the notebook, then relink two spots in the line." Both steps are instant, regardless of how many people are in line. The lookup table gives you the address; the line gives you a cheap way to reorder once you're there. Neither piece is doing the other's job they're doing their own job, wired to the same underlying entries.

Eviction is the same trick pointed at the back of the line instead of the front: whoever is standing at the very back is, by definition, the stalest entry so when the cache is full, that's who gets dropped, and the notebook forgets their name too.

Why real systems don't build this exactly

Here's the part worth sitting with: at genuinely large scale, most real caching systems don't implement pure LRU, because keeping a perfectly ordered "line" updated on literally every single read becomes its own overhead once you're handling millions of operations a second.

Redis's LRU eviction, for instance, doesn't maintain one global perfectly-ordered line at all it samples a handful of random keys and evicts whichever of those looks stalest, repeated as needed. It's an approximation, and a good one, because it gets 90% of the benefit of true LRU for a fraction of the bookkeeping cost.

Your browser's HTTP cache and CDN edge caches lean on the same core idea evict whatever's gone longest untouched once storage fills up to decide what to drop when they hit their limits, which is exactly why re-visiting a page you loaded five minutes ago feels instant, but a page from three weeks ago fetches fresh.

Databases play the same game one layer down. A database's in-memory buffer pool the pages of the table currently held in RAM instead of read from disk often uses something called clock-sweep instead of textbook LRU: cheaper to maintain, same underlying goal of keeping "hot" pages in memory and letting cold ones get evicted first.

And plenty of ordinary application code hits this without ever calling it LRU by name "cache the last 500 computed results, and once that limit is hit, drop whatever hasn't been asked for in a while" is the identical problem, just at a size where the textbook version runs perfectly well with no approximation needed.

The actual takeaway

The mechanism is almost deceptively small once you see it: pair a lookup table with an ordered line, and let the table's entries point directly into the line instead of duplicating what's in it. That's the whole trick. What's genuinely interesting is how far that one idea travels from a toy interview problem, to the reason your database feels fast after warming up, to the reason revisiting a webpage is instant and revisiting an old one isn't. You've probably relied on a system built this way today without ever knowing it had a name.