Multi-level caching in HLD - System Design Exercise

Design: Multi-level Caching System

Design focuses on read path caching with multiple cache layers and cache consistency. Write path and cache invalidation strategies are included at a high level. Out of scope: detailed database schema design and write-heavy workload optimization.

Functional Requirements

FR1: Serve data requests with minimal latency

FR2: Support multiple cache layers (e.g., in-memory, distributed cache, disk cache)

FR3: Ensure cache consistency and freshness

FR4: Handle cache misses by fetching data from the primary database

FR5: Support high read throughput with low latency

FR6: Provide fallback mechanisms if a cache layer fails

Non-Functional Requirements

NFR1: System must handle 100,000 read requests per second

NFR2: P99 latency for cache hits should be under 5 milliseconds

NFR3: Availability target of 99.9% uptime

NFR4: Cache layers should have configurable expiration policies

NFR5: Data consistency should be eventual between cache layers and database

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Client application or service

In-memory cache (e.g., local cache like LRU cache)

Distributed cache (e.g., Redis, Memcached)

Persistent cache or disk cache layer

Primary database

Cache invalidation and refresh mechanism

Monitoring and metrics system

Design Patterns

Cache-aside pattern

Write-through and write-back caching

Cache invalidation strategies (time-based, event-based)

Multi-level cache hierarchy

Fallback and retry mechanisms

Reference Architecture

Client
  |
  v
Local In-Memory Cache (Level 1)
  |
  v
Distributed Cache (Level 2)
  |
  v
Persistent Cache / Disk Cache (Level 3)
  |
  v
Primary Database

Monitoring & Metrics system observes all layers

Components

Client

Any application or service

Sends data requests and receives responses

Local In-Memory Cache (Level 1)

LRU Cache or similar in-memory cache

Fastest cache layer to serve frequent requests with minimal latency

Distributed Cache (Level 2)

Redis or Memcached cluster

Shared cache across multiple clients or servers to reduce database load

Persistent Cache / Disk Cache (Level 3)

SSD-based cache or local disk cache

Stores less frequently accessed data with higher latency but larger capacity

Primary Database

Relational or NoSQL database

Source of truth for all data

Cache Invalidation and Refresh Mechanism

Background jobs or event-driven triggers

Keeps cache data fresh and consistent with the database

Monitoring and Metrics System

Prometheus, Grafana, or similar

Tracks cache hit rates, latencies, errors, and system health

Request Flow

1. Client sends a data request.

2. Request checks Local In-Memory Cache (Level 1). If hit, return data immediately.

3. If miss, request goes to Distributed Cache (Level 2). If hit, return data and update Level 1 cache.

4. If miss again, request goes to Persistent Cache (Level 3). If hit, return data and update Level 2 and Level 1 caches.

5. If still miss, fetch data from Primary Database.

6. Update all cache layers with fresh data.

7. Return data to client.

8. Cache invalidation jobs run periodically or are triggered by data changes to refresh or remove stale cache entries.

Database Schema

Entities: - DataItem(id, value, last_updated) Relationships: - No complex relationships needed for caching; primary key 'id' used for cache keys. Cache entries map to DataItem by id with expiration timestamps.

Scaling Discussion

Bottlenecks

Local in-memory cache size limits and eviction under high load

Distributed cache network latency and throughput limits

Cache consistency delays causing stale data

Database overload on cache misses

Cache invalidation complexity at scale

Solutions

Use efficient eviction policies and increase local cache size with memory optimization

Scale distributed cache horizontally with sharding and clustering

Implement event-driven cache invalidation and TTLs to reduce staleness

Use read replicas and database sharding to handle load

Automate cache invalidation with messaging systems and monitor cache freshness

Interview Tips

Time: Spend 10 minutes understanding requirements and clarifying constraints, 20 minutes designing the multi-level cache architecture and data flow, 10 minutes discussing scaling and trade-offs, and 5 minutes summarizing.

Explain why multi-level caching reduces latency and load

Describe cache hit and miss flows clearly

Discuss cache consistency and invalidation strategies

Highlight scalability challenges and solutions

Mention monitoring importance for cache health

Practice

1. What is the main purpose of multi-level caching in system design?

easy

A. To increase the size of the main database

B. To reduce data access time by storing data in multiple cache layers

C. To slow down data retrieval for security reasons

D. To store data only in the slowest storage layer

Solution

1. Step 1: Understand the role of caching

   Caching stores frequently accessed data closer to the user to reduce access time.

