Cache eviction policies (LRU, LFU, TTL) in HLD - Deep Dive

Overview - Cache eviction policies (LRU, LFU, TTL)

What is it?

Cache eviction policies are rules that decide which data to remove from a cache when it is full. They help keep the cache efficient by removing less useful data to make space for new data. Common policies include LRU (Least Recently Used), LFU (Least Frequently Used), and TTL (Time To Live). Each policy uses a different way to pick what to evict.

Why it matters

Without eviction policies, caches would fill up and stop working well, slowing down systems that rely on fast data access. Good eviction policies keep the cache fresh and relevant, improving speed and reducing load on slower storage or databases. This makes apps feel faster and saves resources.

Where it fits

Learners should first understand what a cache is and why caching improves performance. After learning eviction policies, they can explore cache implementation details, distributed caching, and how eviction affects system scalability and consistency.

Mental Model

Core Idea

Cache eviction policies decide which stored data to remove when space runs out, balancing freshness and usefulness to keep the cache effective.

Think of it like...

Imagine a small backpack with limited space. You decide what to take out when it’s full: either the items you haven’t used recently (LRU), the items you rarely use (LFU), or the items that have expired (TTL).

┌───────────────┐
│   Cache Full  │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│  Eviction Policy Decision    │
│ ┌─────────┬─────────┬──────┐ │
│ │   LRU   │   LFU   │ TTL  │ │
│ └─────────┴─────────┴──────┘ │
└─────────────┬───────────────┘
              │
              ▼
     ┌─────────────────┐
     │ Remove Selected  │
     │ Cache Entry     │
     └─────────────────┘

Build-Up - 7 Steps

1

Foundation

What is a Cache and Why Evict

Concept: Introduce the basic idea of a cache and why eviction is necessary.

A cache is a small, fast storage that keeps copies of data to speed up access. Since cache size is limited, it cannot hold everything. When full, it must remove some data to make room for new data. This removal process is called eviction.

Result

Learners understand that eviction is essential to keep caches working efficiently.

Knowing why eviction is needed helps learners appreciate the role of eviction policies in maintaining cache performance.

2

Foundation

Basic Cache Eviction Concepts

Concept: Explain what eviction policies are and their purpose.

Eviction policies are rules that decide which cache entries to remove when space is needed. They aim to keep the most useful data in the cache. Different policies use different criteria like recent use, frequency, or time.

Result

Learners grasp that eviction policies guide cache data removal to optimize usefulness.

Understanding eviction policies as decision rules clarifies how caches stay effective under space limits.

3

Intermediate

Least Recently Used (LRU) Policy

🤔Before reading on: do you think LRU removes the oldest data or the least used data? Commit to your answer.

Concept: Introduce LRU, which removes the data not used for the longest time.

LRU tracks when each cache entry was last accessed. When eviction is needed, it removes the entry that was used longest ago. This assumes recently used data is more likely to be used again soon.

Result

Learners understand how LRU prioritizes recent usage to keep cache relevant.

Knowing LRU’s focus on recency helps predict cache behavior in workloads with temporal locality.

4

Intermediate

Least Frequently Used (LFU) Policy

🤔Before reading on: does LFU remove data used least recently or least often? Commit to your answer.

Concept: Explain LFU, which removes data accessed the fewest times.

LFU counts how often each cache entry is accessed. When space is needed, it evicts the entry with the lowest access count. This assumes frequently used data is more valuable to keep.

Result

Learners see how LFU focuses on long-term popularity rather than recent use.

Understanding LFU’s frequency-based approach reveals its strength in workloads with stable popular data.

5

Intermediate

Time To Live (TTL) Policy

🤔Before reading on: does TTL evict based on usage or time? Commit to your answer.

Concept: Introduce TTL, which removes data after a fixed time expires.

TTL assigns an expiration time to each cache entry when added. Once the time passes, the entry is removed regardless of usage. This ensures data freshness and avoids stale information.

Result

Learners understand TTL’s role in controlling data age in caches.

Knowing TTL’s time-based eviction helps manage cache freshness in dynamic data environments.

6

Advanced

Comparing Eviction Policies and Tradeoffs

🤔Before reading on: which policy do you think works best for all cases? Commit to your answer.

Concept: Discuss strengths and weaknesses of LRU, LFU, and TTL and when to use each.

LRU works well when recent data is likely reused but can fail if old data is still important. LFU favors long-term popular data but can keep stale entries. TTL ensures freshness but may evict useful data prematurely. Hybrid approaches combine policies for better results.

Result

Learners appreciate that no single policy fits all scenarios and tradeoffs exist.

Understanding tradeoffs guides choosing or designing eviction policies tailored to specific workloads.

7

Expert

Implementing Efficient Eviction in Large Systems

🤔Before reading on: do you think tracking exact usage for all entries is cheap or costly? Commit to your answer.

Concept: Explore challenges and solutions for implementing eviction policies efficiently at scale.

