Consistent Hashing Explained

When you spread data across many cache or database nodes, you need a rule for which node owns which key. Consistent hashing is the rule most large systems use, because it keeps working smoothly when nodes are added or removed.

The problem with modulo hashing

The simple approach is node = hash(key) % N. It distributes keys evenly, until N changes. Add a fifth server to four and almost every key maps to a different node. For a cache, that means a sudden flood of misses; for a database, it means moving nearly all your data.

How consistent hashing works

1. Imagine a circle (the ring) of hash values.
2. Hash each node to a position on the ring.
3. Hash each key to a position on the ring.
4. A key belongs to the first node clockwise from its position.

When a node joins, it takes over only the keys between it and the previous node. When a node leaves, only its keys move to the next node. On average, only about 1/N of keys move.

Virtual nodes

With a handful of physical nodes, positions on the ring can be uneven, leaving some nodes with far more keys. The fix is virtual nodes: each physical node is placed on the ring many times under different hashes.

• Load spreads more evenly.
• When a node fails, its keys scatter across many nodes rather than overloading one neighbour.
• More powerful machines can be given more virtual nodes.

import bisect, hashlib

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.ring = sorted((self.h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
        self.keys = [k for k, _ in self.ring]

    def h(self, s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)

    def node_for(self, key):
        i = bisect.bisect(self.keys, self.h(key)) % len(self.ring)
        return self.ring[i][1]

Where it’s used

• Distributed caches, so adding a cache node doesn’t wipe out the hit rate; see caching strategies.
• Distributed databases and key-value stores to partition data; see database sharding.
• Load balancers that need session affinity; see load balancing algorithms.

Replication on the ring

To keep copies of data, a key is stored on its owner and the next few distinct nodes clockwise. If one fails, the others still serve it, a pattern tied closely to the trade-offs in the CAP theorem.

Frequently asked questions

How many virtual nodes should each server have?

Often somewhere between tens and a few hundred. More gives smoother balance at the cost of a larger ring to search.

Does consistent hashing guarantee perfect balance?

No, but with virtual nodes it gets close, and it minimises data movement when nodes change.

What hash function should I use?

Any fast function with good distribution. Cryptographic strength isn’t required.