What problem does consistent hashing solve, and how does the ring work?

Modulo hashing remaps almost every key when the server count changes, which is catastrophic for caches and expensive for sharded data. Consistent hashing maps both keys and servers onto the same circular hash space; a key belongs to the first server encountered clockwise from its position. Adding or removing a server only affects keys between it and its neighbour, so on average only K/N keys move instead of nearly all of them. Virtual nodes - placing each physical server at many points on the ring - are what make the distribution even in practice. | Modulo hashing | Consistent hashing. Keys moved when adding node N+1 | ~N/(N+1) - nearly all | ~1/(N+1) - one node's share. 10 → 11 servers | ~91% of keys move | ~9% of keys move. Lookup cost | O(1) | O(log V) binary search over virtual nodes. Distribution | Perfectly even | Even only with enough virtual nodes. Used by | Simple static shards | Cassandra, DynamoDB, memcached clients, CDNs The ring 1 · One hash space, both kinds of thing: Take a hash function with a large output range, say 0 to 2³²−1, and treat it as a circle where the maximum wraps to zero. Hash servers onto it (by name or IP) and hash keys onto it with the same function.. 2 · Ownership is 'next clockwise': A key is owned by the first server found walking clockwise from the key's position. Implementation is a sorted array of node positions plus a binary search - O(log V).. 3 · Adding a node: The new node takes ownership of the arc between itself and its counter-clockwise predecessor. Only keys in that arc move; every other key is untouched.. 4 · Removing a node: Its arc merges into the next clockwise node. Again, only that node's keys move. Virtual nodes are not an optimisation - they are required: With 3 physical nodes hashed to 3 random ring positions,

Consistent Hashing Explained with Virtual Nodes

Advancedconsistent hashingshardingdistributedAsked at Amazon, Discord

30-second answer

Modulo hashing remaps almost every key when the server count changes, which is catastrophic for caches and expensive for sharded data. Consistent hashing maps both keys and servers onto the same circular hash space; a key belongs to the first server encountered clockwise from its position. Adding or removing a server only affects keys between it and its neighbour, so on average only K/N keys move instead of nearly all of them. Virtual nodes - placing each physical server at many points on the ring - are what make the distribution even in practice.

	Modulo hashing	Consistent hashing
Keys moved when adding node N+1	~N/(N+1) - nearly all	~1/(N+1) - one node's share
10 → 11 servers	~91% of keys move	~9% of keys move
Lookup cost	O(1)	O(log V) binary search over virtual nodes
Distribution	Perfectly even	Even only with enough virtual nodes
Used by	Simple static shards	Cassandra, DynamoDB, memcached clients, CDNs

The ring

1 · One hash space, both kinds of thing
Take a hash function with a large output range, say 0 to 2³²−1, and treat it as a circle where the maximum wraps to zero. Hash servers onto it (by name or IP) and hash keys onto it with the same function.
2 · Ownership is 'next clockwise'
A key is owned by the first server found walking clockwise from the key's position. Implementation is a sorted array of node positions plus a binary search - O(log V).
3 · Adding a node
The new node takes ownership of the arc between itself and its counter-clockwise predecessor. Only keys in that arc move; every other key is untouched.
4 · Removing a node
Its arc merges into the next clockwise node. Again, only that node's keys move.

pythonA complete implementation, virtual nodes included

import bisect, hashlib

class ConsistentHashRing:
    def __init__(self, nodes=(), vnodes=150):
        self.vnodes = vnodes            # replicas per physical node
        self._keys  = []                # sorted ring positions
        self._nodes = {}                # position -> physical node
        for n in nodes:
            self.add(n)

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add(self, node: str):
        for i in range(self.vnodes):
            pos = self._hash(f"{node}#{i}")
            bisect.insort(self._keys, pos)
            self._nodes[pos] = node

    def remove(self, node: str):
        for i in range(self.vnodes):
            pos = self._hash(f"{node}#{i}")
            self._keys.remove(pos)
            del self._nodes[pos]

    def get(self, key: str) -> str:
        if not self._keys:
            raise IndexError("empty ring")
        pos = self._hash(key)
        idx = bisect.bisect_right(self._keys, pos) % len(self._keys)   # wrap around
        return self._nodes[self._keys[idx]]

    def get_replicas(self, key: str, n: int) -> list[str]:
        """Walk clockwise collecting DISTINCT physical nodes - the subtlety
        that makes replication correct when virtual nodes are in play."""
        if not self._keys:
            return []
        idx, out, seen = bisect.bisect_right(self._keys, self._hash(key)), [], set()
        for i in range(len(self._keys)):
            node = self._nodes[self._keys[(idx + i) % len(self._keys)]]
            if node not in seen:
                seen.add(node); out.append(node)
                if len(out) == n:
                    break
        return out

σ \propto \frac{1}{V}

Load imbalance falls with the square root of virtual nodes per server. 100–200 is the usual sweet spot before memory and lookup cost start to matter.

Replication on the ring

For a replication factor of 3, walk clockwise from the key and take the next three distinct physical nodes. Two subtleties matter: skipping duplicates (several virtual nodes may belong to the same server, which would silently give you fewer than three real copies), and rack- or zone-awareness - a production implementation skips candidates that share a failure domain with one already chosen, so all three replicas are not in the same rack.

The alternative worth knowing: rendezvous hashing

Rendezvous (highest-random-weight) hashing computes hash(key + node) for every node and picks the maximum. It gives the same minimal-disruption property with no ring, no virtual nodes and perfectly even distribution, at O(N) lookup instead of O(log V). For small N - tens of nodes - it is simpler and strictly better. For thousands of nodes, the ring's logarithmic lookup wins. Mentioning it shows you know the ring is one solution rather than the only one.

Say these points

Modulo hashing remaps ~N/(N+1) of keys on resize; consistent hashing moves ~1/(N+1).
Key belongs to the first node clockwise; lookup is a binary search over sorted positions.
Virtual nodes (100–200 per server) are required for even distribution and graceful removal.
Replication walks clockwise for distinct physical nodes, skipping shared failure domains.
Hot keys are a separate problem; consider bounded loads or key replication.

Avoid these mistakes

Implementing the ring without virtual nodes and getting a 60/20/20 split.
Collecting replicas without deduplicating virtual nodes to physical ones.
Assuming even key distribution means even traffic.
Using consistent hashing for data that also needs range scans.

Expect these follow-ups

How does Cassandra use the ring for both partitioning and replication?
How would you implement bounded-load consistent hashing?
When is rendezvous hashing the better choice?

Consistent Hashing Explained