Bird
Raised Fist0

Cache Stampede - Thundering Herd Problem and Prevention Strategies

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Cache Stampede - Thundering Herd Problem and Prevention Strategies
Design strategies to prevent cache stampede and thundering herd at scale
mediumCachingFreq: common
⚙️
Functional Requirements
  • Serve cached data for high read QPS with sub-10ms latency
  • Prevent multiple clients from simultaneously querying backend on cache miss (thundering herd)
  • Support automatic cache expiration and refresh strategies
  • Allow fallback to backend data source on cache failure
  • Provide metrics and alerts for cache hit/miss rates and stampede events
📊
Non-Functional Requirements
  • Support 2 billion daily active users generating 40 cache reads per user per day
  • Achieve 99.99% availability for cache reads
  • Ensure 100ms P99 latency for cache read requests
  • Handle peak read QPS of at least 925K requests per second
  • Cache consistency within 1 minute of backend data updates
❓
Clarifying Questions to Ask
  • What is the expected cache miss rate under normal and peak loads?
  • Are stale reads acceptable during cache refresh or must data be strongly consistent?
  • What is the TTL range for cached entries and are there hot keys with different TTLs?
  • Is the cache distributed globally or regionally? What is the network topology?
  • What backend data sources are used and what is their read latency?
  • Are there existing cache layers or is this a greenfield design?
Out of Scope
✗ Design of the backend database or primary data store
✗ Authentication and authorization mechanisms
✗ Detailed UI or client-side caching strategies
📌
Assumptions
  • 2 billion DAU
  • 40 cache reads per user per day
  • 100 bytes average cache entry size
  • Cache miss rate of 5%
⚡
QPS Calculation
read qps2B × 40 / 86400 ≈ 925,926 reads/sec
write qps925,926 × 5% ≈ 46,296 writes/sec (cache misses)
peak write qpsAssuming 3× peak factor: 46,296 × 3 ≈ 138,888 writes/sec
💾
Storage Estimate
daily storage925,926 reads × 100 bytes ≈ 88.3 GB/day
retention days7
total storage88.3 GB × 7 ≈ 618.1 GB
with replication618.1 GB × 3 replicas ≈ 1.85 TB
🖥️
Server Estimate
cache nodesAssuming 50 MB/s per Redis node outbound bandwidth, need 2 nodes per 100 MB/s outbound → ~2 nodes per 100 MB/s × 1 = 2 nodes minimum; with overhead and replication, estimate 10 Redis nodes
backend db nodesTo handle 138,888 writes/sec peak, Cassandra nodes with 10K writes/sec capacity → 14-15 nodes
🏗️
Architecture Diagram
Architecture Diagram
       +-------------+
       |   Clients   |
       +------+------+
              |
              v
       +------+-------+
       | Load Balancer|
       +------+-------+
              |
              v
       +------+-------+
       |  Redis Cache |
       +------+-------+
              |
      Cache Miss? |
        Yes       |
              v
       +------+-------+
       | Lock Manager |
       +------+-------+
              |
        Lock Acquired?
         /        \
       Yes        No
       /            \
      v              v
 +---------+    +------------+
 | Backend |    | Wait & Poll|
 |  Store  |    +------------+
 +---------+
      |
      v
 +---------+
 | Redis   |
 | Cache   |
 +---------+
🧩
Components
Redis Cache
Primary caching layer serving reads with TTL-based expiration
Why thisRedis supports sub-millisecond lookups with native TTL expiration and Lua scripting for atomic lock operations
Why notMemcached lacks native TTL expiration and atomic locking, making it unsuitable for stampede prevention
Lock Manager (Redis-based)
Coordinates distributed locks on cache keys to prevent thundering herd on cache miss
Why thisRedis SETNX with expiration provides lightweight distributed locking with fail-safe expiry
Why notZookeeper introduces higher latency and operational complexity unsuitable for sub-100ms P99 latency
Backend Data Store (e.g., Cassandra)
Source of truth for data on cache misses and refreshes
Why thisCassandra scales linearly for high write throughput and offers tunable consistency for cache refreshes
Why notPostgreSQL requires complex manual sharding at 138K writes/sec; B-tree writes don't scale linearly
Load Balancer
Distributes client requests evenly across cache nodes to avoid hotspots
Why thisNginx or Envoy provide low-latency, high-throughput load balancing with health checks
Why notDNS round-robin lacks health checks and fine-grained traffic control
Wait & Poll Mechanism
Clients that fail to acquire lock wait and poll cache for updated data
Why thisPolling with exponential backoff reduces load on backend and prevents stampede
Why notImmediate retries cause backend overload and exacerbate thundering herd
🔄
Data Flow
1
Client → Redis Cache
Read request for key
Fast path: cache hit returns data immediately
2
Redis Cache → Client
Return cached data if present
Sub-millisecond response on hit
3
Client → Lock Manager (Redis)
Attempt to acquire distributed lock for cache key on miss
Only one client proceeds to backend
4
Lock Manager → Client
Grant or deny lock
Lock expires automatically to prevent deadlocks
5
Client with lock → Backend Data Store
Fetch fresh data
Single backend query prevents stampede
6
Client with lock → Redis Cache
Update cache with fresh data and TTL
Cache refreshed atomically
7
Client without lock → Redis Cache
Poll cache with exponential backoff
Waits for cache to be refreshed
8
Redis Cache → Client without lock
Return updated data once available
Prevents multiple backend queries

