go-sharded-lru-eviction-race

Answer

Design. The cache is a hash map (key -> *list.Element) plus a doubly linked list ordered most-recently-used (front) to least-recently-used (back), the classic O(1)-amortized LRU layout. A single sync.Mutex serializes every operation. This is deliberate: the requirement "eviction must remove the least-recently-used key" plus an explicit recency-order assertion demands a global LRU. Naive sharded designs (per-shard maps/lists with per-shard capacities) break exact global LRU semantics — a key can be evicted from one shard while a globally older key survives in another shard — which is exactly the class of "eviction race" bugs this problem targets. With one lock, recency and eviction are exact, and race-freedom is structural (the race detector has nothing to find).

• Get: lock → map lookup → MoveToFront (refreshes recency) → return value, or (nil, false).
• Put: lock → if cap == 0, no-op (capacity 0 rejects all puts) → if key exists, update value in place (size unchanged) and move to front → else push front, insert in map, and if over capacity evict the back (LRU) entry.
• O(1) amortized: list moves are O(1), map ops are O(1) average.
• The stress test records every serialized op (appended under the same lock, so the log order is the serialization order) and replays it on an independently implemented O(n) reference LRU. Every Get result and the final state — including exact recency order — must match, proving the concurrent cache is equivalent to some valid serial execution.

package main

import (
    "container/list"
    "fmt"
    "math/rand"
    "os"
    "reflect"
    "sync"
    "sync/atomic"
    "time"
)

// entry is the value stored in the doubly-linked list: one per cached key.
type entry struct {
    key   any
    value any
}

// Op records one serialized cache operation; used by the linearizability
// replay check in main().
type Op struct {
    kind  byte // 'g' = Get, 'p' = Put
    key   any
    value any // Get: returned value; Put: stored value
    ok    bool // Get: found; Put: key already existed before this Put
}

// Cache is a concurrency-safe LRU cache with a fixed capacity N >= 0.
//
// Layout: a hash map from key to list element, plus a doubly linked list
// ordered most-recently-used (front) to least-recently-used (back).
// A single mutex serializes every operation, so eviction is a *global* LRU:
// the evicted key is always the true least-recently-used key and the cache
// is race-free by construction. Get/Put are O(1) amortized.
//
// Capacity 0 (or negative, treated as 0) rejects every Put.
type Cache struct {
    mu    sync.Mutex
    cap   int
    ll    *list.List
    items map[any]*list.Element

    log *[]Op // optional: append serialized ops (test hook, nil = off)
}

// NewCache returns a cache that stores at most capacity entries.
func NewCache(capacity int) *Cache {
    if capacity < 0 {
        capacity = 0
    }
    return &Cache{
        cap:   capacity,
        ll:    list.New(),
        items: make(map[any]*list.Element),
    }
}

// newRecordingCache returns a cache that appends every serialized operation
// to *log (used by the concurrent stress test for exact replay).
func newRecordingCache(capacity int, log *[]Op) *Cache {
    c := NewCache(capacity)
    c.log = log
    return c
}

// Get returns the value for key, or (nil, false) if key is absent.
// A successful Get refreshes the key's recency: it becomes the MRU entry.
func (c *Cache) Get(key any) (any, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()

    el, ok := c.items[key]
    if !ok {
        if c.log != nil {
            *c.log = append(*c.log, Op{kind: 'g', key: key})
        }
        return nil, false
    }
    c.ll.MoveToFront(el)
    e := el.Value.(*entry)
    if c.log != nil {
        *c.log = append(*c.log, Op{kind: 'g', key: key, value: e.value, ok: true})
    }
    return e.value, true
}

// Put inserts key with value, or updates the value if key is already cached
// (size unchanged; recency refreshed). When at capacity, the
// least-recently-used key is evicted. If capacity is 0, Put is a no-op.
func (c *Cache) Put(key any, value any) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if c.cap <= 0 {
        return // capacity 0: reject all puts
    }

    if el, ok := c.items[key]; ok {
        el.Value.(*entry).value = value
        c.ll.MoveToFront(el)
        if c.log != nil {
            *c.log = append(*c.log, Op{kind: 'p', key: key, value: value, ok: true})
        }
        return
    }

    el := c.ll.PushFront(&entry{key: key, value: value})
    c.items[key] = el
    if c.log != nil {
        *c.log = append(*c.log, Op{kind: 'p', key: key, value: value, ok: false})
    }
    if c.ll.Len() > c.cap {
        c.evictLRU()
    }
}

