Consistent hashing in HLD - System Design Exercise

Design: Consistent Hashing System

Design the consistent hashing mechanism and its integration with nodes for key distribution. Out of scope: detailed node internals, network protocols, and client-side caching.

Functional Requirements

FR1: Distribute keys evenly across multiple nodes (servers).

FR2: Minimize key remapping when nodes are added or removed.

FR3: Support dynamic scaling of nodes without major data reshuffling.

FR4: Handle node failures gracefully with minimal impact on key distribution.

FR5: Provide a way to locate the node responsible for a given key efficiently.

Non-Functional Requirements

NFR1: System should handle up to 10,000 nodes.

NFR2: Key lookup latency should be under 5 milliseconds.

NFR3: System availability target is 99.9% uptime.

NFR4: Memory usage per node should be optimized to handle millions of keys.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Hash function module

Hash ring data structure

Node manager for adding/removing nodes

Virtual node implementation

Failure detection and recovery mechanism

Client lookup interface

Design Patterns

Consistent hashing ring

Virtual nodes for load balancing

Hashing with rendezvous (highest random weight) as alternative

Replication strategies for fault tolerance

Reference Architecture

Client
  |
  v
+-------------------+
| Consistent Hashing |
|       Ring        |
+-------------------+
  |        |        |
  v        v        v
Node1    Node2    Node3
(Physical nodes with virtual nodes mapped on ring)

Components

Hash Function

MurmurHash3 or SHA-256

Generate uniform hash values for keys and nodes.

Consistent Hash Ring

Sorted data structure (e.g., balanced tree or sorted array)

Map hash values of nodes and keys on a circular ring.

Virtual Nodes

Multiple hash points per physical node

Improve key distribution and balance load across nodes.

Node Manager

Service or module managing node lifecycle

Add or remove nodes and update the hash ring accordingly.

Client Lookup Interface

API or library

Given a key, find the responsible node by hashing and ring traversal.

Failure Detection

Heartbeat or health checks

Detect node failures and trigger ring updates.

Request Flow

1. Client wants to store or retrieve a key.

2. Client hashes the key using the hash function.

3. The hash value is located on the consistent hash ring.

4. Traverse clockwise on the ring to find the first node hash greater than or equal to the key hash.

5. The corresponding physical node owning that virtual node is selected.

6. Client sends request to the selected node.

7. If nodes are added or removed, Node Manager updates the ring with minimal key remapping.

Database Schema

Not applicable as consistent hashing is a data distribution technique rather than a database schema. Key entities: Node (id, virtual node hashes), Key (hashed value), Hash Ring (sorted list of virtual node hashes mapped to physical nodes).

Scaling Discussion

Bottlenecks

Hash ring lookup latency increases with very large number of nodes.

Uneven key distribution if virtual nodes are insufficient.

Node failure detection delay causing stale ring state.

Memory overhead for storing many virtual nodes per physical node.

Solutions

Use efficient data structures like balanced binary search trees or skip lists for ring lookup to keep O(log N) complexity.

Increase number of virtual nodes per physical node to improve balance.

Implement fast failure detection mechanisms like gossip protocols or heartbeat intervals.

Tune virtual node count to balance memory usage and distribution quality.

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the consistent hashing ring and components, 10 minutes discussing scaling and failure handling, 5 minutes summarizing.

Explain the problem of key distribution and why consistent hashing helps.

Describe how the hash ring works and the role of virtual nodes.

Discuss how node addition/removal affects key remapping.

Mention failure detection and recovery strategies.

Talk about scaling challenges and how to mitigate them.

Practice

1. What is the main advantage of consistent hashing in distributed systems?

easy

A. It stores data only on one server

B. It guarantees equal data size on all servers

C. It requires no hashing function

D. It minimizes data movement when servers are added or removed

Solution

1. Step 1: Understand consistent hashing purpose

   Consistent hashing is designed to reduce the amount of data that needs to be moved when servers join or leave the system.

2. Step 2: Compare options with consistent hashing benefits

   Only It minimizes data movement when servers are added or removed correctly states this key advantage. Other options are incorrect or unrelated.

