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

You are building a distributed key-to-node assignment service for a 50 million daily active user (DAU) startup. The system must assign user requests to backend nodes using Rendezvous Hashing to ensure minimal disruption on node changes. The startup requires all routing decisions to be encrypted end-to-end for compliance, supports offline node delivery for resilience, and must maintain P99 request assignment latency under 200ms at peak load.

Constraints
  • End-to-end encryption of routing keys and node assignments is mandatory
  • Offline node delivery support to handle transient node unavailability
  • P99 request assignment latency must be under 200ms at 50M DAU scale
  • System must handle dynamic node membership with minimal key remapping
  • Must support at least 10,000 routing requests per second with linear scalability
📋
Guided Steps
1/5
Step 1
Choosing the Hashing Algorithm and Data Structure
Which hashing algorithm and data structure will you use to implement Rendezvous Hashing at scale, and why?
💡 Hint
Consider hash collision resistance and computational efficiency for 10k+ requests/sec.
Key Decision
Use MurmurHash3 combined with a priority queue per key to compute weighted scores for nodes - MurmurHash3 offers fast non-cryptographic hashing with low collision rate suitable for high throughput.
Interviewer Expectation
Mid: Names MurmurHash3 for speed. Senior: Explains why cryptographic hashes like SHA-256 are too slow for 10k+ QPS and how priority queues enable efficient max-score selection.
⚠️Common Wrong Answer
Using SHA-256 for all hashing - causes high CPU overhead and increases latency beyond 200ms P99.
Step 2
Handling Encrypted Routing Keys
How will you incorporate encryption into the hashing process without breaking consistent assignment guarantees?
💡 Hint
Think about deterministic encryption or hashing on encrypted inputs.
Key Decision
Apply deterministic AES-GCM encryption with a fixed nonce per key before hashing - ensures encrypted keys produce consistent hash outputs while preserving confidentiality.
Interviewer Expectation
Mid: Mentions encrypting keys before hashing. Senior: Details deterministic encryption mode choice and how fixed nonce avoids randomization breaking consistent hashing.
⚠️Common Wrong Answer
Encrypt keys with random IVs before hashing - breaks consistent hashing as encrypted outputs differ per request.
Step 3
Node Membership Management and Offline Delivery
How will you manage dynamic node membership and support offline node delivery to maintain availability?
💡 Hint
Consider a distributed coordination system and fallback mechanisms for unreachable nodes.
Key Decision
Use Apache ZooKeeper for node membership coordination and maintain a local cache with fallback to secondary nodes via Rendezvous Hashing re-computation on misses.
Interviewer Expectation
Mid: Names ZooKeeper for membership. Senior: Explains ZooKeeper ephemeral nodes for liveness, local cache for latency, and fallback logic for offline nodes.
⚠️Common Wrong Answer
Polling a central database for node status - causes stale membership info and increases latency beyond 200ms P99.
Step 4
Ensuring Low Latency at Scale
What architectural choices ensure P99 latency under 200ms for 10k+ requests per second at 50M DAU scale?
💡 Hint
Think about caching, parallelism, and avoiding blocking calls in the request path.
Key Decision
Deploy stateless Rendezvous Hashing workers behind a load balancer with local in-memory caches (e.g., Caffeine) and asynchronous ZooKeeper watchers to avoid blocking on membership updates.
Interviewer Expectation
Mid: Mentions caching and load balancing. Senior: Explains asynchronous membership updates, cache TTL tuning, and horizontal scaling to maintain latency SLAs.
⚠️Common Wrong Answer
Synchronous ZooKeeper calls on every request - causes blocking and latency spikes above 200ms P99.
Step 5
API Design for Client Interaction
Design 3 core API endpoints for key assignment, node membership updates, and health checks. What are their inputs, outputs, and security considerations?
💡 Hint
Consider encrypted inputs, idempotency, and monitoring needs.
Key Decision
Endpoints: (1) POST /assignNode with encrypted key returns assigned node ID; (2) POST /updateNodes accepts encrypted node list with versioning; (3) GET /health returns node status and encryption key version. All use TLS and JWT for authentication.
Interviewer Expectation
Mid: Lists endpoints and basic inputs/outputs. Senior: Details encryption handling, versioning for membership updates, idempotency, and security via TLS+JWT.
⚠️Common Wrong Answer
Exposing unencrypted keys or node info in APIs - violates compliance and security requirements.
🔌
API Design Challenge
Sketch 3 core API endpoints for the Rendezvous Hashing service that handle key assignment, node membership updates, and health checks.
Hints
  • How does the client request the assigned node for a given key?
  • How are node membership changes propagated and acknowledged?
  • How does the system expose node health and encryption status?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of a fast non-cryptographic hash (MurmurHash3) for scalable hashing
  • Deterministic encryption approach preserving consistent hashing guarantees
  • Dynamic node membership management with ZooKeeper ephemeral nodes
  • Caching and asynchronous updates to meet P99 latency < 200ms
