Skip to content

lru.md

Latest commit

 

History

History
59 lines (44 loc) · 2.42 KB

lru.md

File metadata and controls

59 lines (44 loc) · 2.42 KB

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