Consistent Hashing: Hash Ring, Virtual Nodes, and Distributed Key Routing

TL;DR

• Bottom line: Consistent hashing minimizes key redistribution when nodes join or leave a cluster — only K/n keys move on average, compared to near-total rehashing with modular hashing.
• Key tool: Hash ring with 100-200 virtual nodes per physical node for even load distribution.
• Watch out for: Skipping virtual nodes — bare consistent hashing gives wildly uneven load (up to O(log n) imbalance factor).
• Works with: Any distributed system — language and platform agnostic. Used by Cassandra, DynamoDB, Memcached, Redis Cluster, Riak, Akamai CDN.

Constraints

• Hash function must be uniform and deterministic (e.g., MD5, SHA-1, xxHash) — non-uniform hashing destroys load balance.
• Virtual nodes are mandatory for production — bare ring hashing gives O(log n) expected max-to-average load ratio.
• Do not use consistent hashing for clusters with fewer than 3 nodes — simple modular hashing is sufficient.
• Node removal requires reassigning only the departing node's keys to its successor — never rehash the entire ring.
• Hash ring metadata must be replicated to all clients/proxies — stale ring state causes misrouted requests.

Quick Reference

Decision Tree

START: What is your distributed hashing use case?
|
+-- Is the node set static (rarely add/remove nodes)?
|   +-- YES: Is the bucket count append-only?
|   |   +-- YES --> Use Jump Hash (perfect balance, zero memory overhead)
|   |   +-- NO --> Use modular hashing (simplest, perfect balance)
|   +-- NO (dynamic node membership) ↓
|
+-- How many nodes in the cluster?
|   +-- < 3 nodes --> Use modular hashing (overhead not justified)
|   +-- 3-20 nodes ↓
|   |   +-- Need k-way replication with no ring metadata?
|   |   |   +-- YES --> Use Rendezvous (HRW) hashing
|   |   |   +-- NO --> Use Ring Hash + 100-200 virtual nodes per node
|   +-- 20+ nodes ↓
|       +-- L4 load balancing?
|       |   +-- YES --> Use Maglev hashing (O(1) lookup)
|       |   +-- NO --> Use Ring Hash + virtual nodes
|
+-- Storage cluster with failure domains (rack/DC awareness)?
    +-- YES --> Use CRUSH algorithm (Ceph-style)
    +-- NO --> Use Ring Hash + virtual nodes (default recommendation)

Step-by-Step Guide

1. Define the hash ring space

Map both nodes and keys onto a circular hash space [0, 2^32 - 1]. Use a uniform hash function like MD5, SHA-1, or xxHash. [src1]

import hashlib

RING_SIZE = 2**32  # Standard 32-bit hash space

def hash_key(key: str) -> int:
    digest = hashlib.md5(key.encode('utf-8')).hexdigest()
    return int(digest, 16) % RING_SIZE

Verify: hash_key("my-key-1") → returns a deterministic integer in range [0, 4294967295].

2. Place physical nodes on the ring

Hash each node identifier to get its position on the ring. [src2]

nodes = ["cache-01", "cache-02", "cache-03"]
node_positions = {hash_key(node): node for node in nodes}
sorted_positions = sorted(node_positions.keys())

Verify: Each node has a unique position; len(sorted_positions) == len(nodes).

3. Add virtual nodes for load balance

Create 100-200 hash positions per physical node by appending a suffix. [src5]

VIRTUAL_NODES = 150

ring = {}
for node in nodes:
    for i in range(VIRTUAL_NODES):
        pos = hash_key(f"{node}#vn{i}")
        ring[pos] = node
sorted_keys = sorted(ring.keys())

Verify: len(sorted_keys) == len(nodes) * VIRTUAL_NODES (e.g., 3 * 150 = 450).

4. Route keys to nodes via clockwise lookup

Find the first node position clockwise using binary search for O(log n) lookup. [src2]

import bisect

def get_node(key: str) -> str:
    pos = hash_key(key)
    idx = bisect.bisect_right(sorted_keys, pos)
    if idx == len(sorted_keys):
        idx = 0  # Wrap around the ring
    return ring[sorted_keys[idx]]

Verify: get_node("user:42") → returns same node name consistently across calls.

5. Handle node addition

Add virtual nodes to the ring. Only keys between the new node and its predecessor need reassignment. [src6]

def add_node(node: str):
    for i in range(VIRTUAL_NODES):
        pos = hash_key(f"{node}#vn{i}")
        ring[pos] = node
    sorted_keys.clear()
    sorted_keys.extend(sorted(ring.keys()))

Verify: After adding a 4th node, approximately 25% of keys remap (K/4).

6. Handle node removal

Remove all virtual nodes belonging to the departing node. Keys are automatically reassigned to the next clockwise node. [src6]

def remove_node(node: str):
    positions_to_remove = [pos for pos, n in ring.items() if n == node]
    for pos in positions_to_remove:
        del ring[pos]
    sorted_keys.clear()
    sorted_keys.extend(sorted(ring.keys()))

Verify: After removing 1 node from a 4-node cluster, approximately 25% of keys remap.

Code Examples

Python: Complete Hash Ring with Virtual Nodes

# Input:  list of node names, number of virtual nodes
# Output: ConsistentHashRing with get_node(), add_node(), remove_node()

import hashlib
import bisect
from typing import Optional

class ConsistentHashRing:
    def __init__(self, nodes: list[str] = None, vnodes: int = 150):
        self.vnodes = vnodes
        self._ring: dict[int, str] = {}
        self._sorted_keys: list[int] = []
        for node in (nodes or []):
            self.add_node(node)

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

    def add_node(self, node: str) -> None:
        for i in range(self.vnodes):
            pos = self._hash(f"{node}#vn{i}")
            self._ring[pos] = node
        self._sorted_keys = sorted(self._ring.keys())

    def remove_node(self, node: str) -> None:
        self._ring = {k: v for k, v in self._ring.items() if v != node}
        self._sorted_keys = sorted(self._ring.keys())

    def get_node(self, key: str) -> Optional[str]:
        if not self._ring:
            return None
        pos = self._hash(key)
        idx = bisect.bisect_right(self._sorted_keys, pos) % len(self._sorted_keys)
        return self._ring[self._sorted_keys[idx]]

Go: Hash Ring with Virtual Nodes

// Input:  list of node names, replicas count
// Output: Ring struct with Get(), Add(), Remove()

package chash

import (
    "crypto/md5"
    "encoding/binary"
    "fmt"
    "sort"
    "sync"
)

type Ring struct {
    mu       sync.RWMutex
    nodes    map[uint32]string
    keys     []uint32
    replicas int
}

func New(replicas int, nodes ...string) *Ring {
    r := &Ring{replicas: replicas, nodes: make(map[uint32]string)}
    for _, n := range nodes {
        r.Add(n)
    }
    return r
}

func (r *Ring) hash(key string) uint32 {
    h := md5.Sum([]byte(key))
    return binary.BigEndian.Uint32(h[:4])
}

func (r *Ring) Add(node string) {
    r.mu.Lock()
    defer r.mu.Unlock()
    for i := 0; i < r.replicas; i++ {
        h := r.hash(fmt.Sprintf("%s#vn%d", node, i))
        r.nodes[h] = node
        r.keys = append(r.keys, h)
    }
    sort.Slice(r.keys, func(i, j int) bool { return r.keys[i] < r.keys[j] })
}

func (r *Ring) Get(key string) string {
    r.mu.RLock()
    defer r.mu.RUnlock()
    if len(r.keys) == 0 {
        return ""
    }
    h := r.hash(key)
    idx := sort.Search(len(r.keys), func(i int) bool { return r.keys[i] >= h })
    if idx == len(r.keys) {
        idx = 0
    }
    return r.nodes[r.keys[idx]]
}

Java: Hash Ring with Virtual Nodes

// Input:  collection of node names, virtual node count
// Output: ConsistentHashRing with getNode(), addNode(), removeNode()

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;

public class ConsistentHashRing {
    private final int vnodeCount;
    private final ConcurrentSkipListMap<Long, String> ring = new ConcurrentSkipListMap<>();

