Cache Replacement Policies in Haskell: LRU

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, starting with LRU, or least recently used.

This first post is all about building a mutable LRU cache out of IORefs and a hand-rolled doubly linked list. A follow-up will put it through its paces with property-based tests using QuickCheck.

Why not follow along with the source code?

LRU Cache Behaviour

#

Let’s define the behaviour of an LRU cache.

1. Adding elements.
   1. Adding a new entry puts its value at the head of the recency list, evicting the entry at the tail if the cache is already full.
   2. Adding a duplicate entry overwrites its value and moves it to the head of the recency list.
2. Getting elements.
   1. Getting an entry moves it to the head of the recency list.
   2. Getting an entry not in the cache returns nothing and leaves ordering untouched.
3. Deleting elements.
   1. Deleting an element in the cache removes it from both the recency list and the map.
   2. Deleting an element not in the cache is a no-op.

Architecture

#

As I’ve mentioned, our LRU will be backed by a hash table. It will map keys to nodes in a doubly linked list, with the nodes holding the data.

The doubly linked list will model the recency ordering of our elements, making it easy to change the order of arbitrary nodes without having to constantly traverse the list, as would be the case with a singly linked list.

This is the standard approach to implementing an LRU cache in an imperative language such as C++ or Java. But Haskell is a pure language. Side effects are tracked within the type system rather than implicitly, so to perform the pointer manipulation required to adjust the recency list, we’ll make extensive use of IORef.

Idiomatic Haskell wouldn’t approach this problem in this way. An idiomatic solution would likely make use of something like a priority-search queue such as Data.OrdPSQ, trading \(O(1)\) for \(O(\log{n})\) ops, but getting persistence and thread-safety for free.

Fine, but we’re all about learning new things, so we’ll explore IO-based mutation.

IORef Primer

#

Since the whole implementation leans on IORef, what actually is it?

An IORef a is a mutable box holding a value of type a, the closest thing Haskell has to a re-assignable variable, or to a pointer in C. Reading or writing one is a side effect, so every operation lives in IO:

newIORef     :: a -> IO (IORef a)             -- create a box holding an initial value
readIORef    :: IORef a -> IO a               -- read the current contents
writeIORef   :: IORef a -> a -> IO ()         -- overwrite the contents
modifyIORef' :: IORef a -> (a -> a) -> IO ()  -- update the contents by applying a function

