Consistent Hashing

• Consistent hashing : a distribution technique that maps both data keys and server nodes onto a conceptual ring using a hash function.
• Key assignment : each key belongs to the first node encountered clockwise from the key's hash position on the ring.
• Minimal movement : adding or removing a node remaps only about 1/N of the keys, instead of nearly all as modulo hashing would.
• Virtual nodes : each physical node is placed at many points on the ring to smooth out distribution and balance load.
• Replication : achieved by walking clockwise to the next N distinct physical nodes, placing copies on different machines.

What problem does consistent hashing solve?

The problem is the instability of modulo hashing. If you place a key on node = hash(key) % nodeCount, then changing the node count changes the result for almost every key, causing a near-total reshuffle. In a distributed cache that means a near-total cache miss storm whenever you scale.

How does consistent hashing work?

Consistent hashing maps the hash space onto a ring that wraps around. Each node is hashed to one or more points on the ring, and each key is hashed to a point. A key belongs to the first node encountered moving clockwise from the key's point.

package com.bank.distributed;

import java.util.TreeMap;

public class ConsistentHashRing {
    private final TreeMap<Integer, String> ring = new TreeMap<>();

    public String nodeFor(String key) {
        int h = key.hashCode();
        var entry = ring.ceilingEntry(h);       // first node >= key hash
        return (entry != null ? entry : ring.firstEntry()).getValue();
    }

    public void addNode(String node, int vnodes) {
        for (int i = 0; i < vnodes; i++)
            ring.put((node + "#" + i).hashCode(), node);
    }

    public void removeNode(String node, int vnodes) {
        for (int i = 0; i < vnodes; i++)
            ring.remove((node + "#" + i).hashCode());
    }
}

What happens when a node is added or removed?

When a node is added, it takes over only the keys that fall between it and its predecessor on the ring. When a node is removed, only its keys move to the next node clockwise. In both cases the fraction of keys that move is about 1/N.

package com.bank.distributed;

public class NodeChangeDemo {
    public static void main(String[] args) {
        // With 3 nodes and 1000 keys:
        // Adding a 4th node moves ~250 keys (1/4), not ~750
        // Removing a node moves ~333 keys (1/3), not ~667
        System.out.println("Consistent: ~1/N keys move");
        System.out.println("Modulo:     ~(N-1)/N keys move");
    }
}

What are virtual nodes and why are they needed?

With few physical nodes, the ring can be unevenly divided, giving some nodes much more data than others. Virtual nodes solve this by placing each physical node at many points on the ring, so the arcs are finely interleaved and load is balanced.

package com.bank.distributed;

public class VirtualNodes {
    // 3 physical nodes, 100 virtual nodes each = 300 ring points
    // Arcs are small and evenly distributed
    // Weighting: stronger hardware gets more virtual nodes
    public int vnodeCount(String node) {
        return isHighMemory(node) ? 200 : 100; // proportional load
    }
}

How does replication work with consistent hashing?

Replication is achieved by walking clockwise from the key's position to the next N distinct physical nodes and placing copies on each. This ensures replicas are on different machines.

package com.bank.distributed;

import java.util.ArrayList;
import java.util.List;

public class ReplicationRing {
    public List<String> replicaNodes(String key, int replicaCount) {
        List<String> replicas = new ArrayList<>();
        int h = key.hashCode();
        for (var entry : ring.tailMap(h).values()) {
            if (!replicas.contains(entry)) replicas.add(entry);
            if (replicas.size() == replicaCount) return replicas;
        }
        // wrap around
        for (var entry : ring.values()) {
            if (!replicas.contains(entry)) replicas.add(entry);
            if (replicas.size() == replicaCount) return replicas;
        }
        return replicas;
    }
}

How is this different from modulo hashing?

| Aspect | Modulo hashing | Consistent hashing |
|---|---|---|
| Keys moved on change | ~(N-1)/N (nearly all) | ~1/N (small fraction) |
| Load balance | Even with good hash | Even with virtual nodes |
| Complexity | Trivial | Moderate (TreeMap) |
| Used in | Simple sharding | Cassandra, DynamoDB, Memcached |

Where is consistent hashing used in practice?

Consistent hashing is the backbone of distributed caches like Memcached clients, databases like Cassandra and DynamoDB, and partitioned systems like Kafka. It also enables replication by walking clockwise to replicas and supports heterogeneous hardware by weighting virtual node counts.

What should a senior engineer know?

A senior engineer knows that consistent hashing is not perfect: even with virtual nodes, there can be slight imbalance during transient states. They also know about bounded-load consistent hashing, which caps the maximum load any node can take, redirecting overflow to the next node. They understand that the hash function must distribute well and that the ring is typically implemented as a sorted map (TreeMap in Java).