Consistent Hashing Explained Simply

1 The Problem with Naive Modulo Hashing

Suppose you have 3 cache servers (A, B, C) and want to distribute keys evenly. The simplest approach:

# Naive hashing: server = hash(key) % N
# N = number of servers

def get_server(key, servers):
    return servers[hash(key) % len(servers)]

# Works great with N=3:
hash("user_123") % 3 = 1  → Server B
hash("user_456") % 3 = 0  → Server A
hash("user_789") % 3 = 2  → Server C

What happens when you add a 4th server?

# N changes from 3 to 4
# Now: hash(key) % 4

hash("user_123") % 3 = 1  → was Server B
hash("user_123") % 4 = 3  → now Server D   ← MOVED

hash("user_456") % 3 = 0  → was Server A
hash("user_456") % 4 = 0  → still Server A ← OK

hash("user_789") % 3 = 2  → was Server C
hash("user_789") % 4 = 1  → now Server B   ← MOVED

# For N=3 → N=4: approximately 75% of all keys get remapped to different servers
# In a cache: 75% of requests suddenly miss (cache invalidated) → massive DB load spike
# In a database cluster: 75% of data must migrate to a new shard → huge I/O storm

# This is why naive modulo hashing doesn't work for distributed systems:
# Adding or removing ONE server remaps ~(N-1)/N of all keys

2 The Hash Ring — How Consistent Hashing Works

Consistent hashing maps both servers and keys onto a circular ring (0 to 2³²-1 for 32-bit hashes, or 0 to 2¹²⁸-1 for MD5).

Step 1: Place servers on the ring

Step 2: Place keys on the ring

Step 3: Adding a new server

class ConsistentHashRing:
    def __init__(self, servers=None, replicas=150):
        self.replicas = replicas          # virtual nodes per server
        self.ring = {}                    # position → server_name
        self.sorted_keys = []            # sorted list of positions
        for server in (servers or []):
            self.add_server(server)

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

    def add_server(self, server: str):
        for i in range(self.replicas):
            key = f"{server}:{i}"        # virtual node: "Server_A:0", "Server_A:1", etc.
            position = self._hash(key)
            self.ring[position] = server
            bisect.insort(self.sorted_keys, position)

    def remove_server(self, server: str):
        for i in range(self.replicas):
            key = f"{server}:{i}"
            position = self._hash(key)
            del self.ring[position]
            self.sorted_keys.remove(position)

    def get_server(self, key: str) -> str:
        if not self.ring:
            return None
        position = self._hash(key)
        # Find the first position in sorted_keys >= position (clockwise)
        idx = bisect.bisect_left(self.sorted_keys, position)
        if idx == len(self.sorted_keys):
            idx = 0   # wrap around (circular ring)
        return self.ring[self.sorted_keys[idx]]

# Usage:
ring = ConsistentHashRing(["Server_A", "Server_B", "Server_C"], replicas=150)
ring.get_server("user_123")  # → "Server_A"
ring.get_server("user_456")  # → "Server_B"
ring.add_server("Server_D")
ring.get_server("user_456")  # → may now be "Server_D" (only moved if D is closer)

3 Virtual Nodes — Solving Uneven Distribution

With only 3 real server positions on the ring, distribution can be very uneven by chance:

Solution: Virtual Nodes (VNodes)

Each physical server is assigned multiple positions on the ring (virtual nodes). With 150 virtual nodes per server, each server ends up with approximately 1/N of the ring, regardless of where real servers happen to hash.

Heterogeneous Servers (Different Capacities)

# What if Server_A has 2× the RAM of Server_B?
# Assign 2× as many virtual nodes to Server_A:

ring = ConsistentHashRing()
ring.add_server("Server_A", weight=2)   # 300 virtual nodes (2 × 150)
ring.add_server("Server_B", weight=1)   # 150 virtual nodes
ring.add_server("Server_C", weight=1)   # 150 virtual nodes

# Result:
# Server_A gets 300/600 = 50% of keys (2× the data → needs 2× the memory ✓)
# Server_B gets 150/600 = 25%
# Server_C gets 150/600 = 25%

