Go Programming

Building a Thread-Safe LRU Cache in Go: Concurrency Patterns and Benchmarking Against sync.Map

By admin · May 29, 2026 · 33 views 🤖 AI
Gogolangconcurrencyperformancelru-cachesync-mapbenchmark

Concurrency is one of Go’s strongest selling points, but it introduces complexity when managing shared state. A common requirement in high-performance Go applications is an in-memory cache with Least Recently Used (LRU) eviction policy. While Go’s standard library offers sync.Map for concurrent key-value stores, it is not optimized for caching workloads. In this post, we will explore how to implement a robust, thread-safe LRU cache using a sync.Mutex and sync.Cond, and we will benchmark it against sync.Map to understand their respective trade-offs.

The Challenges of Shared State

An LRU cache requires two primary data structures: a doubly-linked list to maintain access order and a hash map for O(1) lookups. When multiple goroutines access this structure concurrently, race conditions can corrupt the list pointers or the map entries. The naive approach of using a global variable is unsafe. We need synchronization primitives that allow high throughput without creating bottlenecks.

There are two main architectural decisions here:

  • Coarse-grained locking: Using a single sync.Mutex protects the entire cache structure. This is simple to implement and usually sufficient for many use cases.
  • Fine-grained locking (Sharding): Dividing the cache into multiple segments, each with its own mutex, to reduce lock contention.

For this demonstration, we will focus on a clean, simple implementation using a single mutex, as it is often the most performant starting point for moderate-sized caches.

Implementing the Thread-Safe LRU Cache

Our implementation will wrap a doubly-linked list and a map. The sync.Mutex will ensure that operations like Get, Set, and Evict are atomic.

package lru

import (
    "container/list"
    "sync"
)

// Cache represents a thread-safe LRU cache.
type Cache struct {
    mu    sync.Mutex
    items map[string]*list.Element
    ll    *list.List
    maxSize int
}

// element stores the key and value in the linked list.
type element struct {
    key   string
    value interface{}
}

// New creates a new LRU cache with a specified maximum size.
func New(maxSize int) *Cache {
    return &Cache{
        items:   make(map[string]*list.Element),
        ll:      list.New(),
        maxSize: maxSize,
    }
}

// Get retrieves a value from the cache. If the key exists, it is moved to the front.
func (c *Cache) Get(key string) (interface{}, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if elem, ok := c.items[key]; ok {
        // Move to front (most recently used)
        c.ll.MoveToFront(elem)
        return elem.Value.(*element).value, true
    }
    return nil, false
}

// Set adds a key-value pair to the cache. If full, it evicts the least recently used item.
func (c *Cache) Set(key string, value interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()

    // Check if key already exists
    if elem, ok := c.items[key]; ok {
        c.ll.MoveToFront(elem)
        elem.Value.(*element).value = value
        return
    }

    // Evict if at capacity
    if c.ll.Len() >= c.maxSize {
        oldest := c.ll.Back()
        if oldest != nil {
            c.ll.Remove(oldest)
            delete(c.items, oldest.Value.(*element).key)
        }
    }

    // Add new item to front
    newElem := c.ll.PushFront(&element{key: key, value: value})
    c.items[key] = newElem
}

Benchmarking: sync.Mutex vs. sync.Map

Go’s sync.Map is optimized for specific use cases: when key sets are disjoint across goroutines, or when there are many more reads than writes. However, for a general-purpose cache with mixed read/write operations and frequent key updates, sync.Map often underperforms due to its internal complexity and memory overhead.

Let’s look at a conceptual benchmark scenario. We will simulate 100,000 concurrent reads and 10,000 writes.

package main

import (
    "testing"
    "sync"
)

func BenchmarkLRUCache(b *testing.B) {
    cache := New(10000)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        cache.Set(string(rune(i)), i)
    }
}

func BenchmarkSyncMap(b *testing.B) {
    var m sync.Map
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        m.Store(string(rune(i)), i)
    }
}

In typical benchmarks involving random key access and frequent updates, the mutex-based LRU cache outperforms sync.Map by a significant margin. sync.Map uses indirection and conditional locking internally, which adds latency. The standard mutex, especially with modern Go implementations (Go 1.12+), utilizes adaptive spinning and efficient futexes, making it highly efficient for short critical sections like our cache operations.

When to Use What?

Use the custom sync.Mutex LRU cache when:

  • You need strict eviction policies (LRU, LFU, FIFO).
  • Your workload involves mixed read/write patterns.
  • You want predictable memory usage and lower overhead.

Use sync.Map when:

  • You have static data that is rarely deleted.
  • Readers and writers operate on completely disjoint sets of keys.
  • You need a quick, no-overhead concurrent map without implementing eviction logic.

Conclusion

Building a thread-safe LRU cache in Go is a straightforward exercise in understanding synchronization primitives. While sync.Map is a powerful tool in the standard library, it is not a drop-in replacement for specialized caching structures. By implementing a custom cache with sync.Mutex, developers gain fine-grained control over eviction logic and often achieve better performance in general-purpose caching scenarios.

For production systems with extreme concurrency, consider sharding your cache or using established libraries like groupcache or bigcache. However, for most applications, the simple mutex-based approach provides the best balance of simplicity, performance, and control.

Share:
Related Posts