Bifalgorithm post

Your application was slow, so you added a cache. That's the easy part. The hard part is deciding what to delete. Caches need to be bounded. Memory is limited, and without an eviction policy, it'll grow forever and crash your app with an out-of-memory error. So when it's full and a new key arrives, how do you decide what to delete? The optimal eviction policy would evict whatever you won't need for the longest time. But there's no way to know that without seeing the future. That's where the LRU policy comes in. It makes one key assumption, that whatever you needed recently, you'll probably need again soon. This is known as temporal locality, and it's a real-life phenomenon that happens everywhere. Here's how it works. We keep all the entries in one line ordered by what got touched last. Every hit moves an entry to the front. And when it's full and we need to make room, we delete from the back, which is the least recently used item. B, then C. A gets a hit, so it jumps to the front. Now D arrives. FIFO would evict A because it got there first, but LRU evicts B because that's the one nobody asked for the longest. It's implemented using a hash table for constant time lookups, and the values are pointers to nodes in a doubly linked list. And it needs to be doubly linked because to unlink a node, you need to know what's That's the key to doing lookups, promotions, and evictions all in constant time. LRU can't see the future, but it makes the best bet that it can with the information it has, and it usually gets it right.

Your application was slow, so you added a cache. That's the easy part. The hard part is deciding what to delete. Caches need to be bounded. Memory is limited,…