Bird
Raised Fist0

Hash Ring - Virtual Nodes, Token Assignment, Node Addition and Removal

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Hash Ring with Virtual Nodes, Token Assignment, Node Addition and Removal
45 min · senior
senior

You are building a distributed key-value store backend for a startup with 50 million daily active users (DAU). The system must distribute keys evenly across nodes using consistent hashing with virtual nodes. Nodes can be added or removed dynamically without causing significant data reshuffling or downtime. The system must maintain P99 latency under 200ms for key lookups and support encrypted communication between nodes. The design must handle up to 10,000 nodes and 1 billion keys with minimal imbalance and support offline node detection.

Constraints
  • Support up to 10,000 physical nodes with virtual nodes for load balancing
  • P99 key lookup latency under 200ms at 50M DAU scale
  • Encrypted communication between nodes using TLS
  • Minimal data movement on node addition/removal (<5% keys remapped)
  • Offline node detection and automatic token reassignment
  • API must support dynamic node management and token queries
📋
Guided Steps
1/5
Step 1
Choosing the Consistent Hashing Mechanism
How would you implement consistent hashing with virtual nodes to evenly distribute keys and handle node churn?
💡 Hint
Consider using a hash ring with multiple tokens per physical node to reduce load imbalance.
Key Decision
Use a consistent hashing ring implemented with Murmur3 hash and virtual nodes (e.g., 100-200 tokens per physical node) stored in a sorted data structure like a TreeMap in Java or a skip list for O(log N) lookups.
Interviewer Expectation
Mid: Names consistent hashing with virtual nodes. Senior: Explains why Murmur3 hash is chosen for uniform distribution and how virtual nodes reduce load imbalance and hot spots.
⚠️Common Wrong Answer
Using a simple modulo-based partitioning which causes massive data reshuffling on node changes and uneven load distribution.
Step 2
Token Assignment and Data Movement Minimization
How do you assign tokens to nodes and ensure minimal key remapping when nodes join or leave?
💡 Hint
Assign multiple tokens per node randomly on the ring and reassign only affected token ranges on node changes.
Key Decision
Assign each physical node multiple virtual node tokens uniformly at random on the hash ring; on node addition/removal, only keys in the affected token ranges are remapped, limiting data movement to less than 5%.
Interviewer Expectation
Mid: Describes virtual nodes reduce imbalance. Senior: Quantifies data movement reduction and explains token reassignment algorithm with examples.
⚠️Common Wrong Answer
Assigning a single token per node causing large-scale key remapping and hotspots on node churn.
Step 3
Handling Node Addition and Removal
Describe the process and data structures used to add or remove nodes dynamically without downtime.
💡 Hint
Maintain a consistent hash ring data structure with atomic updates and use a distributed coordination system for synchronization.
Key Decision
Use Apache ZooKeeper or etcd for distributed coordination to atomically update the consistent hash ring metadata; update virtual node tokens in a sorted map and notify clients to refresh their routing tables.
Interviewer Expectation
Mid: Mentions ZooKeeper for coordination. Senior: Explains atomic ring updates, client cache invalidation, and how to avoid split-brain scenarios.
⚠️Common Wrong Answer
Updating ring metadata in a non-atomic way causing inconsistent routing and data loss.
Step 4
Offline Node Detection and Failover
How would you detect offline nodes and reassign their tokens to maintain availability?
💡 Hint
Use heartbeats with TTL in a distributed cache or coordination service to detect node liveness.
Key Decision
Implement node liveness detection using Redis with TTL keys updated every 30 seconds; if TTL expires, trigger token reassignment and notify clients to update routing.
Interviewer Expectation
Mid: Suggests heartbeat mechanism. Senior: Details Redis TTL usage, failover triggering, and how to avoid cascading failures.
⚠️Common Wrong Answer
Relying on client timeouts alone causing delayed failover and increased P99 latency.
Step 5
API Design for Node and Token Management
Design 3 core API endpoints for node addition/removal, key lookup, and token assignment queries.
💡 Hint
Consider REST or gRPC endpoints with clear request/response schemas for each operation.
Key Decision
Define RESTful APIs: POST /nodes to add nodes with virtual node count, DELETE /nodes/{nodeId} to remove nodes, GET /lookup?key= to return node responsible, GET /nodes/{nodeId}/tokens to return assigned token ranges.
Interviewer Expectation
Mid: Lists basic endpoints. Senior: Explains request validation, idempotency, and security (TLS + auth) for APIs.
⚠️Common Wrong Answer
No API for token queries causing clients to guess routing and increasing errors.
🔌
API Design Challenge
Sketch 3 core API endpoints for the hash ring system: node addition/removal, key-to-node lookup, and token assignment query.
Hints
  • How does a client add or remove a node and specify virtual nodes?
  • How does a client query which node owns a given key?
  • How does a client retrieve the token ranges assigned to a node?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Consistent hashing with virtual nodes to balance load
  • Atomic ring metadata updates using ZooKeeper or etcd
  • Node liveness detection with TTL-based heartbeats in Redis
  • API design covering node management and key lookup
