The problem with infinite memory
You are building a service that fetches user profiles from a slow database. The first request takes 200 milliseconds. The second request for the same user should be instant. You add a map to cache the results. Traffic grows. The map grows. Your server runs out of memory and the operating system kills the process.
Memory is finite. You need a cache that respects a limit. When the cache is full and you insert a new item, something must go. The Least Recently Used (LRU) strategy is the standard answer. It keeps the items you touch most often and evicts the ones you haven't touched in a while.
LRU is a trade-off. You trade memory for speed. Pick the size that fits your budget.
The data structure combo
A naive implementation fails on performance. If you use a slice, looking up a key is O(n). If you use a map, you get O(1) lookups but no order. You can't evict the least recently used item efficiently because the map doesn't track recency.
You need both speed and order. The solution is a hybrid: a map for lookups and a doubly linked list for order.
The map stores keys and points to nodes in the list. The list maintains the access order. When you access a key, you find the node in the map and move that node to the front of the list. When you need to evict, you remove the node at the back of the list and delete the key from the map.
Go's standard library provides container/list, which is a doubly linked list. It supports O(1) insertion, deletion, and moving elements. Combined with a map, you get O(1) for both Get and Put.
The map finds the item. The list remembers the order. Together they give you speed and structure.
Building the cache
Here is the structure. The cache holds a capacity, a list, and a map. The map keys are the cache keys. The map values are pointers to list.Element nodes. Each node holds an entry with the key and value.
package main
import "container/list"
// LRUCache stores key-value pairs with a fixed capacity.
// It evicts the least recently used item when full.
type LRUCache struct {
capacity int // maximum number of items allowed
list *list.List // doubly linked list tracking access order
cache map[string]*list.Element // map for O(1) key lookup
}
// entry holds the actual data stored in the list node.
type entry struct {
key string
value interface{}
}
// NewLRUCache creates a cache with the given capacity.
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
capacity: capacity,
list: list.New(), // initializes the doubly linked list with a sentinel node
cache: make(map[string]*list.Element), // pre-allocates the map
}
}
container/list uses a circular doubly linked list with a dummy root element. list.New() creates this root. The root itself doesn't hold data. It acts as an anchor so PushFront and Back always have a reference point. This design avoids null pointer checks for empty lists.
Convention aside: receiver names should be short. (c *LRUCache) is standard. Avoid (this *LRUCache) or (self *LRUCache). Go doesn't have a this keyword, and the community prefers one or two letters that match the type name.
The Get method checks the map. If the key exists, it moves the corresponding element to the front of the list to mark it as recently used, then returns the value. If the key is missing, it returns a miss.
// Get retrieves a value by key.
// It returns the value and true if found, or nil and false on a miss.
// Accessing a key moves it to the front of the list.
func (c *LRUCache) Get(key string) (interface{}, bool) {
// map lookup is O(1); check if key exists
if elem, ok := c.cache[key]; ok {
// move node to front updates recency without copying data
c.list.MoveToFront(elem)
// type assert to extract the entry struct from the list element
return elem.Value.(*entry).value, true
}
return nil, false
}
The Put method handles two cases. If the key exists, it updates the value and moves the element to the front. If the key is new, it creates a new entry, pushes it to the front, and adds it to the map. If the list exceeds capacity, it evicts the oldest item from the back.
// Put inserts or updates a key-value pair.
// If the cache is full, it evicts the least recently used item.
func (c *LRUCache) Put(key string, value interface{}) {
// check if key already exists to update in place
if elem, ok := c.cache[key]; ok {
// update value and refresh recency
elem.Value.(*entry).value = value
c.list.MoveToFront(elem)
return
}
// new key: create entry and push to front of list
c.cache[key] = c.list.PushFront(&entry{key: key, value: value})
// evict oldest if capacity is exceeded
if c.list.Len() > c.capacity {
c.removeOldest()
}
}
// removeOldest deletes the item at the back of the list.
func (c *LRUCache) removeOldest() {
// Back() returns the element just before the sentinel root
elem := c.list.Back()
if elem == nil {
return
}
// remove from list and delete key from map to free memory
c.list.Remove(elem)
delete(c.cache, elem.Value.(*entry).key)
}
MoveToFront is O(1) because it only rewires pointers in the linked list. It doesn't shift elements like a slice would. PushFront and Remove are also O(1). The map operations are O(1) on average. The whole cache operates in constant time.
The map finds the item. The list remembers the order. Together they give you speed and structure.
Walkthrough of operations
Consider a cache with capacity 3. You call Put("a", 1), Put("b", 2), Put("c", 3). The list looks like c -> b -> a. The map has entries for all three keys.
Now you call Get("a"). The map finds the element for "a". MoveToFront rewires the list to a -> c -> b. The value 1 is returned. "a" is now the most recently used.
You call Put("d", 4). The key "d" is new. PushFront adds "d" to the list: d -> a -> c -> b. The length is 4, which exceeds capacity 3. removeOldest is called. Back() returns the element for "b". The element is removed from the list and the key "b" is deleted from the map. The list is now d -> a -> c.
If you call Get("b") now, the map lookup fails. You get a cache miss. "b" was evicted.
This behavior is deterministic. The item at the back of the list is always the one that hasn't been accessed for the longest time.
Ah-ha moment: LRU is an approximation. It assumes that items accessed recently will be accessed again soon. This fails for periodic scans. If you iterate over a large dataset once, LRU will evict items that are rarely used but accessed periodically, while keeping items that were just scanned once. LRU is great for locality of reference, not for periodic access patterns.
LRU is a trade-off. You trade memory for speed. Pick the size that fits your budget.
Real-world constraints
The example above uses interface{} for values. This requires type assertions on every access. Type assertions have a small runtime cost and lose compile-time type safety. Go 1.18 introduced generics. A modern cache should use generics to avoid assertions and catch errors at compile time.
Concurrency is the bigger issue. The map and the list are not thread-safe. If two goroutines call Get and Put simultaneously, you get a race condition. The compiler might warn you with possible race detected if you run with the race detector, but the program can also panic at runtime with concurrent map read and map write.
A production cache needs a mutex. sync.RWMutex is better than sync.Mutex because reads are more common than writes. RWMutex allows multiple readers concurrently while blocking writers.
package main
import (
"container/list"
"sync"
)
// LRUCache is a thread-safe LRU cache using generics.
type LRUCache[K comparable, V any] struct {
capacity int
list *list.List
cache map[K]*list.Element
mu sync.RWMutex // protects map and list from concurrent access
}
// entry holds the key and value for the list node.
type entry[K comparable, V any] struct {
key K
value V
}
// NewLRUCache creates a generic LRU cache.
func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {
return &LRUCache[K, V]{
capacity: capacity,
list: list.New(),
cache: make(map[K]*list.Element),
}
}
// Get retrieves a value. It acquires a read lock.
func (c *LRUCache[K, V]) Get(key K) (V, bool) {
c.mu.RLock()
elem, ok := c.cache[key]
c.mu.RUnlock()
if !ok {
var zero V
return zero, false
}
// MoveToFront modifies the list, so we need a write lock.
// We release the read lock first to avoid deadlock.
c.mu.Lock()
c.list.MoveToFront(elem)
val := elem.Value.(*entry[K, V]).value
c.mu.Unlock()
return val, true
}
The Get method shows a subtle pattern. The map lookup can be done under a read lock. But MoveToFront modifies the list, which requires a write lock. You can't hold a read lock and upgrade to a write lock in Go. You must release the read lock, acquire the write lock, and then proceed. This introduces a small window where another goroutine could modify the list, but the element pointer remains valid until eviction. Since we hold the element pointer and check existence before the write lock, this is safe.
Convention aside: context.Context is not relevant for a cache. Caches are fast, local operations. Passing context through a cache adds overhead without benefit. Save context for I/O and long-running tasks.
Locks are expensive. Batch your reads or use a read-write lock to keep throughput high.
Pitfalls and errors
A nil map causes a panic. If you forget to initialize the map in NewLRUCache, the first Put crashes with assignment to entry in nil map. Always initialize maps with make.
// BAD: cache.cache is nil
c := &LRUCache{capacity: 10}
c.Put("key", "value") // panic: assignment to entry in nil map
Forgetting the mutex in a concurrent program leads to runtime panics. The map implementation detects concurrent writes and panics with concurrent map read and map write. The list can also corrupt its internal pointers, leading to hard-to-debug crashes. Always protect shared state.
Memory overhead is real. Each list.Element has four pointers (prev, next, list, value). The map has its own overhead. If you cache small values, the metadata can dominate memory usage. Profile your cache size. If memory is tight, consider a library that uses less overhead or stores values in a compact format.
LRU can be fooled. As mentioned, periodic access patterns defeat LRU. If your workload has periodic scans, consider a different eviction policy like LFU (Least Frequently Used) or a random eviction. LRU is not the best algorithm for every workload.
A cache without locks is a time bomb. Protect the map and the list.
Decision matrix
Use a manual LRU with container/list when you need strict eviction order and want to avoid external dependencies. This is the standard library approach. It works well for moderate concurrency and simple use cases.
Use a simple map with periodic cleanup when your keys are ephemeral and exact eviction order doesn't matter. You can run a background goroutine that deletes old entries based on timestamps. This is simpler but less predictable.
Use a third-party library like ristretto when you need high-performance, thread-safe caching with statistical eviction policies. ristretto uses a sampling-based approach that handles periodic scans better than strict LRU and has lower overhead.
Use a database or Redis when the cache needs to survive restarts or be shared across multiple processes. An in-memory cache is local to one process. Distributed caching requires a network service.
Use a manual LRU with container/list when you need strict eviction order and want to avoid external dependencies. Use a simple map with periodic cleanup when your keys are ephemeral and exact eviction order doesn't matter. Use a third-party library like ristretto when you need high-performance, thread-safe caching with statistical eviction policies. Use a database or Redis when the cache needs to survive restarts or be shared across multiple processes.