Cache invalidation strategies in HLD - System Design Exercise

Design: Cache Invalidation Strategies System

Design focuses on cache invalidation strategies and mechanisms. Cache storage implementation and client application logic are out of scope.

Functional Requirements

FR1: Support multiple cache invalidation methods to keep cache data fresh

FR2: Handle cache invalidation for read-heavy applications with frequent updates

FR3: Ensure minimal stale data served to users

FR4: Support distributed cache systems

FR5: Provide mechanisms to invalidate cache entries automatically or manually

Non-Functional Requirements

NFR1: System must handle up to 100,000 cache invalidations per minute

NFR2: Cache invalidation latency should be under 100ms for most cases

NFR3: System availability target is 99.9% uptime

NFR4: Cache consistency should be eventual but minimize stale reads

NFR5: Support horizontal scaling for cache nodes and invalidation services

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

❓ Question 7

Key Components

Cache storage layer (Redis, Memcached, CDN)

Invalidation event producer (application or database triggers)

Invalidation event consumer or processor

Message queue or pub/sub system for invalidation events

TTL (Time To Live) configuration

Cache client with invalidation hooks

Design Patterns

Write-through cache

Write-around cache

Write-back cache

Cache aside pattern

Time-based expiration (TTL)

Explicit invalidation via events

Lazy invalidation

Cache versioning or tagging

Reference Architecture

  +----------------+       +-------------------+       +----------------+
  | Application    | <---> | Cache Client      | <---> | Cache Storage  |
  +----------------+       +-------------------+       +----------------+
           |                         ^                          ^
           |                         |                          |
           v                         |                          |
  +----------------+                |                          |
  | Database       |                |                          |
  +----------------+                |                          |
           |                        |                          |
           v                        |                          |
  +----------------+       +-------------------+              |
  | Invalidation   | ----> | Message Queue /   | --------------+
  | Event Producer |       | Pub/Sub System    |
  +----------------+       +-------------------+
                                   |
                                   v
                          +-------------------+
                          | Invalidation       |
                          | Event Consumer     |
                          +-------------------+

Components

Application

Any backend service

Generates data changes and triggers cache invalidation events

Cache Client

Custom or library-based client

Handles cache reads/writes and listens for invalidation signals

Cache Storage

Redis, Memcached, or CDN cache

Stores cached data with TTL and supports invalidation

Database

Relational or NoSQL database

Source of truth for data; changes trigger invalidation

Invalidation Event Producer

Application hooks or DB triggers

Detects data changes and publishes invalidation events

Message Queue / Pub/Sub System

Kafka, RabbitMQ, Redis Pub/Sub

Distributes invalidation events to consumers reliably

Invalidation Event Consumer

Service or worker process

Receives invalidation events and removes or updates cache entries

Request Flow

1. 1. Application updates data in the database.

2. 2. Invalidation Event Producer detects the data change (via hooks or triggers).

3. 3. Producer publishes an invalidation event to the Message Queue or Pub/Sub system.

4. 4. Invalidation Event Consumer subscribes to the queue and receives the event.

5. 5. Consumer invalidates or updates the corresponding cache entries in Cache Storage.

6. 6. Cache Client fetches fresh data from the database on next cache miss or after invalidation.

7. 7. Cache entries may also expire automatically based on TTL settings.

Database Schema

Entities: - DataEntity: Represents the main data stored in the database. - InvalidationEvent: Records events with fields: event_id (PK), data_entity_id (FK), event_type (update/delete), timestamp. Relationships: - DataEntity 1:N InvalidationEvent (one data entity can have many invalidation events). This schema supports tracking changes that trigger cache invalidation.

Scaling Discussion

Bottlenecks

High volume of invalidation events causing message queue overload.

Cache storage becoming a bottleneck under heavy invalidation and read traffic.

Latency in propagating invalidation events causing stale cache reads.

Single point of failure in invalidation event consumers.

Database triggers or hooks adding overhead on write operations.

Solutions

Partition and scale message queues horizontally; use topic partitioning.

Use distributed cache clusters with sharding and replication.

Implement batch invalidation or debounce rapid invalidation events.

Deploy multiple consumers with load balancing and failover.

Optimize database triggers; consider asynchronous event generation.

Interview Tips

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

Explain different cache invalidation strategies and when to use each.

Discuss trade-offs between data freshness and system performance.

Describe how event-driven invalidation improves scalability.

Highlight importance of TTL and manual invalidation combination.

Address potential bottlenecks and scaling solutions clearly.

Practice

1. Which cache invalidation strategy automatically removes cached data after a set time period?

