Cache eviction policies (LRU, LFU, TTL) in HLD - System Design Guide

Problem Statement

Caches have limited space, so when they fill up, old data must be removed to make room for new data. Without a smart way to decide which data to remove, the cache may evict useful data, causing more slow database or API calls and hurting performance.

Solution

Cache eviction policies decide which cached items to remove when space is needed. LRU removes the least recently used items, assuming recent use means importance. LFU removes the least frequently used items, assuming frequent use means importance. TTL removes items after a set time, ensuring data freshness.

Architecture

┌─────────────┐        ┌─────────────┐        ┌─────────────┐
│   Client    │  ───→  │   Cache     │  ───→  │   Database  │
└─────────────┘        └─────────────┘        └─────────────┘
        ↑                    │  ↑  │
        │                    │  │  │
        │                    │  │  └─ Eviction based on policy
        │                    │  └───── LRU / LFU / TTL
        └────────────────────┘

This diagram shows a client requesting data from a cache. The cache serves data if present or fetches from the database if missing. When the cache is full, it evicts items based on LRU, LFU, or TTL policies.

Trade-offs

✓ Pros

→

LRU is simple and adapts well to recent usage patterns.

→

LFU captures long-term popularity of items, reducing eviction of frequently accessed data.

→

TTL ensures data freshness by removing stale entries automatically.

✗ Cons

→

LRU can evict frequently used items if they are not recently accessed.

→

LFU requires tracking usage counts, increasing memory and computation overhead.

→

TTL may evict still useful data prematurely if the time is too short.

Use LRU when recent access is a good indicator of future use and cache size is moderate. Use LFU when long-term frequency matters and you can afford extra tracking. Use TTL when data freshness is critical and stale data must be removed after a fixed time.

Avoid LRU if access patterns are highly irregular or bursty, causing frequent evictions. Avoid LFU if tracking overhead is too costly or usage patterns change rapidly. Avoid TTL if data validity varies widely or precise freshness is not required.

Real World Examples

Amazon

Amazon uses LRU caching in their product recommendation system to keep recently viewed items quickly accessible.

Netflix

Netflix uses LFU caching in their content delivery to prioritize frequently watched shows and movies.

Twitter

Twitter applies TTL caching for user session tokens to ensure they expire after a set time for security.

Alternatives

Random Eviction

Evicts a random cache item instead of based on usage or time.

Use when: Use when simplicity is more important than hit rate and cache size is small.

Most Recently Used (MRU)

Evicts the most recently used items, opposite of LRU.

Use when: Use when older data is more valuable than recent data, such as in certain streaming scenarios.

Summary

Cache eviction policies decide which data to remove when cache space runs out.

LRU removes least recently used, LFU removes least frequently used, and TTL removes data after a set time.

Choosing the right policy depends on access patterns, data freshness needs, and system constraints.

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