Cache Invalidation Strategies - Learning Module

Loading content...

0/273

LFU (Least Frequently Used)

When Frequency Trumps Recency

LRU assumes that recently accessed items will be accessed again soon. But what about items that are accessed frequently? Consider a popular product page that gets 10,000 views per day versus a newly uploaded product that got 2 views in the last minute. LRU would favor the new product (more recent access), but intuition suggests the popular product is more valuable to cache.

Least Frequently Used (LFU) inverts the assumption: items accessed more frequently are more valuable and should be retained longer. Instead of tracking when an item was last accessed, LFU tracks how many times it has been accessed.

This approach excels for workloads with stable popularity distributions—where some items are consistently "hot" and others are consistently "cold." However, it introduces new challenges: how do you count frequency efficiently, and how do you handle popularity changes over time?

What You Will Learn

By the end of this page, you will understand LFU deeply: how frequency counting works, the O(1) LFU implementation with frequency buckets, the cache pollution problem and frequency decay solutions, adaptive LFU variants, and when to choose LFU over LRU. You'll also learn how Redis implements LFU in production.

LFU Conceptual Model

The Core Idea:

Every cache entry maintains an access counter. On each access, the counter increments. When eviction is needed, the entry with the lowest counter (least frequently used) is removed.

Formal Definition:

On insert: New entry starts with frequency = 1
On access: Increment the entry's frequency counter
On eviction: Remove the entry with the minimum frequency. If multiple entries share the minimum frequency, use a secondary policy (typically LRU among ties)

This simple model captures the intuition that frequently accessed items are valuable. However, as we'll see, naive implementation has significant problems.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
LFU Cache with capacity 4
 
Initial state with access counts:
┌─────────────────────────────────────────────────────────┐
│  Key  │  A   │  B   │  C   │  D   │                     │
│  Freq │  50  │  10  │  25  │   3  │                     │
│       │      │      │      │  ↑   │                     │
│       │      │      │      │ LFU  │                     │
└─────────────────────────────────────────────────────────┘
 
On access to C:
┌─────────────────────────────────────────────────────────┐
│  Key  │  A   │  B   │  C   │  D   │                     │
│  Freq │  50  │  10  │  26  │   3  │  ← C's count +1     │
│       │      │      │      │  ↑   │                     │
│       │      │      │      │ LFU  │                     │
└─────────────────────────────────────────────────────────┘
 
Insert E (need to evict, D has lowest frequency):
┌─────────────────────────────────────────────────────────┐
│  Key  │  A   │  B   │  C   │  E   │                     │
│  Freq │  50  │  10  │  26  │   1  │  ← E starts at 1    │
│       │      │      │      │  ↑   │                     │
│       │      │      │      │ LFU  │  (D evicted)        │
└─────────────────────────────────────────────────────────┘
 
Problem: E now has lowest frequency and will be evicted next
if the cache needs to evict again, even though E is brand new!

Why Frequency Locality Matters:

