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.