// evictLRU removes the least-recently-used entry. Caller holds c.mu.
func (c *Cache) evictLRU() {
    if back := c.ll.Back(); back != nil {
        c.ll.Remove(back)
        delete(c.items, back.Value.(*entry).key)
    }
}

// Len returns the number of cached entries.
func (c *Cache) Len() int {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.ll.Len()
}

// snapshot returns cached keys in recency order (MRU first) together with
// their values.
func (c *Cache) snapshot() (keys []any, values []any) {
    c.mu.Lock()
    defer c.mu.Unlock()
    for el := c.ll.Front(); el != nil; el = el.Next() {
        e := el.Value.(*entry)
        keys = append(keys, e.key)
        values = append(values, e.value)
    }
    return keys, values
}

// checkInvariants verifies that the map and list agree with each other and
// that no key is duplicated. Returns "" when consistent, else a description.
func (c *Cache) checkInvariants() string {
    c.mu.Lock()
    defer c.mu.Unlock()
    if len(c.items) != c.ll.Len() {
        return fmt.Sprintf("map size %d != list size %d", len(c.items), c.ll.Len())
    }
    seen := make(map[any]bool, len(c.items))
    for el := c.ll.Front(); el != nil; el = el.Next() {
        k := el.Value.(*entry).key
        if seen[k] {
            return fmt.Sprintf("duplicate key in list: %v", k)
        }
        seen[k] = true
        if _, ok := c.items[k]; !ok {
            return fmt.Sprintf("list key %v missing from map", k)
        }
    }
    for k := range c.items {
        if !seen[k] {
            return fmt.Sprintf("map key %v missing from list", k)
        }
    }
    return ""
}

// refLRU is an independent, intentionally simple LRU (O(n) per op, different
// structure: recency = position in a slice) used only to cross-check the
// concurrent cache: the recorded serialized op stream is replayed on it and
// every Get result plus the final state (including exact recency order) must
// match the real cache.
type refLRU struct {
    cap    int
    keys   []any // MRU first
    values map[any]any
}

func newRefLRU(cap int) *refLRU {
    return &refLRU{cap: cap, values: make(map[any]any)}
}

func indexOf(keys []any, key any) int {
    for i, k := range keys {
        if k == key {
            return i
        }
    }
    return -1
}

func (r *refLRU) moveToFront(key any) {
    i := indexOf(r.keys, key)
    if i <= 0 {
        return
    }
    copy(r.keys[1:i+1], r.keys[0:i])
    r.keys[0] = key
}

func (r *refLRU) get(key any) (any, bool) {
    v, ok := r.values[key]
    if !ok {
        return nil, false
    }
    r.moveToFront(key)
    return v, true
}

func (r *refLRU) put(key, value any) (existed bool) {
    if r.cap <= 0 {
        return false
    }
    if _, ok := r.values[key]; ok {
        existed = true
    } else {
        r.keys = append([]any{key}, r.keys...)
        if len(r.keys) > r.cap {
            lru := r.keys[len(r.keys)-1]
            r.keys = r.keys[:len(r.keys)-1]
            delete(r.values, lru)
        }
    }
    r.values[key] = value
    r.moveToFront(key)
    return existed
}

// ---- Test helpers ----------------------------------------------------------

func fail(format string, args ...any) {
    fmt.Fprintf(os.Stderr, "FAIL: "+format+"\n", args...)
    os.Exit(1)
}

func expectOrder(c *Cache, want ...any) {
    keys, _ := c.snapshot()
    if !reflect.DeepEqual(keys, want) {
        fail("recency order = %v, want %v", keys, want)
    }
}

func expectLen(c *Cache, want int) {
    if got := c.Len(); got != want {
        fail("Len() = %d, want %d", got, want)
    }
}

func expectValue(c *Cache, key, want any) {
    got, ok := c.Get(key)
    if !ok {
        fail("Get(%v) miss, want value %v", key, want)
    }
    if !reflect.DeepEqual(got, want) {
        fail("Get(%v) = %v, want %v", key, got, want)
    }
}

func expectMissing(c *Cache, key any) {
    if got, ok := c.Get(key); ok {
        fail("Get(%v) = (%v, true), want miss", key, got)
    }
}

