LRU (Least Recently Used)

Feature: policy-lru

Goal

Evict the entry that has not been accessed for the longest time.

Core Data Structures

src/policy/lru.rs uses a pool-based design:

• SlotArena<Node<K, V>> — contiguous Vec with a free list for O(1) slot reuse. Each Node stores prev/next as Option<SlotId> indices, plus the key and Arc<V>.
• FxHashMap<K, SlotId> — O(1) key-to-slot lookup.
• head/tail: Option<SlotId> — doubly-linked recency order (head = MRU, tail = LRU).
• ConcurrentLruCache — thread-safe wrapper via parking_lot::RwLock.

At steady state (cache full), every insert evicts the tail node (returning its slot to the free list) then inserts the new node (reusing a free slot). No heap allocations occur after the initial warm-up phase.

Operations

get(key)

• Lookup key in map; if present: detach node, attach at head (MRU), return &Arc<V>.

insert(key, value)

• If key exists: replace value in-place, detach + attach at head.
• Else:
  • If at capacity: pop_tail() removes the LRU node from the arena (slot returned to free list), remove its key from the map.
  • arena.insert(Node{...}) reuses a free slot or appends.
  • Insert SlotId into the map, attach at head.

pop_lru()

• Remove tail node from arena + map, return (K, Arc<V>).

peek(key) / peek_lru()

• Read-only lookup; no list reordering.

Complexity & Overhead

• Lookup / update / evict: O(1)
• Memory per entry: SlotId prev/next (2 × 12 bytes) + key + Arc<V> + Option discriminant in arena slot
• Steady-state allocations: zero (free-list recycling)

Concurrency Notes

Strict global LRU mutates shared metadata on every hit; cachekit provides:

• ConcurrentLruCache — single RwLock around LruCore.
• get() requires a write lock (moves node to head).
• peek() requires only a read lock (no reordering).
• Read-heavy workloads can still contend on get(); prefer peek() when recency updates are not needed.

Safety / Invariants (Rust)

• No unsafe: all list manipulation uses SlotId indices into the arena.
• ABA prevention: SlotId includes a generation counter; stale handles return None.
• Automatic cleanup: SlotArena drops all live nodes when LruCore is dropped.
• Send/Sync auto-derive from the safe field types; no manual unsafe impl.

References

• Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies