LRU Cache Design: Eviction Strategies and Trade-offs

Learn the classic LRU cache implementation, understand its limitations, and explore modern alternatives like LRU-K, 2Q, ARC, and SIEVE for building high-performance caching systems.

Abstract

Cache eviction is fundamentally a prediction problem: given limited memory, which items should be kept to maximize future hits? The core insight is that different access patterns require different prediction strategies.

The Trade-off Space:

Key Design Decisions:

1. Recency vs. Frequency: LRU assumes “recently used = soon needed.” This fails catastrophically during sequential scans. Solutions: filter first-time accesses (2Q), adapt dynamically (ARC), or use lazy promotion (SIEVE).

2. Exact vs. Approximated: True LRU requires O(1) linked list operations on every access. Approximated LRU (Redis, Linux) samples random keys, trading accuracy for throughput—often 95%+ as effective with better scalability.

3. Memory Overhead vs. Accuracy: Ghost lists (ARC) and history tracking (LRU-K) improve hit rates but consume memory. SIEVE achieves comparable results with just one bit per entry.

Mental Model: Think of cache eviction as a bouncer at a club with limited capacity. LRU removes whoever hasn’t been seen longest. 2Q makes newcomers wait in a probationary area. ARC keeps notes on who was wrongly kicked out and learns from mistakes. SIEVE marks regulars with a wristband and only evicts unmarked patrons.

The Classic: Understanding LRU

Least Recently Used (LRU) is a cache eviction policy based on a single assumption: recently accessed data is likely to be accessed again soon. This principle, called temporal locality, holds for many workloads—web browsing, file system access, database queries—making LRU the default choice for general-purpose caching.

Why LRU Works:

• Temporal locality is common: users revisit pages, code re-executes hot paths, queries repeat
• Simple mental model: recent = important, old = expendable
• No frequency tracking: avoids overhead of counting accesses

Why LRU Fails:

• Sequential scans: A full table scan evicts your entire working set with data you’ll never access again
• No frequency signal: An item accessed 1000 times gets evicted after one scan if it wasn’t touched recently
• One-shot pollution: Batch jobs, backups, and analytics queries poison the cache

LRU Implementation: Achieving O(1) Operations

A cache is only useful if it’s fast. Both get and put must be O(1)—anything slower defeats the purpose of caching. The challenge: tracking recency requires ordering, but maintaining sorted order is O(n) or O(log n).

The Classic Solution: Hash Map + Doubly Linked List

How Operations Work:

Why Doubly Linked List? A singly linked list requires O(n) to find the predecessor for unlinking. Doubly linked lists store prev and next pointers, enabling O(1) removal from any position.

Implementation 1: Utilizing JavaScript Map’s Insertion Order

9 collapsed lines
1
class LRUCache<K, V> {
2
  capacity: number
3
  cache: Map<K, V>
4

5
  constructor(capacity: number) {
6
    this.capacity = capacity
7
    this.cache = new Map()
8
  }
9

10
  get(key: K): V | null {
11
    if (!this.cache.has(key)) {
12
      return null
13
    } else {
14
      const value = this.cache.get(key)!
15
      // Remove and re-insert to move to end (most recently used)
16
      this.cache.delete(key)
17
      this.cache.set(key, value)
18
      return value
19
    }
20
  }
21

22
  put(key: K, value: V): void {
23
    if (this.cache.has(key)) {
24
      // Update existing key - remove and re-insert
25
      this.cache.delete(key)
26
    } else if (this.cache.size >= this.capacity) {
27
      // Remove least recently used (first key in Map)
28
      const keyToRemove = this.cache.keys().next().value
29
      this.cache.delete(keyToRemove)
30
    }
31
    this.cache.set(key, value)
32
  }
33
}

Implementation 2: Classic Doubly Linked List & Hash Map

1
class LRUCache {
2
  capacity: number
3
  cache: Map<number, ListNode>
4
  list: DoublyLinkedList
5

6
  constructor(capacity: number) {
7
    this.capacity = capacity
8
    this.cache = new Map()
9
    this.list = new DoublyLinkedList()
10
  }
11

12
  get(key: number): number {
13
    if (!this.cache.has(key)) {
14
      return -1
15
    } else {
16
      const node = this.cache.get(key)!
17
      // Move to head (most recently used)
18
      this.list.removeNode(node)
19
      this.list.addToHead(node)
20
      return node.value
21
    }
22
  }
23

24
  put(key: number, value: number): void {
25
    if (this.cache.has(key)) {
26
      // Update existing key
27
      const node = this.cache.get(key)!
28
      node.value = value
29
      this.list.removeNode(node)
30
      this.list.addToHead(node)
31
    } else {
32
      if (this.cache.size >= this.capacity) {
33
        // Remove least recently used (tail)
34
        const removed = this.list.removeTail()
35
        if (removed) {
36
          this.cache.delete(removed.key)
37
        }
38
      }
39
      const node = new ListNode(key, value)
40
      this.list.addToHead(node)
41
      this.cache.set(key, node)
42
    }
43
  }
44
}
45