Tracking exact usage or frequency for millions of entries is costly. Systems use approximations like counters with limited bits, sampling, or segmented caches. TTL requires timers or lazy expiration. Efficient data structures like linked lists or heaps help maintain eviction order with minimal overhead.

Result

Learners understand practical constraints and optimizations in real-world cache eviction.

Knowing implementation challenges prevents naive designs that hurt performance and scalability.

Under the Hood

Cache eviction policies work by maintaining metadata about each cache entry, such as last access time (LRU), access count (LFU), or expiration timestamp (TTL). When the cache is full, the policy uses this metadata to select entries to remove. Data structures like doubly linked lists (for LRU), frequency lists (for LFU), and priority queues or timers (for TTL) support efficient updates and lookups.

Why designed this way?

These policies were designed to balance cache hit rate and resource use. LRU leverages temporal locality common in many workloads. LFU captures long-term popularity but is more complex. TTL addresses data freshness needs. Alternatives like random eviction exist but perform worse. The chosen designs reflect tradeoffs between accuracy, complexity, and overhead.

Cache Storage
┌─────────────────────────────┐
│  ┌───────────────┐          │
│  │ Cache Entry 1 │◄─────────┤
│  ├───────────────┤          │
│  │ Cache Entry 2 │◄─────────┤ Metadata
│  ├───────────────┤          │
│  │ Cache Entry 3 │◄─────────┤  ┌─────────────┐
│  └───────────────┘          │  │ Last Access │
│                             │  │ Count      │
│                             │  │ Expiry     │
│                             │  └─────────────┘
└─────────────┬───────────────┘
              │
              ▼
      Eviction Decision
┌─────────────────────────────┐
│  Use Metadata to Select Entry│
│  to Remove Based on Policy   │
└─────────────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does LRU always remove the oldest data in the cache? Commit yes or no.

Common Belief: LRU removes the oldest data stored in the cache regardless of usage.

Reality: LRU removes the data that was least recently used, not necessarily the oldest stored. Data accessed recently stays even if it was added long ago.

Why it matters: Confusing age with usage can lead to wrong expectations about cache behavior and poor tuning.

Quick: Does LFU always keep the freshest data? Commit yes or no.

Common Belief: LFU keeps the freshest data because it tracks usage frequency.

Reality: LFU tracks how often data is used, not how fresh it is. It can keep stale data if it was popular before but no longer relevant.

Why it matters: Assuming LFU ensures freshness can cause stale data to persist, harming application correctness.

Quick: Does TTL evict data based on usage patterns? Commit yes or no.

Common Belief: TTL evicts data based on how often it is used.

Reality: TTL evicts data strictly based on time expiration, ignoring usage frequency or recency.

Why it matters: Misunderstanding TTL can lead to unexpected cache misses or stale data if expiration times are not set properly.

Quick: Is it cheap to track exact usage for millions of cache entries? Commit yes or no.

Common Belief: Tracking exact usage for all cache entries is cheap and easy.

Reality: Tracking exact usage or frequency for large caches is costly in memory and CPU, requiring approximations or special data structures.

Why it matters: Ignoring implementation costs can cause performance bottlenecks or system crashes in production.

Expert Zone

1

LRU can be approximated with CLOCK algorithms to reduce overhead while maintaining similar eviction behavior.

2

LFU often requires aging mechanisms to prevent cache pollution by old popular items that are no longer relevant.

3

TTL eviction can be implemented lazily during access or eagerly with timers, each with tradeoffs in complexity and accuracy.

When NOT to use

Avoid LRU in workloads with cyclic or scan-heavy access patterns where it performs poorly; prefer LFU or hybrid policies. Avoid LFU when data popularity changes rapidly; TTL or LRU may be better. TTL is unsuitable when data usage patterns matter more than freshness; use LRU or LFU instead.

Production Patterns

Real systems often combine policies, like LFU with TTL, or use segmented caches separating hot and cold data. Distributed caches use consistent hashing with local eviction policies. Approximate counters and sampling reduce overhead. Monitoring eviction rates helps tune policies dynamically.

Connections

Operating System Page Replacement

Similar eviction strategies are used to decide which memory pages to swap out.

Understanding cache eviction helps grasp OS memory management, as both optimize limited fast storage.

Garbage Collection in Programming Languages

Both remove unused or less useful data to free resources based on usage patterns.

Knowing eviction policies clarifies how garbage collectors decide which objects to reclaim.

Inventory Management in Retail

Deciding which products to remove or discount based on sales frequency or shelf life mirrors eviction policies.

Recognizing this connection shows how eviction balances freshness and demand in diverse fields.

Common Pitfalls

#1 Evicting cache entries randomly without a policy.

Wrong approach:

When cache is full, remove any entry without checking usage or time.

Correct approach:

Use a defined eviction policy like LRU, LFU, or TTL to select entries to remove.

Root cause:

Misunderstanding that eviction needs to be strategic to keep cache effective.

#2 Implementing LRU by scanning all entries to find the least recently used.

Wrong approach:

On eviction, loop through entire cache to find oldest access time.

Correct approach:

Maintain a linked list or queue to track usage order for O(1) eviction decisions.

