SLRU (Segmented LRU)

Feature: policy-slru

Goal

Reduce scan pollution by separating “probationary” entries from “protected” entries.

Core Idea

Maintain two LRU lists:

• Probationary segment: new or recently demoted entries
• Protected segment: entries that have proven reuse

Rules (typical):

• New inserts go to probationary MRU.
• On hit in probationary: promote to protected MRU.
• On hit in protected: move to protected MRU.
• Evict from probationary LRU first; if probationary is empty/too small, evict from protected LRU.

Core Data Structures

In cachekit, src/policy/slru.rs uses:

• HashMap<K, NonNull<Node<K,V>>> with segment membership + intrusive list pointers
• Two intrusive LRU lists (probationary and protected)
• Raw pointer-based doubly-linked lists for O(1) operations

Operations

get(key)

• Lookup key in index
• If in probationary: detach from probationary, attach to protected MRU
• If in protected: detach and reattach to protected MRU (move to front)
• Return value reference

insert(key, value)

• If key exists: update value in place, preserve segment position
• Else:
  • Evict if needed (from probationary LRU or protected LRU)
  • Create new node in probationary segment
  • Insert into index and attach to probationary MRU

Eviction Logic

• If probationary length > probationary_cap: evict from probationary LRU
• Otherwise: evict from protected LRU
• This ensures scan traffic stays in probationary and doesn’t pollute protected

Complexity & Overhead

• Lookup/update/evict: O(1)
• Memory: per-entry list pointers + hash entry + segment marker
• Slightly more overhead than plain LRU due to two lists and segment tracking

Tuning

Requires choosing sizes for probationary/protected partitions:

• Typical ratio: 25% probationary, 75% protected
• Higher probationary ratio: more tolerance for scans, but less protection for hot set
• Lower probationary ratio: stronger protection for hot set, but may evict useful items too quickly

Concurrency Notes

Like plain LRU, SLRU mutates shared metadata on every hit:

• Single lock around the entire structure (simple approach)
• Sharding (key->shard) for scalability
• Approximate approaches (Clock-based) when write-amplification is too high

cachekit’s SlruCore is designed for single-threaded use or external synchronization.

Safety / Invariants (Rust)

Uses intrusive pointers (NonNull<Node<_>>):

• Nodes allocated on heap (Box) for stable addresses
• Every pointer update preserves list invariants
• On eviction: detach from list, remove from map, then drop
• Drop implementation cleans up all nodes

When to Use

• Use SLRU when:
  • You have scan-heavy workloads that pollute plain LRU
  • You want simple scan resistance without complex frequency tracking
  • You can tolerate the tuning of probationary/protected ratio
• Avoid SLRU when:
  • Pure temporal locality (plain LRU is simpler and faster)
  • Need adaptive partitioning (use ARC or 2Q with ghost lists)
  • Metadata overhead is critical (use Clock or simpler policies)

Comparison with Other Policies

Policy	Segments	Adaptivity	Complexity
LRU	1	None	Low
SLRU	2	None	Medium
2Q	2 + ghost	Some	Medium
ARC	2 + 2 ghost	Full	High

SLRU sits between plain LRU and more complex adaptive policies like 2Q or ARC.

References

• Karedla et al., “Caching Strategies to Improve Disk System Performance”, Computer, 1994
• Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies