Cache Eviction Policies

A cache has limited memory, so when it fills up it must evict an existing entry to store a new one. The eviction policy is the rule that picks the victim, and it directly affects the hit rate.

1. Learning Objectives

By the end of this lesson, you will be able to:

• Explain the necessity of cache eviction policies and their direct impact on the cache hit ratio.
• Distinguish between foundational eviction policies: Least Recently Used (LRU), Least Frequently Used (LFU), First In First Out (FIFO), and Most Recently Used (MRU).
• Analyze advanced eviction policies such as Segmented LRU (SLRU), 2-Queue (2Q), and Window TinyLFU (W-TinyLFU) used in high-performance application caches.
• Implement strict LRU and LFU cache classes in TypeScript with true O(1) runtime complexities.
• Describe production-grade caching mechanisms used in Redis and Memcached, including how they approximate eviction to reduce memory footprints.
• Evaluate the performance trade-offs, lock contention vulnerabilities, and memory overheads associated with eviction metadata.

2. Prerequisites

To get the most out of this lesson, you should be familiar with:

• Core Caching Concepts: Understanding cache hits, misses, latency profiles (RAM vs. SSD vs. HD), and basic read/write strategies (Cache-Aside, Write-Back).
• Basic Data Structures: Knowledge of HashMaps, Doubly Linked Lists, Queues, and Min-Heaps.
• Complexity Analysis: Big O notation for time and space complexity.

3. Why This Topic Matters

In a hypothetical world with infinite memory, a cache would simply grow forever, storing every piece of data ever accessed. However, in physical architectures, random-access memory (RAM) is a constrained and expensive resource. Caches must operate with a fixed maximum size (configured via parameters like maxmemory in Redis).

When a cache reaches its maximum capacity, any attempt to insert a new entry requires freeing up space. The rule that dictates which item is evicted is known as the eviction policy. Choosing the wrong eviction policy leads to cache thrashing—a state where items are evicted and immediately fetched again. This causes the cache hit rate to plummet toward 0%, overloading underlying databases and causing application latencies to spike, potentially leading to cascading system-wide outages.

4. Real-world Analogy

Imagine you are a chef working in a small, fast-paced restaurant. Your prep table (the cache) has space to hold exactly five ingredients. The main walk-in pantry (the database) is located far away at the back of the kitchen. Walking back and forth to the pantry takes a full minute.

If your table is full and a dish requires an ingredient you don't have, you must discard one of the ingredients on your table to make room. How do you choose?

• First In, First Out (FIFO): You evict the ingredient that was placed on the table the earliest, even if you are about to use it again for your next dish.
• Least Recently Used (LRU): You evict the ingredient that you have not touched for the longest period of time. This assumes that if you haven't used it recently, you won't need it soon (temporal locality).
• Least Frequently Used (LFU): You keep count of how many times you have used each ingredient. You discard the ingredient with the lowest count, even if you used it just a few minutes ago.
• Most Recently Used (MRU): You discard the ingredient you just finished using, which is highly useful when your process requires linear scanning of different items without backtracking.

5. Core Concepts

To master cache eviction, you must understand several foundational metrics and concepts:

• Locality of Reference: Caching works because application access patterns display predictable structures:
  • Temporal Locality: Data that was accessed recently is likely to be accessed again soon.
  • Frequency Locality: Data that is accessed many times historically is likely to be accessed frequently in the future.
• Passive vs. Active Eviction:
  • Passive (On-demand) Eviction: The cache removes items when a write request occurs and capacity is fully exhausted.
  • Active (Time-based/Asynchronous) Eviction: A background thread sweeps the cache to evict expired items (e.g., matching a TTL) or clean up memory pools.
• Cache Hit Ratio: The core performance metric. It represents the percentage of read requests satisfied by the cache: Hit Ratio = Hits / (Hits + Misses).
• Cache Thrashing: A destructive loop where eviction and misses feed into each other, exhausting network resources and rendering the cache useless.

6. Visualization

The diagram below illustrates the conceptual architecture of a classic LRU Cache (which combines a Hash Map and a Doubly Linked List for O(1) performance) and a Frequency-based LFU Cache.

The following flowchart describes the internal node movement inside an LRU cache during read and write operations:

7. How It Works

Let us trace the step-by-step lifecycle of a write operation to a cache that is fully saturated:

1. Client Write Command: The client issues a command (e.g., SET user:456 '{"name":"Alice"}').
2. Capacity Inspection: The cache system compares current memory usage (or item count) against the configured threshold.
3. Eviction Trigger: Finding that capacity is exceeded, the cache holds the write-lock and queries its eviction index to select a candidate for deletion.
   • In a FIFO policy, the cache grabs the tail node of the insertion queue.
   • In a strict LRU policy, the cache grabs the tail node of the usage-tracking Doubly Linked List.
   • In a strict LFU policy, the cache looks up the bucket containing the lowest access count and selects the oldest node in that bucket.
