Caching
Cache Policies
Read aloud is unavailable in this browser.
The Art of Deciding What to Forget
A cache's effectiveness hinges on one critical decision: when space runs out, what should be evicted? The wrong choice means evicting data that will be needed again soon, causing an expensive cache miss. The right choice means evicting data unlikely to be accessed, maximizing the cache's benefit.
This decision is made by the cache replacement policy—an algorithm that uses available information (access history, frequency, recency) to predict which cached data is least likely to be useful in the future. The quality of this prediction directly determines cache hit rate, which in turn determines system performance.
By the end of this page, you will understand the major cache replacement policies (LRU, LFU, ARC, and variants), their theoretical foundations, practical trade-offs, and how modern operating systems combine multiple strategies to achieve excellent performance across diverse workloads.
Replacement Policy Fundamentals
The Optimal Policy (Bélády's Algorithm)
The theoretically optimal policy is simple: evict the page that will be accessed furthest in the future. This minimizes misses by keeping data that will be needed soonest.
Unfortunately, this requires knowledge of future accesses—impossible in practice. But it provides an upper bound for comparison: no realizable policy can do better.
Realizable Policies
Practical policies must predict future access using only past behavior. They rely on locality:
- Temporal locality: Recently accessed data is likely to be accessed again soon
- Frequency locality: Frequently accessed data is likely to be accessed again
Different policies weight these factors differently, making each better suited to certain workload patterns.
| Policy | Principle | Tracks | Weakness |
|---|---|---|---|
| FIFO | First In, First Out | Insertion order | Ignores access patterns entirely |
| LRU | Least Recently Used | Recency | Scan-resistant workloads defeat it |
| LFU | Least Frequently Used | Frequency | Cannot adapt to changing patterns |
| ARC | Adaptive Replacement | Both + history | More complex implementation |
| CLOCK | LRU approximation | Reference bit | Less accurate than true LRU |
Least Recently Used (LRU)
LRU is the most widely used cache replacement policy. It evicts the page that hasn't been accessed for the longest time, based on the assumption that recent access predicts future access.
LRU Implementation
True LRU requires tracking access order precisely. The classic implementation uses a doubly-linked list:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
/* * LRU Cache Implementation * Uses doubly-linked list for O(1) operations */struct lru_node { void *key; void *value; struct lru_node *prev; struct lru_node *next;}; struct lru_cache { struct lru_node *head; /* Most recently used */ struct lru_node *tail; /* Least recently used (evict) */ struct hash_table *lookup; /* O(1) key lookup */ size_t capacity; size_t size;}; /* Move node to head (most recently used) */void lru_touch(struct lru_cache *cache, struct lru_node *node) { if (node == cache->head) return; /* Already MRU */ /* Remove from current position */ if (node->prev) node->prev->next = node->next; if (node->next) node->next->prev = node->prev; if (node == cache->tail) cache->tail = node->prev; /* Insert at head */ node->next = cache->head; node->prev = NULL; if (cache->head) cache->head->prev = node; cache->head = node;} /* Evict least recently used (tail) */void *lru_evict(struct lru_cache *cache) { struct lru_node *victim = cache->tail; if (!victim) return NULL; cache->tail = victim->prev; if (cache->tail) cache->tail->next = NULL; else cache->head = NULL; hash_remove(cache->lookup, victim->key); cache->size--; void *evicted = victim->value; free(victim); return evicted;}LRU Strengths and Weaknesses
Strengths:
- Excellent for workloads with strong temporal locality
- Simple conceptual model
- Naturally adapts to working set changes
Weaknesses:
- Scan vulnerability: A single sequential scan through data larger than the cache evicts everything useful, leaving the cache filled with scan data that won't be accessed again
- No frequency awareness: A page accessed once recently beats a page accessed 1000 times slightly less recently
- Implementation overhead: True LRU requires updating data structures on every access
Consider a database backup scanning all tables while the database handles normal queries. The backup's sequential access pattern could evict frequently-used indexes and hot rows, devastating performance for normal operations. This real-world scenario motivates more sophisticated policies.
Least Frequently Used (LFU)
LFU evicts the page with the lowest access count, keeping frequently-accessed (popular) data cached regardless of recency.
LFU Implementation
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
/* * LFU Cache with O(1) operations * Uses frequency buckets linked together */struct lfu_node { void *key; void *value; size_t frequency; struct list_head freq_list; /* Position in frequency bucket */}; struct freq_bucket { size_t freq; struct list_head nodes; /* Nodes with this frequency */ struct list_head bucket_list; /* All buckets, ordered by freq */}; struct lfu_cache { struct hash_table *lookup; struct list_head freq_buckets; /* Ascending frequency order */ size_t min_freq; size_t capacity, size;}; void lfu_access(struct lfu_cache *cache, struct lfu_node *node) { /* Remove from current frequency bucket */ struct freq_bucket *old_bucket = get_bucket(cache, node->frequency); list_del(&node->freq_list); /* If bucket empty and was minimum, update min_freq */ if (list_empty(&old_bucket->nodes) && node->frequency == cache->min_freq) cache->min_freq++; /* Increment frequency and add to new bucket */ node->frequency++; struct freq_bucket *new_bucket = get_or_create_bucket( cache, node->frequency); list_add_tail(&node->freq_list, &new_bucket->nodes);} struct lfu_node *lfu_evict(struct lfu_cache *cache) { /* Get minimum frequency bucket */ struct freq_bucket *min_bucket = get_bucket(cache, cache->min_freq); /* Evict least recently used within that frequency (LRU tiebreaker) */ struct lfu_node *victim = list_first_entry( &min_bucket->nodes, struct lfu_node, freq_list); list_del(&victim->freq_list); hash_remove(cache->lookup, victim->key); cache->size--; return victim;}LFU Strengths and Weaknesses
Strengths:
- Resists scan pollution—sequential scans accumulate low frequency
- Keeps genuinely hot data in cache
- Excellent for stable, skewed access distributions
Weaknesses:
- Cache pollution: Once-hot data that's no longer accessed fills the cache with high-frequency zombies
- Slow warmup: New data starts with frequency 1, vulnerable to eviction before it can prove its value
- No recency: Can't distinguish between 1000 accesses yesterday vs. 1000 accesses last month
The CLOCK Algorithm
CLOCK (also called Second-Chance) is a practical approximation of LRU that dramatically reduces overhead. Instead of maintaining a fully-ordered list, it uses a single reference bit per page.
CLOCK Operation
Pages are arranged in a circular buffer with a 'clock hand' pointer. Each page has a reference bit set to 1 when accessed. When eviction is needed:
123456789101112131415161718192021222324252627282930313233343536
/* * CLOCK page replacement algorithm * Used by Linux for page cache management */struct page { unsigned int referenced : 1; /* Set on access */ unsigned int dirty : 1; void *data;}; struct clock_cache { struct page *pages; size_t capacity; size_t hand; /* Current position */}; struct page *clock_evict(struct clock_cache *cache) { while (1) { struct page *p = &cache->pages[cache->hand]; if (p->referenced) { /* Give second chance - clear and move on */ p->referenced = 0; cache->hand = (cache->hand + 1) % cache->capacity; } else { /* Found victim - not recently referenced */ cache->hand = (cache->hand + 1) % cache->capacity; return p; } }} /* Hardware/kernel sets this on access */void clock_access(struct page *p) { p->referenced = 1;}Why CLOCK Works
CLOCK approximates LRU behavior:
- Recently-accessed pages have reference bit set, get second chances
- Long-untouched pages have reference bit clear (cleared by previous passes), get evicted
- The clock hand's sweep period determines 'recency' granularity
Advantages over LRU:
- O(1) access without data structure updates
- Reference bit can be set by hardware (page table accessed bit)
- Scales to millions of pages efficiently
Enhanced CLOCK Variants
CLOCK-Pro: Tracks both recent and frequent access patterns CAR: Combines CLOCK with adaptive behavior like ARC 2Q: Uses two queues to distinguish one-time from repeated access
Adaptive Replacement Cache (ARC)
ARC represents a breakthrough in cache replacement by adaptively balancing between recency (LRU) and frequency (LFU) based on observed workload behavior. It dynamically learns whether the current access pattern benefits more from recency or frequency information.
ARC Structure
ARC maintains four lists:
T1: Recent pages accessed only once (recency-focused) T2: Pages accessed at least twice (frequency-focused) B1: Ghost entries for recently evicted T1 pages B2: Ghost entries for recently evicted T2 pages
The cache holds pages in T1 ∪ T2, limited to cache size. B1 and B2 are metadata-only (no data cached), tracking what was recently evicted.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
/* * Simplified ARC implementation * Demonstrates the adaptive balancing mechanism */struct arc_cache { struct list_head T1, T2; /* Cached pages */ struct list_head B1, B2; /* Ghost lists */ size_t c; /* Cache capacity */ size_t p; /* Target size for T1 (adaptive) */ size_t t1_size, t2_size; size_t b1_size, b2_size;}; void arc_request(struct arc_cache *arc, void *page) { /* Case 1: Hit in T1 - move to T2 (now frequent) */ if (in_list(page, &arc->T1)) { move_to_mru(&arc->T2, page); arc->t1_size--; arc->t2_size++; return; } /* Case 2: Hit in T2 - move to MRU of T2 */ if (in_list(page, &arc->T2)) { move_to_mru(&arc->T2, page); return; } /* Case 3: Hit in B1 ghost - recency was useful */ if (in_list(page, &arc->B1)) { /* Adapt: increase target size for T1 */ arc->p = min(arc->c, arc->p + max(1, arc->b2_size/arc->b1_size)); replace(arc, 0); /* Make room */ remove_from(&arc->B1, page); arc->b1_size--; add_to_mru(&arc->T2, page); arc->t2_size++; /* Now in cache */ return; } /* Case 4: Hit in B2 ghost - frequency was useful */ if (in_list(page, &arc->B2)) { /* Adapt: decrease target size for T1 */ arc->p = max(0, arc->p - max(1, arc->b1_size/arc->b2_size)); replace(arc, 1); /* Make room */ remove_from(&arc->B2, page); arc->b2_size--; add_to_mru(&arc->T2, page); arc->t2_size++; return; } /* Case 5: Complete miss - not in cache or ghosts */ /* Manage ghost list sizes */ if (arc->t1_size + arc->b1_size == arc->c) { if (arc->t1_size < arc->c) { evict_lru(&arc->B1); arc->b1_size--; replace(arc, 0); } else { evict_lru(&arc->T1); arc->t1_size--; } } add_to_mru(&arc->T1, page); arc->t1_size++;} /* Replace a page - favor T1 or T2 based on p */void replace(struct arc_cache *arc, int in_b2) { if (arc->t1_size > 0 && (arc->t1_size > arc->p || (in_b2 && arc->t1_size == arc->p))) { /* Evict from T1, add ghost to B1 */ void *victim = evict_lru(&arc->T1); arc->t1_size--; add_to_mru(&arc->B1, victim); arc->b1_size++; } else { /* Evict from T2, add ghost to B2 */ void *victim = evict_lru(&arc->T2); arc->t2_size--; add_to_mru(&arc->B2, victim); arc->b2_size++; }}ARC's Adaptive Mechanism
The key insight is the ghost lists (B1, B2). When a request hits in B1 (we previously evicted it from T1-recency), it means LRU would have kept it—recency was valuable. So we increase p, growing T1's share. Conversely, B2 hits indicate frequency was valuable, so we decrease p.
This self-tuning means ARC automatically adapts to:
- Recency-dominated workloads (more T1)
- Frequency-dominated workloads (more T2)
- Mixed workloads (balanced T1/T2)
- Changing workload patterns (adapts continuously)
ZFS uses ARC as its primary caching algorithm, achieving excellent performance across diverse workloads. IBM holds patents on ARC, which limited its adoption in some open-source projects, though patent-safe variants like CAR exist.
Linux Page Cache Policies
Linux uses a sophisticated multi-generation LRU (MGLRU) system that addresses classical LRU weaknesses while maintaining practical efficiency for millions of pages.
Two-List Approach (Traditional)
Traditionally, Linux maintained two lists:
Active List: Pages accessed recently (likely to be accessed again) Inactive List: Pages not accessed recently (candidates for eviction)
Pages start on the inactive list. If accessed while inactive, they're promoted to the active list. Active pages gradually demote to inactive if not re-accessed.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
/* * Simplified Linux page aging and reclaim */ /* Page flags for reclaim decisions */#define PG_referenced 1 /* Recently accessed */#define PG_active 2 /* On active list */ /* * Determine if page should be promoted * Called when page is accessed */void mark_page_accessed(struct page *page) { if (!PageReferenced(page)) { SetPageReferenced(page); } else if (!PageActive(page)) { /* Second access while inactive - promote */ activate_page(page); ClearPageReferenced(page); }} /* * Page reclaim: scan inactive list */unsigned shrink_inactive_list(struct lruvec *lruvec, unsigned nr_to_scan) { LIST_HEAD(pages_to_free); unsigned nr_reclaimed = 0; while (nr_to_scan-- && !list_empty(&lruvec->inactive)) { struct page *page = lru_to_page(&lruvec->inactive); if (PageReferenced(page)) { /* Referenced - give another chance */ ClearPageReferenced(page); list_move(&page->lru, &lruvec->inactive); continue; } if (PageDirty(page)) { /* Must write back first */ pageout(page); continue; } /* Unreferenced, clean - can reclaim */ list_move(&page->lru, &pages_to_free); nr_reclaimed++; } free_pages_list(&pages_to_free); return nr_reclaimed;}Multi-Gen LRU (MGLRU)
Modern Linux (5.18+) features MGLRU, which uses multiple generations instead of two lists:
- Pages progress through generations as they age
- Younger generations have higher eviction priority
- Hardware page-table access bits efficiently track real access
- Scan cost is O(hot pages) not O(total pages)
This dramatically improves behavior under memory pressure, especially for workloads with large working sets.
Choosing the Right Policy
Different workloads favor different policies. Understanding your access patterns helps choose appropriately:
| Workload Pattern | Best Policy | Reasoning |
|---|---|---|
| Working set fits in cache | Any | All policies work well |
| Strong temporal locality | LRU/CLOCK | Recency is the dominant predictor |
| Zipf-distributed access | LFU or ARC | Hot items stay hot |
| Sequential scans mixed with random access | ARC or 2Q | Resists scan pollution |
| Changing access patterns | ARC | Adapts automatically |
| Memory constrained system | CLOCK/MGLRU | Low overhead matters |
ARC and its variants (CAR, CLOCK-Pro) provide robust performance across diverse workloads without tuning. If you're building a new caching layer and don't have strong evidence for a specific policy, start with something adaptive.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.