Many real-world access patterns follow power-law distributions (Zipf's law):

A small percentage of items receive the majority of accesses
The top 10% of products might receive 90% of views
Popular API endpoints are called orders of magnitude more than rare ones

For these workloads, LFU naturally retains the "head" of the distribution (popular items) while evicting the "tail" (rare items). This matches the actual value each item contributes to cache hit rate.

The Cache Pollution Problem

Naive LFU has a critical flaw: cache pollution. Items that were popular in the past accumulate high frequency counts and become nearly impossible to evict, even if they're no longer accessed. Meanwhile, newly popular items can never build up enough frequency to be retained. This is the opposite problem of LRU's scan pollution.

O(1) LFU Implementation with Frequency Buckets

Achieving O(1) for all LFU operations is more complex than LRU. The standard approach uses a clever two-level structure:

Frequency Map: Maps each frequency value to a doubly-linked list of entries with that frequency
Key Map: Maps each key to its frequency bucket and node pointer
Minimum Frequency Tracker: Tracks the current minimum frequency for O(1) eviction

Key Insight:

When an entry's frequency increases from F to F+1, we move it from the frequency-F list to the frequency-(F+1) list. This is O(1) because we have direct pointers. Eviction removes from the frequency-MinFreq list, also O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
┌─────────────────────────────────────────────────────────────────────────┐
│                      O(1) LFU CACHE STRUCTURE                            │
└─────────────────────────────────────────────────────────────────────────┘
 
Key Map (key → CacheNode):
┌───────────────────────────────────────────┐
│ "item:A" → ●  (freq=5, value=...)        │
│ "item:B" → ●  (freq=5, value=...)        │
│ "item:C" → ●  (freq=2, value=...)        │
│ "item:D" → ●  (freq=1, value=...)        │
│ "item:E" → ●  (freq=1, value=...)        │
└───────────────────────────────────────────┘
 
Frequency Buckets (frequency → LRU list of nodes):
┌─────────────────────────────────────────────────────────────────────────┐
│                                                                          │
│  freq=1: [D] ←→ [E]              ← minFreq points here                  │
│           ↑                                                              │
│          LRU (evict D first among freq=1 items)                         │
│                                                                          │
│  freq=2: [C]                                                             │
│                                                                          │
│  freq=3: (empty)                                                         │
│                                                                          │
│  freq=4: (empty)                                                         │
│                                                                          │
│  freq=5: [A] ←→ [B]                                                     │
│           ↑                                                              │
│          LRU within this frequency                                       │
└─────────────────────────────────────────────────────────────────────────┘
 
minFreq = 1  ← Track minimum for O(1) eviction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
from typing import TypeVar, Generic, Optional, Dict
from dataclasses import dataclass
from collections import defaultdict
 
K = TypeVar('K')
V = TypeVar('V')
 
@dataclass
class LFUNode(Generic[K, V]):
    """Node storing key, value, frequency, and list pointers."""
    key: K
    value: V
    freq: int = 1
    prev: Optional['LFUNode[K, V]'] = None
    next: Optional['LFUNode[K, V]'] = None
 
 
class DoublyLinkedList(Generic[K, V]):
    """Doubly-linked list with O(1) add/remove operations."""
    
    def __init__(self):
        self.head = LFUNode(None, None)  # Sentinel head (MRU)
        self.tail = LFUNode(None, None)  # Sentinel tail (LRU)
        self.head.next = self.tail
        self.tail.prev = self.head
        self._size = 0
    
    def add_to_front(self, node: LFUNode[K, V]) -> None:
        """Add node at front (most recently used within this frequency)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self._size += 1
    
    def remove(self, node: LFUNode[K, V]) -> None:
        """Remove specific node from list."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        self._size -= 1
    
    def pop_lru(self) -> Optional[LFUNode[K, V]]:
        """Remove and return the LRU node (from tail)."""
        if self._size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node
    
    def is_empty(self) -> bool:
        return self._size == 0
    
    def __len__(self) -> int:
        return self._size
 
 
class LFUCache(Generic[K, V]):
    """
    LFU Cache with O(1) get, put, and eviction.
    
    Uses frequency buckets (each a doubly-linked list) to organize
    entries by access frequency. Within each frequency bucket,
    entries are ordered by recency (LRU for tie-breaking).
    """
    
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be positive")
        
        self.capacity = capacity
        self.min_freq = 0
        
        # Key → Node mapping for O(1) key lookup
        self.key_map: Dict[K, LFUNode[K, V]] = {}
        
        # Frequency → List of nodes with that frequency
        self.freq_map: Dict[int, DoublyLinkedList[K, V]] = defaultdict(DoublyLinkedList)
    
    def get(self, key: K) -> Optional[V]:
        """
        Retrieve value by key.
        
        On hit: increment frequency, move to higher frequency bucket.
        On miss: return None.
        Time complexity: O(1)
        """
        if key not in self.key_map:
            return None  # Cache miss
        
        node = self.key_map[key]
        self._update_frequency(node)
        return node.value
    
    def put(self, key: K, value: V) -> Optional[K]:
        """
        Store key-value pair.
        
        If key exists: update value and increment frequency.
        If key is new and cache is full: evict LFU entry first.
        
        Returns evicted key if eviction occurred.
        Time complexity: O(1)
        """
        if self.capacity == 0:
            return None
        
        evicted_key = None
        
        if key in self.key_map:
            # Update existing
            node = self.key_map[key]
            node.value = value
            self._update_frequency(node)
        else:
            # New entry - may need eviction
            if len(self.key_map) >= self.capacity:
                evicted_key = self._evict()
            
            # Create new node with frequency 1
            new_node = LFUNode(key=key, value=value, freq=1)
            self.key_map[key] = new_node
            self.freq_map[1].add_to_front(new_node)
            self.min_freq = 1  # New entry always has min frequency
        
        return evicted_key
    
    def _update_frequency(self, node: LFUNode[K, V]) -> None:
        """
        Increment node's frequency and move to appropriate bucket.
        
        1. Remove from current frequency bucket
        2. Update min_freq if needed
        3. Increment frequency
        4. Add to new frequency bucket
        """
        old_freq = node.freq
        new_freq = old_freq + 1
        
        # Remove from current frequency list
        self.freq_map[old_freq].remove(node)
        
        # Update min_freq if we just removed the last item at min_freq
        if old_freq == self.min_freq and self.freq_map[old_freq].is_empty():
            self.min_freq = new_freq
        
        # Increment frequency and add to new list
        node.freq = new_freq
        self.freq_map[new_freq].add_to_front(node)
    
    def _evict(self) -> K:
        """
        Evict the least frequently used entry.
        
        If multiple entries have the same (minimum) frequency,
        evict the least recently used among them (LRU tie-breaker).
        """
        # Get the list at minimum frequency
        min_freq_list = self.freq_map[self.min_freq]
        
        # Pop the LRU entry from this list
        victim = min_freq_list.pop_lru()
        
        # Remove from key map
        del self.key_map[victim.key]
        
        return victim.key
    
    def delete(self, key: K) -> bool:
        """Explicitly remove key from cache."""
        if key not in self.key_map:
            return False
        
        node = self.key_map[key]
        self.freq_map[node.freq].remove(node)
        del self.key_map[key]
        
        # Note: We don't update min_freq here for simplicity.
        # It will be corrected on next eviction or insert.
        
        return True
    
    def __len__(self) -> int:
        return len(self.key_map)
    
    def __contains__(self, key: K) -> bool:
        return key in self.key_map
 
 
# Usage example:
cache = LFUCache[str, dict](capacity=100)
 
# Simulate access pattern
cache.put("product:popular", {"name": "iPhone", "price": 999})
for _ in range(100):  # 100 accesses
    cache.get("product:popular")
 
cache.put("product:rare", {"name": "Widget", "price": 5})
# Only 1 access (the put)
 
# If eviction needed, product:rare (freq=1) evicts before product:popular (freq=101)

LRU as Tie-Breaker

When multiple entries have the same frequency, we use LRU ordering within that frequency bucket. This gives us LFU behavior globally (evict least frequent) with LRU behavior locally (among ties, evict least recent). This hybrid is sometimes called 'LFU with Aging' or 'LFU-LRU'.

The Frequency Decay Problem and Solutions

Pure LFU has a fundamental problem: historical frequency dominates current relevance.

The Problem Illustrated:

Time T1: Item A receives 10,000 accesses (viral moment)
Time T2: Item A stops being accessed entirely
Time T3: Item B starts receiving 100 accesses/hour

After 10 hours:
- Item A: 10,000 (hasn't been touched for 10 hours)
- Item B: 1,000 (actively accessed)

LFU keeps A (higher frequency) and would evict B!

Item A has become "cache pollution"—permanently occupying space despite being useless now. This is the inverse of LRU's scan pollution problem.

Solution 1: Time-Windowed Frequency

Only count accesses within a recent time window (e.g., last hour). This requires storing access timestamps, which is memory-expensive.

Solution 2: Periodic Decay (Halving)

Periodically reduce all frequency counters by half. Old popularity fades; recent popularity is preserved.

Every hour:
  for item in cache:
    item.frequency = item.frequency // 2

Solution 3: Exponential Decay Counter

Use a counter that naturally decays over time. On each access, increment counter. Over time, counter value decays toward zero. This is what Redis uses.

Solution 4: Frequency with Age Weighting

Weight frequency by recency: effective_freq = raw_freq / (time_since_last_access + 1). Recent frequent items score highest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import threading
import time
from typing import Dict, Any, Optional
 
class DecayingLFUCache:
    """
    LFU cache with periodic frequency decay to handle popularity shifts.
    
    Every decay_interval seconds, all frequencies are halved.
    This allows old popular items to become evictable as their
    frequency decays, while recently accessed items maintain
    their (halved but still relatively high) frequencies.
    """
    
    def __init__(self, capacity: int, decay_interval: int = 3600):
        """
        Args:
            capacity: Maximum cache size
            decay_interval: Seconds between decay cycles (default: 1 hour)
        """
        self.capacity = capacity
        self.decay_interval = decay_interval
        
        self.cache = LFUCache[str, Any](capacity)
        self.decay_lock = threading.Lock()
        
        # Start decay thread
        self._running = True
        self._decay_thread = threading.Thread(target=self._decay_loop, daemon=True)
        self._decay_thread.start()
    
    def _decay_loop(self):
        """Background thread that periodically decays all frequencies."""
        while self._running:
            time.sleep(self.decay_interval)
            self._apply_decay()
    
    def _apply_decay(self):
        """
        Halve all frequency counters.
        
        This makes old popular items evictable while preserving
        relative ordering of recently accessed items.
        """
        with self.decay_lock:
            # Access internal structure (in production, expose a method)
            for node in self.cache.key_map.values():
                old_freq = node.freq
                new_freq = max(1, old_freq // 2)  # Never go below 1
                
                if new_freq != old_freq:
                    # Need to move node to different frequency bucket
                    self.cache.freq_map[old_freq].remove(node)
                    node.freq = new_freq
                    self.cache.freq_map[new_freq].add_to_front(node)
            
            # Recalculate min_freq
            self.cache.min_freq = min(
                (f for f, lst in self.cache.freq_map.items() if not lst.is_empty()),
                default=1
            )
    
    def get(self, key: str) -> Optional[Any]:
        with self.decay_lock:
            return self.cache.get(key)
    
    def put(self, key: str, value: Any) -> None:
        with self.decay_lock:
            self.cache.put(key, value)
    
    def stop(self):
        """Stop the decay thread."""
        self._running = False
 
 
# Decay effect over time:
#
# T=0h: ItemA=1000, ItemB=100, ItemC=50
# T=1h (decay): ItemA=500, ItemB=50, ItemC=25
#   ItemA still wins if no new accesses
#   
# T=2h: ItemA=250, ItemB gets 200 accesses → ItemB=250 (tied!)
# T=3h (decay): ItemA=125, ItemB=125
#   
# Now ItemA and ItemB are equal despite ItemA's historical dominance
# Recent activity (ItemB) has equalized with historical popularity (ItemA)

Decay Trade-offs

Faster decay: More responsive to popularity changes, but loses information about truly popular items faster. Slower decay: Preserves popularity information longer, but slower to evict stale popular items. Tune based on how quickly your access patterns change. E-commerce during flash sales needs faster decay than a static content library.

Redis LFU Implementation Deep Dive

Redis 4.0+ introduced LFU as an alternative eviction policy. Rather than tracking exact frequency counts, Redis uses a clever probabilistic logarithmic counter that combines frequency tracking with time-based decay.

Redis LFU Counter Structure:

Redis stores an 8-bit counter per key (values 0-255). This counter is logarithmic: value 100 represents far more than 10× the accesses of value 10.

Counter increment logic:

On each access, the counter increments probabilistically based on its current value:

counter = 0-255
baseFactor = 10 (configurable via lfu-log-factor)

random_value = random(0, 1)
increment_probability = 1.0 / ((counter * baseFactor) + 1)

if random_value < increment_probability:
    counter = min(255, counter + 1)

This means:

Low counter (0-10): Almost always increments
Medium counter (50-100): Sometimes increments
High counter (200+): Rarely increments

The result is a logarithmic scale where doubling access count only increments the counter by about 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import random
import time
 
# Redis LFU uses 8 bits: 16 bits for last decrement time, 8 bits for counter
# Here we focus on the counter logic
 
def redis_lfu_increment(counter: int, lfu_log_factor: int = 10) -> int:
    """
    Increment LFU counter probabilistically (Redis algorithm).
    
    Lower counters increment easily; higher counters rarely increment.
    This creates logarithmic scaling of access counts.
    """
    # Special case: always increment from 0
    if counter == 0:
        return 1
    
    # Calculate increment probability
    # probability = 1 / (counter * lfu_log_factor + 1)
    probability = 1.0 / (counter * lfu_log_factor + 1)
    
    # Random increment
    if random.random() < probability:
        return min(255, counter + 1)
    
    return counter
 
 
def simulate_access_pattern(accesses: int, lfu_log_factor: int = 10) -> int:
    """Simulate N accesses and return final counter value."""
    counter = 0
    for _ in range(accesses):
        counter = redis_lfu_increment(counter, lfu_log_factor)
    return counter
 
 
# Demonstrate logarithmic scaling
print("Access Count → LFU Counter (average of 100 trials)")
print("-" * 50)
 
for access_count in [1, 10, 100, 1000, 10000, 100000, 1000000]:
    # Average over multiple trials due to probabilistic nature
    counters = [simulate_access_pattern(access_count) for _ in range(100)]
    avg_counter = sum(counters) / len(counters)
    print(f"{access_count:>10} accesses → counter ≈ {avg_counter:.1f}")
 
# Example output:
#          1 accesses → counter ≈ 1.0
#         10 accesses → counter ≈ 2.9
#        100 accesses → counter ≈ 10.2
#       1000 accesses → counter ≈ 18.1
#      10000 accesses → counter ≈ 24.6
#     100000 accesses → counter ≈ 29.8
#    1000000 accesses → counter ≈ 34.5
#
# Note: 1 million accesses only reaches counter ~35!
# This logarithmic compression fits frequency info in 8 bits.

Redis LFU Decay Mechanism:

Redis also implements time-based decay. Along with the 8-bit counter, each key stores a 16-bit "last decrement timestamp" (in minutes, mod 65536 ≈ 45 days).

On each access, Redis computes how many minutes have passed and decrements the counter:

// Simplified Redis decay logic
decrement = (current_minutes - last_decrement_minutes) / lfu_decay_time;
counter = max(0, counter - decrement);

With lfu-decay-time = 1 (default), the counter decrements by 1 for each minute since last access. A key not accessed for 30 minutes loses 30 from its counter.

Effect: Items not accessed for extended periods have their counters decay, making them evictable even if historically popular.

Redis LFU Configuration Parameters
Parameter	Default	Description	Tuning Guidance
maxmemory-policy	noeviction	Must be allkeys-lfu or volatile-lfu	Set to allkeys-lfu for general caching, volatile-lfu if using TTL
lfu-log-factor	10	Controls counter increment probability	Higher = slower counter growth. Increase for very high traffic
lfu-decay-time	1	Minutes per counter decrement	Lower = faster decay. Increase if access patterns are stable
maxmemory-samples	5	Keys sampled for eviction	Higher = more accurate but slower eviction. 10 is good balance

Redis LFU Debugging

Use OBJECT FREQ <key> to see a key's current LFU counter. Use DEBUG OBJECT <key> for detailed metadata. Monitor eviction behavior with INFO stats and track evicted_keys. Compare LRU vs LFU hit rates with INFO keyspace to validate your policy choice.

LRU vs LFU: When to Use Which

Choosing between LRU and LFU depends on your workload characteristics. Neither is universally better—each excels in different scenarios.

LRU vs LFU Comparison
Factor	LRU	LFU
Optimizes for	Temporal locality (recent = relevant)	Frequency locality (popular = relevant)
Scan resistance	Poor (scans flush cache)	Good (scans don't build frequency)
Adapts to popularity changes	Immediately (next access)	Slowly (needs decay)
Implementation complexity	Moderate (doubly-linked list)	Higher (frequency buckets + decay)
Memory overhead	Low (~24 bytes/entry)	Moderate (~32+ bytes/entry)
Cache pollution	By scans	By historically popular items
Best for	Session caches, query results, web pages	CDN caching, product catalogs, API responses

Choose LRU When

•Access patterns are time-correlated (recent items are hot)
•Popularity changes rapidly (trending content, news)
•Workload is dominated by sequential or batch access
•Implementation simplicity is valued
•Memory overhead must be minimized
•You don't have strong frequency skew (items equally popular)

Choose LFU When

•Some items are consistently more popular than others
•Popularity changes slowly (stable product rankings)
•Workload has many one-time accesses mixed with repeated accesses
•Cache pollution from scans is a problem with LRU
•You can tune decay parameters for your workload
•You need to protect hot items from burst traffic to cold items

Real-World Policy Selection Examples:

E-commerce product pages:

Top products get 90% of views (strong frequency skew)
Popularity is relatively stable
→ LFU is better (protects popular products)

News/social media feeds:

Today's news was irrelevant yesterday
Content popularity changes hourly
→ LRU is better (adapts to trending content)

Database query cache:

Query patterns vary by time of day
Batch jobs can scan many records
→ LRU or SLRU (handles batch scans better)

CDN static assets:

Some assets (JS, CSS) loaded on every page
Most assets are rarely accessed
→ LFU is better (keeps core assets cached)

When in Doubt, Experiment

Run both policies on production traffic (A/B test) and measure hit rates. The difference can be substantial—we've seen 10-15% hit rate improvements by switching policies for specific workloads. Let data decide, not intuition.

Advanced LFU Variants: W-TinyLFU and Beyond

Research has produced several LFU variants that address its weaknesses while preserving its advantages. The most notable is TinyLFU and its practical variant W-TinyLFU, used in the Caffeine cache library.

TinyLFU:

Rather than storing exact frequency counts, TinyLFU uses a Count-Min Sketch (a probabilistic data structure) to estimate frequencies with minimal memory. This allows tracking frequency for all items (not just cached items) while using only ~8 bits per tracked item.

Admission Policy:

TinyLFU acts as a "doorkeeper." When a new item wants to enter the cache, TinyLFU compares its estimated frequency to the victim's. Only if the new item has higher frequency does it get admitted.

If frequency(new_item) > frequency(victim):
    Evict victim, admit new_item
Else:
    Reject new_item, keep victim

This prevents one-time accesses from evicting frequently accessed items.

W-TinyLFU (Window-TinyLFU):

Caffeine's W-TinyLFU adds a small "window" LRU segment that admits items immediately. Only when items are evicted from the window segment does TinyLFU decide if they should enter the "main" cache.

┌─────────────────────────────────────────────────────────────┐
│                    W-TinyLFU STRUCTURE                       │
└─────────────────────────────────────────────────────────────┘

┌─────────────┐           ┌─────────────────────────────────┐
│   Window    │──evict──▶│        TinyLFU Filter          │
│   (1% LRU)  │           │   (admit if freq > victim)     │
└─────────────┘           └───────────────┬─────────────────┘
       ↑                                    │
   new items                                │ admit
                                           ↓
                          ┌─────────────────────────────────┐
                          │   Main Cache (99% SLRU)         │
                          │   [Protected 80%][Probation 20%]│
                          └─────────────────────────────────┘

Advantages:

Near-optimal hit rates across diverse workloads
Low memory overhead (Count-Min Sketch is compact)
Handles burst traffic well (window admits immediately)
Scan resistant (TinyLFU rejects items without history)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import hashlib
from typing import List
 
class CountMinSketch:
    """
    Count-Min Sketch for approximate frequency counting.
    
    Used by TinyLFU to estimate access frequencies with minimal memory.
    Space: O(width × depth) counters
    Error: O(total_count / width) with probability 1 - delta
    Where delta relates to depth via depth = ln(1/delta)
    """
    
    def __init__(self, width: int = 10000, depth: int = 4):
        """
        Args:
            width: Number of counters per row (more = less collision)
            depth: Number of hash functions (more = lower error probability)
        """
        self.width = width
        self.depth = depth
        self.table: List[List[int]] = [[0] * width for _ in range(depth)]
    
    def _hash(self, key: str, seed: int) -> int:
        """Generate hash for given key and seed."""
        combined = f"{seed}:{key}"
        hash_bytes = hashlib.md5(combined.encode()).digest()
        return int.from_bytes(hash_bytes[:4], 'little') % self.width
    
    def increment(self, key: str) -> None:
        """Increment count for key."""
        for i in range(self.depth):
            index = self._hash(key, i)
            self.table[i][index] += 1
    
    def estimate(self, key: str) -> int:
        """
        Estimate count for key.
        
        Returns minimum across all hash positions.
        This gives an upper bound on true count (never underestimates).
        """
        min_count = float('inf')
        for i in range(self.depth):
            index = self._hash(key, i)
            min_count = min(min_count, self.table[i][index])
        return min_count
    
    def decay(self, factor: int = 2) -> None:
        """
        Decay all counters by dividing by factor.
        
        Called periodically to prevent counter saturation
        and allow frequency rankings to change over time.
        """
        for i in range(self.depth):
            for j in range(self.width):
                self.table[i][j] //= factor
 
 
class TinyLFUAdmissionFilter:
    """
    TinyLFU admission filter for cache eviction decisions.
    
    When a new item wants to enter a full cache, TinyLFU compares
    its estimated frequency to the victim's. Only allows admission
    if new item has higher estimated frequency.
    """
    
    def __init__(self, expected_items: int = 100000):
        # Size sketch to expected number of items
        # Width ≈ 10× expected items gives good accuracy
        self.sketch = CountMinSketch(width=expected_items * 10, depth=4)
        self.sample_count = 0
        self.reset_threshold = expected_items * 10  # Reset after this many samples
    
    def record_access(self, key: str) -> None:
        """Record an access (call on every cache hit or miss)."""
        self.sketch.increment(key)
        self.sample_count += 1
        
        # Periodic decay to prevent saturation
        if self.sample_count >= self.reset_threshold:
            self.sketch.decay(2)
            self.sample_count //= 2
    
    def should_admit(self, new_key: str, victim_key: str) -> bool:
        """
        Decide if new_key should evict victim_key.
        
        Returns True if new_key has higher estimated frequency.
        """
        new_freq = self.sketch.estimate(new_key)
        victim_freq = self.sketch.estimate(victim_key)
        
        # Admit new item only if it's more popular
        return new_freq > victim_freq
 
 
# Usage in a cache:
# filter = TinyLFUAdmissionFilter()
# 
# def get(key):
#     filter.record_access(key)  # Record every access
#     return cache.get(key)
# 
# def put(key, value):
#     if cache.is_full():
#         victim = cache.get_lru()  # Get least recently used
#         if filter.should_admit(key, victim):
#             cache.evict(victim)
#             cache.put(key, value)
#         # else: reject new item, keep victim
#     else:
#         cache.put(key, value)

Caffeine Cache Library

For Java applications, Caffeine implements W-TinyLFU and consistently achieves near-optimal hit rates. It's the successor to Guava Cache and is used by major projects including Spring Framework. If you're in the JVM ecosystem, prefer Caffeine over rolling your own eviction.

LFU in Production: Monitoring and Tuning

Running LFU effectively in production requires monitoring specific metrics and tuning parameters based on observed behavior.

Key Metrics to Watch:

LFU-Specific Monitoring

•Frequency distribution: Histogram of counter values. If most items have high counters, decay might be too slow. If most are low, decay might be too aggressive.
•Counter saturation: Percentage of items at maximum counter (255 for 8-bit). High saturation means counters aren't differentiating effectively.
•Admission rate: For TinyLFU, percentage of insert attempts that are admitted. Very low rates might indicate filter is too restrictive.
•New item survival rate: Of items admitted in the last hour, how many are still cached? Low survival means new items are being evicted quickly—possibly correctly (one-time access) or incorrectly (rising popularity).
•Hit rate by counter bucket: Hit rate for items with counter 1-10, 11-20, etc. Should generally increase with counter. If not, LFU might not be appropriate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Grafana dashboard for LFU cache monitoring
 
panels:
  - title: "Frequency Counter Distribution"
    type: histogram
    query: |
      histogram_quantile(0.5, 
        sum(rate(cache_lfu_counter_bucket[5m])) by (le)
      )
    description: "Distribution of LFU counter values. Healthy: bell curve. Unhealthy: spike at 0 or 255"
  
  - title: "Counter Saturation Rate"
    type: gauge
    query: |
      sum(cache_items_at_max_counter) / sum(cache_total_items) * 100
    thresholds:
      - value: 10
        color: green
      - value: 30
        color: yellow
      - value: 50
        color: red
    description: "Items at max counter (255). >30% indicates decay is too slow"
  
  - title: "LFU Hit Rate vs LRU Baseline"
    type: timeseries  
    queries:
      - expr: cache_hit_rate{policy="lfu"}
        legend: "LFU"
      - expr: cache_hit_rate{policy="lru"}
        legend: "LRU (shadow)"
    description: "Compare LFU to shadow LRU. If LRU is higher, consider switching"
  
  - title: "New Item Survival Rate"
    type: stat
    query: |
      (cache_items_admitted_1h_ago - cache_items_evicted_since_admit)
      / cache_items_admitted_1h_ago * 100
    description: "Items admitted 1h ago still in cache. Low = high churn"
  
  - title: "Decay Effectiveness"
    type: timeseries
    query: |
      avg(cache_lfu_counter) by (instance)
    description: "Average counter over time. Should fluctuate, not grow monotonically"
 
alerts:
  - name: LFUCounterSaturation
    expr: sum(cache_items_at_max_counter) / sum(cache_total_items) > 0.3
    for: 30m
    labels:
      severity: warning
    annotations:
      summary: "High LFU counter saturation"
      description: "Over 30% of items at max counter. Consider faster decay."
  
  - name: LFUHitRateDrop
    expr: |
      cache_hit_rate{policy="lfu"} 
      < cache_hit_rate{policy="lru"} - 0.05
    for: 1h
    labels:
      severity: warning  
    annotations:
      summary: "LFU underperforming LRU"
      description: "LFU hit rate lower than LRU. Consider policy switch."

Tuning Guidelines:

If counter saturation is high (>30% at max):

Increase decay rate (lower lfu-decay-time)
This allows counters to decrease, making rankings more dynamic

If new items are evicted too quickly:

Decrease decay rate (higher lfu-decay-time)
Or decrease lfu-log-factor to make counters grow faster

If old popular items never evict:

Increase decay rate significantly
Consider switching to LRU or W-TinyLFU

If hit rate is lower than LRU baseline:

Your workload likely has stronger temporal than frequency locality
Switch to LRU or experiment with SLRU

Shadow Mode for Policy Comparison

Before switching eviction policies in production, run both in 'shadow mode': the actual cache uses one policy, while you simulate the other in memory (no actual queries, just track what would be cached). Compare hit rates. This gives you data-driven confidence before making changes.

Summary: LFU Mastery

LFU provides an alternative to LRU that excels when access frequency is a better predictor of future access than recency. Let's consolidate the key insights:

Key Takeaways

•LFU evicts least frequently accessed items — This preserves popular items even if they haven't been accessed in the last few seconds.
•O(1) LFU uses frequency buckets — Each frequency level has its own LRU list. Moving between frequencies is O(1) with proper pointers.
•Frequency decay is essential — Without decay, historically popular items become unmovable, polluting the cache. Periodic halving or time-based decay solves this.
•Redis LFU uses probabilistic logarithmic counters — 8 bits per key suffice because counter growth is probabilistic and logarithmic. Decay happens per-access based on time elapsed.
•LRU vs LFU depends on workload — LRU for rapidly changing popularity (news, trending). LFU for stable popularity (product catalogs, assets).
•W-TinyLFU achieves near-optimal hit rates — Combining frequency filtering with SLRU addresses both LRU's scan sensitivity and LFU's resistance to new items.
•Monitor counter distribution and saturation — These metrics reveal if LFU is working for your workload and if decay tuning is needed.

What's Next:

We've covered the most sophisticated eviction algorithms (LRU, LFU). The next page explores the simplest: FIFO (First In, First Out)—an algorithm that ignores both recency and frequency, evicting in pure insertion order. Understanding why FIFO is sometimes useful despite its simplicity completes our eviction algorithm toolkit.

Page Complete

You now have deep expertise in LFU cache eviction. You can implement O(1) LFU, configure decay mechanisms, choose between LRU and LFU for your workload, and leverage advanced variants like W-TinyLFU. This knowledge enables you to design caches that maximize hit rates for frequency-skewed access patterns.