4. Resource Cleanup: The chosen key is unlinked from the Hash Map index and the node memory is returned to the allocator.
5. New Node Allocation: The new key-value pair is allocated, wrapped in metadata (pointers, timestamps, or counters), and added to the HashMap index.
6. Position Insertion: The new node is set as the Most Recently Used item (head of the DLL in LRU) or placed in the frequency counter table (LFU).
7. Write Confirmed: The lock is released and the client receives a success status.

8. Internal Architecture

A production-ready cache with an eviction policy requires multiple internal components working in concert. Below is a breakdown of their components, responsibilities, and failure modes:

9. Request Lifecycle

Below is a detailed trace of the two standard request paths in a cache layer implementing eviction:

1. The Read Request Path

1. The application client executes a GET request.
2. The cache coordinator obtains a read lock and queries the Hash Map.
3. Scenario A (Hit):
   • The key is found. The value is loaded.
   • The lock is upgraded or queued to update the eviction metadata (e.g., moving the node to the head of the DLL, incrementing frequency counter).
   • The value is returned to the client.
4. Scenario B (Miss):
   • The key is not found. A miss is returned to the client/application.
   • The application queries the database, fetches the raw value, and schedules a write request to the cache.

2. The Write Request Path

1. The application issues a PUT command containing key, value, and optional TTL.
2. The cache checks if the key already exists:
   • If it exists, the cache replaces the value and updates the eviction order.
3. If the key is new, the cache checks if it has run out of memory limits:
   • If at capacity, the cache triggers its eviction subroutine. It selects the victim key, deletes its index entry, and frees the associated memory.
4. A new node structure is initialized, linked to the index, placed in the eviction manager, and write confirmation is returned.

10. Deep Dive

To build robust production caches, we must analyze the engineering details of eviction algorithms and why modern caches have moved away from basic implementations.

1. LRU (Least Recently Used) and Its Multi-Threaded Locking Problem

The standard LRU implementation relies on a Map mapping keys to Doubly Linked List nodes. On every read (GET) operation, the node must be unlinked from its current position in the DLL and re-inserted at the head (MRU).

This design works perfectly in single-threaded environments, but in multi-threaded caches, this pointer rearrangement requires exclusive access. A read operation, which should theoretically be concurrent and scale with hardware cores, now requires a write-lock on the DLL. This introduces severe lock contention, drastically reducing throughput and degrading P99 latencies under high parallel read workloads.

2. LFU (Least Frequently Used) and Stale Metadata

Classic LFU tracks popularity by incrementing a counter on every read. The item with the lowest counter is evicted when capacity is reached. LFU suffers from two critical architectural challenges:

• Time and Space Complexity: Implementing LFU with a Min-Heap yields O(log N) updates and evictions. Achieving O(1) requires a complex "Double Doubly Linked List" (the LFE algorithm), where frequency nodes are linked in a list, and each frequency node points to a list of cache nodes sharing that frequency.
• Stale Popularity Bias: An item that was extremely popular in the past (e.g., during a Black Friday sale) accumulates a massive counter. After the sale ends, this item remains in the cache indefinitely because its counter is too high, even if it is never accessed again. To prevent this, caches must implement a decay function (e.g., dividing all frequency counters by 2 periodically).

3. Modern Caching Evolution: W-TinyLFU

Modern high-performance caches (like Caffeine for Java, Ristretto for Go) utilize W-TinyLFU. It solves the "one-hit wonder" problem of LRU and the metadata overhead of LFU. W-TinyLFU consists of three sub-components:

1. Window Cache (LRU): A small admission window (usually ~1% of total capacity) where newly inserted items are held. This absorbs quick bursts of temporal locality.
2. Main Cache (Segmented LRU): Houses the bulk of the data, split into Protected and Probational segments.
3. TinyLFU Admission Filter: When an item is evicted from the Window Cache, it cannot immediately enter the Main Cache. It must contend with the eviction candidate of the Main Cache. The Admission Filter uses a Count-Min Sketch (a space-efficient probabilistic data structure, similar to a Bloom Filter, that estimates item frequency using minimal memory) to compare the historical frequencies of the two candidate items. The item with the higher frequency is kept; the other is discarded.

4. Clock (Second Chance) Eviction