2. Step 2: Identify multi-level caching benefits

   Multi-level caching uses several layers from fastest to slowest to optimize speed and reduce load on main storage.

3. Final Answer:

   To reduce data access time by storing data in multiple cache layers -> Option B

4. Quick Check:

   Multi-level caching = Faster data access [OK]

Hint: Multi-level caching speeds up data access using layers [OK]

Common Mistakes:

• Thinking caching increases database size
• Assuming caching slows down retrieval
• Believing data is stored only in slow storage

2. Which of the following correctly describes the order of cache levels from fastest to slowest?

easy

A. L3 Cache, L2 Cache, L1 Cache, Main Memory

B. Main Memory, L3 Cache, L2 Cache, L1 Cache

C. L1 Cache, L2 Cache, L3 Cache, Main Memory

D. Main Memory, L1 Cache, L2 Cache, L3 Cache

Solution

1. Step 1: Recall cache hierarchy

   Cache levels are arranged by speed and size: L1 is fastest and smallest, followed by L2, then L3, then main memory.

2. Step 2: Match the correct order

   L1 Cache, L2 Cache, L3 Cache, Main Memory lists caches from fastest (L1) to slowest (main memory) correctly.

3. Final Answer:

   L1 Cache, L2 Cache, L3 Cache, Main Memory -> Option C

4. Quick Check:

   Cache order = L1 -> L2 -> L3 -> Memory [OK]

Hint: Remember L1 is fastest cache closest to CPU [OK]

Common Mistakes:

• Confusing cache order with memory order
• Assuming main memory is faster than caches
• Mixing up L2 and L3 cache speeds

3. Consider a system with three cache levels: L1, L2, and L3. If a data request misses in L1 and L2 but hits in L3, what happens next?

medium

A. Data is discarded and request fails

B. Data is fetched only from L3 and not stored anywhere else

C. Data is fetched from main memory directly, ignoring L3

D. Data is fetched from L3 and copied to L1 and L2 caches

Solution

1. Step 1: Understand cache hit and miss

   A miss means data is not found in that cache level; a hit means data is found.

2. Step 2: Follow multi-level caching behavior

   When data is found in a lower cache (L3), it is promoted to higher caches (L1, L2) to speed future access.

3. Final Answer:

   Data is fetched from L3 and copied to L1 and L2 caches -> Option D

4. Quick Check:

   Cache hit in L3 promotes data up [OK]

Hint: Data moves up cache levels on hit to speed access [OK]

Common Mistakes:

• Assuming data is not copied to higher caches
• Thinking data is fetched from main memory after L3 hit
• Believing request fails on cache miss

4. A multi-level cache system is experiencing frequent cache misses at all levels. Which of the following is the most likely cause?

medium

A. Cache sizes are too small to hold working data set

B. Cache levels are ordered from slowest to fastest

C. Data is always fetched from the highest cache level

D. Cache eviction policy is set to never remove data

Solution

1. Step 1: Analyze cache miss causes

   Frequent misses usually happen if caches cannot hold the data needed, causing constant reloads.

2. Step 2: Evaluate given options

   Cache sizes are too small to hold working data set correctly identifies small cache size as cause; other options describe incorrect or impossible scenarios.

3. Final Answer:

   Cache sizes are too small to hold working data set -> Option A

4. Quick Check:

   Small cache size = frequent misses [OK]

Hint: Small caches cause more misses due to limited space [OK]

Common Mistakes:

• Confusing cache order with miss frequency
• Assuming data always fetched from highest cache
• Believing no eviction means no misses

5. You are designing a multi-level caching system for a high-traffic web application. Which strategy best balances speed and storage cost?

hard

A. Use a small, fast L1 cache; medium L2 cache; large, slower L3 cache

B. Use equally sized caches at all levels for uniform speed

C. Use only one large cache to simplify design

D. Use a large L1 cache and small L3 cache to prioritize speed

Solution

1. Step 1: Understand cache size and speed tradeoff

   Fast caches are expensive and small; slower caches are cheaper and larger.

2. Step 2: Apply multi-level caching best practice

   Using small fast L1, medium L2, and large slower L3 balances cost and performance effectively.

3. Final Answer:

   Use a small, fast L1 cache; medium L2 cache; large, slower L3 cache -> Option A

4. Quick Check:

   Cache size-speed tradeoff = small fast + large slow [OK]

Hint: Small fast + large slow caches balance cost and speed [OK]

Common Mistakes:

• Assuming equal cache sizes improve speed
• Using only one cache ignores multi-level benefits
• Making L1 cache large wastes cost without speed gain