Describe how you would implement a thread-safe LRU cache in Go for a high-throughput service.

Question

Accepted Answer

import (
    "container/list"
    "sync"
)

type entry struct {
    key   string
    value interface{}
}

type LRUCache struct {
    capacity int
    mu       sync.RWMutex
    list     *list.List
    items    map[string]*list.Element
}

func NewLRUCache(cap int) *LRUCache {
    return &LRUCache{
        capacity: cap,
        list:     list.New(),
        items:    make(map[string]*list.Element, cap),
    }
}

func (c *LRUCache) Get(key string) (interface{}, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if el, ok := c.items[key]; ok {
        c.list.MoveToFront(el)
        return el.Value.(*entry).value, true
    }
    return nil, false
}

func (c *LRUCache) Set(key string, value interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if el, ok := c.items[key]; ok {
        c.list.MoveToFront(el)
        el.Value.(*entry).value = value
        return
    }
    if c.list.Len() >= c.capacity {
        oldest := c.list.Back()
        c.list.Remove(oldest)
        delete(c.items, oldest.Value.(*entry).key)
    }
    el := c.list.PushFront(&entry{key, value})
    c.items[key] = el
} Sharded locks: partition key space into N buckets, each with its own mutex — reduces contention sync.Map: suitable for read-heavy workloads with infrequent writes ristretto (DGraph): production-grade cache with TTL, admission policy, and metrics groupcache: distributed caching for multi-node setups Always benchmark with realistic concurrency before choosing between mutex and sync.Map

Describe how you would implement a thread-safe LRU cache in Go for a high-throughput service.

Combine a doubly linked list for O(1) eviction ordering with a hashmap for O(1) lookup, protected by a sync.RWMutex. For extreme throughput, use sharded locks or a library like ristretto.

Describe how you would implement a thread-safe LRU cache in Go for a high-throughput service.

Combine a doubly linked list for O(1) eviction ordering with a hashmap for O(1) lookup, protected by a sync.RWMutex. For extreme throughput, use sharded locks or a library like ristretto.

Scenario Questions

Follow-up Questions