Cache eviction policies (LRU, LFU, TTL) in HLD - Architecture Diagram

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

This system manages a cache to speed up data access by storing frequently used data temporarily. It uses eviction policies like LRU (Least Recently Used), LFU (Least Frequently Used), and TTL (Time To Live) to decide which data to remove when the cache is full or data expires.

Architecture Diagram

User
  |
  v
Load Balancer
  |
  v
API Gateway
  |
  v
Cache Manager
 /   |    \
LRU  LFU   TTL
  \   |    /
   Cache Storage
      |
      v
  Database

Components

User

client

Sends requests to access data

Load Balancer

load_balancer

Distributes incoming requests evenly to API Gateway

API Gateway

api_gateway

Receives requests and routes them to Cache Manager

Cache Manager

service

Handles cache logic and applies eviction policies

LRU

eviction_policy

Evicts least recently used items when cache is full

LFU

eviction_policy

Evicts least frequently used items when cache is full

TTL

eviction_policy

Evicts items after their time to live expires

Cache Storage

cache

Stores cached data for fast access

Database

database

Stores the original persistent data

Request Flow - 11 Hops

User → Load Balancer

Load Balancer → API Gateway

API Gateway → Cache Manager

Cache Manager → Cache Storage

Cache Storage → Cache Manager

Cache Manager → Database

Database → Cache Manager

Cache Manager → Cache Storage

Cache Manager → API Gateway

API Gateway → Load Balancer

Load Balancer → User

Failure Scenario

Component Fails:Cache Storage

Impact:Cache misses increase, causing more direct database queries and higher latency

Mitigation:System continues to serve data from database; cache rebuilds as data is requested; consider cache replication or fallback cache

Architecture Quiz - 3 Questions

Which eviction policy removes the data that was used least recently?

A LFU

B LRU

C TTL

D Random Eviction

Design Principle

This design shows how different cache eviction policies help manage limited cache space by removing data based on usage patterns or expiration time, improving system performance and resource use.

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