61 collapsed lines
46
class ListNode {
47
  key: number
48
  value: number
49
  prev: ListNode | null
50
  next: ListNode | null
51

52
  constructor(key: number, value: number) {
53
    this.key = key
54
    this.value = value
55
    this.prev = null
56
    this.next = null
57
  }
58
}
59

60
class DoublyLinkedList {
61
  head: ListNode | null
62
  tail: ListNode | null
63

64
  constructor() {
65
    this.head = null
66
    this.tail = null
67
  }
68

69
  addToHead(node: ListNode): void {
70
    node.next = this.head
71
    if (this.head) {
72
      this.head.prev = node
73
    }
74
    this.head = node
75
    if (!this.tail) {
76
      this.tail = node
77
    }
78
  }
79

80
  removeNode(node: ListNode): void {
81
    if (node === this.head) {
82
      this.head = node.next
83
    } else if (node === this.tail) {
84
      this.tail = node.prev
85
    } else {
86
      if (node.prev) node.prev.next = node.next
87
      if (node.next) node.next.prev = node.prev
88
    }
89
  }
90

91
  removeTail(): ListNode | null {
92
    if (this.tail) {
93
      const removed = this.tail
94
      if (this.head === this.tail) {
95
        this.head = null
96
        this.tail = null
97
      } else {
98
        this.tail = this.tail.prev
99
        if (this.tail) {
100
          this.tail.next = null
101
        }
102
      }
103
      return removed
104
    }
105
    return null
106
  }
107
}

When LRU Fails: The Scan Problem

LRU equates “recently used” with “important”—an assumption that breaks catastrophically during sequential scans.

The Failure Mechanism:

1
Before scan: Cache contains hot items A, B, C, D (frequently accessed)
2
During scan: Items 1, 2, 3, 4... sequentially accessed
3
After scan:  Cache contains cold items (last N scanned), hot items evicted
4
Result:      Miss storm as application reloads working set

Why This Matters:

• A single SELECT * FROM large_table can destroy hours of cache warmup
• Background jobs (backups, ETL, analytics) poison production caches
• The scan data is never accessed again, but it displaced data that would have been

Quantifying the Impact:

In a cache with 10,000 entries holding a working set with 95% hit rate:

• A 50,000-item sequential scan evicts the entire working set
• Hit rate drops to ~0% until the working set is reloaded
• If working set reload takes 100ms per item, that’s 1,000 seconds of degraded performance

Common LRU Failure Scenarios

Design Choices: Scan-Resistant Algorithms

To overcome LRU’s scan vulnerability, several algorithms incorporate additional signals beyond recency. Each makes different trade-offs between complexity, memory overhead, and adaptivity.

LRU-K: History-Based Filtering

Mechanism: Track the timestamps of the last K accesses per item. Evict based on the K-th most recent access time, not the most recent.

Why It Works: Items accessed only once (scan data) have no K-th access time and are evicted first. Items with K accesses have proven popularity.

Best When:

• Database buffer pools with mixed OLTP/OLAP workloads
• Workloads where frequency is a better predictor than recency
• K can be tuned for the specific access pattern (typically K=2)

Trade-offs:

• ✅ Scan-resistant: single-access items evicted quickly
• ✅ Frequency-aware: distinguishes truly popular items
• ✅ LRU-1 degenerates to standard LRU (backward compatible)
• ❌ Requires K timestamps per entry (memory overhead)
• ❌ K parameter needs tuning (workload-dependent)
• ❌ Naive eviction is O(n); requires heap for O(log n)

Real-World Example: The original LRU-K paper (O’Neil et al., 1993) demonstrated that LRU-2 improved buffer hit rates by 5-20% over LRU on database workloads with mixed sequential and random access patterns.

