LRU is a popular but memory-intensive algorithm, hence Redis tweaked it ⚡
The standard implementation of LRU requires a doubly-linked list; wherein each node will have an overhead of 3 pointers = 24 bytes on a 64-bit machine.
To keep eviction memory efficient, Redis has tweaked the LRU and made it approximate. The implementation just requires an overhead of 4 bytes per object. By trading off accuracy and correctness, Redis optimized to reduce memory overhead.
Redis also leverages the same set of bits to also implement LFU with Sampling. Pretty interesting.
⚡ Whenever possible, trade accuracy for performance. Most fancy data structures like Bloom Filters, Hyperloglogs, Count-min sketches, etc, do exactly this.
To understand this in-depth, and other fancy features of Redis, check out my hands-on course on Redis Internals where I have talked about these algorithms and have re-implemented all key features in Golang.
arpitbhayani.me/redis