A cache with room for 3 things. Your app asks for 4 things in a loop: A, B, C, D, A, B, C, D, and so on.
You'd expect a few hits at least. It gets zero.
12 requests, 12 misses. The cache works exactly like it's supposed to.
What LRU does
LRU means least recently used. When the cache is full and something new comes in, it throws out whatever was used longest ago.
Most of the time that's a good guess. If you used something recently, you'll probably need it again soon.
Why the loop breaks it
Walk through it slowly:
- A, B, C go in. The cache is full.
- D comes in. A is the oldest, so A gets thrown out.
- Next request is A. It was just thrown out. Miss. A goes back in, and now B is the oldest, so B goes.
- Next request is B. Just thrown out. Miss.
Every key gets evicted right before it's needed again. It never gets a single hit.
Add one slot
Give the cache room for 4 instead of 3. Same 12 requests, and now you get 8 hits.
The first 4 still miss because the cache starts empty. After that, everything is already there.
That's 0% to 67% from one extra slot. Cache size doesn't always change things a little. Sometimes it's a cliff.
When LRU does its job
Here A comes back every other request:
Every A after the first one is a hit. That's 5 hits out of 12, and every one of them is an A. B, C, D, E and F get thrown out, but A never does, because it keeps getting used before it can become the oldest.
That's the kind of traffic LRU is good at. A few things are popular, and the rest come and go.
You can build one in about 20 lines
A JavaScript Map remembers the order you inserted keys. Delete a key and set it again, and it moves to the end. So the first key is always the one used longest ago.
class LRU { constructor(size) { this.size = size; this.map = new Map(); } get(key) { if (!this.map.has(key)) return undefined; const value = this.map.get(key); this.map.delete(key); this.map.set(key, value); // move to the end = most recent return value; } set(key, value) { this.map.delete(key); this.map.set(key, value); if (this.map.size > this.size) { this.map.delete(this.map.keys().next().value); // the first key is the oldest } } } Run the A B C D loop through it with size 3 and you get 0 hits out of 12. With size 4 you get 8.
Where this shows up for real
Anything that loops over slightly more data than the cache can hold. A job that goes through the same list every few minutes, or a big table read from start to end over and over.
If the data fits, you get great hit rates. If it's just a bit too big, you can get almost nothing, and it looks like the cache is broken when it isn't.
That's why some caches use smarter rules than plain LRU. But knowing this one case already explains a lot of weird cache numbers.
You can try it here. Use your own keys, change the capacity, or replay the loop and watch every key get kicked out right before it's needed: https://software-atlas.haiduc0147.dev/t/lru#playground