Good to Have - 30%
  • Quantitative reasoning about data movement on node churn
  • Security considerations including TLS for node communication
  • Client cache invalidation and versioning for ring metadata
Bonus - 10%
  • Handling split-brain scenarios during ring updates
  • Optimizations for large-scale ring with 10,000+ nodes
Anti-patterns to Avoid
Using modulo-based partitioning causing massive data reshuffling on node changes, leading to high downtime and uneven load distribution
Single token per node causing load imbalance and hotspots, resulting in uneven resource utilization and potential bottlenecks
Non-atomic ring updates leading to inconsistent routing and data loss, causing client errors and data unavailability
Relying solely on client timeouts for node failure detection causing delayed failover and increased P99 latency, impacting user experience
No API for token queries forcing clients to guess routing increasing errors and operational complexity
Ignoring encryption requirements exposing sensitive metadata in transit, risking data breaches and compliance violations
✅
Model Answer
▼ Reveal

The system uses consistent hashing with Murmur3 and virtual nodes to evenly distribute keys and minimize data movement on node churn. Apache ZooKeeper coordinates atomic ring updates, Redis TTL keys detect offline nodes, and secure REST APIs manage nodes and token queries.

Key Decisions
  • Use Murmur3 hash for uniform distribution of keys and tokens
  • Assign 100-200 virtual nodes per physical node to reduce load imbalance
  • Employ Apache ZooKeeper or etcd for atomic updates to ring metadata to avoid inconsistencies
  • Implement node liveness detection using Redis TTL keys updated every 30 seconds to trigger failover
  • Use a sorted data structure like TreeMap for O(log N) token lookups
  • Design RESTful APIs with TLS encryption and authentication for secure node and token management
  • Murmur3 hash function for uniform key and token hashing distribution
  • Virtual nodes (100-200 per physical node) to reduce load imbalance and hotspots
  • Apache ZooKeeper or etcd for atomic consistent hash ring metadata updates and coordination
  • Redis with TTL keys for node liveness detection and failover triggering
  • Sorted data structure (TreeMap or skip list) for efficient token lookup in O(log N)
  • RESTful APIs with TLS encryption for secure node management and key lookup
  • Token reassignment limited to affected ranges to keep data movement under 5%
  • Client-side caching of ring metadata with versioning and invalidation on updates

Practice

(1/5)
1. In a system designed for 99.999% availability, at step 4 the Delivery Worker checks the message queue for pending retries. What happens if the message is not acknowledged by the consumer within the visibility timeout?
easy
A. The message is archived permanently without retry
B. The message is deleted immediately to prevent duplicates
C. The message becomes visible again for redelivery to another consumer
D. The Delivery Worker blocks until the consumer acknowledges