10 collapsed lines
1
class LRUKCache {
2
  capacity: number
3
  k: number
4
  cache: Map<number, { value: number; accessTimes: number[] }>
5

6
  constructor(capacity: number, k: number = 2) {
7
    this.capacity = capacity
8
    this.k = k
9
    this.cache = new Map()
10
  }
11

12
  get(key: number): number {
13
    if (!this.cache.has(key)) {
14
      return -1
15
    }
16

17
    const item = this.cache.get(key)!
18
    const now = Date.now()
19

20
    // Add current access time
21
    item.accessTimes.push(now)
22

23
    // Keep only the last K access times
24
    if (item.accessTimes.length > this.k) {
25
      item.accessTimes.shift()
26
    }
27

28
    return item.value
29
  }
30

31
  put(key: number, value: number): void {
32
    const now = Date.now()
33

34
    if (this.cache.has(key)) {
35
      const item = this.cache.get(key)!
36
      item.value = value
37
      item.accessTimes.push(now)
38
      if (item.accessTimes.length > this.k) {
39
        item.accessTimes.shift()
40
      }
41
    } else {
42
      if (this.cache.size >= this.capacity) {
43
        this.evictLRU()
44
      }
30 collapsed lines
45
      this.cache.set(key, { value, accessTimes: [now] })
46
    }
47
  }
48

49
  private evictLRU(): void {
50
    let oldestTime = Infinity
51
    let keyToEvict = -1
52

53
    for (const [key, item] of this.cache) {
54
      if (item.accessTimes.length < this.k) {
55
        // Items with fewer than K accesses are evicted first
56
        if (item.accessTimes[0] < oldestTime) {
57
          oldestTime = item.accessTimes[0]
58
          keyToEvict = key
59
        }
60
      } else {
61
        // For items with K+ accesses, use K-th most recent access
62
        const kthAccess = item.accessTimes[item.accessTimes.length - this.k]
63
        if (kthAccess < oldestTime) {
64
          oldestTime = kthAccess
65
          keyToEvict = key
66
        }
67
      }
68
    }
69

70
    if (keyToEvict !== -1) {
71
      this.cache.delete(keyToEvict)
72
    }
73
  }
74
}

Time Complexity Note: The implementation above has O(n) time complexity for eviction due to the linear scan through all cache entries in evictLRU(). For true O(1) operations, you would need:

• Min-Heap Approach: Use a min-heap ordered by K-th access time, achieving O(log n) eviction
• Approximation Approach: Sample random entries instead of scanning all (trading accuracy for speed)
• Hybrid Approach: Maintain sorted structure with periodic rebalancing

In practice, the O(n) eviction complexity is acceptable for small to medium cache sizes (< 10,000 entries), and the simpler implementation reduces bugs and maintenance overhead. For larger caches, production systems typically use approximated LRU-K with sampling.

2Q: Probationary Filtering

Mechanism: Use two queues to filter first-time accesses before admitting to the main cache.

Why It Works: Sequential scan data enters A1, gets evicted from A1 (never touching Am), and the main cache remains unpolluted. Only items accessed twice make it to Am.

Best When:

• Production databases needing scan resistance (PostgreSQL used 2Q in 8.0.1-8.0.2)
• Systems requiring O(1) operations without tuning parameters
• Patent-free implementations required (no patent on 2Q)

Trade-offs:

• ✅ True O(1) operations (no heap, no timestamps)
• ✅ Simple to implement and debug
• ✅ Excellent scan resistance
• ✅ No patents
• ❌ Fixed queue sizes may not adapt to workload changes
• ❌ Requires tuning A1/Am size ratio (typically 25%/75%)
• ❌ Ghost list (A1out) adds memory overhead

Real-World Example: PostgreSQL briefly used 2Q in versions 8.0.1-8.0.2 after discovering the ARC patent issue. The PostgreSQL developers found 2Q provided comparable performance to ARC without legal concerns. They later moved to clock sweep in 8.1 for better concurrency characteristics.