    public ConsistentHashRing(int vnodeCount) { this.vnodeCount = vnodeCount; }

    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] d = md.digest(key.getBytes(StandardCharsets.UTF_8));
            return ((long)(d[0]&0xFF) << 24) | ((long)(d[1]&0xFF) << 16)
                 | ((long)(d[2]&0xFF) << 8) | (d[3]&0xFF);
        } catch (Exception e) { throw new RuntimeException(e); }
    }

    public void addNode(String node) {
        for (int i = 0; i < vnodeCount; i++)
            ring.put(hash(node + "#vn" + i), node);
    }

    public void removeNode(String node) {
        for (int i = 0; i < vnodeCount; i++)
            ring.remove(hash(node + "#vn" + i));
    }

    public String getNode(String key) {
        if (ring.isEmpty()) return null;
        long h = hash(key);
        Map.Entry<Long, String> entry = ring.ceilingEntry(h);
        return (entry != null) ? entry.getValue() : ring.firstEntry().getValue();
    }
}

Anti-Patterns

Wrong: Using modular hashing for dynamic clusters

# BAD -- adding/removing a server rehashes nearly every key
def get_server(key, servers):
    return servers[hash(key) % len(servers)]
# If servers changes from 3 to 4, ~75% of keys remap

Correct: Use consistent hashing for dynamic clusters

# GOOD -- only K/n keys remap when a node joins or leaves
ring = ConsistentHashRing(nodes=["s1", "s2", "s3"], vnodes=150)
server = ring.get_node(key)
# Adding "s4" remaps only ~25% of keys

Wrong: Consistent hashing without virtual nodes

# BAD -- 3 physical nodes on a ring gives wildly uneven load
ring = {}
for node in nodes:
    ring[hash_key(node)] = node  # Only 1 position per node!
# One node may get 60% of keys, another 10%

Correct: Always use 100-200 virtual nodes per physical node

# GOOD -- 150 virtual nodes per physical node ensures even distribution
ring = ConsistentHashRing(nodes=["s1", "s2", "s3"], vnodes=150)
# Standard deviation of load drops proportionally to 1/sqrt(vnodes)

Wrong: Not handling the ring wrap-around

# BAD -- fails when key hash > all node positions
def get_node_broken(key, sorted_keys, ring):
    pos = hash_key(key)
    for k in sorted_keys:
        if k >= pos:
            return ring[k]
    return None  # BUG: returns None instead of wrapping to first node

Correct: Wrap around to the first node

# GOOD -- wraps around the ring correctly
def get_node_correct(key, sorted_keys, ring):
    pos = hash_key(key)
    idx = bisect.bisect_right(sorted_keys, pos)
    if idx == len(sorted_keys):
        idx = 0  # Wrap to first node on the ring
    return ring[sorted_keys[idx]]

Common Pitfalls

• Too few virtual nodes: With fewer than 50 vnodes per node, load variance exceeds 20%. Fix: Use 100-200 vnodes per physical node — standard deviation drops as 1/sqrt(vnodes). [src5]
• Using a non-uniform hash function: Python's built-in hash() is randomized per process (PYTHONHASHSEED) and not portable. Fix: Use hashlib.md5 or hashlib.sha1 for deterministic, cross-platform hashing. [src3]
• Stale ring state on clients: When nodes join/leave, clients with outdated ring state route keys to wrong nodes. Fix: Broadcast ring changes via gossip protocol, ZooKeeper watch, or etcd lease. [src6]
• Not accounting for weighted nodes: Heterogeneous hardware needs proportional key assignment. Fix: Assign vnodes proportionally to node capacity (e.g., 4x vnodes for 4x capacity). [src2]
• Cascading failure on node removal: When one node dies, its successor absorbs all its load and may also fail. Fix: Replicate keys to k successors (replication factor), not just the next node. [src7]
• Using consistent hashing for tiny clusters: For 2-3 nodes, modular hashing is simpler and equally effective. Fix: Only use consistent hashing when n ≥ 4 and node membership changes are expected. [src4]

When to Use / When Not to Use

Important Caveats

• Consistent hashing does not solve hot key problems — if 90% of requests target 1% of keys, load is still uneven regardless of distribution algorithm. Use read replicas or key-space salting for hot keys.
• The original Karger et al. (1997) paper assumes uniform random hashing; in practice, MD5 and SHA-1 are close enough, but CRC32 is NOT sufficiently uniform.
• Virtual node count is a memory-vs-balance tradeoff: 150 vnodes * 1000 nodes = 150K ring entries. For very large clusters (>10K nodes), consider bounded-load consistent hashing (Google, 2017) which caps per-node load at (1 + epsilon) * average.
• Jump hash (Lamping & Veach, 2014) is strictly superior for static shard sets — but it cannot remove arbitrary nodes, only append new ones.