Cache Eviction Algorithms: LRU-K, 2Q & Segmented LRU (SLRU) Implementation

When an in-memory cache reaches its maximum memory allocation, it must decide which key to evict to make room for newly requested data.

For decades, systems relied on Classic LRU (Least Recently Used).

However, classic LRU suffers from a critical vulnerability known as Scan Pollution.

A single sequential database table scan or batch report query reads millions of cold rows into memory once, pushing out all hot, frequently accessed application items.

To achieve Scan Resistance and optimize cache hit ratios under real-world workloads, modern storage engines (PostgreSQL, SQLite, Memcached, Caffeine) utilize advanced eviction algorithms: LRU-K, 2Q (Two-Queue), and Segmented LRU (SLRU).

This article details LRU-K $K$-th backward reference math, 2Q FIFO/LRU separation, and Segmented LRU probationary state transitions.

Cache Eviction & Scan Resistance Architecture

How Segmented LRU (SLRU) isolates cold single-access scan items from hot protected items:

Core Advanced Eviction Algorithms

1. Classic LRU Weakness (Scan Pollution): Classic LRU maintains a single doubly-linked list. Every read moves the requested key to the MRU (Most Recently Used) head. A single batch query reading $N$ un-cached items pushes all $N$ items to the head, evicting frequently accessed hot items to the tail.
2. LRU-K (O'Neil et al.):
   • Instead of tracking only the most recent access time, LRU-K tracks the timestamps of the last $K$ references to each key (typically $K=2$).
   • Eviction Metric: Computes the $K$-th Backward Reference Distance ($r(t, K) = t - t_{\text{last-}K}$). The algorithm evicts the key with the maximum backward distance.
   • Scan Resistance: Keys accessed only once have an infinite $K$-th distance ($r(t, K) = \infty$), ensuring they are evicted before hot items with finite 2nd-access distances.
3. 2Q (Two-Queue Eviction):
   • Approximates LRU-2 with $O(1)$ constant time complexity using two distinct queues:
     • A1in (FIFO Queue): Holds newly loaded keys accessed for the first time.
     • Am (LRU Queue): Holds keys that have been accessed multiple times.
   • Single-access scan keys pass through A1in and are evicted without ever polluting the main Am cache.
4. Segmented LRU (SLRU):
   • Splits total cache memory into two physical LRU segments:
     • Probationary Segment (e.g. 20% of capacity): Holds newly fetched items.
     • Protected Segment (e.g. 80% of capacity): Holds hot items that have received at least two access hits.
   • Items in the Protected Segment are shielded from eviction. If the Protected Segment fills up, evicted items are demoted back to the Probationary Segment.

Python Implementation: Segmented LRU (SLRU) Eviction Engine

Here is a production-grade Python implementation of a Segmented LRU (SLRU) Cache Engine featuring Probationary vs Protected segment state transitions:

from typing import Dict, Optional, Any
from pydantic import BaseModel

class SLRUNode:
    def __init__(self, key: str, value: Any):
        self.key = key
        self.value = value
        self.prev: Optional['SLRUNode'] = None
        self.next: Optional['SLRUNode'] = None

class LRUSegment:
    """Helper Doubly-Linked List + Hash Map LRU Segment."""
    def __init__(self, capacity: int, name: str):
        self.capacity = capacity
        self.name = name
        self.map: Dict[str, SLRUNode] = {}
        self.head = SLRUNode("", None) # Dummy Head
        self.tail = SLRUNode("", None) # Dummy Tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_head(self, node: SLRUNode):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def _remove(self, node: SLRUNode):
        node.prev.next = node.next
        node.next.prev = node.prev

    def get(self, key: str) -> Optional[SLRUNode]:
        if key in self.map:
            node = self.map[key]
            self._remove(node)
            self._add_head(node)
            return node
        return None

    def put_head(self, node: SLRUNode) -> Optional[SLRUNode]:
        """Inserts at MRU head. Returns evicted node if capacity exceeded."""
        if node.key in self.map:
            self._remove(self.map[node.key])

        self._add_head(node)
        self.map[node.key] = node

        if len(self.map) > self.capacity:
            # Evict Tail (LRU)
            lru_node = self.tail.prev
            self._remove(lru_node)
            del self.map[lru_node.key]
            return lru_node
        return None

    def remove_key(self, key: str) -> Optional[SLRUNode]:
        if key in self.map:
            node = self.map[key]
            self._remove(node)
            del self.map[key]
            return node
        return None

class SegmentedLRUCache:
    """
    Implements Segmented LRU (SLRU) with Probationary (20%) & Protected (80%) Segments.
    """
    def __init__(self, total_capacity: int = 10):
        prob_cap = max(1, int(total_capacity * 0.2))
        prot_cap = total_capacity - prob_cap

        self.probationary = LRUSegment(prob_cap, "Probationary")
        self.protected = LRUSegment(prot_cap, "Protected")
        print(f" ⚙️ [SLRU Init] Total Cap: {total_capacity} (Probationary: {prob_cap}, Protected: {prot_cap})")

    def get(self, key: str) -> Optional[Any]:
        # 1. Check Protected Segment
        node_prot = self.protected.get(key)
        if node_prot:
            print(f" 🎯 [SLRU HIT - Protected] Key '{key}' served from Protected Segment.")
            return node_prot.value

        # 2. Check Probationary Segment
        node_prob = self.probationary.remove_key(key)
        if node_prob:
            print(f" 🚀 [SLRU HIT - PROMOTION!] Key '{key}' accessed 2nd time -> Promoted to Protected Segment!")
            # Promote to Protected
            demoted_node = self.protected.put_head(node_prob)
            if demoted_node:
                print(f" ⚠️ [Protected Full] Demoting Key '{demoted_node.key}' back to Probationary Segment.")
                self.probationary.put_head(demoted_node)
            return node_prob.value

        print(f" 💥 [SLRU MISS] Key '{key}' not found in cache.")
        return None

    def put(self, key: str, value: Any):
        # Insert new items into Probationary Segment FIRST
        node = SLRUNode(key, value)
        evicted = self.probationary.put_head(node)
        print(f" 📥 [SLRU PUT] Key '{key}' inserted into Probationary Segment.")
        if evicted:
            print(f" 🗑️ [Probationary Full] Permanently Evicted Key '{evicted.key}'!")

# Demonstration Execution
if __name__ == "__main__":
    slru = SegmentedLRUCache(total_capacity=5) # 1 Prob, 4 Prot

    print("\n🚀 Demonstrating Segmented LRU (SLRU) & Scan Resistance...")
    print("=" * 75)

    # 1. Add Initial Keys
    slru.put("key_A", "Val_A")
    slru.put("key_B", "Val_B")

    # 2. Second Access to key_A -> Promotes to Protected!
    slru.get("key_A")

    # 3. Simulate Sequential DB Table Scan (Accessing cold scan keys once)
    print("\n🔥 Simulating Sequential Database Scan (Inserting Cold Scan Keys once):")
    slru.put("scan_1", "ColdData1")
    slru.put("scan_2", "ColdData2")
    slru.put("scan_3", "ColdData3")

    # 4. Verify Hot key_A is STILL SAFE in Protected Segment!
    print("\n🔍 Checking if Hot 'key_A' survived DB Scan:")
    val_A = slru.get("key_A")
    print(f"   • Hot Key A Status: {'SURVIVED SCAN!' if val_A else 'EVICTED'}")

Eviction Algorithm Gotchas & Best Practices

When tuning cache eviction policies:

Real-World Enterprise Impact

Databases and caching frameworks deploying SLRU / 2Q (such as PostgreSQL Buffer Pool, SQLite Page Cache, and Caffeine Cache) report:

• Over $30%$ Increase in Cache Hit Ratios: Preventing scan pollution keeps hot frequency data pinned in RAM during heavy background batch runs.
• $O(1)$ Constant Time Operations: 2Q and SLRU execute gets, puts, and promotions in constant time without locks.