3. Final Answer:

   It minimizes data movement when servers are added or removed -> Option D

4. Quick Check:

   Minimize data movement = D [OK]

Hint: Remember: consistent hashing reduces data reshuffling [OK]

Common Mistakes:

• Thinking consistent hashing balances data perfectly
• Assuming no hashing function is needed
• Believing data is stored on only one server

2. Which of the following is a correct step in implementing consistent hashing?

easy

A. Assign each server multiple points on the hash ring (virtual nodes)

B. Store all data on a single server to avoid hashing

C. Use a linear list instead of a circular ring

D. Hash data keys directly to server IP addresses without hashing servers

Solution

1. Step 1: Recall consistent hashing implementation details

   Consistent hashing uses a circular ring and assigns multiple virtual nodes per server to balance load.

2. Step 2: Evaluate each option

   Assign each server multiple points on the hash ring (virtual nodes) correctly describes virtual nodes. Options A, C, and D contradict consistent hashing principles.

3. Final Answer:

   Assign each server multiple points on the hash ring (virtual nodes) -> Option A

4. Quick Check:

   Virtual nodes = B [OK]

Hint: Virtual nodes improve load balance in consistent hashing [OK]

Common Mistakes:

• Ignoring virtual nodes and using single points
• Using linear lists instead of circular rings
• Skipping hashing of servers

3. Given a consistent hashing ring with servers at hash points 10, 30, and 50, where will the data key with hash 35 be stored?

medium

A. Server at 50

B. Server at 30

C. Server at 10

D. Server at 35

Solution

1. Step 1: Understand consistent hashing key assignment

   Data is assigned to the next server clockwise on the ring after the key's hash.

2. Step 2: Find the next server after hash 35

   Servers are at 10, 30, and 50. After 35 clockwise is 50.

3. Final Answer:

   Server at 50 -> Option A

4. Quick Check:

   Next clockwise server after 35 = 50 [OK]

Hint: Assign data to next clockwise server on ring [OK]

Common Mistakes:

• Assigning data to previous server instead of next
• Choosing server at 30 because it's closest numerically
• Assuming server at 35 exists

4. In a consistent hashing system, a developer notices that when a new server is added, almost all data moves to the new server. What is the likely cause?

medium

A. The data keys are not hashed before assignment

B. The new server has fewer virtual nodes than others

C. The hash function is not distributing servers evenly on the ring

D. The ring is implemented as a linear list

Solution

1. Step 1: Analyze the problem of data movement on server addition

   If almost all data moves to the new server, it means the new server's position dominates the ring.

2. Step 2: Identify cause related to server distribution

   This happens if the hash function places servers unevenly, clustering many keys near the new server.

3. Final Answer:

   The hash function is not distributing servers evenly on the ring -> Option C

4. Quick Check:

   Uneven server distribution = A [OK]

Hint: Check server hash distribution to avoid data skew [OK]

Common Mistakes:

• Blaming virtual nodes count without checking hash function
• Ignoring hashing of data keys
• Confusing ring structure with linear list

5. You are designing a distributed cache using consistent hashing. To handle server failures gracefully, which approach is best?

hard

A. Assign each data key to only one server without replication

B. Use virtual nodes and replicate data on the next N servers clockwise

C. Use a fixed number of servers without adding or removing nodes

D. Hash data keys to servers randomly each time

Solution

1. Step 1: Understand fault tolerance in consistent hashing

   To handle failures, data should be replicated to multiple servers to avoid data loss.

2. Step 2: Identify best practice for replication

   Using virtual nodes improves load balance, and replicating data on next N servers clockwise ensures availability.

3. Final Answer:

   Use virtual nodes and replicate data on the next N servers clockwise -> Option B

4. Quick Check:

   Replication + virtual nodes = A [OK]

Hint: Replicate data on next servers for fault tolerance [OK]

Common Mistakes:

• Not replicating data causing data loss on failure
• Avoiding virtual nodes and causing imbalance
• Randomly hashing keys each time causing inconsistency