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
45 min · senior
senior

You are designing a distributed caching layer for a 50M DAU startup that requires low-latency key-value access with strong consistency guarantees. The cache cluster must handle dynamic node membership, minimize cache misses during scaling or failures, and support encrypted data in transit. The system must maintain P99 latency under 200ms at peak load.

Constraints
  • Support dynamic addition and removal of cache nodes without significant cache misses
  • Encrypt all data in transit between clients and cache nodes
  • Ensure P99 latency under 200ms for 95% of requests at peak load
  • Handle 50M DAU with estimated 10M QPS cache requests
  • Support cache key distribution with minimal rehashing on node changes
  • Provide mechanisms for client-side failover and retry
📋
Guided Steps
1/5
Step 1
Choosing the Consistent Hashing Algorithm
Which consistent hashing algorithm and data structure will you use to distribute keys across cache nodes, and why?
💡 Hint
Consider virtual nodes to balance load and reduce key remapping on node changes.
Key Decision
Use Ketama consistent hashing with virtual nodes to evenly distribute keys and minimize remapping during node joins/leaves.
Interviewer Expectation
Mid: Names Ketama consistent hashing. Senior: Explains virtual nodes reduce load imbalance and key remapping from O(N) to O(1/N) fraction.
⚠️Common Wrong Answer
Using simple modulo hashing - causes massive cache misses and rebalancing on node changes.
Step 2
Handling Dynamic Node Membership
How will the system detect and handle cache node additions or failures to maintain consistent hashing correctness?
💡 Hint
Think about cluster membership services and how clients get updated hash rings.
Key Decision
Use ZooKeeper or etcd for cluster membership and notify clients to update Ketama hash ring on membership changes.
Interviewer Expectation
Mid: Mentions ZooKeeper for membership. Senior: Explains client-side hash ring update propagation and impact on cache hit ratio.
⚠️Common Wrong Answer
Hardcoding node list in clients - leads to stale hash rings and cache misses after node changes.
Step 3
Encrypting Data In Transit
How will you ensure encryption of data between clients and cache nodes without compromising latency?
💡 Hint
Consider TLS termination and lightweight encryption libraries optimized for low latency.
Key Decision
Use TLS 1.3 with session resumption between clients and Redis Cluster nodes to encrypt traffic with minimal handshake overhead.
Interviewer Expectation
Mid: Suggests TLS encryption. Senior: Explains TLS 1.3 session resumption reduces latency impact and integration with Redis Cluster.
⚠️Common Wrong Answer
Encrypting at application layer with custom crypto - adds latency and complexity, breaking P99 latency SLA.
Step 4
Client Failover and Retry Mechanisms
How will the client handle cache node failures or timeouts to maintain availability and low latency?
💡 Hint
Consider client-side retries, failover to replica nodes, and circuit breaker patterns.
Key Decision
Implement client-side retry with exponential backoff and failover to replica nodes using Redis Cluster's slot migration awareness.
Interviewer Expectation
Mid: Mentions retries on failure. Senior: Explains failover to replicas and avoiding thundering herd with circuit breakers.
⚠️Common Wrong Answer
No retry or failover - leads to increased errors and degraded user experience during node failures.
Step 5
Minimizing Cache Misses During Scaling
What strategies will you use to minimize cache misses and rehashing when scaling the cache cluster up or down?
💡 Hint
Think about consistent hashing properties and virtual node count tuning.
Key Decision
Tune virtual node count per physical node to balance key distribution and minimize remapping; use sticky client hash ring caching.
Interviewer Expectation
Mid: Mentions virtual nodes reduce remapping. Senior: Explains trade-off between virtual node count and client memory overhead, and sticky hash ring caching.
⚠️Common Wrong Answer
Recomputing hash ring from scratch on every node change - causes massive cache misses and latency spikes.
🔌
API Design Challenge
Sketch 3 core API endpoints for the distributed cache client library that interacts with the consistent hashing layer.
Hints
  • How does the client send a key-value pair to the correct cache node?
  • How does the client handle cache misses or node failures transparently?
  • How does the client refresh or update the cluster node membership information?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of Ketama consistent hashing with virtual nodes to minimize remapping
  • Cluster membership management with ZooKeeper or etcd for dynamic node updates
  • TLS 1.3 encryption with session resumption to meet latency constraints
  • Client-side failover and retry mechanisms integrated with Redis Cluster slot awareness
