Bird
Raised Fist0

Consistent Hashing in Distributed Caches - Redis Cluster, Memcached

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Consistent Hashing in Distributed Caches - Redis Cluster, Memcached
Designing scalable distributed caches using consistent hashing to minimize data reshuffling and ensure low latency
mediumConsistent HashingFreq: common
Prerequisites:Distributed Systems BasicsHashing
⚙️
Functional Requirements
  • Distribute cache keys evenly across multiple cache nodes to balance load
  • Minimize key remapping when nodes are added or removed (low rebalancing)
  • Support fast key lookups with sub-millisecond latency
  • Handle node failures gracefully with automatic failover or replication
  • Support dynamic scaling of cache nodes without downtime
  • Provide consistent hashing ring management and metadata synchronization
📊
Non-Functional Requirements
  • Support at least 2 billion daily active users (DAU)
  • Sustain peak write throughput of approximately 925K writes/sec
  • Ensure 99.99% availability with automatic failover
  • Maintain 100ms P99 latency for cache get/set operations
  • Handle data replication with minimal overhead and eventual consistency
❓
Clarifying Questions to Ask
  • What is the expected cache key size and value size distribution?
  • Are we supporting replication or just partitioning for availability?
  • What is the expected read-to-write ratio for cache operations?
  • How frequently do nodes join or leave the cluster (scale dynamics)?
  • Is strong consistency required or eventual consistency acceptable?
  • What failure detection and recovery mechanisms are expected?
Out of Scope
✗ Designing the backend persistent storage or database
✗ Implementing application-level cache invalidation policies
✗ Security and authentication mechanisms for cache access
✗ Detailed network infrastructure or physical data center design
📌
Assumptions
  • 2 billion DAU
  • 40 cache write operations per user per day
  • 100 bytes average size per cache entry
  • Read-to-write ratio of 10:1
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor → 1,851,852 writes/sec
read qpswrite_qps × 10 = 9,259,260 reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day
retention days7
total storage8 TB × 7 = 56 TB
with replication56 TB × 2 (replication factor) = 112 TB
🖥️
Server Estimate
cache nodesAssuming each Redis node handles 50K writes/sec → 1,851,852 / 50,000 ≈ 38 nodes
metadata nodes3-5 nodes for consistent hashing ring management and cluster metadata
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |   Client Application  |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Consistent Hashing    |
          | Ring Metadata Manager |
          +----------+-----------+
                     |
          +----------+-----------+
          |                      |
   +------+-----+          +-----+------+
   | Redis Node |          | Redis Node |
   |   (Shard)  |          |   (Shard)  |
   +------------+          +------------+
          |                      |
          +----------+-----------+
                     |
          +----------+-----------+
          |  Replication / Failover|
          +----------------------+
🧩
Components
Client Application
Generates cache requests and uses consistent hashing metadata to route keys
Why thisClient-side routing reduces proxy bottlenecks and latency by directly contacting cache nodes using Redis Cluster or Memcached clients
Why notCentral proxy (e.g., Twemproxy) creates a single point of failure and adds latency at 10M+ QPS
Consistent Hashing Ring Metadata Manager
Maintains the hash ring, node membership, and virtual nodes for even key distribution
Why thisCentralized metadata with distributed caching clients ensures minimal key remapping on node changes using technologies like ZooKeeper or etcd
Why notStatic hashing or modulo-based partitioning causes massive key remapping on node changes
Redis Cluster Nodes
Store cache data shards; each node holds a subset of keys based on consistent hashing
Why thisRedis Cluster natively supports hash slots and automatic failover with sub-millisecond lookups
Why notMemcached lacks native cluster management and replication, increasing operational complexity
Replication / Failover Layer
Replicates data across nodes and promotes replicas on primary failure to ensure availability
Why thisRedis Sentinel or Cluster mode provides automatic failover and high availability
Why notManual failover or external orchestration adds latency and risk of data loss
Virtual Nodes (VNodes)
Each physical node hosts multiple virtual nodes to smooth key distribution and reduce hotspots
Why thisVNodes reduce uneven load and minimize data movement during scaling events, a technique used in systems like Cassandra and Amazon Dynamo
Why notSingle hash per node causes uneven load and large data reshuffling on node changes
🔄
Data Flow
1
Client Application → Consistent Hashing Ring Metadata Manager
Fetch latest hash ring metadata and node mappings
Clients cache metadata locally and refresh periodically or on cluster events
2
Client Application → Redis Cluster Node
Hash key using consistent hashing to identify target node
Client routes get/set requests directly to responsible Redis node
3
Redis Cluster Node → Replication / Failover Layer
Replicate writes asynchronously to replica nodes
Ensures data durability and availability on node failure
4
Replication / Failover Layer → Redis Cluster Node
Promote replica to primary on failure detection
Automatic failover minimizes downtime and data loss
5
Consistent Hashing Ring Metadata Manager → Client Application
Notify clients of node addition/removal and updated ring
Clients update local metadata to minimize key remapping