18 collapsed lines
1
class TwoQueueCache {
2
  capacity: number
3
  a1Size: number
4
  amSize: number
5

6
  // A1: probationary queue (FIFO) - uses Map insertion order
7
  a1: Map<number, number>
8

9
  // Am: main cache (LRU) - uses Map insertion order with re-insertion on access
10
  am: Map<number, number>
11

12
  constructor(capacity: number) {
13
    this.capacity = capacity
14
    this.a1Size = Math.floor(capacity * 0.25) // 25% for probationary
15
    this.amSize = capacity - this.a1Size
16
    this.a1 = new Map()
17
    this.am = new Map()
18
  }
19

20
  get(key: number): number {
21
    // Check main cache first (LRU: re-insert to move to end)
22
    if (this.am.has(key)) {
23
      const value = this.am.get(key)!
24
      this.am.delete(key)
25
      this.am.set(key, value)
26
      return value
27
    }
28

29
    // Check probationary queue
30
    if (this.a1.has(key)) {
31
      const value = this.a1.get(key)!
32
      // Promote to main cache
33
      this.a1.delete(key)
34
      this.am.set(key, value)
35

36
      // Ensure main cache doesn't exceed capacity
37
      if (this.am.size > this.amSize) {
38
        this.evictFromAm()
39
      }
40

41
      return value
42
    }
43

44
    return -1
45
  }
46

47
  put(key: number, value: number): void {
48
    // If already in main cache, update (LRU: re-insert)
49
    if (this.am.has(key)) {
50
      this.am.delete(key)
51
      this.am.set(key, value)
52
      return
53
    }
54

55
    // If in probationary queue, promote to main cache
56
    if (this.a1.has(key)) {
57
      this.a1.delete(key)
58
      this.am.set(key, value)
59

60
      if (this.am.size > this.amSize) {
61
        this.evictFromAm()
62
      }
63
      return
64
    }
65

66
    // New item goes to probationary queue (FIFO)
67
    this.a1.set(key, value)
68

69
    if (this.a1.size > this.a1Size) {
16 collapsed lines
70
      this.evictFromA1()
71
    }
72
  }
73

74
  private evictFromA1(): void {
75
    // Remove oldest item from A1 (FIFO - first key in Map)
76
    const oldestKey = this.a1.keys().next().value
77
    if (oldestKey !== undefined) {
78
      this.a1.delete(oldestKey)
79
    }
80
  }
81

82
  private evictFromAm(): void {
83
    // Remove least recently used from Am (LRU - first key in Map)
84
    const oldestKey = this.am.keys().next().value
85
    if (oldestKey !== undefined) {
86
      this.am.delete(oldestKey)
87
    }
88
  }
89
}

Implementation Note: This implementation achieves true O(1) operations by leveraging JavaScript Map’s guaranteed insertion order (ES2015+). The A1 queue uses FIFO semantics (oldest = first inserted = first key), while Am uses LRU semantics (re-insert on access moves to end, evict from beginning).

ARC: Adaptive Self-Tuning

Mechanism: Maintain two LRU lists (T1 for recency, T2 for frequency) with adaptive sizing based on “ghost lists” that remember recently evicted keys.

The Learning Rule:

• Hit in B1 → “We shouldn’t have evicted that recent item” → Increase T1 size
• Hit in B2 → “We shouldn’t have evicted that frequent item” → Increase T2 size
• Parameter p controls the T1/T2 split and adapts continuously

Why It Works: The ghost lists act as a feedback mechanism. ARC learns from its eviction mistakes and automatically adjusts the recency/frequency balance for the current workload.

Best When:

• Workloads with unpredictable or shifting access patterns
• Systems where self-tuning eliminates operational burden
• ZFS (uses ARC for its Adjustable Replacement Cache)

Trade-offs:

• ✅ Self-tuning: no parameters to configure
• ✅ Handles mixed workloads dynamically
• ✅ Ghost lists provide learning without storing values
• ✅ Patent expired February 22, 2024 (US6996676B2) — now freely usable
• ❌ Memory overhead: 4 data structures + ghost lists can equal cache size
• ❌ More complex to implement and debug
• ❌ Ghost list maintenance adds CPU overhead

Patent History and Industry Impact:

ARC was developed by Nimrod Megiddo and Dharmendra S. Modha at IBM Almaden Research Center. The patent (US6996676B2, filed November 14, 2002, granted February 7, 2006) had significant industry implications:

Real-World Example: ZFS has used ARC since its inception (2005) through Sun’s cross-licensing agreement with IBM. ZFS extended ARC with L2ARC for SSD caching, demonstrating that the adaptive approach works well for storage systems with mixed sequential/random workloads.

