Consistent Hashing: Distributing Load Without a Full Reshuffle

Naive hashing (hash(key) % N) works fine until you add or remove a node — then N changes and almost every key maps to a different server. For a distributed cache or shard, that means a near-total cache miss storm or a mass data migration, right when you can least afford it.

Consistent hashing fixes this by mapping both nodes and keys onto the same ring, so a topology change only remaps the keys between the changed node and its neighbor.

The Ring

graph LR
    subgraph Ring["Hash Ring (0 to 2^32-1)"]
        NA((Node A))
        NB((Node B))
        NC((Node C))
        K1[key1] -.-> NB
        K2[key2] -.-> NC
        K3[key3] -.-> NA
    end

Each node is hashed onto the ring (often multiple times — see "Virtual Nodes" below). To find which node owns a key, hash the key and walk clockwise until you hit the first node.

Adding or Removing a Node

When node B leaves, only the keys that were mapped to B move — to B's clockwise neighbor. Every other key stays exactly where it was. That's the whole point: roughly 1/N of the keyspace moves per topology change, not the whole keyspace.

Virtual Nodes (Replicas)

Hashing raw node names onto the ring directly creates hot spots — some nodes end up owning much bigger arcs than others. The fix: hash each node multiple times, e.g. node-A#0, node-A#1, ..., node-A#149 (150 virtual nodes is a common default). More virtual nodes means smoother distribution, at the cost of a bigger in-memory ring.

Implementation

:::tabs

class ConsistentHash
{
    private array $ring = [];
    private array $sortedKeys = [];
    private int $replicas;

    public function __construct(int $replicas = 150)
    {
        $this->replicas = $replicas;
    }

    public function addNode(string $node): void
    {
        for ($i = 0; $i < $this->replicas; $i++) {
            $this->ring[$this->hash("$node#$i")] = $node;
        }
        $this->sortedKeys = $this->sortedRingKeys();
    }

    public function getNode(string $key): ?string
    {
        if (empty($this->sortedKeys)) {
            return null;
        }

        $hash = $this->hash($key);
        foreach ($this->sortedKeys as $ringKey) {
            if ($ringKey >= $hash) {
                return $this->ring[$ringKey];
            }
        }

        return $this->ring[$this->sortedKeys[0]];
    }

    private function sortedRingKeys(): array
    {
        $keys = array_keys($this->ring);
        sort($keys);
        return $keys;
    }

    private function hash(string $value): int
    {
        return crc32($value);
    }
}

import bisect
import zlib


class ConsistentHash:
    def __init__(self, replicas: int = 150):
        self.replicas = replicas
        self.ring: dict[int, str] = {}
        self.sorted_keys: list[int] = []

    def add_node(self, node: str) -> None:
        for i in range(self.replicas):
            self.ring[self._hash(f"{node}#{i}")] = node
        self.sorted_keys = sorted(self.ring.keys())

    def get_node(self, key: str) -> str | None:
        if not self.sorted_keys:
            return None

        h = self._hash(key)
        index = bisect.bisect_left(self.sorted_keys, h)
        if index == len(self.sorted_keys):
            index = 0

        return self.ring[self.sorted_keys[index]]

    @staticmethod
    def _hash(value: str) -> int:
        return zlib.crc32(value.encode())

:::

Common Pitfalls

Too few virtual nodes leads to uneven load, with hot spots on a handful of physical nodes. Using a weak or poorly-distributed hash function makes the same problem worse — prefer something like CRC32 or xxHash over a naive sum-of-bytes hash. Forgetting to remove all of a node's virtual nodes on removal leaves ghost entries that route traffic to a dead server. And rehashing the entire keyspace on every topology change defeats the whole purpose — only the ring should change, not every key's mapping.

When to Reach for This

Distributed caches doing client-side sharding, CDN edge selection, distributed hash tables, sharded databases, and load balancers that need session affinity without a central coordinator. If your cluster size is fixed and rarely changes, plain modulo hashing is simpler and perfectly fine.

---

Originally published at https://cslant.com/tips/consistent-hashing-distributing-load-without-a-full-reshuffle