Building a High‑Performance LRU Cache in Go from Scratch

Why Caching Matters

Caching temporarily stores frequently accessed data to reduce latency, lower server load, and improve overall system performance, especially under high concurrency.

Cache Replacement Policies

Beyond the classic LRU (Least Recently Used) algorithm, other strategies include:

FIFO : Removes the earliest inserted item, simple but ignores access frequency.

LFU : Evicts the least frequently accessed item, better for skewed workloads but more complex.

ARC : IBM’s Adaptive Replacement Cache combines LRU and LFU, dynamically adjusting to workload patterns.

MRU : Removes the most recently used item, useful when recent data becomes stale quickly.

Designing a Go LRU Cache

Instead of using external frameworks such as Redis, Memcached, or Go libraries like go‑cache, bigcache, and ristretto, the article demonstrates how to implement a local LRU cache from the ground up.

Cache Interface Definition

type LRUCacheInterface[T any] interface {
    // Retrieve a value
    Get(key string) (value T, found bool)
    // Insert or update a value
    Put(key string, value T)
    // List all keys
    Keys() []string
    // Remove a specific key
    Remove(key string) bool
    // Clear the entire cache
    Clear()
    // Capacity of the cache
    Capacity() int
    // Current number of entries
    Len() int
}

Data Structures

The cache stores entries with the actual data and a timestamp for the last access, enabling quick identification of the least‑recently used item.

type cacheEntry[T any] struct {
    Data          T
    LastAccessed  time.Time
}

The main cache struct holds a fixed capacity, a map for O(1) lookups, and a linked list to maintain usage order.

type LRUCache[T any] struct {
    capacity int
    keyMap   map[string]*Node[cacheEntry[T]]
    list     LinkedList[cacheEntry[T]]
}

Linked List Support

type LinkedList[T any] interface {
    Head() *Node[T]
    Tail() *Node[T]
    Append(data T) *Node[T]
    Push(data T) *Node[T]
    Remove(node *Node[T]) *Node[T]
    RemoveTail() *Node[T]
    MoveToHead(node *Node[T])
}

type Node[T any] struct {
    Data T
    Prev *Node[T]
    Next *Node[T]
}

Cache Implementation

The concrete LRU cache implements the Get and Put methods, updating the linked list to reflect recent usage and evicting the tail when the capacity is exceeded.

func (l *lruCache[T]) Get(key string) (value T, found bool) {
    if node, ok := l.keyMap[key]; ok {
        l.list.MoveToHead(node)
        return node.Data.value, true
    }
    var zero T
    return zero, false
}

func (l *lruCache[T]) Put(key string, value T) {
    if node, ok := l.keyMap[key]; ok {
        node.Data = lruCacheEntry[T]{key: key, value: value}
        l.list.MoveToHead(node)
    } else {
        newNode := l.list.Push(lruCacheEntry[T]{key: key, value: value})
        l.keyMap[key] = newNode
    }
    if len(l.keyMap) > l.capacity {
        tail := l.list.RemoveTail()
        delete(l.keyMap, tail.Data.key)
    }
}

The Put method follows three steps: check for existing key and update, insert a new entry at the head if absent, and remove the least‑recently used entry when the cache exceeds its capacity.

Concurrency Safety

To make the cache safe for concurrent access, a sync.Mutex protects the critical sections. The example shows locking in the Get method; the same pattern can be applied to other operations.

func (l *lruCache[T]) Get(key string) (value T, found bool) {
    l.mutex.Lock()
    defer l.mutex.Unlock()
    if node, ok := l.keyMap[key]; ok {
        l.list.MoveToHead(node)
        return node.Data.value, true
    }
    var zero T
    return zero, false
}

Developers can extend this approach to lock finer‑grained sections or use sharded locks for higher throughput.