Consistent hashing in HLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of consistent hashing

Why is consistent hashing preferred over traditional hashing methods in distributed systems?

A Because it evenly distributes keys and minimizes reassignments when nodes change

B Because it uses less memory than traditional hashing

C Because it guarantees zero collisions between keys

D Because it requires no hashing function at all

💡 Hint

Think about what happens when a server is added or removed in a distributed cache.

Consistent hashing evenly distributes keys and minimizes the number of keys that need to be reassigned when nodes join or leave, unlike traditional hashing which can cause many keys to move.

❓ Architecture

intermediate

Designing a consistent hashing ring

You need to design a consistent hashing ring for 4 cache servers. Which approach correctly represents the ring structure?

A Use a linear list of servers and assign keys based on server index

B Assign keys randomly to any server without a ring structure

C Assign all keys to the first server and switch when it fails

D Place servers on a circular hash space and assign keys to the next clockwise server

💡 Hint

Visualize a clock face where servers are points on the circle.

Consistent hashing uses a circular hash space where each server is placed on the ring. Keys are assigned to the next server clockwise, ensuring balanced distribution and minimal movement on changes.

❓ scaling

advanced

Handling node additions in consistent hashing

When a new node is added to a consistent hashing ring, what is the impact on key distribution?

A Only keys that map between the new node and its predecessor move to the new node

B All keys are redistributed evenly among all nodes

C No keys move because the ring is static

D Keys assigned to the last node move to the new node

💡 Hint

Consider which keys fall between the new node and the previous node on the ring.

Adding a node only affects keys that fall between the new node and its predecessor on the ring, minimizing key movement and maintaining balance.

❓ tradeoff

advanced

Tradeoffs of using virtual nodes in consistent hashing

What is a key tradeoff when using virtual nodes (vnodes) in consistent hashing?

A Reduced load balancing but simpler implementation

B Improved load balancing but increased complexity in node management

C No change in load balancing but higher memory usage

D Eliminates the need for hashing functions

💡 Hint

Think about how virtual nodes affect distribution and system complexity.

Virtual nodes improve load balancing by spreading each physical node across the ring multiple times, but they add complexity in tracking and managing these virtual nodes.

❓ estimation

expert

Estimating key remapping after node failure

In a consistent hashing ring with 100 nodes and 1 million keys evenly distributed, approximately how many keys need to be remapped if one node fails?

A About 100,000 keys

B About 1,000 keys

C About 10,000 keys

D All 1 million keys

💡 Hint

Consider the fraction of the ring that one node covers.

Each node is responsible for roughly 1/100th of the keys, so when one node fails, about 1% of keys (10,000) need remapping.