Root cause:

Not using proper data structures leads to inefficient eviction and slow cache performance.

#3 Setting TTL values too long or too short without workload analysis.

Wrong approach:

Assign a fixed TTL like 24 hours for all cache entries regardless of data nature.

Correct approach:

Tune TTL based on data freshness needs and access patterns, possibly varying per entry type.

Root cause:

Ignoring workload characteristics causes stale data or excessive cache misses.

Key Takeaways

Cache eviction policies are essential to keep caches efficient by removing less useful data when space runs out.

LRU evicts data not used recently, LFU evicts data used least often, and TTL evicts data after a set time.

No single eviction policy fits all workloads; understanding tradeoffs helps choose or design the right one.

Efficient implementation of eviction policies requires careful data structures and approximations at scale.

Misunderstanding eviction policies leads to poor cache performance, stale data, or system bottlenecks.

Practice

1. Which cache eviction policy removes the data that was used the longest time ago?

easy

A. Random Replacement

B. Least Frequently Used (LFU)

C. Time To Live (TTL)

D. Least Recently Used (LRU)

Solution

1. Step 1: Understand LRU policy

   LRU removes the cache entry that was accessed the longest time ago, prioritizing recent usage.

2. Step 2: Compare with other policies

   LFU removes least used items by frequency, TTL removes expired items by time, Random Replacement is arbitrary.

3. Final Answer:

   Least Recently Used (LRU) -> Option D

4. Quick Check:

   Oldest access time = LRU [OK]

Hint: LRU = remove oldest used data [OK]

Common Mistakes:

• Confusing LRU with LFU
• Thinking TTL removes based on usage
• Assuming random removal is LRU

2. Which of the following is a correct description of the TTL cache eviction policy?

easy

A. Removes data after a fixed expiration time

B. Removes the least recently used data

C. Removes the least frequently used data

D. Removes data randomly when cache is full

Solution

1. Step 1: Define TTL policy

   TTL (Time To Live) removes cache entries after their set expiration time passes.

2. Step 2: Contrast with other policies

   LRU removes oldest used, LFU removes least used by frequency, random is arbitrary.

3. Final Answer:

   Removes data after a fixed expiration time -> Option A

4. Quick Check:

   TTL = expiration time removal [OK]

Hint: TTL means data expires after set time [OK]

Common Mistakes:

• Mixing TTL with LRU or LFU
• Thinking TTL depends on usage frequency
• Assuming TTL removes randomly

3. Consider a cache with the following access pattern: keys A, B, A, C, B, A. Using LFU eviction, which key will be evicted when the cache is full and a new key D is added?

medium

A. Key C

B. Key A

C. Key B

D. Key D

Solution

1. Step 1: Count frequency of each key

   Key A accessed 3 times, B accessed 2 times, C accessed 1 time.

2. Step 2: Identify LFU eviction candidate

   LFU removes the least frequently used key, which is C with frequency 1.

3. Final Answer:

   Key C -> Option A

4. Quick Check:

   Lowest frequency = C [OK]

Hint: LFU evicts lowest frequency key [OK]

Common Mistakes:

• Evicting most recent key instead of least frequent
• Confusing frequency with recency
• Evicting key D which is new

4. A cache using TTL eviction is not removing expired entries as expected. Which of the following is the most likely cause?

medium

A. The TTL value is set too low

B. The cache uses LRU instead of TTL

C. The cache does not check expiration before access

D. The cache size is too large

Solution

1. Step 1: Understand TTL eviction mechanism

   TTL eviction requires checking if entries have expired before returning or during cleanup.

2. Step 2: Identify why expired entries remain

   If cache does not check expiration on access or cleanup, expired entries stay indefinitely.

3. Final Answer:

   The cache does not check expiration before access -> Option C

4. Quick Check:

   Expiration check missing = no TTL eviction [OK]

Hint: TTL needs expiration checks to remove entries [OK]

Common Mistakes:

• Assuming low TTL causes no eviction
• Confusing TTL with LRU behavior
• Thinking cache size affects TTL eviction

5. You are designing a cache for a news website where articles are frequently accessed shortly after publishing but rarely after a few days. Which eviction policy is best suited to keep fresh content while removing stale data efficiently?

hard

A. Least Recently Used (LRU)

B. Time To Live (TTL)

C. Random Replacement

D. Least Frequently Used (LFU)

Solution

1. Step 1: Analyze data usage pattern

   Articles are popular shortly after publishing, then become stale after days.

2. Step 2: Match eviction policy to pattern

   TTL removes data after expiration time, ideal for removing stale articles automatically.

3. Step 3: Compare with other policies

   LRU and LFU focus on usage, but TTL ensures freshness by time. Random is inefficient.

4. Final Answer:

   Time To Live (TTL) -> Option B

5. Quick Check:

   Freshness by expiration time = TTL [OK]

Hint: Use TTL for time-based freshness eviction [OK]

Common Mistakes:

• Choosing LRU or LFU ignoring data staleness
• Assuming random eviction is efficient
• Not considering time-based expiration