// deterministicTests asserts exact recency order on a single thread:
// eviction removes the LRU key, Get refreshes recency, Put of an existing
// key updates the value without changing size, capacity 0 rejects puts.
func deterministicTests() {
    // T1: insertion order; back of the list is the LRU key.
    c := NewCache(3)
    c.Put("a", 1)
    c.Put("b", 2)
    c.Put("c", 3)
    expectOrder(c, "c", "b", "a")

    // T2: Get refreshes recency; a new Put evicts the true LRU key.
    c.Get("b")
    expectOrder(c, "b", "c", "a")
    c.Put("d", 4)
    expectLen(c, 3)
    expectOrder(c, "d", "b", "c")
    expectMissing(c, "a")
    expectValue(c, "d", 4)

    // T3: refreshing an old key keeps it alive; the real LRU is evicted.
    c2 := NewCache(3)
    c2.Put("a", 1)
    c2.Put("b", 2)
    c2.Put("c", 3)
    c2.Get("a")
    c2.Put("d", 4)
    expectOrder(c2, "d", "a", "c")
    expectMissing(c2, "b")

    // T4: Put of an existing key updates the value without changing size.
    c3 := NewCache(5)
    c3.Put("a", 1)
    c3.Put("b", 2)
    c3.Put("c", 3)
    c3.Put("a", 99)
    expectLen(c3, 3)
    expectOrder(c3, "a", "c", "b")
    expectValue(c3, "a", 99)

    // T5: repeated Gets change only recency, never size.
    c4 := NewCache(2)
    c4.Put("a", 1)
    c4.Put("b", 2)
    c4.Get("a")
    c4.Get("a")
    c4.Get("a")
    expectLen(c4, 2)
    expectOrder(c4, "a", "b")
    c4.Put("c", 3)
    expectOrder(c4, "c", "a")
    expectMissing(c4, "b")

    // T6: capacity 1 keeps only the most recent key.
    c5 := NewCache(1)
    c5.Put("a", 1)
    c5.Put("b", 2)
    expectLen(c5, 1)
    expectOrder(c5, "b")
    expectMissing(c5, "a")

    // T7: capacity 0 (and negative capacity) reject all puts.
    c6 := NewCache(0)
    c6.Put("x", 1)
    c6.Put("y", 2)
    expectLen(c6, 0)
    expectMissing(c6, "x")
    c7 := NewCache(-3)
    c7.Put("x", 1)
    expectLen(c7, 0)

    // T8: nil values are valid; missing keys return (nil, false).
    c8 := NewCache(10)
    expectMissing(c8, "zzz")
    c8.Put("k", nil)
    expectLen(c8, 1)
    v, ok := c8.Get("k")
    if !ok || v != nil {
        fail("Get(\"k\") = (%v, %v), want (nil, true)", v, ok)
    }

    // T9: internal map/list consistency after all the above.
    for _, cc := range []*Cache{c, c2, c3, c4, c5, c6, c7, c8} {
        if msg := cc.checkInvariants(); msg != "" {
            fail("invariants: %s", msg)
        }
    }
    fmt.Println("deterministic recency/eviction tests:        ok (T1-T9)")
}

