Implement a Thread-Safe LRU Cache

Implement a Thread-Safe LRU Cache | DevPrep


┌─────────────────────────────────────────────────────────┐
│                      LRU Cache                          │
├─────────────────────────────────────────────────────────┤
│  HashMap: key -> *Node (O(1) lookup)                   │
│                                                         │
│  Doubly Linked List: (O(1) insert/remove)              │
│                                                         │
│  HEAD ←→ [MRU] ←→ [Node] ←→ [Node] ←→ [LRU] ←→ TAIL   │
│   ↑                                              ↑      │
│   Most Recently Used              Least Recently Used   │
└─────────────────────────────────────────────────────────┘

package lru

import (
    "container/list"
    "sync"
)

type entry struct {
    key   string
    value interface{}
}

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

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

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

func (c *LRUCache) Put(key string, value interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()
    
    // Update existing
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }
    
    // Evict if at capacity
    if c.list.Len() >= c.capacity {
        oldest := c.list.Back()
        if oldest != nil {
            c.list.Remove(oldest)
            delete(c.cache, oldest.Value.(*entry).key)
        }
    }
    
    // Insert new
    elem := c.list.PushFront(&entry{key: key, value: value})
    c.cache[key] = elem
}

func (c *LRUCache) Len() int {
    c.mu.RLock()
    defer c.mu.RUnlock()
    return c.list.Len()
}

func (c *LRUCache) Delete(key string) {
    c.mu.Lock()
    defer c.mu.Unlock()
    
    if elem, ok := c.cache[key]; ok {
        c.list.Remove(elem)
        delete(c.cache, key)
    }
}

func main() {
    cache := lru.NewLRUCache(3)
    
    cache.Put("a", 1)
    cache.Put("b", 2)
    cache.Put("c", 3)
    
    cache.Get("a") // Access "a", moves to front
    
    cache.Put("d", 4) // Evicts "b" (least recently used)
    
    _, ok := cache.Get("b")
    fmt.Println("b exists:", ok) // false
}

type ShardedLRU struct {
    shards    []*LRUCache
    numShards int
}

func NewShardedLRU(numShards, capacityPerShard int) *ShardedLRU {
    shards := make([]*LRUCache, numShards)
    for i := range shards {
        shards[i] = NewLRUCache(capacityPerShard)
    }
    return &ShardedLRU{shards: shards, numShards: numShards}
}

func (s *ShardedLRU) getShard(key string) *LRUCache {
    hash := fnv.New32a()
    hash.Write([]byte(key))
    return s.shards[hash.Sum32()%uint32(s.numShards)]
}

func (s *ShardedLRU) Get(key string) (interface{}, bool) {
    return s.getShard(key).Get(key)
}

Implement a Thread-Safe LRU Cache

Problem Statement

Requirements

Data Structure

Implementation

Usage Example

Performance Optimization: Sharded LRU

Follow-up Questions

Problem Statement

Requirements

Data Structure

Implementation

Usage Example

Performance Optimization: Sharded LRU

Follow-up Questions