#483·ristretto

[FEATURE] Split global policy mutex into separate locks for tinyLFU and sampledLFU

Author: huynhanx03Created Mar 24, 2026Updated Aug 26, 2026
LabelsStale

Is your feature request related to a problem? Please describe

defaultPolicy uses a single sync.Mutex shared between tinyLFU (admission) and sampledLFU (eviction). All operations - Add, Del, Has, Cap, Update, Cost, Clear, and processItems - contend on this one lock.

This causes unnecessary contention:

  • processItems blocks on Add: The Add method holds the lock for the entire eviction loop (sampling, estimating, deleting victims). During this time, processItems cannot push frequency counters to tinyLFU.
  • Reads block on writes: Has, Cap, and Cost only read sampledLFU.keyCosts but acquire an exclusive lock, blocking all other operations.
  • Independent subsystems share a lock: Frequency counter updates (tinyLFU.Push) and eviction metadata updates (sampledLFU.add/del) rarely need mutual exclusion.

Describe the solution you'd like

Split into two locks:

go
type defaultPolicy[V any] struct {
    admitMu  sync.Mutex   // protects tinyLFU
    evictMu  sync.RWMutex // protects sampledLFU
    admit    *tinyLFU
    evict    *sampledLFU
    // ...
}

What changes:

Operation Before After
processItems (Push) Lock (global) admitMu.Lock only
Has, Cap, Cost Lock (global) evictMu.RLock
Del, Update Lock (global) evictMu.Lock
Add (eviction loop) Lock (global, held entire loop) evictMu.Lock + brief admitMu.Lock for Estimate

Lock ordering: admitMu before evictMu (or never hold both) to prevent deadlocks.

Describe alternatives you've considered

  1. Single sync.RWMutex: Helps reads but processItems and Add still contend on write lock.
  2. Reduce critical section in Add: Release/re-acquire between iterations. Adds complexity and potential inconsistency.
  3. Lock-free tinyLFU via atomics: 4-bit counters in count-min sketch make atomics awkward.

Additional context

  • processItems already runs in its own goroutine, so it naturally benefits from a separate lock.
  • getMaxCost/updateMaxCost already use atomic.LoadInt64/StoreInt64, consistent with fine-grained concurrency approach.