One question that recently made me rethink cache eviction was:

If Redis uses LRU, why doesn't it maintain a heap (or a perfectly sorted list) of keys?

The answer comes down to optimizing the common case.

The Problem

Imagine a Redis instance with 10 million keys.