[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:
processItemsblocks onAdd: TheAddmethod holds the lock for the entire eviction loop (sampling, estimating, deleting victims). During this time,processItemscannot push frequency counters totinyLFU.- Reads block on writes:
Has,Cap, andCostonly readsampledLFU.keyCostsbut 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:
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
- Single
sync.RWMutex: Helps reads butprocessItemsandAddstill contend on write lock. - Reduce critical section in
Add: Release/re-acquire between iterations. Adds complexity and potential inconsistency. - Lock-free tinyLFU via atomics: 4-bit counters in count-min sketch make atomics awkward.
Additional context
processItemsalready runs in its own goroutine, so it naturally benefits from a separate lock.getMaxCost/updateMaxCostalready useatomic.LoadInt64/StoreInt64, consistent with fine-grained concurrency approach.
Source: dgraph-io/ristretto