Consistent hashing in HLD - Scalability & System Analysis

Scalability Analysis - Consistent hashing

Growth Table: Consistent Hashing at Different Scales

Users / Requests	Number of Nodes	Data Distribution	Node Changes Impact	Load Balancing
100 users	3-5 nodes	Simple hashing works, consistent hashing optional	Minimal impact, rehashing simple	Basic round-robin or hashing
10K users	10-50 nodes	Consistent hashing reduces data movement on node changes	Small portion of keys remapped	Virtual nodes improve balance
1M users	100-500 nodes	Data distribution critical, consistent hashing essential	Node failure causes minimal remapping (~1/n keys)	Use virtual nodes and replication
100M users	1000+ nodes	Highly dynamic cluster, consistent hashing with replication and multi-ring	Efficient scaling, minimal data movement	Advanced load balancing, monitoring, and auto-scaling

First Bottleneck

At small scale, the first bottleneck is uneven data distribution causing some nodes to be overloaded.

As the system grows, the bottleneck shifts to the cost of rehashing and data movement when nodes join or leave.

Without consistent hashing, large-scale systems suffer from massive data reshuffling, causing downtime and performance drops.

Scaling Solutions

• Consistent Hashing: Minimizes data movement by mapping keys and nodes on a hash ring.
• Virtual Nodes: Each physical node hosts multiple virtual nodes to improve load balance.
• Replication: Store copies of data on multiple nodes for fault tolerance and read scalability.
• Multi-Ring Hashing: Use multiple hash rings for different data types or regions to isolate impact.
• Auto-Scaling: Dynamically add or remove nodes with minimal disruption.
• Monitoring & Load Balancing: Track node load and redistribute virtual nodes if imbalance occurs.

Back-of-Envelope Cost Analysis

Assuming 1M keys and 100 nodes:

• Each node handles ~10,000 keys.
• Adding/removing a node remaps ~1% of keys (~10,000 keys).
• Requests per second (RPS): If total RPS is 100,000, each node handles ~1,000 RPS.
• Network bandwidth per node depends on key size and replication factor; e.g., 1 KB per key * 1,000 RPS = ~1 MB/s.
• Storage scales linearly with keys per node.

Interview Tip

Start by explaining the problem of data distribution and node churn in distributed systems.

Describe how consistent hashing solves these by minimizing data movement.

Discuss virtual nodes and replication to improve balance and fault tolerance.

Use examples with increasing scale to show how the system adapts.

Highlight trade-offs and monitoring needs.

Self Check

Your database handles 1000 QPS. Traffic grows 10x. What do you do first?

Answer: Add more nodes and use consistent hashing to redistribute keys with minimal data movement, ensuring no single node is overloaded.

Key Result

Consistent hashing enables smooth scaling by minimizing data movement during node changes, making it ideal for large dynamic distributed systems.

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