21 collapsed lines
1
class ARCCache {
2
  capacity: number
3
  p: number // Adaptation parameter
4

5
  // Main cache lists
6
  t1: Map<number, { value: number; timestamp: number }> // Recently accessed once
7
  t2: Map<number, { value: number; timestamp: number }> // Recently accessed multiple times
8

9
  // Ghost lists (keys only)
10
  b1: Set<number> // Recently evicted from T1
11
  b2: Set<number> // Recently evicted from T2
12

13
  constructor(capacity: number) {
14
    this.capacity = capacity
15
    this.p = 0
16
    this.t1 = new Map()
17
    this.t2 = new Map()
18
    this.b1 = new Set()
19
    this.b2 = new Set()
20
  }
21

22
  get(key: number): number {
23
    // Check T1
24
    if (this.t1.has(key)) {
25
      const item = this.t1.get(key)!
26
      this.t1.delete(key)
27
      this.t2.set(key, { value: item.value, timestamp: Date.now() })
28
      return item.value
29
    }
30

31
    // Check T2
32
    if (this.t2.has(key)) {
33
      const item = this.t2.get(key)!
34
      item.timestamp = Date.now()
35
      return item.value
36
    }
37

38
    // Check ghost lists for adaptation
39
    if (this.b1.has(key)) {
40
      this.adapt(true) // Increase T1 size
41
      this.b1.delete(key)
42
    } else if (this.b2.has(key)) {
43
      this.adapt(false) // Increase T2 size
44
      this.b2.delete(key)
45
    }
46

47
    return -1
48
  }
49

50
  put(key: number, value: number): void {
51
    // If already in cache, update
52
    if (this.t1.has(key)) {
53
      const item = this.t1.get(key)!
54
      this.t1.delete(key)
55
      this.t2.set(key, { value, timestamp: Date.now() })
56
      return
57
    }
58

59
    if (this.t2.has(key)) {
60
      this.t2.set(key, { value, timestamp: Date.now() })
61
      return
62
    }
63

64
    // New item goes to T1
65
    this.t1.set(key, { value, timestamp: Date.now() })
66

67
    // Ensure capacity constraints
69 collapsed lines
68
    this.ensureCapacity()
69
  }
70

71
  private adapt(increaseT1: boolean): void {
72
    if (increaseT1) {
73
      this.p = Math.min(this.p + 1, this.capacity)
74
    } else {
75
      this.p = Math.max(this.p - 1, 0)
76
    }
77
  }
78

79
  private ensureCapacity(): void {
80
    const totalSize = this.t1.size + this.t2.size
81

82
    if (totalSize <= this.capacity) {
83
      return
84
    }
85

86
    // Calculate target sizes
87
    const targetT1 = Math.min(this.p, this.capacity)
88
    const targetT2 = this.capacity - targetT1
89

90
    // Evict from T1 if needed
91
    while (this.t1.size > targetT1) {
92
      const oldestKey = this.getOldestKey(this.t1)
93
      if (oldestKey !== null) {
94
        const item = this.t1.get(oldestKey)!
95
        this.t1.delete(oldestKey)
96
        this.b1.add(oldestKey)
97

98
        // Limit ghost list size
99
        if (this.b1.size > this.capacity) {
100
          const firstKey = this.b1.values().next().value
101
          this.b1.delete(firstKey)
102
        }
103
      }
104
    }
105

106
    // Evict from T2 if needed
107
    while (this.t2.size > targetT2) {
108
      const oldestKey = this.getOldestKey(this.t2)
109
      if (oldestKey !== null) {
110
        const item = this.t2.get(oldestKey)!
111
        this.t2.delete(oldestKey)
112
        this.b2.add(oldestKey)
113

114
        // Limit ghost list size
115
        if (this.b2.size > this.capacity) {
116
          const firstKey = this.b2.values().next().value
117
          this.b2.delete(firstKey)
118
        }
119
      }
120
    }
121
  }
122

123
  private getOldestKey(map: Map<number, { value: number; timestamp: number }>): number | null {
124
    let oldestKey = null
125
    let oldestTime = Infinity
126

127
    for (const [key, item] of map) {
128
      if (item.timestamp < oldestTime) {
129
        oldestTime = item.timestamp
130
        oldestKey = key
131
      }
132
    }
133

134
    return oldestKey
135
  }
136
}

SIEVE: Lazy Promotion (NSDI’24)

Mechanism: Maintain a single FIFO queue with one “visited” bit per entry and a “hand” pointer for eviction.

1
Queue: [A*] [B] [C*] [D*] [E] ← hand points here
2
       *=visited bit set
3

4
On hit:  Set visited bit (no list manipulation)
5
On miss: Move hand from tail, reset visited bits, evict first unvisited item

Why It Works:

• Items accessed multiple times have their visited bit set and survive the hand sweep
• Scan data enters, never gets revisited, and is evicted on the first hand pass
• No list manipulation on hits = better cache locality and concurrency

Best When:

• Web caches with high throughput requirements
• Systems where lock contention is a concern
• Workloads where items tend to be accessed in bursts

Trade-offs:

• ✅ Simpler than LRU (no list manipulation on hits)
• ✅ Better throughput (fewer memory operations)
• ✅ One bit per entry (minimal memory overhead)
• ✅ Outperforms LRU on 45%+ of web cache traces
• ❌ Less effective for very short TTLs (items may be evicted before hand reaches them)
• ❌ Newer algorithm (2024), less battle-tested than LRU/2Q/ARC

