Bird
Raised Fist0

Rendezvous Hashing - Alternative Approach and Trade-offs

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Rendezvous Hashing - Alternative Approach and Trade-offs
Designing and evaluating alternative approaches to Rendezvous Hashing for distributed key assignment
mediumConsistent HashingFreq: medium
Prerequisites:Distributed Systems BasicsHashing
⚙️
Functional Requirements
  • Assign keys (e.g., user IDs, cache keys) to nodes deterministically with minimal remapping on node changes
  • Support dynamic addition and removal of nodes with minimal disruption
  • Provide uniform load distribution across nodes to avoid hotspots
  • Allow efficient lookup of node responsible for a given key with low latency
  • Support replication of keys to multiple nodes for fault tolerance
  • Expose APIs for node membership management and key-to-node resolution
📊
Non-Functional Requirements
  • Support at least 2 billion daily active users (DAU) with 40 messages per user per day
  • Achieve 99.99% availability for key-to-node resolution requests
  • Ensure 100ms P99 latency for node lookup operations
  • Handle peak write QPS of approximately 1 million writes per second
  • Scale to at least 10,000 nodes in the cluster without significant performance degradation
❓
Clarifying Questions to Ask
  • What is the expected churn rate of nodes joining and leaving the cluster?
  • Is the key distribution uniform or skewed (e.g., hot keys)?
  • What is the replication factor for keys across nodes?
  • Are node failures expected to be transient or permanent?
  • Is the system read-heavy, write-heavy, or balanced?
  • What is the maximum acceptable latency for key-to-node resolution?
Out of Scope
✗ Design of the underlying storage system for key-value data
✗ Security and authentication mechanisms for node communication
✗ Detailed network topology or physical data center placement
✗ Client-side caching or retry logic
📌
Assumptions
  • 2 billion DAU
  • 40 messages per user per day
  • 100 bytes per message
  • Replication factor of 3
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor → 1,851,852 writes/sec
read qpsAssuming 10× read amplification → 9,259,260 reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8,000 TB/day ≈ 8 PB/day
retention days7
total storage8 PB × 7 = 56 PB
with replication56 PB × 3 = 168 PB
🖥️
Server Estimate
node management serviceAssuming 10,000 nodes, 1 server per 100 nodes → 100 servers
lookup serviceTo handle 9.2M reads/sec with 10k QPS/server → 926 servers
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |  Client Applications  |
          +----------+-----------+
                     | Key Lookup / Write
                     v
          +----------------------+
          |  Rendezvous Hashing   |
          |  Lookup Service (API) |
          +----------+-----------+
                     | Node assignment
                     v
          +----------------------+
          |  Node Membership Svc  |
          +----------+-----------+
                     | Node state updates
                     v
          +----------------------+
          |  Node Registry Store  |
          | (e.g., Apache Zookeeper)|
          +----------+-----------+
                     | Node health monitoring
                     v
          +----------------------+
          |  Data Nodes (10,000)  |
          +----------------------+
🧩
Components
Rendezvous Hashing Lookup Service
Computes node assignment for keys using Rendezvous Hashing algorithm
Why thisRendezvous Hashing provides minimal key remapping on node changes and uniform load distribution
Why notConsistent Hashing with virtual nodes causes uneven load and higher remapping on node churn
Node Membership Service
Manages cluster membership, node join/leave events, and propagates membership changes
Why thisCentralized membership service ensures consistent view of nodes for hashing decisions
Why notGossip protocols have eventual consistency and can cause inconsistent node views at scale
Node Registry Store (Apache Zookeeper)
Stores node metadata, health status, and membership info with strong consistency
Why thisZookeeper provides reliable coordination and watches for membership changes with low latency
Why notEtcd or Consul have higher latencies or weaker guarantees under heavy load at 10k nodes
Client Applications
Perform key lookups and writes by querying the Rendezvous Hashing Lookup Service
Why thisCentralized lookup service abstracts node assignment complexity from clients
Why notClient-side hashing risks inconsistent views and stale node info causing errors
Data Nodes
Store actual data assigned by hashing; handle replication and serve read/write requests
Why thisDistributed nodes scale horizontally to handle 1M+ writes/sec and large storage
Why notMonolithic storage cannot scale to 10k nodes or handle dynamic membership
🔄
Data Flow
1
Client Applications → Rendezvous Hashing Lookup Service
Send key lookup request
Client queries which node is responsible for a given key
2
Rendezvous Hashing Lookup Service → Node Membership Service
Fetch current node list
Ensures hashing uses up-to-date membership info
3
Node Membership Service → Node Registry Store
Watch for node join/leave events
Keeps membership consistent and updated
4
Rendezvous Hashing Lookup Service → Client Applications
Return assigned node for key
Client uses this info to route data requests
5
Client Applications → Data Nodes
Send read/write requests
Data nodes store or retrieve data for assigned keys
6
Data Nodes → Node Membership Service
Send health heartbeats
Membership service detects node failures
7
Node Membership Service → Rendezvous Hashing Lookup Service
Notify membership changes
Lookup service updates hashing ring accordingly
🗄️
NodeMembership
PK: cluster_id
cluster_id (string)node_id (string)status (string)last_heartbeat (timestamp)
Stores membership info and health status of nodes per cluster
🗄️
KeyAssignment
PK: key_hash
key_hash (string)replica_index (int)node_id (string)
Maps keys to assigned nodes including replicas
🔌
GetNodeForKey
Request
{
  "key": "string"
}
Response
{
  "primary_node": "string",
  "replica_nodes": "string[]"
}
Returns primary and replica nodes responsible for the given key
🔌
UpdateNodeMembership
Request
{
  "node_id": "string",
  "status": "string"
}
Response
{
  "success": "boolean"
}
Updates node status in membership service
🔌
GetClusterNodes
Request
{
  "cluster_id": "string"
}
Response
{
  "nodes": "string[]"
}
Returns list of active nodes in the cluster

