Eviction Policies: The Art of Forgetting

[!TIP] Interview Insight: If asked to “Design an LRU Cache”, do not just explain it. Write the code (or pseudo-code) for the get and put operations using a HashMap and Doubly Linked List to achieve O(1) time complexity.

1. Why O(1) Matters?

When your cache has 10 items, O(N) (looping through a list) is fast (10 operations). When your cache has 10 million items, O(N) takes 10 million operations. That’s a 100ms latency spike for every single request.

We need O(1) (Constant Time). No matter if you have 10 or 10 billion items, the operation takes the same amount of time.

Complexity: O(N) vs O(1)

Time (ms)
Items (N)
O(N)
O(1)
Hover over the chart...

2. LRU (Least Recently Used)

The most common policy. It assumes that if you used it recently, you will use it again soon (Temporal Locality).

Implementation: The Magic of O(1)

To achieve O(1) for both get and put, we combine two data structures:

  1. HashMap: For O(1) access to values by key.
  2. Doubly Linked List: To maintain the order of usage.
  • On Access (Get): Look up in Map. If found, move the node to the Head (Most Recently Used).
  • On Add (Put): Create node. Add to Head. Add to Map.
  • On Evict: Remove the node from the Tail (Least Recently Used). Remove from Map.

3. Interactive Demo: LRU Internals & Hit Ratio

Visualizing the HashMap + Linked List structure.

  • Head (Left): Most Recently Used (Safe).
  • Tail (Right): Least Recently Used (Danger Zone).
  • Scan Attack: Simulate a database scan (e.g., SELECT * FROM big_table) that floods the cache with one-time-use keys, wiping out your useful data.
HEAD (MRU) TAIL (LRU)
Waiting...
Hits: 0
Misses: 0
Ratio: 0%

4. Modern Policies: Beyond LRU

LRU is great, but it has a flaw: Cache Pollution. If I scan a DB (read every item once), LRU replaces everything with data I will never use again.

A. W-TinyLFU (Window TinyLFU) - The Solution

Used in Caffeine (Java) and Ristretto (Go). It solves the memory problem using a Count-Min Sketch and a Window Admission Policy.

1. The Count-Min Sketch (Probabilistic Frequency)

Think of it as a Bloom Filter for Counting. Instead of 1 counter per key (Expensive), we have a small 2D array of counters (Cheap).

  1. Hash: We hash the key using multiple hash functions (e.g., 3 functions).
  2. Increment: We increment the counters at those 3 positions.
  3. Read: To get the frequency, we check the 3 positions and take the Minimum value.

Why Minimum? Because of collisions. A cell might be shared by “Apple” and “Banana”. If “Apple” is 10 and “Banana” is 2, the cell says 12. But since we use multiple hashes, it’s unlikely all cells collide. The Minimum value is the closest to the truth.

2. The Admission Policy (Doorkeeper)

Unlike LRU, which blindly admits everything, W-TinyLFU asks: “Is this new item more valuable than the victim I am about to evict?”

  • Yes: Evict the victim, admit the new item.
  • No: Reject the new item. Keep the victim.

This protects the cache from Scan Attacks.

Scan Resistance: LRU vs TinyLFU

LRU Cache
Vulnerable to Scans
TinyLFU Cache
Protects Hot Items
Frequent Items: [A, B, C]

B. ARC (Adaptive Replacement Cache) - The Gold Standard

ARC is one of the most intelligent caching algorithms ever invented (used by ZFS, PostgreSQL). It beats LRU by maintaining Four Lists to balance Recency vs Frequency.

It dynamically tunes the cache size between “Recent” items and “Frequent” items based on workload.

C. The Clock Algorithm (Second Chance)

Common in Operating System Page Replacement (Linux Page Cache). It approximates LRU with very low overhead.

  • Structure: Pages are arranged in a Circle (Clock).
  • Reference Bit (R): Every page has a bit (0 or 1).
  • Clock Hand: A pointer moves around the circle.

Algorithm:

  1. On Page Fault: Look at the page pointed by the Hand.
  2. If R=1: Give it a “Second Chance”. Set R=0. Move Hand to next page.
  3. If R=0: Evict this page. Replace with new page. Move Hand.
Pointer at index 0

6. Eviction Policy Decision Matrix

Choosing the right policy depends on your access pattern.

Access Pattern Best Policy Why
Temporal Locality (Recently used → used again) LRU News feed, user sessions, recent posts
Frequency-Based (Popular items stay popular) LFU / TinyLFU Top 100 songs, trending videos, product catalog
Scanning Workloads (Full table scans) ARC / Clock-Pro Database buffer pools, large reports
Mixed Workload W-TinyLFU CDN edge caches (mix of hot + one-hit-wonders)
Small Cache (< 1000 items) LRU Simple, O(1), minimal overhead
Large Cache (> 1M items) TinyLFU Memory efficient, still O(1)

[!TIP] Summary: Use LRU for general cases. Use TinyLFU or ARC if you have high-throughput and “scan” workloads (e.g., Database Cache).