# This is exactly how Cassandra's vnodes work:
# Each node's token count is proportional to its disk/memory capacity

4 Replication with Consistent Hashing

Most distributed systems don't store data on just one server — they replicate it for fault tolerance. With consistent hashing, replication is elegant:

# Replication factor RF = 3 (store data on 3 servers)
# Rule: store the key on the server it hashes to, PLUS the next (RF-1) clockwise servers

def get_servers_for_key(ring, key, rf=3):
    """Returns list of RF servers where this key should be stored."""
    primary_server = ring.get_server(key)
    servers = [primary_server]

    # Walk clockwise to find next RF-1 unique servers
    position = ring._hash(key)
    idx = bisect.bisect_left(ring.sorted_keys, position)

    seen = {primary_server}
    while len(servers) < rf:
        idx = (idx + 1) % len(ring.sorted_keys)
        server = ring.ring[ring.sorted_keys[idx]]
        if server not in seen:         # skip virtual nodes of same physical server
            servers.append(server)
            seen.add(server)

    return servers   # e.g., ["Server_A", "Server_C", "Server_B"]

# Example:
# key "user_123" → primary: Server_A → replicas: Server_C, Server_B
# Written to all three. Reads can come from any replica.
# If Server_A fails: read from Server_C or Server_B.
# When Server_A recovers: hinted handoff or anti-entropy (gossip) repairs it.

5 Real-World Usage

Redis Cluster: Hash Slots vs Hash Ring

# Redis uses a variant: 16,384 fixed hash slots (not a continuous ring)
# CRC16(key) % 16384 = slot number (0–16383)
# Slots are assigned to master nodes (not dynamically, but by configuration)

# 3-node cluster example:
# Master A: slots 0–5460       (~33%)
# Master B: slots 5461–10922   (~33%)
# Master C: slots 10923–16383  (~33%)

# Resharding: to add Master D, move some slots from A, B, C to D
# Only data in the moved slots needs to migrate (keys in other slots stay put)

# Key difference from pure consistent hashing:
# Redis Cluster: slot ranges assigned manually (predictable but less flexible)
# Cassandra: token ranges assigned dynamically (more automatic, with VNodes)

6 When to Mention Consistent Hashing in Interviews

Bring up consistent hashing whenever you're:

• Designing a distributed cache (Redis Cluster, Memcached cluster) — "I'll use consistent hashing to route requests to the right cache server so that adding a new cache node only invalidates ~1/N of keys."
• Sharding a database — "Consistent hashing means adding a new shard only requires migrating ~1/N of data, not a full reshuffle."
• Building a load balancer with sticky sessions — "Consistent hashing on user_id ensures the same user always routes to the same app server (maintaining in-memory session state)."
• Designing a CDN or distributed storage — "We use consistent hashing to assign content to edge nodes so that adding a new PoP doesn't cause a global cache invalidation storm."

Quick Interview Answer Template

"To distribute [data/requests] across N [servers/shards], I'll use consistent hashing.
 Each server is mapped to multiple positions on a hash ring using virtual nodes.
 When a key comes in, we hash it to a ring position and find the first clockwise server.

 The benefit over naive modulo hashing: when we add or remove a server,
 only ~1/N of keys are remapped instead of most of them — so there's no cache
 invalidation storm or mass data migration when we scale."

Limitations of Consistent Hashing

• Hot keys: A popular key always routes to the same server regardless of the ring. Consistent hashing distributes keys, not traffic. If 90% of reads go to one key, one server gets 90% of load — consistent hashing doesn't help. Solution: replicate hot keys to multiple servers.
• Data skew: Even with VNodes, random hashing might not be perfectly uniform for small N servers. Monitor per-shard sizes and rebalance manually if needed.
• Operational complexity: When a server fails, data temporarily becomes inaccessible (or routes to the next server if using replication). You need rebalancing scripts and monitoring.

7 Naive Hashing vs Consistent Hashing vs Range Sharding