Solution

  1. Step 1: Trace Delivery Worker decision at Step 4 -- message visibility timeout

    If the message is not acknowledged within the visibility timeout, it becomes visible again for redelivery to ensure no message loss.

  2. Step 2: Eliminate incorrect options

    Immediate deletion (A) risks message loss; archiving without retry (C) breaks availability; blocking (D) reduces throughput and availability.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Visibility timeout expiry -> message re-queued for retry [check]
Hint: Visibility timeout expiry -> message re-queued for retry [check]
Common Mistakes:
2. In the request flow, at Step 4 the Delivery Worker checks the message queue's visibility timeout before processing. What happens if the visibility timeout expires before the message is acknowledged?
easy
A. The message is moved to a dead-letter queue without retry
B. The message is deleted immediately to prevent duplicates
C. The message is archived permanently without redelivery
D. The message becomes visible again and can be redelivered to another worker

Solution

  1. Step 1: Understand visibility timeout semantics

    Visibility timeout hides the message during processing; if not acknowledged, it reappears for redelivery.

  2. Step 2: Analyze options

    Immediate deletion (A) risks data loss; archiving without retry (C) prevents recovery; dead-letter queue (D) is for failed retries, not timeout expiry.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Visibility timeout expiry -> message reappears for retry [check]
Hint: Visibility timeout expiry -> message requeued for retry [check]
Common Mistakes:
3. A social media platform must handle 1 million tweet writes per second and fan-out to millions of followers asynchronously. Which component best decouples tweet ingestion from timeline delivery to ensure durability and scalability?
easy
A. Use a relational database with immediate fan-out triggers on write
B. Use a distributed log system like Kafka partitioned by user ID
C. Use an in-memory cache like Redis for immediate fan-out
D. Use a direct synchronous RPC call to each follower's timeline service

Solution

  1. Step 1: Identify the role of the distributed log

    Kafka partitions by user ID to preserve ordering and durability, decoupling ingestion from delivery.

  2. Step 2: Eliminate other options

    Relational DB triggers (A) cause synchronous blocking and don't scale; Redis (C) lacks durability and persistence; synchronous RPC (D) blocks on follower availability.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Kafka partitions ensure durable, ordered, asynchronous fan-out [check]
Hint: Distributed log decouples ingestion and delivery [check]
Common Mistakes:
4. In the faceted search request flow, at Step 4 the Query Coordinator merges partial results from multiple shard nodes. What happens if one shard node responds with a partial result missing some facet counts due to a timeout?
easy
A. The Query Coordinator excludes the shard's data entirely from the final result
B. The Query Coordinator merges available partial results and marks missing facets as zero counts
C. The Query Coordinator returns an error to the user immediately
D. The Query Coordinator retries the shard query synchronously before merging

Solution

  1. Step 1: Understand Query Coordinator's merge logic

    The coordinator merges partial results from all shards; if a shard times out, its data is excluded to avoid blocking the entire query.

  2. Step 2: Eliminate other options

    Returning an error breaks availability; marking missing facets as zero is inaccurate; synchronous retries would increase latency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Timeout shard data excluded -> partial but available results [check]
Hint: Timeout shards excluded to keep query latency low [check]
Common Mistakes:
5. For a high-throughput system requiring SSL termination and HTTP header manipulation, which architecture is more appropriate and why?
medium
A. Use a Reverse Proxy for SSL termination and header manipulation because it operates at the HTTP layer with fine-grained control
B. Use an API Gateway for SSL termination and header manipulation because it is optimized for high throughput
C. Use a Load Balancer for SSL termination and header manipulation because it handles traffic efficiently
D. Use DNS load balancing to distribute SSL termination across multiple servers

Solution

  1. Step 1: Identify component capabilities

    Load Balancers typically operate at transport layer and may support SSL termination but lack detailed HTTP header manipulation; API Gateways add overhead and are less optimized for raw throughput; DNS load balancing does not handle SSL termination.

  2. Step 2: Match requirement to component

    Reverse Proxy operates at HTTP layer, supports SSL termination and header manipulation efficiently, suitable for high throughput.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Reverse Proxy = HTTP layer control + SSL termination [check]
Hint: Reverse Proxy = SSL termination + HTTP header control [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