Cache Replacement Policies in Haskell

A cache stores data so that future requests can be served faster. The idea shows up at every level of computing, from the SRAM caches built into a CPU to the in-memory key-value stores that sit in front of a database.

This series is about the software kind. Since a cache is a key-value store, it’s typically backed by a hash table, which gives us lookups in constant time (\(O(1)\)) on average. That gets us fast reads, but a cache has a finite amount of space, so what happens when it fills up?

The answer is a cache replacement policy, an algorithm to decide which entry to evict. The policy is one of the biggest factors in how often you get a cache hit, and so largely determines whether the cache is worth having at all.

Over the next few articles we’ll implement several of these policies in Haskell and weigh their trade-offs.