modifyIORef' (with trailing ') is the strict variant of modifyIORef. modifyIORef (with no ') stores an unevaluated thunk, so doesn’t actually compute a new value until something forces it. modifyIORef' forces the new value as it’s written, so nothing piles up.

Let’s see a quick example. We’ll create a box, overwrite it, bump it, then read it back:

example :: IO ()
example = do
  ref <- newIORef (0 :: Int)  -- ref holds 0
  writeIORef ref 42           -- ref now holds 42
  modifyIORef' ref (+ 1)      -- ref now holds 43
  x <- readIORef ref
  print x                     -- prints 43

With that down, let’s start building!

Implementation

#

Node

#

We’ll start by implementing a Node datatype to hold data and maintain pointers to neighbours.

module Nodes (Node (value)) where

import Data.IORef (IORef)

data Node a = Node
  { prev, next :: IORef (Maybe (Node a)),
    value :: IORef a
  }

We account for a Node possibly having no neighbours by wrapping prev and next in Maybe, and since we want to move Nodes around and change their value, the prev, next, and value fields are wrapped in IORef.

Neighbours

#

It’d be a good idea to keep prev and next hidden from users, to avoid pointer-mutation bugs. We’ll add a Neighbours datatype so users of Nodes.hs can read a node’s neighbouring nodes without touching the mutable references.

module Nodes (Node (value), Neighbours (before, after)) where

import Data.IORef (IORef)

data Node a = Node
  { prev, next :: IORef (Maybe (Node a)),
    value :: IORef a
  }

data Neighbours a = Neighbours {before, after :: Maybe (Node a)}

We’ll export the before and after fields from Neighbours (which are immutable), and not the prev and next fields from Node (which are mutable).

As for the Node datatype, we’ll only export the value field since our cache may need to overwrite it.

Next we’ll add some helper functions.

Node Helper Functions

#

Given:

• a value a, create a new Node a.
• a Node n, return its Neighbours.
• a Node n and the head of a linked list l, make n the new head of l.
• a Node n already in the list, and the head of a linked list l, move n to the head of l.
• a Node n, delete it, bridging prev and next.

Here’s the complete module:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

-- lets us write a.b to mean 
-- “take the field 'b' out of record 'a'”
{-# LANGUAGE OverloadedRecordDot #-}

module Nodes (Node (value), Neighbours (before, after), neighbours, newNode, addNode, moveToHead, dropNode) where

import Data.IORef (IORef, newIORef, readIORef, writeIORef)

data Node a = Node
  { prev, next :: IORef (Maybe (Node a)),
    value :: IORef a
  }

data Neighbours a = Neighbours {before, after :: Maybe (Node a)}

-- Given an 'a', create a new 'Node a'
-- with mutable 'prev', 'value', and 'next' fields
newNode :: a -> IO (Node a)
newNode val = do
  p <- newIORef Nothing
  v <- newIORef val
  n <- newIORef Nothing
  pure Node {prev = p, value = v, next = n}

-- Given a 'Node a', return its Neighbours
neighbours :: Node a -> IO (Neighbours a)
neighbours node = do
  previous <- readIORef node.prev
  nextNode <- readIORef node.next
  pure Neighbours {before = previous, after = nextNode}

-- Given a 'Node a' nNode and the head of a
-- linked list (also a 'Node a') listHead,
-- add nNode to the head of listHead
addNode :: Node a -> Node a -> IO ()
addNode nNode listHead = do
  writeIORef nNode.next (Just listHead)
  writeIORef listHead.prev (Just nNode)

-- Move a 'Node a' already in a linked list to the head.
moveToHead :: Node a -> Node a -> IO ()
moveToHead node listHead = do
  nodePrev <- readIORef node.prev
  nodeNext <- readIORef node.next
  case nodePrev of
    -- 'node' is already the head
    Nothing -> pure ()
    Just p -> do
      writeIORef p.next nodeNext
      case nodeNext of
        Nothing -> pure () -- 'node' is the last element
        Just n -> writeIORef n.prev (Just p)
      writeIORef node.prev Nothing
      writeIORef node.next (Just listHead)
      writeIORef listHead.prev (Just node)

-- Drop a Node from the linked list, bridging its neighbours.
dropNode :: Node a -> IO ()
dropNode node = do
  nodePrev <- readIORef node.prev
  nodeNext <- readIORef node.next
  case nodePrev of
    Nothing -> pure ()
    Just previousNode -> writeIORef previousNode.next nodeNext
  case nodeNext of
    Nothing -> pure ()
    Just nextNode -> writeIORef nextNode.prev nodePrev

Visualising Rewrites

#

moveToHead and dropNode each rewrite several pointers at once, so they’re easier to follow as a picture than as a nest of case expressions. In the diagrams below, HEAD and TAIL are the references the cache owns and everything between them is the node chain.

moveToHead - move C to the front

before:  HEAD -> [A] <-> [B] <-> [C] <-> [D] <- TAIL

after:   HEAD -> [C] <-> [A] <-> [B] <-> [D] <- TAIL
                  ^               ^       ^
    ([C] moved to head)         ([B] and [D] now bridged)

dropNode - remove a middle node C

before:  HEAD -> [A] <-> [B] <-> [C] <-> [D] <- TAIL

after:   HEAD -> [A] <-> [B] <-> [D] <- TAIL ([C] discarded)
                          ^       ^
                        ([B] and [D] now bridged)

dropNode as eviction - remove the tail D

before:  HEAD -> [A] <-> [B] <-> [C] <-> [D] <- TAIL

after:   HEAD -> [A] <-> [B] <-> [C] <- TAIL ([D] evicted)

Going back to the code, there are some things to clarify:

• Notice that none of the functions track the head of the list itself? They only rewire the prev and next pointers of the nodes they’re handed. That’s deliberate, since the head and tail of the list will be owned by the cache. Each helper does the \(O(1)\) pointer surgery, and the cache is responsible for updating its own head and tail references to match.
• Two assumptions are baked into addNode. First, it expects nNode to be a fresh node whose prev is Nothing. Second, its type Node a -> Node a -> IO () demands an existing listHead, so it can’t seed an empty list. That very first insertion, where the new node becomes both head and tail, is a special case the cache will handle.
• You might also wonder where the helper for evicting the least-recently-used element is. Well there isn’t one, since eviction is just dropNode applied to the tail, which as I’ve mentioned, is a reference the cache will keep.

Cache

#

Let’s define a Cache datatype.

Our Cache will have the following fields:

• cap - the maximum capacity of the cache, defined at creation time
• len - the number of elements currently in the cache
• cacheMap - the key/value store holding data
• listHead - points to the current head of the recency list
• listTail - points to the current tail of the recency list

module Cache (Cache) where

import Data.HashMap.Strict (HashMap)
import Data.IORef (IORef)
import Data.Word (Word8)
import Nodes (Node)

data Cache k v = Cache
  { cap :: Word8,
    len :: IORef Word8,
    cacheMap :: IORef (HashMap k (Node (k, v))),
    listHead, listTail :: IORef (Maybe (Node (k, v)))
  }

Some explanatory comments:

• cap and len are Word8 meaning the cache can hold up to 255 elements. I’ve chosen this simply to keep things small. Note a cache with cap == 0 would hold nothing.
• listHead and listTail hold mutable Node (k, v). Why (k, v)? Well, when we drop a node, we need a way to link back to the key in the HashMap, so we can delete that too.

Now we’ll add some helper functions.

Cache Helper Functions

#

Given:

• a capacity cap, create a new cache with that capacity.
• a cache c, a key k and value v, add k and v to c.
• a cache c and a key k, retrieve the value v associated with k.
• a cache c and a key k, delete k from c.

These functions will make up the public API, and so will be exported from the module.

We’ll also need some private internal functions to manage the ordering of nodes.

When:

• a value is retrieved from the cache, promote that node to the head of the recency list.
• a new key and value are added to the cache, the associated node should be pushed to the head of the recency list.
• the cache is full and a new key/value pair is added, the key, value and node at the tail of the recency list should be removed.

Here’s the complete implementation:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

{-# LANGUAGE OverloadedRecordDot #-}

module Cache (Cache, createCache, addTo, getFrom, deleteFrom) where

import Control.Monad (when)
import Data.HashMap.Strict (HashMap)
import qualified Data.HashMap.Strict as HM
import Data.Hashable (Hashable)
import Data.IORef (IORef, modifyIORef', newIORef, readIORef, writeIORef)
import Data.Maybe (isJust, isNothing)
import Data.Word (Word8)
import Nodes (Neighbours (after, before), Node, addNode, dropNode, moveToHead, neighbours, newNode, value)

data Cache k v = Cache
  { cap :: Word8,
    len :: IORef Word8,
    cacheMap :: IORef (HashMap k (Node (k, v))),
    listHead, listTail :: IORef (Maybe (Node (k, v)))
  }

createCache :: Word8 -> IO (Cache k v)
createCache capacity = do
  l <- newIORef 0
  m <- newIORef HM.empty
  h <- newIORef Nothing
  t <- newIORef Nothing
  pure Cache {cap = capacity, len = l, cacheMap = m, listHead = h, listTail = t}

-- Insert or overwrite a key, 
-- promoting it to the most-recently-used position.
-- Evicts the least-recently-used entry first if the cache is full.
addTo :: (Hashable k) => Cache k v -> k -> v -> IO ()
addTo cache key val
  | cache.cap == 0 = pure () -- a zero-capacity cache holds nothing
  | otherwise = do
      m <- readIORef cache.cacheMap
      case HM.lookup key m of
        -- Key present: overwrite its value, then promote the node to the top.
        Just node -> do
          writeIORef node.value (key, val)
          promote cache node
        -- New key: evict if full, then push a fresh node to the top.
        Nothing -> do
          cacheLen <- readIORef cache.len
          when (cacheLen == cache.cap) (evictLRU cache)
          newN <- newNode (key, val)
          pushFront cache newN
          modifyIORef' cache.cacheMap (HM.insert key newN)
          modifyIORef' cache.len (+ 1)

-- Look up a key. On a hit the entry is promoted to most-recently-used.
getFrom :: (Hashable k) => Cache k v -> k -> IO (Maybe v)
getFrom cache key = do
  m <- readIORef cache.cacheMap
  case HM.lookup key m of
    -- miss: nothing to promote, return Nothing
    Nothing -> pure Nothing
    Just node -> do
      promote cache node
      (_, v) <- readIORef node.value
      pure (Just v)

-- Remove a key (its value and its Node) from the cache entirely.
-- A miss is a no-op. Unlike evictLRU, the node may be anywhere in the list,
-- so BOTH ends may need patching.
deleteFrom :: (Hashable k) => Cache k v -> k -> IO ()
deleteFrom cache key = do
  m <- readIORef cache.cacheMap
  case HM.lookup key m of
    Nothing -> pure () -- key absent: nothing to delete
    Just node -> do
      -- Read neighbours BEFORE dropNode rewires them (same as evictLRU).
      ns <- neighbours node
      dropNode node
      when (isNothing ns.before) (writeIORef cache.listHead ns.after)
      when (isNothing ns.after) (writeIORef cache.listTail ns.before)
      modifyIORef' cache.cacheMap (HM.delete key)
      modifyIORef' cache.len (subtract 1)

-- Move an existing node to the most-recently-used (top) position.
-- Shared by addTo (on overwrite) and getFrom (on a hit).
promote :: Cache k v -> Node (k, v) -> IO ()
promote cache node = do
  mTop <- readIORef cache.listHead
  case mTop of
    Nothing -> pure ()
    Just topNode -> do
      ns <- neighbours node
      when (isNothing ns.after && isJust ns.before) (writeIORef cache.listTail ns.before)
      moveToHead node topNode
      writeIORef cache.listHead (Just node)

-- Link a fresh node at the top of the list. Updates listHead, and also listTail when the
-- list was empty (the new node is then both ends).
pushFront :: Cache k v -> Node (k, v) -> IO ()
pushFront cache node = do
  mTop <- readIORef cache.listHead
  case mTop of
    Nothing -> writeIORef cache.listTail (Just node)
    Just topNode -> addNode node topNode
  writeIORef cache.listHead (Just node)

-- Drop the least-recently-used (last) node from both the list and the map.
evictLRU :: (Hashable k) => Cache k v -> IO ()
evictLRU cache = do
  mLast <- readIORef cache.listTail
  case mLast of
    Nothing -> pure () -- empty list: nothing to evict
    Just lastNode -> do
      (evictedKey, _) <- readIORef lastNode.value
      modifyIORef' cache.cacheMap (HM.delete evictedKey)
      -- Query the neighbours BEFORE dropNode rewires them; the old prev is the new tail.
      ns <- neighbours lastNode
      dropNode lastNode
      writeIORef cache.listTail ns.before
      when (isNothing ns.before) (writeIORef cache.listHead Nothing) -- list now empty
      modifyIORef' cache.len (subtract 1)

A few things worth drawing out from the code:

• As promised in the primer, every read-modify-write update goes through the strict modifyIORef'. readIORef and writeIORef are left un-strict for two reasons: readIORef has nothing to force since it just hands back the current contents, and writeIORef replaces the box outright rather than deriving the new value from the old, so successive writes never nest.
• promote, evictLRU, and deleteFrom form a little hierarchy of pointer-patching. promote only ever moves a node up, so the sole endpoint it can disturb is the tail, and only when the node it’s promoting was sitting there. evictLRU only ever removes the tail, so it always patches the tail. deleteFrom is the general case: the node could be anywhere, so it inspects each end independently with its two when guards, and either, both, or neither may fire.
• Both evictLRU and deleteFrom read the node’s neighbours before calling dropNode. Since dropNode rewires the prev and next pointers, in order to find the new head or tail, we have to snapshot them first. Snapshot, then mutate — the recurring shape of every operation here.
• deleteFrom on a missing key is a no-op, and a hit keeps len and the map in lockstep because HM.delete and subtract 1 always happen together.

Trying It Out

#

Let’s take it for a spin.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

-- lets us specify the type arguments 
-- for polymorphic functions using the @ symbol.
{-# LANGUAGE TypeApplications #-}

module Main where

import Cache (addTo, createCache, deleteFrom, getFrom)

main :: IO ()
main = do
  -- create a cache with String keys, Int values, and capacity 2.
  cache <- createCache @String @Int 2
  -- recency shown MRU -> LRU
  addTo cache "a" 1            -- a
  addTo cache "b" 2            -- b, a
  _ <- getFrom cache "a"       -- a, b   (reading "a" promotes it)
  addTo cache "c" 3            -- c, a   (cache full, so "b" is evicted)

  print =<< getFrom cache "b"  -- Nothing  ("b" was the LRU entry)
  print =<< getFrom cache "a"  -- Just 1
  print =<< getFrom cache "c"  -- Just 3

  deleteFrom cache "a"         -- removes "a" wherever it sits
  print =<< getFrom cache "a"  -- Nothing

The key moment is the _ <- getFrom cache "a" line. Had we not read "a" beforehand, it would have been the least-recently-used entry and "c" would have evicted it. That one getFrom is the difference between "a" surviving and "a" being dropped.

Invariants, and What’s Next

#

Every operation above is careful to preserve a handful of structural invariants. Note that these operations aren’t atomic, so the cache assumes single-threaded use.

At rest, a well-formed cache should satisfy:

• Size agreement — len equals the number of entries in cacheMap.
• Capacity — len never exceeds cap.
• Endpoints — if the cache is non-empty, listHead and listTail are both Just, the head node has no prev, and the tail node has no next; if it’s empty, both are Nothing.
• Reachability — following next from the head visits every node exactly once and lands on the tail, following prev from the tail does the opposite. The nodes visited are exactly the values of cacheMap, and each is stored under the key it holds.

Every one of them is tedious to check by hand and easy to break with a single stray pointer write. They’re exactly what you’d want a test to hammer on. There’s only one problem: none of the state you’d need to check them is reachable! len, cacheMap, listHead and listTail are all private, prev and next too, and that encapsulation is deliberate, as it stops us corrupting the list by accident.

So we have an interesting question to answer: how do you test a data structure whose state is hidden?

That’s where we’ll go next.