Cache eviction policies (LRU, LFU, TTL) in HLD - Scalability & System Analysis

Scalability Analysis - Cache eviction policies (LRU, LFU, TTL)

Growth Table: Cache Eviction Policies at Different Scales

Users / Requests	Cache Size	Eviction Policy Behavior	Performance Impact
100 users	Small (MBs)	LRU or TTL works well; simple eviction	Low latency, minimal overhead
10K users	Medium (GBs)	LRU may cause overhead; LFU helps with popular items; TTL for freshness	Moderate CPU for eviction; good hit rate
1M users	Large (10s GBs)	LFU preferred for stable popularity; TTL combined to expire stale data	Eviction overhead grows; need efficient data structures
100M users	Very Large (100s GBs+)	Distributed cache with TTL; hybrid policies; eviction done per shard	Network and coordination overhead; eviction must be distributed

First Bottleneck

The first bottleneck is the eviction algorithm's CPU and memory overhead as cache size grows.

LRU requires tracking usage order, which can be costly with large caches.

LFU needs frequency counters, increasing memory and CPU usage.

TTL requires timers or expiration checks, which can add overhead at scale.

Scaling Solutions

• Horizontal scaling: Use distributed caches (e.g., Redis Cluster) to shard data and eviction.
• Approximate algorithms: Use approximate LRU/LFU (e.g., CLOCK, TinyLFU) to reduce overhead.
• TTL tuning: Set TTLs to limit stale data and reduce eviction complexity.
• Cache partitioning: Separate hot and cold data to apply different eviction policies.
• Eviction offloading: Use background threads or separate processes to handle eviction asynchronously.

Back-of-Envelope Cost Analysis

• Requests per second (RPS):
  • 1K users -> ~100-500 RPS
  • 10K users -> ~1K-5K RPS
  • 1M users -> ~100K RPS
  • 100M users -> ~10M+ RPS (requires distributed caching)
• Storage needed:
  • Small scale: MBs to GBs
  • Large scale: 10s to 100s GBs or more
• Bandwidth:
  • Eviction metadata updates add overhead
  • Distributed cache requires network bandwidth for coordination

Interview Tip

Start by explaining the eviction policies simply: LRU removes least recently used, LFU removes least frequently used, TTL removes after time expires.

Discuss how each policy affects CPU, memory, and complexity as cache size grows.

Identify the bottleneck (eviction overhead) and propose scaling solutions like distributed caching and approximate algorithms.

Use real numbers to show understanding of scale and trade-offs.

Self Check

Your cache eviction algorithm handles 1000 QPS. Traffic grows 10x. What do you do first?

Answer: The eviction overhead will increase. First, consider switching to an approximate eviction algorithm (e.g., CLOCK or TinyLFU) to reduce CPU and memory usage, or shard the cache horizontally to distribute load.

Key Result

Cache eviction policies face CPU and memory overhead as cache size and traffic grow; approximate algorithms and distributed caching help scale efficiently.

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