Bird
Raised Fist0

Distributed Cache Design - Consistent Hashing for Cache Node Assignment

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Distributed Cache Design - Consistent Hashing for Cache Node Assignment
Design a scalable distributed cache using consistent hashing to assign keys to cache nodes
mediumCachingFreq: common
Prerequisites:Distributed Systems BasicsHashing
⚙️
Functional Requirements
  • Cache key-value pairs with low latency (sub-millisecond) lookups
  • Distribute cache keys evenly across multiple cache nodes using consistent hashing
  • Support dynamic addition and removal of cache nodes with minimal key remapping
  • Provide cache TTL (time-to-live) for automatic expiration of stale entries
  • Ensure cache availability and fault tolerance during node failures
  • Support cache invalidation and updates from backend data sources
📊
Non-Functional Requirements
  • Support 2 billion daily active users (DAU)
  • Handle peak write QPS of approximately 1 million writes/sec
  • Achieve 99.99% availability SLA for cache operations
  • Maintain 100ms P99 latency for cache read and write operations
  • Ensure minimal cache rebalancing overhead on node changes (<5% keys remapped)
❓
Clarifying Questions to Ask
  • What is the expected cache hit ratio and cache size per node?
  • Are cache nodes homogeneous in capacity or heterogeneous?
  • What is the expected frequency of cache node addition/removal?
  • Is the cache write-through or write-back with the backend data store?
  • What is the maximum acceptable cache warm-up time after node changes?
  • Are there any constraints on network topology or data center locations?
Out of Scope
✗ Design of backend persistent storage or database
✗ Cache consistency models beyond eventual consistency (e.g., strong consistency)
✗ Detailed security and encryption mechanisms
✗ Client-side caching or CDN integration
📌
Assumptions
  • 2 billion DAU
  • Each user generates 40 cacheable events/messages per day
  • Average cache entry size is 100 bytes
  • Cache retention period is 7 days
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor: 925,926 × 2 ≈ 1,851,852 writes/sec
read qpsAssuming 10× read-to-write ratio: 925,926 × 10 ≈ 9,259,260 reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day
retention storage8 TB × 7 days = 56 TB
with replication56 TB × 3 replicas = 168 TB total storage
🖥️
Server Estimate
cache nodesAssuming each Redis node handles 50K writes/sec and 500K reads/sec, need ~40 nodes for writes and ~20 nodes for reads; provision 50 nodes for headroom
metadata nodes3 nodes running ZooKeeper or etcd for consistent hashing ring metadata and coordination
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |      Client App      |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Consistent Hash Ring |
          |  (ZooKeeper/etcd)    |
          +----------+-----------+
                     |
                     v
          +----------------------+
          |   Cache Nodes (Redis) |
          |  (50 nodes cluster)   |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Backend Data Store    |
          +----------------------+
🧩
Components
Client Application
Generates cache read/write requests and queries the consistent hash ring to locate cache nodes
Why thisClients perform hashing locally to reduce coordination overhead and latency using local consistent hashing libraries
Why notCentralized proxy would become a bottleneck at 1M+ QPS and increase latency
Consistent Hash Ring Metadata Store (ZooKeeper/etcd)
Maintains the consistent hashing ring state and cache node membership metadata
Why thisZooKeeper/etcd provide strong consistency and watch APIs for fast membership updates
Why notUsing a relational DB would add latency and lack native watch/notify features
Cache Nodes (Redis Cluster)
Store cache key-value pairs with TTL and serve low-latency read/write requests
Why thisRedis supports TTL natively, sub-millisecond lookups, and cluster mode for sharding
Why notMemcached lacks native TTL and cluster management, complicating scaling
Backend Data Store
Source of truth for data; cache invalidation and updates originate here
Why thisPersistent storage ensures durability beyond cache eviction
Why notUsing cache as source of truth risks data loss and inconsistency
Cache Client Library
Implements consistent hashing logic and routes requests to appropriate cache nodes
Why thisLocal hashing reduces network hops and avoids centralized routing bottlenecks
Why notProxy-based routing adds latency and single point of failure
🔄
Data Flow
1
Client Application → Consistent Hash Ring Metadata Store
Fetch latest cache node membership and hash ring info
Clients cache ring info locally and subscribe to updates
2
Client Application → Cache Client Library
Hash cache key using consistent hashing to find target cache node
Minimizes key remapping on node changes
3
Cache Client Library → Cache Node (Redis)
Send read/write request to selected cache node
Redis handles TTL and fast in-memory operations
4
Cache Node → Backend Data Store
On cache miss or invalidation, fetch or update data from backend
Ensures cache consistency with source of truth
5
Backend Data Store → Cache Node
Push cache invalidation or update events
Keeps cache entries fresh and consistent