Real-World Example: SIEVE (Zhang et al., NSDI’24) was evaluated on 1,559 traces containing 247 billion requests. It reduces miss ratio by 21% on average compared to FIFO and has been adopted by production systems including TiDB and Pelikan (Twitter’s cache).

8 collapsed lines
1
class SIEVECache<K, V> {
2
  capacity: number
3
  cache: Map<K, { value: V; visited: boolean }>
4
  order: K[] // FIFO order
5
  hand: number // Eviction pointer
6

7
  constructor(capacity: number) {
8
    this.capacity = capacity
9
    this.cache = new Map()
10
    this.order = []
11
    this.hand = 0
12
  }
13

14
  get(key: K): V | null {
15
    const entry = this.cache.get(key)
16
    if (!entry) return null
17

18
    // Lazy promotion: just set the visited bit (no list manipulation)
19
    entry.visited = true
20
    return entry.value
21
  }
22

23
  put(key: K, value: V): void {
24
    if (this.cache.has(key)) {
25
      const entry = this.cache.get(key)!
26
      entry.value = value
27
      entry.visited = true
28
      return
29
    }
30

31
    // Evict if at capacity
32
    while (this.cache.size >= this.capacity) {
33
      this.evict()
34
    }
26 collapsed lines
35

36
    // Insert at head (newest position)
37
    this.cache.set(key, { value, visited: false })
38
    this.order.unshift(key)
39
  }
40

41
  private evict(): void {
42
    // Move hand from tail toward head, looking for unvisited item
43
    while (this.order.length > 0) {
44
      // Wrap around if needed
45
      if (this.hand >= this.order.length) {
46
        this.hand = this.order.length - 1
47
      }
48

49
      const key = this.order[this.hand]
50
      const entry = this.cache.get(key)
51

52
      if (!entry) {
53
        // Key was deleted externally
54
        this.order.splice(this.hand, 1)
55
        continue
56
      }
57

58
      if (entry.visited) {
59
        // Give it another chance, reset visited bit
60
        entry.visited = false
61
        this.hand--
62
        if (this.hand < 0) this.hand = this.order.length - 1
63
      } else {
64
        // Evict this item
65
        this.cache.delete(key)
66
        this.order.splice(this.hand, 1)
67
        return
68
      }
69
    }
70
  }
71
}

Window TinyLFU (Caffeine)

Mechanism: Combine a small “window” LRU cache (1%) with a large “main” cache (99%) using frequency-based admission filtering.

1
Request → Window (1%) → Admission Filter → Main Cache (99%)
2
                              ↓
3
                    CountMinSketch (frequency estimate)

Why It Works:

• Window cache handles burst traffic (recency)
• Main cache uses segmented LRU (protected + probationary)
• Admission filter blocks low-frequency items from polluting main cache
• 4-bit CountMinSketch provides frequency estimates with minimal memory

Best When:

• High-throughput Java applications
• Workloads with skewed popularity distributions
• Systems needing near-optimal hit rates with bounded memory

Trade-offs:

• ✅ Near-optimal hit rates (within 1% of theoretical best)
• ✅ Only 8 bytes overhead per entry (vs. ARC’s doubled cache size for ghosts)
• ✅ Battle-tested (Caffeine is the standard Java cache library)
• ❌ More complex than simpler algorithms
• ❌ Requires frequency decay mechanism (adds CPU overhead)
• ❌ Java-specific reference implementation

Real-World Example: Caffeine’s W-TinyLFU achieves 39.6% hit rate on benchmark traces where ARC achieves 20% and the theoretical optimal is 40.3%. The key insight: don’t track evicted keys (like ARC’s ghost lists) — use probabilistic frequency counting instead.

How to Choose

Decision Matrix

Choosing by Workload Pattern

Common Decision Patterns

“I just need a cache, nothing special” → Start with LRU. It’s simple, well-understood, and works for most workloads.

“Full table scans are killing my cache” → Use 2Q. It filters scan data effectively with O(1) operations and no patents.

“My workload keeps changing” → Use ARC. It adapts automatically and the patent expired in 2024.

“I need maximum throughput” → Use SIEVE. No list manipulation on hits means better CPU cache locality.

“I’m building a CDN or web cache” → Use W-TinyLFU (Caffeine) or SIEVE. Both handle popularity skew well.

Real-World Applications

The choice of algorithm has profound, practical implications across different domains.

Memory Overhead Analysis