// concurrentStress runs 64 goroutines x 10k random ops (70% Put / 30% Get,
// 20% of ops hammering a single hot key) and then verifies:
//   - operation counters are exact,
//   - size never exceeds capacity and map/list stay consistent,
//   - the concurrent run is linearizable: the serialized op stream replayed
//     on an independent reference LRU yields identical Get results and an
//     identical final state, including exact recency order.
func concurrentStress() {
    const (
        goroutines = 64
        opsPerG    = 10_000
        capacity   = 64
        poolSize   = 256
    )
    pool := make([]string, poolSize)
    for i := range pool {
        pool[i] = fmt.Sprintf("key%03d", i)
    }
    hot := "HOT-KEY"

    log := make([]Op, 0, goroutines*opsPerG)
    cache := newRecordingCache(capacity, &log)

    var wg sync.WaitGroup
    var seq atomic.Int64 // unique value per Put
    var puts, hits, misses atomic.Int64

    for g := 0; g < goroutines; g++ {
        wg.Add(1)
        go func(seed int64) {
            defer wg.Done()
            rng := rand.New(rand.NewSource(seed))
            for i := 0; i < opsPerG; i++ {
                var k string
                if rng.Intn(5) == 0 {
                    k = hot // 20% of ops contend on one key: update path stress
                } else {
                    k = pool[rng.Intn(poolSize)]
                }
                if rng.Intn(10) < 3 { // 30% Get / 70% Put
                    if _, ok := cache.Get(k); ok {
                        hits.Add(1)
                    } else {
                        misses.Add(1)
                    }
                } else {
                    puts.Add(1)
                    cache.Put(k, seq.Add(1))
                }
            }
        }(time.Now().UnixNano() + int64(g)*7919)
    }
    wg.Wait()

    wantOps := goroutines * opsPerG
    if got := puts.Load() + hits.Load() + misses.Load(); got != int64(wantOps) {
        fail("op counter = %d, want %d", got, wantOps)
    }
    if n := cache.Len(); n > capacity {
        fail("Len() = %d exceeds capacity %d", n, capacity)
    }
    if msg := cache.checkInvariants(); msg != "" {
        fail("concurrent invariants: %s", msg)
    }

    // Replay the recorded serialized op stream on the independent reference.
    ref := newRefLRU(capacity)
    for i, op := range log {
        switch op.kind {
        case 'g':
            v, ok := ref.get(op.key)
            if ok != op.ok || (ok && !reflect.DeepEqual(v, op.value)) {
                fail("replay mismatch at op %d: Get(%v) recorded (%v,%v), ref (%v,%v)",
                    i, op.key, op.value, op.ok, v, ok)
            }
        case 'p':
            if existed := ref.put(op.key, op.value); existed != op.ok {
                fail("replay mismatch at op %d: Put(%v) existed recorded %v, ref %v",
                    i, op.key, op.ok, existed)
            }
        default:
            fail("unknown op kind %q at op %d", op.kind, i)
        }
    }

    cKeys, cVals := cache.snapshot()
    rVals := make([]any, 0, len(ref.keys))
    for _, k := range ref.keys {
        rVals = append(rVals, ref.values[k])
    }
    if !reflect.DeepEqual(cKeys, ref.keys) || !reflect.DeepEqual(cVals, rVals) {
        fail("final state mismatch: cache order %v, ref order %v", cKeys, ref.keys)
    }

    fmt.Printf("concurrent stress (64 x 10k):                 ok (%d puts, %d hits, %d misses; %d ops replayed; final len=%d)\n",
        puts.Load(), hits.Load(), misses.Load(), len(log), cache.Len())
}

// zeroCapConcurrent hammers a capacity-0 cache from many goroutines:
// every Put must be rejected and Len must stay 0.
func zeroCapConcurrent() {
    c := NewCache(0)
    var wg sync.WaitGroup
    for g := 0; g < 16; g++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for i := 0; i < 100_000; i++ {
                c.Put(i, i)
                c.Get(i)
            }
        }()
    }
    wg.Wait()
    if c.Len() != 0 {
        fail("capacity-0 cache Len() = %d, want 0", c.Len())
    }
    if msg := c.checkInvariants(); msg != "" {
        fail("capacity-0 invariants: %s", msg)
    }
    fmt.Println("capacity-0 concurrent reject-all-puts:       ok")
}

// perfSmoke shows that operations scale linearly (O(1) amortized).
func perfSmoke() {
    const n = 1_000_000
    c := NewCache(1000)
    rng := rand.New(rand.NewSource(42))
    start := time.Now()
    for i := 0; i < n; i++ {
        k := rng.Int63n(5000)
        if i%4 == 0 {
            c.Get(k)
        } else {
            c.Put(k, i)
        }
    }
    elapsed := time.Since(start)
    fmt.Printf("perf smoke (1M ops, cap 1000):                %v (%.1f M ops/s) -> O(1) amortized\n",
        elapsed.Round(time.Millisecond), float64(n)/elapsed.Seconds()/1e6)
}

func main() {
    fmt.Println("=== go-sharded-lru-eviction-race: concurrency-safe LRU cache ===")
    deterministicTests()
    concurrentStress()
    zeroCapConcurrent()
    perfSmoke()
    fmt.Println()
    fmt.Println("ALL TESTS PASSED")
    fmt.Println("(race-detector clean: go run -race .)")
}