Practice

(1/5)
1. In the message delivery trace, at Step 4 the Delivery Worker checks Bob's presence TTL in the presence service cache. What happens if Bob's presence TTL has expired at this step?
easy
A. The Delivery Worker queues the message for offline storage and does not send over WebSocket
B. The Delivery Worker immediately marks the message as delivered without sending
C. The Delivery Worker retries presence check indefinitely before sending
D. The Delivery Worker sends the message over WebSocket regardless of presence TTL

Solution

  1. Step 1: Trace Delivery Worker decision at Step 4 -- Bob's presence TTL

    If Bob's presence TTL expired, Delivery Worker treats Bob as offline and queues message for offline storage.

  2. Step 2: Eliminate other options

    Marking delivered without sending is incorrect; retrying indefinitely blocks delivery; sending regardless ignores offline status.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Expired presence TTL -> queue for offline delivery [check]
Hint: Expired presence TTL means offline -> queue message [check]
Common Mistakes:
2. In a system where a Layer 7 load balancer receives an HTTP request at step 3, what happens at step 4 when it applies URL-based routing rules?
easy
A. The load balancer inspects HTTP headers and forwards to the matched backend pool
B. The load balancer forwards the raw TCP packet without modification
C. The load balancer performs DNS resolution to select backend IP
D. The load balancer encrypts the request before forwarding

Solution

  1. Step 1: Understand Layer 7 load balancer behavior at step 4

    At step 4, the Layer 7 load balancer inspects HTTP headers (like URL path) to decide routing.

  2. Step 2: Eliminate options inconsistent with Layer 7 behavior

    Forwarding raw TCP packets (A) is Layer 4 behavior; DNS resolution (C) is client-side; encryption (D) is unrelated here.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Layer 7 LB inspects HTTP headers and routes accordingly [check]
Hint: Layer 7 LB inspects HTTP headers before forwarding [OK]
Common Mistakes:
3. In a message delivery system, at Step 4 the Delivery Worker reads the message offset from Kafka and attempts to deliver it to the consumer. What happens if the consumer's acknowledgment is not received within the configured timeout?
easy
A. The Delivery Worker retries delivery without committing the offset
B. The Delivery Worker marks the message as delivered and commits the offset
C. The Delivery Worker discards the message and moves to the next offset
D. The Delivery Worker pauses all deliveries until manual intervention

Solution

  1. Step 1: Understand Kafka offset commit semantics

    Kafka commits offsets only after successful acknowledgment to avoid message loss.

  2. Step 2: Delivery Worker behavior on missing ack

    If no ack is received, the worker retries delivery to ensure at-least-once semantics; it does not commit offset or discard messages.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Retries without committing offset -> ensures message redelivery [check]
Hint: No ack -> retry delivery, no offset commit [OK]
Common Mistakes:
4. In a relational database transaction flow, at Step 4 the transaction manager checks the lock table before committing. What happens if the lock is held by another transaction at this step?
easy
A. The transaction manager immediately aborts the transaction without retry
B. The transaction manager waits (blocks) until the lock is released or a timeout occurs
C. The transaction manager skips the lock check and commits anyway
D. The transaction manager escalates the lock to a global lock manager

Solution

  1. Step 1: Understand lock table role at Step 4

    The transaction manager uses the lock table to ensure no conflicting writes before commit.

  2. Step 2: Behavior on lock contention

    If the lock is held, the transaction manager blocks to maintain serializability, waiting or timing out rather than aborting immediately or skipping checks.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Lock contention causes blocking until release or timeout [check]
Hint: Lock held -> transaction blocks, no skipping or immediate abort [check]
Common Mistakes:
5. For ensuring exactly-once payment event processing in a distributed payment gateway, which architecture is more appropriate given the constraint that external payment processors may send duplicate callbacks?
medium
A. Use an event sourcing pattern with idempotent event handlers and a unique event ID store
B. Use a relational database with unique constraints on callback IDs and synchronous processing
C. Use a stateless microservice that processes each callback independently without deduplication
D. Use a batch job that aggregates callbacks and processes them periodically

Solution

  1. Step 1: Identify the need for deduplication and exactly-once semantics

    Duplicate callbacks require idempotent processing and event tracking to avoid double charges.

  2. Step 2: Evaluate event sourcing with idempotent handlers

    Event sourcing stores all events immutably with unique IDs, enabling replay and deduplication.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Event sourcing with idempotent handlers ensures exactly-once processing [check]
Hint: Event sourcing + idempotent handlers handle duplicates best [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