Consistent Hashing

Analogy categoryAnalogies

Consistent hashing is a technique for mapping keys to nodes in a way that minimizes the number of keys that must be remapped when the set of nodes changes. It was introduced to solve exactly the problem that plagues naive modulo hashing (hash(key) % N): with plain modulo hashing, adding or removing a single node changes N and reassigns nearly every key to a different node, forcing a massive, disruptive redistribution of data. Consistent hashing instead guarantees that, on average, only a fraction of keys (roughly 1/N of them) need to move when a node joins or leaves — a property that makes it foundational to distributed caches, sharded databases, and content delivery systems.

🏏

Cricket analogy: Consistent hashing is like a franchise reshuffling which net a player practices at when a new coach joins — only a fraction of players get reassigned nets, unlike naive modulo scheduling that would reshuffle almost every player's net the moment the coach count changes.

The hash ring

The classic construction maps both nodes and keys onto the same circular hash space (commonly visualized as a ring from 0 to 2^32−1). Each node is hashed to a position on the ring, and each key is also hashed to a position on the ring; the key belongs to the first node encountered walking clockwise from the key's position. When a new node is added, it only takes ownership of the keys between itself and the previous node counter-clockwise — every other node's key range is untouched. When a node is removed, only the keys it owned move, to the next node clockwise.

🏏

Cricket analogy: Picture fielding positions arranged clockwise around the boundary rope; a new fielder inserted only takes over the arc between themselves and the fielder before them, leaving every other fielder's zone of the boundary untouched.

Virtual nodes

A plain hash ring with one point per physical node can distribute load unevenly, since a random hash placement can leave one node responsible for a disproportionately large arc of the ring. The standard fix is virtual nodes: each physical node is hashed to many points on the ring (e.g., 100–200 virtual nodes per physical node), so its total owned key-space is the sum of many small, randomly-scattered arcs. This averages out to a much more even distribution and also means that when a node fails, its load spreads across many other nodes rather than dumping entirely onto one neighbor.

🏏

Cricket analogy: One net per coach can leave one coach overloaded with players by random luck, so top academies assign each coach many small virtual slots across the schedule — spreading load evenly, and if a coach is out sick, their players scatter across many substitutes instead of dumping onto one.

Where consistent hashing is used

Distributed caches like Memcached client libraries and Redis Cluster use consistent hashing (or close variants) to decide which cache node owns a given key, so that adding a cache node doesn't invalidate nearly the entire cache. Sharded databases and distributed storage systems (Cassandra, DynamoDB, Amazon S3's older internals) use it to place data partitions, and some load balancers use it to route requests, which is valuable for session affinity — the same client tends to land on the same backend even as the backend pool scales up and down.

🏏

Cricket analogy: Just as a franchise's rotation policy keeps assigning the same bowler to the same end without reshuffling everyone when a new bowler joins, teams place data the same way for DRS-style infrastructure, and selectors use similar logic for session affinity — the same player tends to bat in the same slot across matches.

python

import bisect, hashlib

class ConsistentHashRing:
    def __init__(self, nodes=None, virtual_nodes=150):
        self.virtual_nodes = virtual_nodes
        self.ring = {}       # hash_position -> physical node
        self.sorted_keys = []
        for node in nodes or []:
            self.add_node(node)

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

    def add_node(self, node: str):
        for i in range(self.virtual_nodes):
            h = self._hash(f"{node}#{i}")
            self.ring[h] = node
            bisect.insort(self.sorted_keys, h)

    def remove_node(self, node: str):
        for i in range(self.virtual_nodes):
            h = self._hash(f"{node}#{i}")
            del self.ring[h]
            self.sorted_keys.remove(h)

    def get_node(self, key: str) -> str:
        h = self._hash(key)
        idx = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]  # first node clockwise

Amazon's Dynamo paper (2007) popularized consistent hashing with virtual nodes for large-scale distributed storage, directly influencing the design of Cassandra, Riak, and DynamoDB, all of which use ring-based partitioning to add and remove capacity with minimal data reshuffling.

Consistent hashing without virtual nodes is a common half-implementation that looks correct in small tests but shows significant load imbalance in production once node counts are small and hash placement luck matters — always use enough virtual nodes (typically 100+) per physical node to smooth out the distribution.

Consistent hashing minimizes key remapping (roughly 1/N of keys) when nodes are added or removed, unlike naive modulo hashing.
Keys and nodes are mapped onto a shared hash ring; a key belongs to the next node clockwise from its position.
Virtual nodes give each physical node many small positions on the ring, smoothing out load distribution.
When a node fails, virtual nodes spread its load across many surviving nodes instead of overloading one neighbor.
It underpins distributed caches, sharded databases, and some load balancers that need minimal-disruption rebalancing.
Insufficient virtual nodes is a common implementation mistake that reintroduces load imbalance.

Practice what you learned

1. What problem does consistent hashing solve compared to naive modulo hashing (hash(key) % N)?

2. In the hash ring model, which node owns a given key?

3. Why are virtual nodes used in consistent hashing implementations?

4. What happens to the ring when a new node is added, assuming enough virtual nodes are used?

5. Which real-world system's design was directly influenced by consistent hashing with virtual nodes?

Was this page helpful?

Database Sharding

Related Study Notes in Software Engineering

Browse all study notes

Software Engineering

Microservices Study Notes

Software Architecture · 30 topics

Software Engineering

Testing & TDD Study Notes

Software Testing · 30 topics

Software Engineering

Design Patterns Study Notes

Software Design · 30 topics

Software Engineering

Software Engineering Study Notes

Python · 40 topics

Software Engineering

Git & Version Control Study Notes

Bash · 40 topics

Topics covered

#Architecture#SystemDesignStudyNotes#SoftwareEngineering#ConsistentHashing#Consistent#Hashing#Hash#Ring#StudyNotes#SkillVeris

Consistent Hashing