this post follows part 1 of the series, in which I build a single node key-value cache with CRUD operations and simple concurrency handling, and is followed by part 3 of the series.
Ah, but memory grows forever!
As magical as hardware may seem, even it has its limits (which get broken time and time again, mind...). We can't let our cache grow forever or we'll hit our memory limits and probably get a SIGKILL from our OS/container runtime. A kill signal. Well, gotta be responsible with our powers! That's where eviction policies come into play. To keep making room for new data, we need to take out the trash, so to speak. There's several different methods I've studied for doing this. I'll have a section for each.
Time-to-live
TTL: each item expires after a set time (ex: 5 min) has passed after the latest update/creation time. Great for data that can go stale, like API responses.
If I implemented this, I would add a timestamp to each key, set to the latest create/update time.
type TTLItem struct {
value string
timestamp time.Time
}
type TTLCache struct {
items map[string]TTLItem
}Then I would implement some deletion method. There's two ways I'm thinking of.
One is a background job (a goroutine!) which runs perpetually, parallel to all other logic, and deletes keys that get old. This is the more complicated option, and it comes with some sub-decisions too. For example, how do we even know what keys are ready to be deleted? My first guess was to have the job loop over all the keys periodically, and just delete any entries that have timestamps older than time.Now() - ttl. But that's O(n) time.... pretty slow... and also means it needs read locks on every key, which is not too efficient if we had writes queued up to happen concurrently. Our goroutines need to work together, not against each other!
I looked up a better solution and found that using a heap vastly improves efficiency of a background job. We store all our entries in a heap (sorted by timestamp, such that the oldest entry is at the top) and the background job can start its search from the top of the heap. Heaps are great since they give a sorted view of the cache data without actually sorting every entry, but it does cost extra memory. It also adds complexity, since we now have an invariant to keep it in sync with the map/dictionary state.
type TTLCache struct {
mu sync.Mutex
items map[string]*cacheEntry
pq expiryHeap
ttl time.Duration // expiry time
}
type cacheEntry struct {
value string
timestamp time.Time // latest create/update time
item *heapItem // back-pointer into the heap
}
func NewTTLCache(ttl time.Duration) *TTLCache {
c := &TTLCache{
items: make(map[string]*cacheEntry),
pq: expiryHeap{},
ttl: ttl,
}
heap.Init(&c.pq)
return c
}
func (c *TTLCache) evictExpired() {
c.mu.Lock()
defer c.mu.Unlock()
cutoff := time.Now().Add(-c.ttl) // anything stamped before this is expired
for c.pq.Len() > 0 {
top := c.pq[0] // peek — oldest timestamp — O(1)
if top.timestamp.After(cutoff) {
break // all entries still alive
}
heap.Pop(&c.pq) // remove from heap — O(log n)
delete(c.items, top.key) // remove from map — O(1)
}
}This code sample showcases one example of the complexity of adding a heap. Now, even simple cache reads mutate state (by updating the heap with the new timestamp!), so every operation now involves a write. This means our mutex will be changed to the standard one (sync.Mutex) in which all locks are mutually exclusive.
Background job deletion can be very involved, so it was refreshingly simple to think about another solution, which is aptly called 'lazy deletion'. Whenever we read an entry, we first check if it's expired. If it has, we delete it. Yes, this means we only check expiry on read (the general pattern of 'evaluation on read' is always described as 'lazy'!)! But yes, it also runs the risk of letting our cache grow infinitely if we never read most of the keys. Paired with another method of expiry, such as LRU, discussed below, I imagine this could still be a strong TTL method in production systems.
Least Recently Used
LRU: evict entries that haven’t been used recently. Most common solution.
Intuition for the logic: for this method we can define a maximum limit for how many key-value pairs we allow. If we ever call Create() while the limit is reached, we delete the least recently used pair to make room for the new one. 'Usage' can be defined as any operation on an item, either a read or a write. So we'll need to always know what the least recently used item is while also allowing reordering whenever a read/write operation happens. This points to needing a data structure besides just the map. Linearly finding the lru item points to a simple list, like a linked list, but to support O(1) reordering, a doubly-linked list works even better! That way, each node knows who its previous and next neighbor is, so if it's removed (such as to be moved to the 'most recent' end of the list after it was read), it can stitch together both of those neighbors instantly. We don't need to store a timestamp field (unlike the TTL implementations) since only relative ordering matters in LRU and our linked list provides that.
For our implementation, we can use Go's container/list package for a built-in doubly linked list.
import (
"container/list"
"sync"
)
type entry struct {
key string // stored so eviction can delete from the map
value string
}
type LRUCache struct {
mu sync.Mutex
items map[string]*list.Element // key → node in the list
order *list.List // front = most recent, back = least recent
capacity int
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
items: make(map[string]*list.Element),
order: list.New(),
capacity: capacity,
}
}And here's an example method:
func (c *LRUCache) Create(key, value string) bool {
c.mu.Lock()
defer c.mu.Unlock()
if _, exists := c.items[key]; exists {
return false // key already exists → caller returns 409
}
if c.order.Len() >= c.capacity {
c.evictLRU()
}
elem := c.order.PushFront(&entry{key: key, value: value})
c.items[key] = elem
return true
}As we can see, our map stores pointers to nodes in the linked list as values to allow for O(1) lookup. And since the linked list allows for O(1) removes and additions, all operations in CRUD are still O(1)!
This will be the method I choose going forward. It's widely used, great for temporal locality (this is not a fantasy term I made up, but a fancy way of saying "if you access a piece of data, you're likely to access it again soon"), and simple enough to implement. Still, let's briefly look at the two other main eviction policies.
Least Frequently Used
LFU: evict items that are used least often, even if accessed recently.
Motivation: this is good for highly skewed access patterns, where popularity is stable over time. Items that have been popular over a long period get a strong bias and are allowed to remain in the cache for fast access. The biggest advantage is seen in a scenario where there's only a few such popular items but a large number of unpopular items (this is starting to sound like middle school...). In that case, the few popular items will always remain in the cache. So just because a bunch of unpopular items get one read each in a row doesn't mean the popular ones run a risk of being deleted, like they would in LRU.
To implement this, we'd need a frequency counter for each item. From there, I couldn't figure out an O(1) solution. Linear scan is naive and O(n). Using a heap, with the lowest frequency item always at the top, is decent with O(log n). I looked up if there was anything better and found a research paper from 2010 which found a way to make it O(1) for all operations! Here's a quick summary of the data structure breakdown:
- you have a doubly linked list called a frequency list. Each node of that frequency list is a node that represents a frequency count (ex: 1, 2, 3) and owns a doubly linked list, called a node list, of its own. A frequency node only exists for frequencies that at least one item has.
- Each node list represents all items with the same frequency, and each element in the node list has a pointer to its corresponding frequency node.
- And of course, we have a hash map, mapping keys to nodes in a node list.
Let's walk through one algorithmic example of the above: if we do a read operation on an existing item, first we look up the key in the hash map to find the existing node. The node stores the value so we'll be able to return it at the end of the function. But first, we need to update the frequency, incrementing by one. We find the frequency using the node's pointer to its frequency node, getting the existing frequency value from that. We look at the .next pointer in the frequency node to see the next node in the frequency list. Supposing it's frequency is more than 1 higher, than means no nodes currently exist at the new frequency we want to set our item to. So we create a new frequency node with that frequency, then delete our node from its existing position and add it as the head of a new node list, setting a pointer to the new frequency node we created. All of that was done in O(1) time! A hashmap lookup, some pointer checks, and doubly linked list removals/additions. Clean. It was really cool to learn about this.
First-in-first-out
FIFO: evict the oldest item first. While simple, it’s rarely the right choice, since some items are more important due to higher frequency access (ex: viral video links) or by being more topical and fresh (ex: recent news article) or any number of other reasons. Not all items deserve equal consideration! And on that note, not all eviction policies deserve equal consideration, so I won't write any more about this one :)