Here’s something interesting about cache eviction - instead of tracking the exact LRU (Least Recently Used) item, we can just pick two random items and evict the older one.
This is called “2-random,” and it works surprisingly well.
The idea is simple. When we need to evict something from our cache, randomly sample two keys, compare their last access times, and evict the one that was accessed longer ago. That’s it.
Why not just track true LRU? Because maintaining a perfect LRU requires extra memory and CPU overhead. We need a doubly linked list with pointers for every cache entry, plus the cost of updating it on every access.
Btw, picking two keys at random and evicting the least recently used of the two becomes virtually indistinguishable from true LRU. It works because it avoids the worst random choices (by picking the better of two) while retaining enough randomness.
2-random also degrades gracefully when your working set exceeds the cache size. True LRU can cause near-100% cache misses when looping over data larger than the cache. Random eviction handles this better, and 2-random gives you the best of both worlds.
Many in-memory databases are full of such “good enough” approximations. Dig deeper when you find time. It’s fun.