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

Design: Cache Eviction Policy System

Design focuses on the eviction policy mechanism within a cache system. Cache storage, network communication, and persistence are out of scope.

Functional Requirements

FR1: Support caching of data to improve read performance

FR2: Implement eviction policies to remove stale or less useful data when cache is full

FR3: Support three eviction policies: Least Recently Used (LRU), Least Frequently Used (LFU), and Time-To-Live (TTL)

FR4: Allow switching between eviction policies dynamically

FR5: Ensure eviction decisions are efficient to maintain low latency

FR6: Provide metrics on cache hits, misses, and evictions

Non-Functional Requirements

NFR1: Cache size limited to 1 million entries

NFR2: Eviction decision latency must be under 5 milliseconds

NFR3: System must handle 10,000 cache requests per second

NFR4: Availability target of 99.9% uptime

NFR5: Memory usage must be optimized to avoid excessive overhead

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Cache storage data structure

Eviction policy manager

Access tracking mechanism (timestamps, counters)

TTL timer or scheduler

Metrics collector

API to switch eviction policies

Design Patterns

LRU implemented with doubly linked list and hashmap

LFU with frequency counters and min-heap or linked lists

TTL using priority queue or timing wheel

Decorator pattern to add eviction logic to cache

Observer pattern for metrics collection

Reference Architecture

  +---------------------+
  |   Client Requests   |
  +----------+----------+
             |
             v
  +---------------------+
  |   Cache Interface   |
  +----------+----------+
             |
             v
  +---------------------+       +---------------------+
  | Eviction Policy Mgr |<----->|  Metrics Collector   |
  +----------+----------+       +---------------------+
             |
             v
  +---------------------+
  |   Cache Storage     |
  | (HashMap + LRU/LFU) |
  +---------------------+
             |
             v
  +---------------------+
  |    TTL Scheduler    |
  +---------------------+

Components

Cache Interface

In-memory data structure

Handles client cache requests and forwards to eviction manager

Eviction Policy Manager

Custom logic with data structures

Implements LRU, LFU, TTL eviction policies and manages switching

Cache Storage

HashMap with auxiliary data structures

Stores cached entries and metadata for eviction

TTL Scheduler

Priority queue or timing wheel

Tracks expiration times and triggers TTL evictions

Metrics Collector

Counters and logging

Collects cache hits, misses, and eviction statistics

Request Flow

1. Client sends a cache read or write request to Cache Interface.

2. Cache Interface checks Cache Storage for the key.

3. If key found, update access metadata (timestamp or frequency) in Eviction Policy Manager and return value.

4. If key not found, fetch from source (out of scope), insert into Cache Storage.

5. Eviction Policy Manager checks if cache size exceeds limit.

6. If full, Eviction Policy Manager selects entries to evict based on current policy (LRU, LFU, or TTL).

7. TTL Scheduler triggers eviction for expired entries asynchronously.

8. Metrics Collector updates hit/miss/eviction counters after each operation.

9. Client receives response with cached data or miss indication.

Database Schema

Not applicable as this is an in-memory cache system. Key entities are cache entries with fields: key, value, last_access_time, access_frequency, expiration_time. Relationships are managed via data structures: hashmap for key lookup, linked list or heap for eviction ordering.

Scaling Discussion

Bottlenecks

Eviction decision latency increases with cache size

Memory overhead from tracking access metadata

TTL scheduler overhead with many expiring entries

Metrics collection causing contention under high load

Solutions

Use efficient data structures like doubly linked lists for LRU and frequency lists for LFU to keep eviction O(1)

Limit metadata size per entry and use approximate counters if needed

Implement hierarchical timing wheels or bucketed TTL to reduce scheduler overhead

Batch metrics updates asynchronously to reduce contention

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the eviction policies and data structures, 10 minutes discussing scaling and trade-offs, and 5 minutes summarizing.

Explain differences and use cases for LRU, LFU, and TTL

Describe data structures used for each eviction policy

Discuss how to switch policies dynamically

Highlight performance considerations and latency targets

Mention how metrics help monitor cache health

Address scaling challenges and practical solutions

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