Questions: Consistent Hashing

Question 1

A distributed cache has 10 servers and uses hash(key) % 10 to assign keys to servers. A new server is added, making 11 total. Approximately what fraction of keys must be remapped?

• A. About 1/11 — only the keys that will belong to the new server need to move
• B. About 1/10 — only the keys on the least-loaded server need to be redistributed
• C. About 90% — changing n from 10 to 11 changes the result of hash(key) % n for nearly every key
• D. 0% — hash functions are stable, so existing key assignments are preserved

Answer: (C)

With modular hashing, the number of servers n is baked into every assignment. Changing n from 10 to 11 means hash(key) % 10 vs. hash(key) % 11 give different results for approximately (n−1)/n ≈ 90% of keys. This near-total remapping causes a cache miss storm in distributed caches and massive data migration in storage systems. Consistent hashing solves exactly this problem — only the keys in the arc adjacent to the new node (roughly 1/11) need remapping.

Question 2

A consistent hashing ring has five servers at widely spaced positions. One server owns 5% of the ring, another owns 60%. Which technique addresses this load imbalance?

• A. Replicate data from the overloaded server to the underloaded one to balance storage
• B. Add more physical servers until ring arcs are approximately equal
• C. Use virtual nodes — hash each physical server to many ring positions so each server's responsibility is spread across many small arcs
• D. Switch to modular hashing, which produces more uniform distribution by design

Answer: (C)

Virtual nodes (vnodes) solve the load imbalance that arises when few physical nodes produce uneven arc lengths. By hashing variations of each server's identifier (e.g., 'nodeA-1', 'nodeA-2', ...) to place it at 100–200 positions on the ring, each physical server owns many small, scattered arcs. The law of large numbers smooths the distribution. When a node leaves, its load is spread across all remaining nodes rather than dumped onto a single successor.

Question 3

With consistent hashing, when a node is added to or removed from the ring, only keys in a contiguous arc of the ring need to be reassigned.

• T. True
• F. False

Answer: True

This is the core property that makes consistent hashing valuable. When a node joins, it takes over the arc between itself and the next node counterclockwise — only those keys need remapping. When a node leaves, its keys transfer to the next node clockwise. All keys outside this arc remain with their existing nodes, unchanged. This localized disruption is the fundamental advantage over modular hashing, where any change to n disrupts nearly all assignments globally.

Question 4

A cluster using consistent hashing will experience a near-total cache miss storm when a node is added, just like modular hashing, because most hash values need to be recomputed.

• T. True
• F. False

Answer: False

Hash values for existing keys do not change in consistent hashing — keys and nodes are already mapped to the ring. Adding a node only changes which node 'owns' the arc containing the new node's ring position; only the keys in that arc need remapping, approximately 1/n of all keys. The cache miss storm in modular hashing comes from changing n, which invalidates nearly all hash(key) % n assignments. Consistent hashing decouples assignments from n entirely.

Question 5

Explain why consistent hashing is described as 'elastic' — what property makes it fundamentally better suited to horizontally scalable distributed systems?

Model answer: Consistent hashing decouples key assignment from the number of nodes. In modular hashing, n is embedded in every assignment, so any change to n invalidates nearly all mappings. In consistent hashing, keys and nodes share a stable ring, and only the keys in the arc adjacent to an added or removed node need reassignment. Because the vast majority of keys are unaffected by any single node change, the system can expand and contract — scaling up under load, removing failed nodes — without triggering mass data migration or cache miss storms.

'Elastic' means the system can change size without global disruption. This is essential for distributed systems that must handle variable load, hardware failures, and rolling upgrades — all of which cause nodes to join and leave. The disruption is proportional and local rather than catastrophic, which is exactly what horizontal scalability requires.