Good to Have - 30%
  • Tuning virtual node count for load balancing and client memory trade-offs
  • Client hash ring caching and update propagation to reduce cache misses
  • Circuit breaker pattern to prevent cascading failures during node outages
Bonus - 10%
  • API design that cleanly exposes routing, membership refresh, and failover
  • Detailed latency and throughput estimation connecting design choices to 50M DAU scale
Anti-patterns to Avoid
Simple modulo hashing for key distribution - causes massive cache misses on node changes
Hardcoding node list in clients - leads to stale hash rings and inconsistent routing
Custom encryption at application layer - adds unacceptable latency breaking P99 SLA
No client retry or failover - results in poor availability and degraded user experience
Recomputing hash ring from scratch on every membership change - causes latency spikes and cache misses
Ignoring virtual node tuning - leads to uneven load and hotspots on cache nodes
✅
Model Answer
▼ Reveal

Design uses Ketama consistent hashing with virtual nodes and ZooKeeper for cluster membership to distribute keys evenly and handle dynamic node changes. TLS 1.3 encrypts data in transit with session resumption to meet latency SLAs. Client libraries implement failover and retry integrated with Redis Cluster slot awareness to maintain availability.

Key Decisions
  • Use Ketama consistent hashing with virtual nodes to minimize key remapping during node changes
  • Employ ZooKeeper or etcd for dynamic cluster membership updates and client notification
  • Implement TLS 1.3 with session resumption to encrypt data in transit with minimal latency impact
  • Integrate client-side failover and retry mechanisms with Redis Cluster slot migration awareness
  • Tune virtual node count to balance load and client memory overhead
  • Cache hash ring client-side and propagate updates to reduce cache misses during scaling
  • Use circuit breaker patterns to prevent cascading failures during node outages
  • Ketama consistent hashing with virtual nodes - balances load and minimizes key remapping on node changes
  • ZooKeeper or etcd for cluster membership management - ensures clients have up-to-date node list
  • TLS 1.3 with session resumption - encrypts data in transit with minimal latency overhead
  • Redis Cluster slot awareness - enables client failover and retry to replicas on node failures
  • Client-side hash ring caching and update propagation - reduces latency and cache misses during scaling
  • Exponential backoff retry and circuit breaker patterns - improve availability and prevent cascading failures
  • Virtual node count tuning - balances between even key distribution and client memory footprint
  • Client library APIs exposing key-based routing, cluster refresh, and failover handling

Practice

(1/5)
1. In the live streaming pipeline, at step 4 the Transcoder Worker reads packets from Kafka and generates HLS segments. What happens if the Transcoder Worker encounters a delayed packet for a segment already finalized?
easy
A. The Transcoder discards the packet and continues streaming
B. The Transcoder reopens the finalized segment and appends the packet
C. The Transcoder buffers the packet until the next segment window
D. The Transcoder triggers a full stream restart to maintain consistency

Solution

  1. Step 1: Understand segment finalization

    Once an HLS segment is finalized and published, it is immutable to ensure consistent playback for viewers.

  2. Step 2: Handling delayed packets

    Reopening finalized segments (B) breaks immutability. Buffering for next segment (C) misplaces packets out of order. Restarting stream (D) is costly and unnecessary. Discarding late packets (A) maintains low latency and stream integrity.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Discarding late packets preserves segment immutability and low latency [check]
