Consistent Hashing

Overview

A naive hash(key) % N distribution scheme ties every key's assigned server directly to the current server count, so adding or removing even one server changes N and remaps nearly every key simultaneously, a wave of cache misses or an unnecessary mass data migration triggered by one small topology change. Consistent hashing fixes this by placing both servers and keys on a fixed conceptual ring instead: a key belongs to whichever server's position comes next walking around the ring, so removing one server only reassigns the keys that were specifically in its arc, roughly 1/N of the total, leaving every other key's assignment completely untouched. Real implementations give each server many positions on the ring, scaled by its intended weight, specifically because a single random position per server would let chance produce wildly uneven arc sizes; many smaller positions average that randomness out into a genuinely even distribution.

Quick Reference

Syntax

# Conceptual ring hash: each server gets many positions,
# a key maps to the next server found clockwise. A deterministic
# hash (not Python's built-in hash(), which is randomized per
# process for strings) keeps ring positions stable across restarts.
import hashlib

def ring_hash(key):
    return int(hashlib.sha256(key.encode()).hexdigest(), 16)

ring = {}
for server in servers:
    for i in range(VIRTUAL_NODES_PER_SERVER):
        ring[ring_hash(f"{server}-{i}")] = server
sorted_positions = sorted(ring)

Examples

# Removing server_2 only reassigns the keys that were in its
# specific ring arc; every other key's server is unaffected.
# Binary search on the pre-sorted ring keeps lookup at O(log N)
# instead of scanning every position.
import bisect

def get_server(key, sorted_positions, ring):
    key_hash = ring_hash(key)
    index = bisect.bisect_left(sorted_positions, key_hash)
    if index == len(sorted_positions):
        index = 0
    return ring[sorted_positions[index]]

Visual Diagram

Common Mistakes

• Using plain hash(key) % N for a cache or shard map and being surprised by a massive remapping event on every scale-up or scale-down.
• Giving each host only a single position on the hash ring, producing uneven arc sizes and load distribution purely from placement chance.
• Assuming consistent hashing eliminates remapping entirely; it minimizes it to roughly 1/N of keys, it doesn't make topology changes free.
• Forgetting to weight ring positions when hosts have genuinely different capacities, treating a bigger and smaller host as equally likely to receive traffic.

Performance

• Consistent hashing's key lookup is a search for the next ring position; with the ring's positions kept sorted, a binary search finds it in O(log N) for N total ring positions, a linear scan of an unsorted ring is O(N) and should be avoided.
• The real performance win is operational, not per-lookup: a ring hash's 1/N remapping on topology change avoids the cache-stampede or mass-migration cost a full remap would otherwise trigger.

Best Practices

• Use consistent hashing (a ring hash) instead of plain modulo hashing for any distributed cache or shard map expected to scale up or down over its lifetime.
• Assign multiple ring positions per host, weighted by intended capacity, rather than one position per host.
• Expect and design around the roughly 1/N remapping consistent hashing still causes on a topology change, it's minimized, not eliminated.
• Reach for this technique specifically when server count is expected to change; a fixed, never-resized cluster has less need for it.