Introduction to LRU Cache
An LRU (Least Recently Used) Cache is a popular caching eviction policy that discards the least recently used items first when the cache reaches its capacity limit. It is based on the heuristic that items accessed recently are more likely to be accessed again in the near future. This makes LRU caches extremely effective in scenarios where access patterns exhibit temporal locality.
In this tutorial, we will walk through a complete implementation of an LRU Cache in Go. We will explore the underlying data structures, build the cache from scratch, and discuss best practices for using it in production systems.
Why LRU Cache Matters
Caching is one of the most effective ways to improve application performance. By storing frequently accessed data in memory, you avoid expensive computations or slow I/O operations such as database queries or network calls. However, memory is finite, so you need an eviction policy to decide which items to remove when the cache is full.
LRU is widely used because it strikes a good balance between simplicity and effectiveness. Common use cases include:
- Web servers caching HTTP responses to reduce backend load
- Database query result caching to avoid repeated expensive queries
- Content delivery networks caching popular assets closer to users
- Operating systems using LRU for page replacement in virtual memory
- Image or thumbnail caching in mobile and desktop applications
Understanding how to implement an LRU cache from scratch is a valuable skill. It is a common interview question, but more importantly, it teaches you how to combine data structures to solve real problems efficiently.
Choosing the Right Data Structures
To implement an LRU cache with O(1) time complexity for both get and put operations, we need to combine two data structures:
- Hash Map: Maps keys to their corresponding cache entries, giving us O(1) lookup.
- Doubly Linked List: Maintains the order of items by recency of access. The most recently used item is at the head, and the least recently used item is at the tail.
The hash map gives us fast access to any node, while the doubly linked list lets us move nodes to the front in O(1) time when they are accessed. Without the linked list, we would need O(n) time to reorder items. Without the hash map, we would need O(n) time to find an item in the list.
Why a Doubly Linked List?
A doubly linked list allows us to remove a node in O(1) time because each node has pointers to both its previous and next neighbors. We do not need to traverse the list to find the predecessor before removing a node. This is the key insight that makes the entire cache operate in constant time.
Implementing the Doubly Linked List
Let us start by defining the building block of our cache: the doubly linked list node.
package lru
// node represents an entry in the doubly linked list.
type node struct {
key string
value interface{}
prev *node
next *node
}
Each node stores the key and value of the cached item, along with pointers to the previous and next nodes. We store the key in the node so that when we evict the tail node, we can remove its entry from the hash map as well.
Next, let us define the cache structure itself:
// Cache represents an LRU cache with a fixed capacity.
type Cache struct {
capacity int
items map[string]*node
head *node
tail *node
}
// New creates a new LRU cache with the given capacity.
func New(capacity int) *Cache {
return &Cache{
capacity: capacity,
items: make(map[string]*node),
}
}
We use sentinel head and tail nodes to simplify boundary conditions. This means we never have to check whether a node is the first or last element when inserting or removing. Let us add helper methods to manage the linked list:
// moveToFront moves an existing node to the front of the list.
func (c *Cache) moveToFront(n *node) {
c.removeNode(n)
c.addToFront(n)
}
// removeNode removes a node from the linked list.
func (c *Cache) removeNode(n *node) {
if n.prev != nil {
n.prev.next = n.next
} else {
c.head = n.next
}
if n.next != nil {
n.next.prev = n.prev
} else {
c.tail = n.prev
}
n.prev = nil
n.next = nil
}
// addToFront inserts a node at the front of the list.
func (c *Cache) addToFront(n *node) {
n.next = c.head
n.prev = nil
if c.head != nil {
c.head.prev = n
}
c.head = n
if c.tail == nil {
c.tail = n
}
}
These three helper methods handle all the linked list manipulation we need. The moveToFront method is called whenever an item is accessed, ensuring the most recently used item is always at the head.
Implementing Get and Put Operations
Now let us implement the two core operations of the cache: Get and Put.
The Get Operation
The Get method retrieves a value from the cache. If the key exists, it moves the corresponding node to the front of the list to mark it as recently used. If the key does not exist, it returns nil and a boolean false to indicate a cache miss.
// Get retrieves a value from the cache.
// Returns the value and true if found, nil and false otherwise.
func (c *Cache) Get(key string) (interface{}, bool) {
if n, ok := c.items[key]; ok {
c.moveToFront(n)
return n.value, true
}
return nil, false
}
The Put Operation
The Put method inserts or updates a key-value pair. If the key already exists, it updates the value and moves the node to the front. If the key is new and the cache is at capacity, it evicts the least recently used item (the tail) before inserting the new item.
// Put adds or updates a key-value pair in the cache.
func (c *Cache) Put(key string, value interface{}) {
// If the key already exists, update the value and move to front.
if n, ok := c.items[key]; ok {
n.value = value
c.moveToFront(n)
return
}
// Create a new node.
n := &node{key: key, value: value}
// If at capacity, evict the least recently used item.
if len(c.items) >= c.capacity {
c.evict()
}
// Add the new node to the front and the map.
c.addToFront(n)
c.items[key] = n
}
// evict removes the least recently used item from the cache.
func (c *Cache) evict() {
if c.tail == nil {
return
}
delete(c.items, c.tail.key)
c.removeNode(c.tail)
}
Putting It All Together
Here is the complete implementation in a single file:
package lru
// node represents an entry in the doubly linked list.
type node struct {
key string
value interface{}
prev *node
next *node
}
// Cache represents an LRU cache with a fixed capacity.
type Cache struct {
capacity int
items map[string]*node
head *node
tail *node
}
// New creates a new LRU cache with the given capacity.
func New(capacity int) *Cache {
return &Cache{
capacity: capacity,
items: make(map[string]*node),
}
}
// Get retrieves a value from the cache.
func (c *Cache) Get(key string) (interface{}, bool) {
if n, ok := c.items[key]; ok {
c.moveToFront(n)
return n.value, true
}
return nil, false
}
// Put adds or updates a key-value pair in the cache.
func (c *Cache) Put(key string, value interface{}) {
if n, ok := c.items[key]; ok {
n.value = value
c.moveToFront(n)
return
}
n := &node{key: key, value: value}
if len(c.items) >= c.capacity {
c.evict()
}
c.addToFront(n)
c.items[key] = n
}
// Len returns the number of items currently in the cache.
func (c *Cache) Len() int {
return len(c.items)
}
// moveToFront moves an existing node to the front of the list.
func (c *Cache) moveToFront(n *node) {
c.removeNode(n)
c.addToFront(n)
}
// removeNode removes a node from the linked list.
func (c *Cache) removeNode(n *node) {
if n.prev != nil {
n.prev.next = n.next
} else {
c.head = n.next
}
if n.next != nil {
n.next.prev = n.prev
} else {
c.tail = n.prev
}
n.prev = nil
n.next = nil
}
// addToFront inserts a node at the front of the list.
func (c *Cache) addToFront(n *node) {
n.next = c.head
n.prev = nil
if c.head != nil {
c.head.prev = n
}
c.head = n
if c.tail == nil {
c.tail = n
}
}
// evict removes the least recently used item from the cache.
func (c *Cache) evict() {
if c.tail == nil {
return
}
delete(c.items, c.tail.key)
c.removeNode(c.tail)
}
Using the Cache in Practice
Let us write a small program to demonstrate how the cache works. We will create a cache with a capacity of 3 and perform a series of get and put operations to observe the eviction behavior.
package main
import (
"fmt"
"lru"
)
func main() {
cache := lru.New(3)
// Add three items.
cache.Put("a", 1)
cache.Put("b", 2)
cache.Put("c", 3)
// Access "a" to make it recently used.
val, ok := cache.Get("a")
fmt.Printf("Get(a) = %v, %v\n", val, ok)
// Add "d", which should evict "b" (the least recently used).
cache.Put("d", 4)
// "b" should no longer be in the cache.
val, ok = cache.Get("b")
fmt.Printf("Get(b) = %v, %v\n", val, ok)
// "c" should still be in the cache.
val, ok = cache.Get("c")
fmt.Printf("Get(c) = %v, %v\n", val, ok)
// "d" should be in the cache.
val, ok = cache.Get("d")
fmt.Printf("Get(d) = %v, %v\n", val, ok)
fmt.Println("Cache size:", cache.Len())
}
When you run this program, the output should be:
Get(a) = 1, true
Get(b) = <nil>, false
Get(c) = 3, true
Get(d) = 4, true
Cache size: 3
Notice that after accessing "a", the least recently used item became "b". When we inserted "d", the cache evicted "b" to make room, exactly as expected.
Making the Cache Thread-Safe
The implementation above is not safe for concurrent use. In production systems, caches are often accessed from multiple goroutines simultaneously. To make the cache thread-safe, we can wrap it with a mutex.
package lru
import "sync"
// SafeCache is a thread-safe wrapper around Cache.
type SafeCache struct {
mu sync.Mutex
cache *Cache
}
// NewSafe creates a new thread-safe LRU cache.
func NewSafe(capacity int) *SafeCache {
return &SafeCache{
cache: New(capacity),
}
}
// Get retrieves a value from the cache safely.
func (sc *SafeCache) Get(key string) (interface{}, bool) {
sc.mu.Lock()
defer sc.mu.Unlock()
return sc.cache.Get(key)
}
// Put adds or updates a key-value pair safely.
func (sc *SafeCache) Put(key string, value interface{}) {
sc.mu.Lock()
defer sc.mu.Unlock()
sc.cache.Put(key, value)
}
// Len returns the number of items in the cache safely.
func (sc *SafeCache) Len() int {
sc.mu.Lock()
defer sc.mu.Unlock()
return sc.cache.Len()
}
Using a sync.Mutex ensures that only one goroutine can access the cache at a time. If your workload is read-heavy, you can use sync.RWMutex instead, which allows multiple concurrent readers but exclusive writers.
Adding Eviction Callbacks
In many real-world applications, you want to perform cleanup work when an item is evicted from the cache. For example, you might want to close a file handle, decrement a reference count, or log the eviction. We can add an optional callback function to support this.
type EvictCallback func(key string, value interface{})
type Cache struct {
capacity int
items map[string]*node
head *node
tail *node
onEvict EvictCallback
}
func NewWithCallback(capacity int, onEvict EvictCallback) *Cache {
return &Cache{
capacity: capacity,
items: make(map[string]*node),
onEvict: onEvict,
}
}
func (c *Cache) evict() {
if c.tail == nil {
return
}
if c.onEvict != nil {
c.onEvict(c.tail.key, c.tail.value)
}
delete(c.items, c.tail.key)
c.removeNode(c.tail)
}
Here is how you would use the callback:
cache := lru.NewWithCallback(3, func(key string, value interface{}) {
fmt.Printf("Evicted: %s = %v\n", key, value)
})
Best Practices
Choose the Right Capacity
The capacity of your cache should be based on the available memory and the size of your cached values. A cache that is too small will have a high eviction rate and low hit ratio. A cache that is too large may consume excessive memory and cause pressure on the garbage collector. Monitor your cache hit ratio and adjust the capacity accordingly.
Measure Cache Hit Ratio
Always instrument your cache to track hits and misses. A low hit ratio means the cache is not effective, and you may need to increase capacity or reconsider your caching strategy. You can add simple counters to the cache:
type Cache struct {
capacity int
items map[string]*node
head *node
tail *node
hits int64
misses int64
}
func (c *Cache) Get(key string) (interface{}, bool) {
if n, ok := c.items[key]; ok {
c.hits++
c.moveToFront(n)
return n.value, true
}
c.misses++
return nil, false
}
func (c *Cache) Stats() (hits, misses int64) {
return c.hits, c.misses
}
Consider Using the Standard Library
If you do not need to implement the cache yourself, consider using the golang.org/x/crypto/internal/lru package or popular community libraries such as github.com/hashicorp/golang-lru. These libraries are well-tested and provide additional features like TTL-based expiration and sharded caches for better concurrency.
Use Generics for Type Safety
Since Go 1.18, you can use generics to make your cache type-safe. Instead of using interface{} for values, you can parameterize the cache with a type parameter:
type Cache[K comparable, V any] struct {
capacity int
items map[K]*node[K, V]
head *node[K, V]
tail *node[K, V]
}
type node[K comparable, V any] struct {
key K
value V
prev *node[K, V]
next *node[K, V]
}
func New[K comparable, V any](capacity int) *Cache[K, V] {
return &Cache[K, V]{
capacity: capacity,
items: make(map[K]*node[K, V]),
}
}
func (c *Cache[K, V]) Get(key K) (V, bool) {
var zero V
if n, ok := c.items[key]; ok {
c.moveToFront(n)
return n.value, true
}
return zero, false
}
This approach eliminates the need for type assertions and provides compile-time type safety, making your code cleaner and less error-prone.
Avoid Storing Large Values
If your cached values are large, consider storing pointers instead of copies. This reduces memory usage and speeds up the moveToFront operation, since Go does not need to copy large structs when reordering the linked list.
Conclusion
Implementing an LRU cache in Go is a great way to understand how combining a hash map with a doubly linked list can achieve O(1) time complexity for both reads and writes. In this tutorial, we built a complete LRU cache from scratch, made it thread-safe with mutexes, added eviction callbacks for cleanup, and explored best practices including cache instrumentation and generics. Whether you implement your own cache or use an existing library, understanding the internals will help you make better decisions about capacity tuning, concurrency, and eviction strategies in your applications.