Memory overhead determines how much of your allocated cache space actually holds data vs. metadata.

Key Insight: ARC’s ghost lists can grow to equal the cache size (storing evicted keys), effectively doubling memory usage for metadata. Caffeine’s W-TinyLFU solved this by using probabilistic frequency counting instead of ghost lists—same accuracy, fraction of the memory.

Production Implementations

Real-world systems often use approximated or specialized variants of these algorithms, optimized for their specific constraints.

Redis: Approximated LRU

Redis uses random sampling instead of tracking exact recency for all keys.

Mechanism:

1. Sample N random keys (default: 5, configurable via maxmemory-samples)
2. Evict the least recently used among the sampled keys
3. Repeat until memory is below threshold

Why This Design:

• No linked list = no pointer overhead per key (just 24 bits for LRU clock)
• No lock contention from list manipulation
• Sampling 10 keys provides ~95% of true LRU accuracy

1
# Redis configuration
2
maxmemory-policy allkeys-lru
3
maxmemory-samples 5   # Increase to 10 for near-true LRU accuracy

As of Redis 3.0: Uses a pool of good eviction candidates that persists across eviction cycles, improving accuracy without increasing per-key memory.

Linux Kernel: MGLRU

The Linux kernel evolved from a two-list approach to Multi-Generational LRU.

MGLRU (merged in Linux 6.1, backported to some 5.x kernels):

• Multiple generations (typically 4) instead of 2 lists
• Pages move to younger generations when accessed
• Workload-aware: adapts scan frequency to access patterns

Google’s deployment results (Chrome OS + Android):

• 40% decrease in kswapd CPU usage
• 85% decrease in low-memory kill events
• 18% decrease in rendering latency

Distribution Support: Enabled by default in Fedora and Arch Linux. Available but not default in Ubuntu and Debian.

Memcached: Segmented LRU

Memcached uses per-slab-class LRU with modern segmentation.

Slab Allocator: Memory is divided into slab classes (64B, 128B, 256B, etc.). LRU is per-class, not global—eviction from the 128B class only evicts 128B items, even if there are older 256B items.

Modern Segmented LRU (since 1.5.x):

Key Optimization: Items are only “bumped” once every 60 seconds, reducing lock contention dramatically.

PostgreSQL: Clock Sweep

PostgreSQL uses clock sweep for buffer pool management since version 8.1.

Mechanism:

• Circular buffer array with usage_count per buffer (0-5)
• “Clock hand” sweeps through buffers
• On sweep: if usage_count > 0, decrement and skip; if 0, evict
• On access: increment usage_count (saturates at 5)

Why Clock Sweep:

• No linked list = no pointer manipulation on buffer access
• Single atomic increment instead of list relinking
• Better concurrency than 2Q (which PostgreSQL used briefly in 8.0.1-8.0.2)

Implementation Detail: The nextVictimBuffer pointer is a simple unsigned 32-bit integer that wraps around the buffer pool. This simplicity enables high concurrency without complex locking.

Concurrency and Thread Safety

Production caches must handle concurrent access. The key trade-off: simplicity vs. scalability.

Production Recommendation: Don’t implement concurrent caches yourself. Use battle-tested libraries:

Common Pitfalls

1. Cache Stampede (Thundering Herd)

The Mistake: Multiple requests miss the cache simultaneously, all hit the backend.

Why It Happens: Cache entry expires, N requests arrive before any can repopulate.

The Consequence: Backend overwhelmed with N duplicate requests for the same data.

The Fix: Use “singleflight” pattern—only one request fetches, others wait for its result.

5 collapsed lines
1
class StampedeProtectedCache<K, V> {
2
  private cache: Map<K, V>
3
  private pending: Map<K, Promise<V>> // In-flight requests
4

5
  constructor() {
6
    this.cache = new Map()
7
    this.pending = new Map()
8
  }
9

10
  async get(key: K, fetch: () => Promise<V>): Promise<V> {
11
    // Return cached value if present
12
    if (this.cache.has(key)) return this.cache.get(key)!
13

14
    // If another request is fetching, wait for it
15
    if (this.pending.has(key)) return this.pending.get(key)!
16

17
    // This request will fetch
8 collapsed lines
18
    const promise = fetch().then((value) => {
19
      this.cache.set(key, value)
20
      this.pending.delete(key)
21
      return value
22
    })
23
    this.pending.set(key, promise)
24
    return promise
25
  }
26
}

2. Cache Inconsistency

The Mistake: Updating database then cache, or vice versa, without atomicity.

Why It Happens: Race conditions between concurrent updates.