Practice

(1/5)
1. A globally distributed application requires strong consistency for writes but must tolerate network partitions gracefully. Which replication pattern best fits this scenario?
easy
A. Primary-replica replication with asynchronous replication to replicas
B. Multi-primary replication with asynchronous conflict resolution
C. Multi-primary replication with eventual consistency and last-write-wins
D. Primary-replica replication with synchronous writes to primary

Solution

  1. Step 1: Understand consistency requirements

    Strong consistency requires writes to be serialized and acknowledged before success.

  2. Step 2: Evaluate replication patterns

    Primary-replica with synchronous writes ensures all writes go through a single primary, preserving consistency. Multi-primary with async or eventual consistency cannot guarantee strong consistency.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Primary sync writes -> strong consistency, tolerates partitions by blocking writes [check]
Hint: Strong consistency -> single primary synchronous writes [check]
Common Mistakes:
2. In the request flow of a video call setup, at step 5 the Signaling Server receives an SDP offer from Alice and forwards it to Bob. What state does the Signaling Server maintain immediately after forwarding the offer?
easy
A. It stores the offer and waits for Bob's SDP answer before updating session state
B. It queues the offer indefinitely until Bob acknowledges receipt
C. It deletes the offer after forwarding, assuming Bob will respond directly to Alice
D. It marks the session as established and starts media relay between Alice and Bob

Solution

  1. Step 1: Trace Signaling Server behavior at step 5

    The server forwards Alice's SDP offer to Bob and stores it to correlate with Bob's answer.

  2. Step 2: Understand session state management

    Session is not established until Bob's SDP answer arrives; the offer must be retained temporarily.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Signaling Server stores offer awaiting answer before session established [check]
Hint: Signaling stores offer until answer arrives, then session established [check]
Common Mistakes:
3. In a system design interview, at step 4, you explain your choice of caching layer to reduce latency. What happens at this step when the cache misses the requested data?
easy
A. The cache silently returns stale data without fetching fresh data
B. The cache duplicates the request to multiple backends simultaneously
C. The cache returns an error immediately to the client without fallback
D. The cache triggers a backend fetch and updates itself before returning data

Solution

  1. Step 1: Trace cache behavior on miss at step 4

    On a cache miss, the cache should fetch fresh data from the backend to serve the request.

  2. Step 2: Confirm cache updates itself before responding

    This ensures subsequent requests hit the cache, reducing latency and load on backend.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Cache miss triggers backend fetch and cache update [check]
Hint: Cache miss triggers backend fetch and update [check]
Common Mistakes:
4. For a large-scale web crawler, which architecture best balances crawl rate and politeness when crawling millions of domains with varying rate limits?
medium
A. Centralized Scheduler with a global queue and a single Politeness Policy enforcer
B. Distributed Scheduler with domain-based sharding and local Politeness Policy enforcement per shard
C. Multiple independent crawlers each with their own Scheduler and no shared Politeness Policy
D. Single-threaded crawler with a priority queue sorted by domain crawl time

Solution

  1. Step 1: Analyze centralized vs distributed scheduling

    Centralized Scheduler becomes a bottleneck at scale; distributed sharding allows parallelism and localized politeness enforcement.

  2. Step 2: Evaluate other options

    Independent crawlers without shared politeness risk domain overload; single-threaded crawler can't scale to millions of domains.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Distributed sharding enables scalable politeness enforcement [check]
Hint: Distributed sharding scales politeness enforcement best [OK]
Common Mistakes:
5. For a globally distributed collaborative editor with many offline users, which approach better supports eventual consistency and offline edits, and why?
medium
A. Use Operational Transformation (OT) because it requires a central server to order operations
B. Use a relational database with strict locking to serialize all edits globally
C. Use CRDTs because they allow local operations to be merged without coordination and support offline edits
D. Use a message queue with timestamp ordering to ensure global operation order

Solution

  1. Step 1: Compare OT and CRDT for offline and distributed scenarios

    OT typically requires a central server to order and transform operations, making offline support complex.

  2. Step 2: Understand CRDT advantages

    CRDTs are designed for decentralized environments, allowing local operations to be merged eventually without coordination, ideal for offline edits and global distribution.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    CRDTs enable offline edits and eventual consistency without central coordination [check]
Hint: CRDTs merge offline edits without central coordination [OK]
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