easy

A. Time-to-Live (TTL)

B. Write-through caching

C. Explicit invalidation

D. Cache-aside

Solution

1. Step 1: Understand TTL concept

   TTL means cached data expires automatically after a fixed time, ensuring freshness.

2. Step 2: Compare with other strategies

   Write-through updates cache on writes, explicit invalidation requires manual removal, cache-aside loads on demand.

3. Final Answer:

   Time-to-Live (TTL) -> Option A

4. Quick Check:

   Automatic expiry = TTL [OK]

Hint: TTL means cache expires after fixed time automatically [OK]

Common Mistakes:

• Confusing write-through with automatic expiry
• Thinking explicit invalidation is automatic
• Mixing cache-aside with TTL

2. Which of the following is the correct description of the write-through cache invalidation strategy?

easy

A. Cache is cleared manually by the application

B. Cache is updated only when data is read

C. Cache is updated immediately when data is written

D. Cache data expires after a fixed time

Solution

1. Step 1: Define write-through caching

   Write-through means every write to the database also updates the cache immediately.

2. Step 2: Eliminate other options

   Cache is updated only when data is read describes cache-aside, C is explicit invalidation, D is TTL.

3. Final Answer:

   Cache is updated immediately when data is written -> Option C

4. Quick Check:

   Write-through = update cache on write [OK]

Hint: Write-through updates cache on every write instantly [OK]

Common Mistakes:

• Confusing read update with write update
• Mixing explicit invalidation with write-through
• Assuming TTL applies to write-through

3. Consider a cache-aside strategy where the cache is empty initially. If a client requests data key K and the cache misses, what happens next?

medium

A. The system returns an error immediately

B. The system fetches data from the database and updates the cache

C. The system waits for explicit invalidation before fetching

D. The system uses stale data from cache

Solution

1. Step 1: Understand cache-aside behavior on miss

   Cache-aside loads data from the database on a cache miss and updates the cache.

2. Step 2: Check other options

   The system returns an error immediately is wrong because system does not error on miss, C is incorrect as explicit invalidation is unrelated, D is wrong because cache is empty.

3. Final Answer:

   The system fetches data from the database and updates the cache -> Option B

4. Quick Check:

   Cache miss triggers DB fetch and cache update [OK]

Hint: Cache-aside loads from DB on miss, then caches data [OK]

Common Mistakes:

• Assuming cache returns error on miss
• Confusing explicit invalidation with cache miss handling
• Thinking stale data is returned on miss

4. A system uses explicit invalidation but sometimes serves stale data. What is the most likely cause?

medium

A. Cache entries expire too quickly

B. Cache updates on every write immediately

C. Cache-aside strategy is used incorrectly

D. Invalidation messages are delayed or lost

Solution

1. Step 1: Analyze explicit invalidation issues

   Explicit invalidation depends on timely invalidation messages to remove stale cache entries.

2. Step 2: Identify cause of stale data

   If invalidation messages are delayed or lost, stale data remains in cache and is served.

3. Final Answer:

   Invalidation messages are delayed or lost -> Option D

4. Quick Check:

   Delayed invalidation causes stale cache [OK]

Hint: Delayed invalidation messages cause stale cache data [OK]

Common Mistakes:

• Thinking cache expiry too fast causes stale data
• Confusing write-through with explicit invalidation
• Assuming cache-aside errors cause stale data here

5. You design a high-traffic e-commerce system where product prices update rarely but must be accurate. Which cache invalidation strategy best balances freshness and performance?

hard

A. Use explicit invalidation triggered by price update events

B. Use write-through caching to update cache on every price change

C. Use cache-aside with manual cache clearing

D. Use a short TTL to expire cache frequently

Solution

1. Step 1: Analyze system requirements

   Prices update rarely but must be accurate, so cache should update only on changes, not frequently expire.

2. Step 2: Evaluate strategies

   Short TTL causes unnecessary reloads, write-through may be costly if writes are rare, cache-aside with manual clearing is error-prone.

3. Step 3: Choose explicit invalidation

   Explicit invalidation triggered by price update events ensures cache is fresh only when needed, balancing performance and accuracy.

4. Final Answer:

   Use explicit invalidation triggered by price update events -> Option A

5. Quick Check:

   Rare updates + accuracy = explicit invalidation [OK]

Hint: Rare updates + accuracy = explicit invalidation best [OK]

Common Mistakes:

• Choosing short TTL causing frequent reloads
• Assuming write-through is best for rare updates
• Ignoring event-driven invalidation benefits