Practice

(1/5)
1. A live streaming platform must ingest RTMP streams from millions of broadcasters with minimal latency and reliably convert them to HLS segments for viewers. Which component is best suited to buffer and order incoming RTMP packets before transcoding?
easy
A. A relational database with ACID transactions to store RTMP packets
B. An in-memory cache like Redis with TTL eviction
C. A distributed message queue like Kafka partitioned by stream ID
D. A CDN edge server caching HLS segments

Solution

  1. Step 1: Identify buffering and ordering needs

    RTMP packets must be buffered and ordered per stream before transcoding to maintain low latency and correct playback order.

  2. Step 2: Evaluate component suitability

    A relational DB (A) is too slow for high-throughput packet buffering. Redis (C) lacks strong ordering guarantees and durability. CDN edge (D) caches output, not input packets. Kafka (B) supports partitioning by stream ID, ensuring ordered, durable buffering.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Kafka partitions ensure ordered, durable buffering per stream [check]
Hint: Kafka partitions per stream ensure ordered, durable buffering [check]
Common Mistakes:
2. In a sliding window rate limiter, at step 3 the system records a new request timestamp. What happens internally to the stored counters at this step?
easy
A. Old timestamps outside the sliding window are removed before adding the new timestamp
B. The leaky bucket drains tokens at a fixed rate before accepting the request
C. The token bucket refills tokens based on elapsed time before decrementing
D. The fixed window counter resets to zero if the current minute changed

Solution

  1. Step 1: Understand sliding window counter mechanics

    Sliding window counters maintain timestamps of recent requests and remove those outside the window to keep an accurate count.

  2. Step 2: At step 3, old timestamps beyond the window are purged before adding the new request timestamp

    This ensures the count reflects only requests within the sliding window duration.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Sliding window removes expired timestamps before counting new requests [check]
Hint: Sliding window purges old timestamps before counting new ones [check]
Common Mistakes:
3. At 10x scale, which component in WhatsApp's architecture is most likely to fail first and why?
hard
A. Chat Servers because WebSocket connections are stateful and cannot be resharded easily
B. Kafka brokers because partition count cannot be increased dynamically
C. The database because it cannot handle 10x more writes without sharding
D. Presence service because TTL cache invalidations become too frequent

Solution

  1. Step 1: Analyze stateful WebSocket connections on Chat Servers

    Chat Servers maintain in-memory state per WebSocket; scaling requires connection migration which is complex.

  2. Step 2: Compare other components

    Databases can shard; Kafka partitions can be increased with rebalancing; presence TTL cache scales horizontally.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful WebSocket connections -> Chat Servers bottleneck at scale [check]
Hint: Stateful WebSocket -> Chat Servers bottleneck at 10x scale [check]
Common Mistakes:
4. At 10x scale, which component fails first in a real-time chat system and why?
hard
A. The database fails first due to increased write volume causing slow queries
B. The message queue fails first due to partition leader overload
C. The load balancer fails first because it cannot handle the increased TCP connections
D. The chat servers fail first because WebSocket connections are stateful and cannot be resharded easily

Solution

  1. Step 1: Identify stateful bottleneck at scale

    Chat servers maintain stateful WebSocket connections bound to server memory, making resharding difficult at 10x scale.

  2. Step 2: Compare other components

    Databases (A) can be scaled with sharding and caching; message queues (C) can add partitions; load balancers (D) scale horizontally more easily.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stateful WebSocket servers -> first bottleneck at 10x scale [check]
Hint: Stateful WebSocket servers block scaling; resharding is hard [check]
Common Mistakes:
5. At 10x scale, which component in a Cassandra cluster is most likely to fail first and why?
hard
A. The coordinator nodes due to increased load managing large partitions and routing requests
B. The storage nodes due to disk space exhaustion
C. The client application due to increased request latency
D. The network switches due to bandwidth saturation

Solution

  1. Step 1: Identify bottlenecks at 10x scale

    Coordinator nodes handle query routing and aggregation; increased scale causes them to manage larger partitions and more requests.

  2. Step 2: Compare other components

    Storage nodes scale horizontally and add disk; network bandwidth scales with infrastructure upgrades; client latency is secondary to cluster bottlenecks.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Coordinator overload -> first failure point at 10x scale [check]
Hint: Coordinator nodes bottleneck first at scale due to routing load [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