Why Redis Uses Approximate LRU Instead of a Perfect Eviction Algorithm

Redis does not maintain a perfectly sorted LRU structure because updating it on every read — even with a doubly-linked list — would add significant overhead at millions of requests per second. Instead, when memory is full, Redis randomly samples a small set of keys (default: five) and evicts the least recently used among them. To improve accuracy, Redis retains the best eviction candidates in an internal pool of 16 entries, merging new samples with existing candidates across iterations. This approach means eviction cost is only paid when memory is actually exhausted, keeping the far more frequent read operations fast. The result is a near-perfect approximation of true LRU that scales efficiently without sacrificing meaningful cache hit rate accuracy.