Thread-Safe LRU

A single-threaded LRU is easy. Multi-threaded is hard. The simplest fix: a global lock.

Easy, but the lock becomes the bottleneck. Every cache operation serializes.

Alternatives:

Sharded LRU — split into N independent caches, each with its own lock. cache_for_key(k) = caches[hash(k) % N]. Lock contention drops by ~N. Used by Java's ConcurrentHashMap, Go's sync.Map.

Lock-free with CAS — atomic operations on the linked list pointers. Possible but very tricky; few production caches do this.

Read-mostly tradeoff — accept that cache hits don't immediately update LRU order. Use a separate eviction process. Used by Caffeine in Java: get is lock-free; recency is updated via a "ring buffer" log that's drained periodically.

For most apps, sharded LRU is the right answer. 16 shards = 16x lock contention reduction at minimal complexity cost.