Hint: Finalized HLS segments are immutable; discard late packets [check]
Common Mistakes:
2. If the rollback mechanism is missing in the deployment system, what exact failure occurs when a faulty version is released during Canary deployment?
medium
A. Users experience degraded service indefinitely as faulty version remains live without fallback
B. The previous stable version is restored manually without affecting users
C. The deployment system retries indefinitely, causing deployment pipeline blockage
D. The system automatically disables all new features, causing partial outages

Solution

  1. Step 1: Understand rollback absence impact

    Without rollback, faulty Canary version cannot be reverted automatically.

  2. Step 2: Trace failure effect

    Faulty version remains live, causing degraded user experience indefinitely.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    No rollback -> faulty version stays live -> degraded service persists [check]
Hint: No rollback means faulty version stays live, degrading users indefinitely [OK]
Common Mistakes:
3. For a global service requiring sub-second failover and consistent user session routing, which architecture is better and why?
medium
A. Use client-side geo-DNS resolution to select data centers for each request
B. Use DNS-based load balancing with short TTLs for fast failover
C. Use Anycast IP routing combined with health-aware GSLB for session stickiness and failover
D. Use BGP routing policies to steer traffic to preferred data centers

Solution

  1. Step 1: Evaluate DNS-based load balancing

    DNS with short TTLs (Use DNS-based load balancing with short TTLs for fast failover) still suffers from caching delays and cannot guarantee session stickiness.

  2. Step 2: Assess Anycast with GSLB

    Anycast IP routing routes users to nearest data center at network level; combined with health-aware GSLB, it enables sub-second failover and consistent session routing.

  3. Step 3: Consider client-side and BGP options

    Client-side geo-DNS (Use client-side geo-DNS resolution to select data centers for each request) is unreliable and complex; BGP policies (Use BGP routing policies to steer traffic to preferred data centers) have slow convergence and no session guarantees.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Anycast + GSLB enables fast failover and session stickiness [check]
Hint: Anycast + GSLB = fast failover + session stickiness [check]
Common Mistakes:
4. At 10x scale, which component is most likely to fail first and why in Slack's real-time delivery system?
hard
A. Chat servers, because WebSocket connections are stateful and cannot be resharded easily
B. Presence service, because TTL cache invalidations overwhelm the system
C. Kafka brokers, because partition count cannot scale beyond a fixed limit
D. The database, because increased writes cause locking and slow queries

Solution

  1. Step 1: Identify stateful bottlenecks at scale

    Chat servers hold WebSocket connections in memory, which are stateful and tied to specific servers, limiting horizontal scaling.

  2. Step 2: Compare other components

    Databases can be sharded; Kafka scales with partitions; presence service caches can be distributed; chat servers' stateful connections are the hardest to shard.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful WebSocket connections -> chat servers bottleneck at 10x scale [check]
Hint: Stateful WebSocket binds chat servers -> first bottleneck [check]
Common Mistakes:
5. At 10x scale, which component in a push-based metrics collection system is most likely to fail first, and why?
hard
A. The aggregation workers, because CPU-intensive aggregation cannot scale horizontally
B. The storage backend, because it cannot handle the increased write throughput
C. The Kafka cluster, because partition count limits throughput and causes broker overload
D. The metric agents, because they overwhelm network bandwidth with frequent pushes

Solution

  1. Step 1: Analyze storage backend scaling

    Storage can be scaled horizontally with sharding; unlikely first failure.

  2. Step 2: Analyze Kafka cluster scaling

    Kafka scales with partitions but requires careful tuning; not first failure at 10x.

  3. Step 3: Analyze aggregation workers

    Aggregation workers scale horizontally; CPU load manageable with more instances.

  4. Step 4: Analyze metric agents

    Agents push metrics frequently, increasing network usage exponentially; network bandwidth at agents is limited and saturates first.

  5. Final Answer:

    Option D -> Option D

  6. Quick Check:

    Agents saturate network bandwidth first at 10x scale [check]
Hint: Agents saturate network bandwidth before backend bottlenecks [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