In database engines (such as PostgreSQL's shared buffer pool), maintaining a DLL for LRU is too expensive. Instead, they use the Clock algorithm. Nodes are arranged in a circular buffer. A "clock hand" sweeps across the buffer. Each node has a reference bit:

• When a node is accessed, its reference bit is set to 1.
• When space is needed, the clock hand sweeps. If a node's reference bit is 1, it is cleared to 0, and the hand moves to the next node (giving it a "second chance").
• If the hand encounters a node with a reference bit of 0, that node is selected for eviction. This avoids pointer changes and locking on reads, providing a thread-friendly approximation of LRU.

11. Production Example

Let us examine how Redis, one of the most popular in-memory caches, handles eviction under constraints.

A true LRU algorithm requires storing double pointers (16 to 24 bytes of memory overhead) per key. For a Redis instance storing 100 million keys, this would waste gigabytes of RAM just on eviction metadata. To avoid this, Redis uses an approximated LRU/LFU algorithm:

• Approximated LRU: Redis stores a 24-bit idle timestamp in each object wrapper (redisObject). When memory limit is reached, instead of selecting the absolute least-recently-used key, Redis randomly samples $N$ keys (configured via maxmemory-samples, default is 5) and evicts the key with the longest idle time among the sample pool. Setting maxmemory-samples 10 approximates true LRU almost perfectly, with negligible CPU overhead.
• Approximated LFU: Redis repurposes the 24-bit LRU field into two sections: the upper 16 bits represent a last-decrement time (for frequency decay), and the lower 8 bits represent a logarithmic access counter. The counter increases probabilistically (requiring more accesses to increment as the counter gets higher, capping at 255) and decays based on the time since the key was last accessed.

Redis eviction policies can be selected via configuration:

• noeviction: Returns out-of-memory errors on writes once capacity is reached.
• allkeys-lru: Approximated LRU among all keys.
• volatile-lru: Approximated LRU only among keys with an active TTL/expiry set.
• allkeys-lfu / volatile-lfu: Approximated LFU across all keys or volatile keys.
• allkeys-random / volatile-random: Evicts a completely random key.

12. Advantages

• LRU: Exceptional performance for temporal patterns. It is simple to understand, predict, and implement in single-threaded environments.
• LFU: Keeps highly popular elements (e.g., logo images, system configuration tables) cached indefinitely, minimizing cache misses for static, long-tail workloads.
• FIFO: Extremely low metadata overhead. Needs no access-tracking pointers or counters, making memory footprint minimal.
• W-TinyLFU: High hit ratios under various traffic shapes (bursts, zipfian distributions, sequential scans) with minimal memory overhead.

13. Limitations

• LRU: Vulnerable to one-hit wonders. A sequential database backup scan that reads millions of records once will completely flush out the hot cache, replacing useful data with useless, single-access records.
• LFU: Suffers from stale accumulation. If access frequencies are high, defunct items remain in the cache until decay reduces their counts. It also has a slow learning curve for new, fast-growing hot items.
• FIFO: Suffers from Belady's Anomaly, where increasing cache size can actually result in a lower hit rate. It also ignores popularity or recency, evicting extremely hot items simply because they were loaded first.

14. Trade-offs

When choosing an eviction policy, you trade off hit rate optimization, CPU throughput, memory consumption, and system complexity:

15. Performance Considerations

• Read Amplification as Writes: In strict LRU, read requests trigger write actions to modify node pointers in the DLL. Under massive parallel read traffic, this creates a major bottleneck due to global locking or read-write lock upgrades.
• Lock Contention Mitigation: Caches like Caffeine address lock contention using a ring buffer architecture. Instead of updating the DLL immediately during a read, access events are written to a lock-free, lossy ring buffer. A background worker thread consumes events from the ring buffer and batches updates to the DLL asynchronously, maintaining maximum read throughput.
• Memory Fragmentation: Constant insertion and deletion of variable-sized cache objects lead to memory fragmentation. Allocators must work hard to merge free chunks, causing latency spikes. Standard solutions include using slab classes to group allocations by size (e.g., Memcached).

16. Failure Scenarios

Below are critical failure modes associated with cache eviction:

• Cache Stampede (Thundering Herd): Under heavy load, if a hot key is evicted or expires, hundreds of concurrent threads may receive a cache miss simultaneously. They will all query the underlying database and attempt to write back to the cache, overloading the database and crashing the system.
  • Mitigation: Use mutual exclusion locks (e.g., single-flight patterns) to let only one thread fetch the missing key, or employ probabilistic early expiration algorithms (like XFetch).
• Belady's Anomaly: A phenomenon where, in FIFO eviction, increasing the cache's page capacity causes the number of page faults (misses) to increase for certain access patterns.
  • Mitigation: Avoid raw FIFO eviction for critical production caches. Use LRU or segmented variants.
• Frequency Counter Overflow: In naive LFU, if access counts are tracked using a small data type (e.g., a single byte or 16-bit integer) and no decay function is implemented, counters will eventually overflow and wrap around to zero, causing hot items to be mistakenly evicted.
  • Mitigation: Implement counter saturation limits and regular decay mechanisms.

17. Best Practices

• Always Set a Hard Memory Limit: Never run a caching layer (like Redis) without setting a hard maximum memory ceiling (e.g., maxmemory) and configuring an eviction policy (e.g., allkeys-lru). Without it, the operating system's Out-Of-Memory (OOM) killer will terminate the cache process when RAM is exhausted.
• Jitter Your TTLs: When setting active expirations on cache keys, inject a random timing offset (jitter) of 5-10%. This prevents keys that were written in a batch from expiring at the exact same millisecond, avoiding massive cache misses.
• Match Policy to Traffic:
  • For temporal data (e.g., user sessions, recent posts), use LRU.
  • For skewed popularity data (e.g., product catalogs, static assets), use LFU or W-TinyLFU.
  • For streaming data with no repetitive access, bypass the cache or use MRU.
• Monitor Hit Rates Continuously: Set up real-time alerting systems for Cache Hit Ratios. A sudden drop in hit ratio is a leading indicator of database performance degradation.

18. Common Mistakes

• Assuming LRU is Concurrency-Friendly: Expecting standard DLL-based LRU caches to scale linearly across multiple CPU cores. Without thread-safe batched event logging (like Caffeine's ring buffer), exclusive lock contention will degrade throughput.
• Relying Exclusively on TTLs: Assuming that setting TTLs on keys makes an eviction policy unnecessary. If write volume spikes unexpectedly, the cache will run out of memory long before TTL expirations occur.
• Using LFU Without Decay: Caching static catalog pages using standard LFU without decay counters, causing stale items from historical promotions to block new, relevant products from entering the cache.

19. Implementation

Below are complete, production-grade implementations of an LRU Cache and an LFU Cache in TypeScript, achieving true O(1) time complexities for lookups and evictions.

1. O(1) Least Recently Used (LRU) Cache

This implementation utilizes a Map mapping keys to Doubly Linked List nodes.

2. O(1) Least Frequently Used (LFU) Cache

This LFU implementation avoids O(log N) heap costs by grouping cache nodes within a secondary set of doubly-linked list nodes representing frequency counts.

20. Interview Questions

21. Practice Exercises

22. Challenge Problem

System Scenario: You are designing a multi-tenant caching layer for a large e-commerce SaaS platform. The cache cluster must service different tenants, each with highly varied traffic patterns.

• Tenant A (Search Crawler): Large, sequential linear queries. Reads items once, rarely reads them again (strong scan pattern).
• Tenant B (Flash Sale): Power-law distribution (Zipfian). A tiny set of products receives 99% of read traffic (extreme popularity/frequency locality).
• Tenant C (User Feed): Highly dynamic temporal locality. Users refresh feeds repeatedly to see recently created posts.

Design Requirements:

1. Propose a partition-based caching architecture that prevents Tenant A's scan behavior from evicting the hot data of Tenant B and Tenant C.
2. Specify which cache eviction algorithm should be selected for each tenant partition to maximize hit ratios.
3. Describe the mechanism to dynamically adjust memory limits (partition sizing) between the tenants based on hit-ratio monitoring.

23. Summary

Cache eviction is the gatekeeper of application performance under hardware limits. While simple policies like FIFO and LIFO are computationally trivial, they ignore key access patterns. LRU capitalizes on temporal locality but fails under massive sequential scans. LFU targets frequency locality but can suffer from historical bias.

Modern high-performance caches solve these design limits by adopting hybrid policies like W-TinyLFU or using approximated sampling models (like Redis) to reduce pointer-based memory overhead.

24. Cheat Sheet

25. Quiz

26. Further Reading

• TinyLFU: A Highly Efficient Cache Admission Policy (Paper) - The fundamental research paper behind Caffeine's W-TinyLFU cache.
• Redis Cache Eviction Official Documentation - In-depth guide on Redis configuration properties for maxmemory and approximation models.
• PostgreSQL Page Buffer Management - Insights on how RDBMS buffers handle clock-sweep page evictions.

27. Next Lesson Preview

Now that you understand what happens when a cache fills up, we will dive into Distributed Caching Patterns. We will explore how clusters partition data using Consistent Hashing, and how distributed caches (such as Redis Sentinel or Memcached clusters) coordinate lookups across thousands of separate server instances.