The Consequence: Cache serves stale data indefinitely.

The Fix: Use cache-aside with TTL, or write-through with single source of truth. For critical data, prefer short TTLs over complex invalidation.

3. Unbounded Cache Growth

The Mistake: Caching everything without size limits.

Why It Happens: “More cache = better performance” thinking.

The Consequence: OOM crashes, GC pauses, or swapping.

The Fix: Always set a max size. For LRU, this is trivial—eviction handles it. For other patterns, monitor memory usage.

4. Wrong Cache Key Granularity

The Mistake: Cache keys too coarse (cache entire page) or too fine (cache every DB row).

Why It Happens: Not analyzing actual access patterns.

The Consequence: Too coarse = low hit rate, too fine = high overhead.

The Fix: Profile your workload. Match cache granularity to access granularity.

5. Ignoring Cache Warmup

The Mistake: Deploying with cold cache and expecting production performance.

Why It Happens: Testing with warm caches, deploying fresh.

The Consequence: Slow starts, backend overload on deployment.

The Fix: Pre-warm caches before routing production traffic, or use rolling deployments that let caches warm gradually.

Conclusion

Cache eviction is fundamentally about prediction: given limited memory, which items should you keep to maximize future hits? The answer depends entirely on your access patterns.

Decision Framework:

1. Start with LRU for most applications—it’s simple, well-understood, and works for temporal locality
2. Switch to 2Q or SIEVE when sequential scans are poisoning your cache (analytics queries, batch jobs, backups)
3. Consider ARC when your workload is unpredictable and you can’t tune parameters (patent expired February 2024)
4. Use W-TinyLFU (Caffeine) for CDNs and web caches with skewed popularity distributions

Production Reality: Most systems use approximated or specialized variants. Redis samples random keys. Linux uses multiple generations. PostgreSQL uses clock sweep. The textbook algorithms are starting points, not endpoints.

The right cache eviction policy can be the difference between a system that degrades gracefully under load and one that falls over. Understand your access patterns, profile your workload, and choose accordingly.

Appendix

Prerequisites

• Understanding of hash tables and linked lists
• Basic knowledge of time complexity (Big O notation)
• Familiarity with cache concepts (hits, misses, eviction)

Summary

1. LRU assumes temporal locality: recently accessed = soon needed. This fails during sequential scans.
2. Scan resistance requires additional signals: 2Q uses probationary filtering, ARC uses ghost lists, SIEVE uses visited bits.
3. Approximated algorithms dominate production: Redis samples keys, Linux uses MGLRU, PostgreSQL uses clock sweep.
4. Memory overhead varies significantly: SIEVE uses 1 bit/entry; ARC can double memory for ghost lists.
5. No single best algorithm: the optimal choice depends on your access patterns, memory constraints, and operational requirements.
6. Common pitfalls are preventable: cache stampede, inconsistency, unbounded growth, and cold starts all have standard solutions.

References

Original Research Papers

• O’Neil, E. J., O’Neil, P. E., & Weikum, G. (1993). The LRU-K Page Replacement Algorithm For Database Disk Buffering. ACM SIGMOD Record, 22(2), 297-306.

• Johnson, T., & Shasha, D. (1994). 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994, 439-450.

• Megiddo, N., & Modha, D. S. (2003). ARC: A Self-Tuning, Low Overhead Replacement Cache. USENIX FAST 2003, 115-130.

• Zhang, Y., Yang, J., Yue, Y., Vigfusson, Y., & Rashmi, K.V. (2024). SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches. USENIX NSDI 2024.

• Einziger, G., Friedman, R., & Manes, B. (2017). TinyLFU: A Highly Efficient Cache Admission Policy. ACM Transactions on Storage.

Patents

• US Patent 6,996,676 - ARC (IBM). Granted February 7, 2006. Expired February 22, 2024.

• US Patent Application 20060069876 - CAR (IBM). Filed September 30, 2004.

Production Implementations

• Redis Key Eviction - Official documentation on approximated LRU.

• Linux MGLRU Documentation - Kernel documentation for Multi-Generational LRU.

• PostgreSQL Buffer Manager - Detailed explanation of clock sweep algorithm.

• Caffeine Wiki - Efficiency - W-TinyLFU benchmarks and design.

• SIEVE Project Website - Algorithm details and implementations.

PostgreSQL History

• PostgreSQL Mailing List: ARC Patent Discussion - Original discussion about patent concerns.

Further Reading

• CMU 15-445 Database Systems - Advanced course covering buffer pool management.

• MDN Web Docs - Map - ES2015 Map insertion order guarantee.