Practice

(1/5)
1. In a composite index on columns (A, B), a query filters only on column B. At step 3 in the query execution plan, the database engine uses the composite index. What is the state of index usage at this step?
easy
A. The composite index cannot be used efficiently because column A is not filtered, causing a full index scan
B. The composite index is fully used to seek on column B alone efficiently
C. The database ignores the composite index and uses a table scan instead
D. The composite index is partially used by scanning leaf nodes but with poor performance

Solution

  1. Step 1: Understand composite index column order

    Composite indexes are ordered by the first column (A), then second (B). Queries filtering only on B cannot efficiently seek the index without filtering on A.

  2. Step 2: Analyze index usage at step 3

    Since column A is not filtered, the engine must scan the entire index or large portions, resulting in a full index scan rather than an efficient seek.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Composite index requires leading column filter for efficient seeks [check]
Hint: Composite index needs leading column filter for seeks [check]
Common Mistakes:
2. In the digital wallet system's transaction processing flow, at Step 4 the Ledger Service applies the debit and credit entries. What happens if the Ledger Service detects a mismatch in the double-entry records at this step?
easy
A. The Ledger Service retries the transaction indefinitely until the entries match
B. The Ledger Service marks the transaction as failed and triggers an alert for manual reconciliation
C. The Ledger Service ignores the mismatch and commits the debit entry only
D. The Ledger Service rolls back the entire transaction and deletes all related entries

Solution

  1. Step 1: Understand Ledger Service's double-entry validation

    The Ledger Service enforces double-entry consistency; mismatches indicate data corruption or bugs.

  2. Step 2: Evaluate failure handling

    Retrying indefinitely (A) risks blocking; ignoring mismatch (C) breaks accounting; deleting entries (D) risks data loss. Marking failed and alerting (B) enables safe manual reconciliation.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Mismatch triggers failure mark and alert -> safe reconciliation [check]
Hint: Mismatch triggers failure mark and alert, not silent retry [OK]
Common Mistakes:
3. A distributed system needs to enforce a global rate limit of 1000 requests per second across multiple API servers. Which component is best suited to maintain a consistent count of requests in real-time?
easy
A. Use a message queue to buffer requests and count them asynchronously
B. Use a local in-memory counter on each API server and aggregate periodically
C. Use a relational database with row-level locking for counting requests
D. Use a centralized Redis counter with atomic increment operations

Solution

  1. Step 1: Identify the need for a consistent global count

    Local counters aggregated periodically (Use a local in-memory counter on each API server and aggregate periodically) cause stale counts and race conditions, failing real-time enforcement.

  2. Step 2: Evaluate Redis atomic increments

    Redis supports atomic INCR commands ensuring consistent, real-time global counters across distributed servers.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Redis atomic counters ensure global consistency and low latency [check]
Hint: Centralized atomic counters ensure global consistency [check]
Common Mistakes:
4. You need to design an Elasticsearch cluster optimized for low-latency search queries on a read-heavy workload with occasional node failures. Which architecture choice best balances query speed and fault tolerance?
medium
A. Use multiple smaller primary shards with replica shards distributed across nodes
B. Use only replica shards for queries and keep primary shards offline
C. Disable replicas to reduce write overhead and rely on snapshot backups
D. Use a single large shard per index to minimize cross-shard coordination

Solution

  1. Step 1: Evaluate shard size and replication

    Multiple smaller shards allow parallel query execution; replicas provide fault tolerance and load balancing.

  2. Step 2: Eliminate other options

    Single large shard causes query bottleneck; disabling replicas risks data loss and no failover; using only replicas offline is invalid as primaries handle writes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Multiple shards + replicas balance speed and fault tolerance [check]
Hint: Multiple shards + replicas optimize read speed and fault tolerance [check]
Common Mistakes:
5. For a high-throughput e-commerce platform requiring sortable, unique order IDs generated across multiple regions with minimal coordination, which ID generation approach is best?
medium
A. Use Twitter Snowflake-style custom IDs with timestamp and region bits
B. Use UUIDv4 generated randomly at each region
C. Use auto-increment IDs generated by a centralized database
D. Use auto-increment IDs generated independently per region without coordination

Solution

  1. Step 1: Identify requirements

    High throughput, sortable, unique IDs across regions with minimal coordination.

  2. Step 2: Evaluate options

    UUIDv4 (A) is unique but not sortable; centralized auto-increment (C) causes bottlenecks; independent auto-increment (D) risks collisions; Snowflake-style IDs (B) embed timestamp and region, enabling sortable, unique IDs with decentralized generation.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Snowflake IDs -> sortable, unique, decentralized [check]
Hint: Sortable unique IDs at scale -> Snowflake pattern [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard