---
# === IDENTITY ===
id: software/patterns/consistent-hashing/2026
canonical_question: "How does consistent hashing work and when to use it?"
aliases:
  - "consistent hashing algorithm"
  - "hash ring implementation"
  - "virtual nodes consistent hashing"
  - "distributed hashing for load balancing"
  - "ketama hashing"
  - "consistent hash ring"
  - "how to distribute keys across nodes evenly"
  - "when to use consistent hashing vs rendezvous hashing"
entity_type: software_reference
domain: software > patterns > consistent hashing
region: global
jurisdiction: global
temporal_scope: 1997-2026

# === VERIFICATION ===
last_verified: 2026-02-24
confidence: 0.92
version: 1.0
first_published: 2026-02-24

# === TEMPORAL VALIDITY ===
temporal_validity:
  status: stable
  last_breaking_change: null
  next_review: 2026-08-23
  change_sensitivity: low

# === CONSTRAINTS ===
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"

# === SKIP CONDITIONS ===
skip_this_unit_if:
  - condition: "Need to partition data by key range (alphabetical, time-based)"
    use_instead: "Range-based partitioning / B-tree sharding"
  - condition: "Static set of buckets that never changes"
    use_instead: "Jump hash (Google, 2014) — perfect balance, zero memory, O(ln n)"
  - condition: "Need weighted routing with replication factor k"
    use_instead: "Rendezvous (HRW) hashing — simpler, O(n) per lookup, no ring metadata"

# === AGENT HINTS ===
inputs_needed:
  - key: system_type
    question: "What type of system are you distributing across?"
    type: choice
    options: ["cache cluster", "database sharding", "load balancing", "content delivery"]
  - key: node_count
    question: "How many nodes (servers) are in your cluster?"
    type: text
  - key: replication_needed
    question: "Do you need data replicated across multiple nodes?"
    type: boolean

# === DISTRIBUTION ===
canonical_source: "https://knowledgelib.io/software/patterns/consistent-hashing/2026"
suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)"

# === RELATED UNITS ===
related_kos:
  depends_on: []
  related_to:
    - id: software/system-design/multi-layer-caching/2026
      label: "Multi-Layer Caching Architecture"
    - id: software/system-design/database-sharding/2026
      label: "Database Sharding Strategies"
  solves:
    - id: software/system-design/cdn-design/2026
      label: "CDN Architecture Design"
  alternative_to: []
  often_confused_with: []

# === SOURCES (7 authoritative sources) ===
sources:
  - id: src1
    title: "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web"
    author: Karger et al. (MIT)
    url: https://en.wikipedia.org/wiki/Consistent_hashing
    type: academic_paper
    published: 1997-01-01
    reliability: authoritative
  - id: src2
    title: "Consistent Hashing Explained"
    author: Ashish Pratap Singh (AlgoMaster)
    url: https://blog.algomaster.io/p/consistent-hashing-explained
    type: technical_blog
    published: 2024-08-15
    reliability: high
  - id: src3
    title: "Consistent Hashing: Algorithmic Tradeoffs"
    author: Damian Gryski
    url: https://dgryski.medium.com/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8
    type: technical_blog
    published: 2018-04-10
    reliability: high
  - id: src4
    title: "Consistent Hashing Algorithms: Jump Hash vs Ring Hash vs Rendezvous Hash"
    author: Umit Unal
    url: https://umitunal.net/2025/09/consistent-hashing-algorithms-jump-hash-vs-ring-hash-vs-rendezvous-hash/
    type: technical_blog
    published: 2025-09-01
    reliability: moderate_high
  - id: src5
    title: "Consistent Hashing — Eli Bendersky's Website"
    author: Eli Bendersky
    url: https://eli.thegreenplace.net/2025/consistent-hashing/
    type: technical_blog
    published: 2025-01-15
    reliability: high
  - id: src6
    title: "Implementing Efficient Consistent Hashing"
    author: Ably Engineering
    url: https://ably.com/blog/implementing-efficient-consistent-hashing
    type: technical_blog
    published: 2023-06-20
    reliability: high
  - id: src7
    title: "The Ultimate Guide to Consistent Hashing"
    author: Toptal Engineering
    url: https://www.toptal.com/big-data/consistent-hashing
    type: technical_blog
    published: 2023-03-01
    reliability: moderate_high
---

# 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 (where K = total keys, n = node count), 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
<!-- Agents: read this section before recommending any action from this unit.
     These are hard constraints that must not be violated. -->

- 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