Good to Have - 30%
  • Stateless worker design for horizontal scalability
  • API design with encrypted inputs and secure authentication
  • Fallback offline node delivery mechanism
  • Versioning in node membership updates to avoid stale state
Bonus - 10%
  • Detailed failure mode analysis for node churn and encryption key rotation
  • Trade-off discussion on hashing algorithm choices and encryption overhead
Anti-patterns to Avoid
Using cryptographic hashes like SHA-256 for all hashing causing CPU bottlenecks and latency spikes
Encrypting keys with random IVs before hashing breaking consistent hashing guarantees
Polling a central database for node membership causing stale data and increased latency
Synchronous blocking calls to ZooKeeper on request path causing P99 latency violations
Exposing unencrypted keys or node info in APIs violating security and compliance
Single monolithic service without horizontal scaling causing throughput bottlenecks
✅
Model Answer
▼ Reveal

The system uses MurmurHash3 combined with deterministic AES-GCM encryption to assign encrypted keys to nodes via Rendezvous Hashing. Apache ZooKeeper manages dynamic node membership with ephemeral nodes to detect liveness. Stateless Rendezvous Hashing workers maintain local in-memory caches (e.g., Caffeine) updated asynchronously via ZooKeeper watchers to ensure P99 latency under 200ms at 10k+ QPS. The API exposes three endpoints secured with TLS and JWT: (1) POST /assignNode accepts encrypted keys and returns assigned node IDs, (2) POST /updateNodes accepts encrypted, versioned node membership lists, and (3) GET /health reports node health and encryption key version. Fallback logic recomputes assignments excluding offline nodes to support offline delivery.

Key Decisions
  • Use MurmurHash3 for hashing keys to nodes due to its speed and low collision rate, avoiding CPU overhead of cryptographic hashes like SHA-256.
  • Encrypt routing keys using deterministic AES-GCM with a fixed nonce to maintain consistent hashing outputs while preserving confidentiality.
  • Manage node membership dynamically with Apache ZooKeeper ephemeral nodes to detect node liveness and changes.
  • Maintain local in-memory caches in stateless workers to reduce ZooKeeper calls and ensure low latency, updated asynchronously via ZooKeeper watchers.
  • Design stateless workers behind a load balancer to horizontally scale and handle 10k+ requests per second.
  • Implement API endpoints with encrypted inputs and versioned node membership updates, secured by TLS and JWT to meet compliance and security requirements.
  • Include fallback logic to recompute node assignments excluding offline nodes to support offline delivery resilience.
  • MurmurHash3 for fast, low-collision hashing suitable for 10k+ QPS
  • Deterministic AES-GCM encryption with fixed nonce to preserve consistent hashing on encrypted keys
  • Apache ZooKeeper ephemeral nodes for dynamic node membership and liveness detection
  • Local in-memory cache (Caffeine) in stateless workers to reduce ZooKeeper calls and maintain P99 < 200ms
  • Stateless Rendezvous Hashing workers behind a load balancer for horizontal scalability
  • Asynchronous ZooKeeper watchers to update membership cache without blocking request path
  • API endpoints secured with TLS and JWT, supporting encrypted inputs and versioned node updates
  • Fallback logic to recompute assignments excluding offline nodes for offline delivery support

Practice

(1/5)
1. A distributed database system needs to evenly distribute data across 100 shards and handle dynamic addition/removal of shards with minimal data movement. Which component is most appropriate to manage shard assignment?
easy
A. Use a modulo-based hash function on the primary key to assign shards directly
B. Implement consistent hashing with virtual nodes to map keys to shards
C. Assign shards based on a centralized lookup table updated on every shard change
D. Use range-based partitioning with fixed key ranges per shard

