Consistent Hashing

In a consistent hashing topology, keys and servers are mapped to the same circular hash ring. Keys route to the nearest clockwise server:

Virtual Nodes (vNodes) Allocation

To prevent hashing hotspots, physical servers map to multiple scattered points on the ring:

• Minimal Key Remapping: Only 1/N of keys migrate on average when scaling out by one node.
• vNode Scaling Matrix: Adjusting virtual nodes balances key distribution against lookup map memory overhead:

• Sharding & Database Partitioning: The physical separation of data sets.
• LSM-Tree Storage Engines: Heavy sharding keys structure.
• Gossip Membership Protocol: Decentralized coordination of node ring positions.

Why Modulo Hashing Fails First

The naive approach maps key K to server hash(K) mod N. It works until N changes. Add one cache node (N=4 → N=5) and roughly 80% of keys remap to different servers — a cache stampede and thundering herd on the database. Remove a failed node and the same catastrophe repeats in reverse.

Consistent hashing exists because elastic infrastructure changes N constantly — auto-scaling, rolling deploys, spot instance preemption. With a hash ring, adding or removing one physical node remaps only about 1/N of keys on average. That is the entire reason interviewers expect you to graduate from modulo to a ring when discussing distributed caches or Dynamo-style partitions.

Hash Ring Array Search Mechanics

In production systems (e.g., Libketama, Cassandra), the hash ring is represented in memory as a sorted array of virtual node hashes mapped to physical server addresses. When a request arrives with key K:

1. Calculate the hash value of the key: h = xxHash(K).
2. Execute a Binary Search (O(log V) where V = N * vNodes) over the sorted ring array to find the first vNode hash greater than or equal to h.
3. If no vNode hash is greater than h, wrap around and select the first element in the array (index 0).

Non-Cryptographic Hashing Efficiency

Never use heavy cryptographic hash functions like SHA-256 or MD5 for key routing on the ring. Consistent hashing is CPU bound. Production systems select ultra-fast, high-distribution non-cryptographic hashes like **Murmur3** or **xxHash** to execute routing lookups in under 10 nanoseconds.