| Approach | Keys Moved on Node Change | Load Balance | Lookup Time | Memory | Best Use Case |
|---|---|---|---|---|---|
| Modular hashing (`key % n`) | ~100% (full rehash) | Perfect (uniform) | O(1) | O(1) | Static cluster, never changes |
| Ring hashing (no vnodes) | K/n average | Poor (O(log n) imbalance) | O(log n) | O(n) | Prototype only |
| Ring hashing + virtual nodes | K/n average | Good (tunable via vnode count) | O(log n) | O(n * v) | Cache clusters, DB sharding |
| Jump hash (Google, 2014) | K/n optimal | Near-perfect (0.0000008% std dev) | O(ln n) | O(1) | Static shard count, append-only |
| Rendezvous / HRW hashing | K/n optimal | Good | O(n) per lookup | O(1) | Small clusters, k-replication |
| Maglev hashing (Google) | K/n near-optimal | Near-perfect | O(1) lookup table | O(n * M) | L4 load balancers |
| CRUSH (Ceph) | K/n optimal | Configurable (weighted) | O(log n) | O(n) | Storage clusters with failure domains |
| Ketama (libmemcached) | K/n average | Good (150 vnodes default) | O(log n) | O(n * 150) | Memcached clusters |

## 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 (consistent 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. Each position on the ring corresponds to a hash value. [src1]

```python
import hashlib

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

def hash_key(key: str) -> int:
    """Hash a string key to a position on the ring."""
    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 (hostname, IP, or unique ID) to get its position on the ring. [src2]

```python
nodes = ["cache-01", "cache-02", "cache-03"]
node_positions = {hash_key(node): node for node in nodes}
# Sort positions for binary search
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 multiple hash positions per physical node by appending a suffix (e.g., `#0`, `#1`, ..., `#149`). 100-200 virtual nodes per physical node is the production standard. [src5]

```python
VIRTUAL_NODES = 150  # Per physical node

ring = {}
sorted_keys = []

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

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

### 4. Route keys to nodes via clockwise lookup

For a given key, find the first node position clockwise (i.e., the smallest ring position >= key hash). Use binary search for O(log n) lookup. [src2]

```python
import bisect

def get_node(key: str) -> str:
    """Find the node responsible for a given key."""
    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 one of the node names consistently.

### 5. Handle node addition

When a new node joins, add its virtual nodes to the ring. Only keys between the new node and its predecessor need reassignment. [src6]

```python
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()))
    # Only keys that now hash to the new node need migration
```

**Verify**: After adding a 4th node to a 3-node cluster, approximately 25% of keys should 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]

```python
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 to remaining nodes.

## Code Examples

### Python: Complete Hash Ring with Virtual Nodes

> Full script: [python-complete-hash-ring-with-virtual-nodes.py](scripts/python-complete-hash-ring-with-virtual-nodes.py) (28 lines)

```python
# 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
# ... (see full script)
```

### Go: Hash Ring with Virtual Nodes

> Full script: [go-hash-ring-with-virtual-nodes.go](scripts/go-hash-ring-with-virtual-nodes.go) (49 lines)

```go
// Input:  list of node names, replicas count
// Output: Ring struct with Get(), Add(), Remove()
package chash
import (
    "crypto/md5"
# ... (see full script)
```

### Java: Hash Ring with Virtual Nodes

> Full script: [java-hash-ring-with-virtual-nodes.java](scripts/java-hash-ring-with-virtual-nodes.java) (33 lines)

```java
// 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.*;
# ... (see full script)
```

## Anti-Patterns

### Wrong: Using modular hashing for dynamic clusters

```python
# 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

```python
# 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

```python
# 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

```python
# 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

```python
# 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

```python
# 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 (e.g., 8GB vs 32GB cache servers) 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

| Use When | Don't Use When | Use Instead |
|---|---|---|
| Distributed cache (Memcached, Redis) with nodes joining/leaving | Static cluster that never changes size | Modular hashing (`key % n`) |
| Database sharding with horizontal scaling | Fewer than 3 nodes | Simple modular hashing |
| Load balancing across a dynamic server pool | Need range queries on keys | Range-based partitioning |
| CDN request routing with server churn | Append-only shard count growth | Jump hash (perfect balance, O(1) memory) |
| Need minimal key migration during scaling events | Need built-in k-replication with no ring metadata | Rendezvous (HRW) hashing |
| Peer-to-peer overlay networks (Chord, Dynamo) | Need rack/DC-aware failure domain placement | CRUSH algorithm (Ceph) |

## 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.

## Related Units
<!-- Generated from related_kos frontmatter -->

- [Multi-Layer Caching Architecture](/software/system-design/multi-layer-caching/2026)
- [Database Sharding Strategies](/software/system-design/database-sharding/2026)
- [CDN Architecture Design](/software/system-design/cdn-design/2026)