Solution

  1. Step 1: Understand shard assignment requirements

    Modulo hashing (Use a modulo-based hash function on the primary key to assign shards directly) causes massive remapping when shards change; centralized lookup (Assign shards based on a centralized lookup table updated on every shard change) creates a bottleneck and single point of failure; range partitioning (Use range-based partitioning with fixed key ranges per shard) can cause hotspots and uneven load.

  2. Step 2: Evaluate consistent hashing benefits

    Consistent hashing with virtual nodes (Implement consistent hashing with virtual nodes to map keys to shards) evenly distributes keys and minimizes remapping when shards are added or removed, making it ideal for dynamic shard management.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Consistent hashing minimizes shard remapping on topology changes [check]
Hint: Consistent hashing minimizes data movement on shard changes [OK]
Common Mistakes:
2. In a system using Long Polling for server-to-client updates, at step 3 the client receives a response and immediately sends a new request. What is the client's state at step 4 before the server responds?
easy
A. The client is disconnected and will retry after a timeout due to connection closure.
B. The client has an open HTTP request waiting for the server response, and a new request is queued but not sent.
C. The client is waiting for the server response on the previous request, so no new request is sent yet.
D. The client has closed the previous connection and sent a new HTTP request, waiting for the next server response.

Solution

  1. Step 1: Trace Long Polling request lifecycle

    In Long Polling, the client sends a request and waits for the server to respond. Upon receiving the response, the client immediately sends a new request.

  2. Step 2: Determine client state at step 4

    At step 4, the previous connection is closed, and the client has an open new HTTP request waiting for the server's next response.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Long Polling client sends new request immediately after response [check]
Hint: Long Polling: response -> new request sent immediately [check]
Common Mistakes:
3. If the Master Node in an Elasticsearch cluster becomes unavailable, what is the immediate failure observed in cluster operations?
medium
A. Indexing requests fail because shards cannot be assigned to nodes
B. Search queries continue normally but cluster state updates are blocked
C. Replica shards stop syncing but primary shards continue indexing
D. All nodes shut down automatically to prevent data corruption

Solution

  1. Step 1: Understand Master Node role

    Master Node manages cluster state and shard allocation; without it, no new assignments occur.

  2. Step 2: Trace failure impact

    Existing primary shards continue indexing; replica syncing halts due to no cluster state updates; search queries may still work on available shards.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Without Master, replica syncing stops but primaries index [check]
Hint: Master down -> replica syncing halts, primaries keep indexing [check]
Common Mistakes:
4. For a system requiring minimal key remapping and uniform load distribution when nodes are frequently added or removed, which approach is best?
medium
A. Use rendezvous hashing without virtual nodes
B. Use modulo hashing with a fixed number of partitions per node
C. Use a centralized directory that reassigns keys on every node change
D. Use consistent hashing with virtual nodes and assign multiple tokens per physical node

Solution

  1. Step 1: Evaluate modulo hashing with fixed partitions

    Modulo hashing causes large remapping on node changes, poor for frequent changes.

  2. Step 2: Compare consistent hashing with virtual nodes

    Virtual nodes spread load evenly and reduce remapping, ideal for frequent node changes.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Virtual nodes in consistent hashing balance load and minimize remapping [check]
Hint: Virtual nodes smooth load and reduce remapping on node changes [check]
Common Mistakes:
5. At 10x current scale, which component in the YouTube view count system is most likely to fail first, and why?
hard
A. The CDN edge caches because they cannot handle the increased video delivery requests
B. The view count database because it is a centralized bottleneck for high write throughput
C. The transcoding pipeline because it cannot process 10x more video uploads in time
D. The upload service because it cannot handle 10x concurrent upload connections

Solution

  1. Step 1: Analyze component scalability at 10x load

    CDN edge caches (A) scale horizontally and are designed for massive read throughput. Transcoding pipeline (C) can be scaled with more workers. Upload service (D) can be scaled with load balancers and stateless servers.

  2. Step 2: Identify view count database bottleneck

    View count DB is a centralized write hotspot with high contention and latency sensitivity. At 10x scale, it becomes the first bottleneck due to write amplification and consistency requirements.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Centralized view count DB write bottleneck fails first [check]
Hint: Centralized DB write bottleneck breaks first at scale [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