---
title: "Consistent Hashing: The 'Locker Room' Mental Model"
description: "How does Cassandra know which server stores your data? Master consistent hashing, virtual nodes, and scaling distributed systems reliably."
pubDate: "2023-05-21"
lang: "en"
slug: "consistent-hashing-distributed-systems"
url: "https://hoangyell.com/consistent-hashing-distributed-systems/"
author: "HoangYell"
translation_vi: "https://hoangyell.com/vi/consistent-hashing-distributed-systems/"
categories: ["System Design"]
tags: ["system-design", "distributed-systems", "hashing"]
heroImage: "https://raw.githubusercontent.com/HoangGeek/store/main/webp/photo-1637028253736-ccf0e0e2da47.webp"
---

You have 3 cache servers. You use `server = hash(key) % 3` to decide which server stores each key.

You add a 4th server. Now `hash(key) % 4` gives different results. **Every cached key maps to a new server.** Your cache hit rate drops from 90% to near 0%. Your database collapses.

This is why **simple modular hashing breaks** when you scale. Consistent Hashing is the solution used by Redis Cluster, Cassandra, DynamoDB, and every CDN.

***

## Part 1: Foundations (The Mental Model)

### Simple Hashing = The School Locker Assignment

Imagine 1,000 students and 10 lockers. `locker = student_id % 10`.

Simple. Uniform. Works perfectly.

**Problem**: A new locker (server) is added. Now `student_id % 11`. Almost every student gets a different locker. Everyone is locked out of their old locker. **Mass confusion.**

### Consistent Hashing = The Clock/Ring

Instead of `% servers`, imagine a giant **clock ring** from 0 to 360 degrees (or 0 to 2^32).

1.  **Place servers on the ring**: Hash each server's name → position on the ring.
2.  **Place keys on the ring**: Hash each key → position on the ring.
3.  **Find the server**: Walk clockwise from the key. The first server you hit owns that key.

```markdy
scene type=constellation width=1100 height=700
theme: light=doodle dark=nebula

service NodeA "Server Node A (0°)" focal=true
service NodeB "Server Node B (120°)"
service NodeC "Server Node C (240°)"
cache CacheKey "Key 'user:123' (Hash: 45°)"

beat ring_lookup "Clockwise Ring Traversal" {
  show $nodes stagger=50ms
  CacheKey -> NodeB "walk clockwise -> assigned to Node B"
  glow NodeB color=#38bdf8
}

player:
    playback:
      loop true
    controls:
      speed true
      speeds "0.25"
      fullscreen true
      gif true
      theme true
    interaction:
      zoom true
      pan true
      click_to_play true
      double_click_to_reset true
      keyboard false
    chrome:
      badge true
      progress none
```

**When a server is added/removed**, only the keys between it and its predecessor on the ring are affected. Everything else stays put.

**Old way**: Add server → ~100% of keys remapped.
**Consistent Hashing**: Add server → ~1/N keys remapped (where N = number of servers).

***

## Part 2: The Investigation (Virtual Nodes)

A naive ring has one problem: **uneven distribution**. By chance, one server might cover 1° and another might cover 180°.

**Virtual Nodes** solve this. Instead of each server having 1 position, it has **100+ positions** on the ring (with different hash seeds).

```
Physical Servers: A, B, C
Virtual Nodes:
  Ring: A₁ B₂ C₃ A₄ B₅ C₆ A₇ B₈ C₉ A₁₀ ...
        (100 virtual nodes each, evenly distributed)
```

Each key still walks clockwise to find its server. But now each physical server handles a well-distributed portion of the ring - even if servers have different capacities (a bigger server gets more virtual nodes).

***

## Part 3: The Diagnosis (Common Problems)

| Problem | Cause | Fix |
|:---|:---|:---|
| **Uneven load** | Few servers, bad hash collisions | Add virtual nodes (100-150 per server) |
| **Hot spots** | One key gets 90% of traffic | Shard the key: `user:123:shard_{0-9}` |
| **Server fails, keys lost** | No replication | Replicate to N servers clockwise on the ring |
| **Stale reads after topology change** | Client still has old ring state | Use gossip protocol (Cassandra) or centralized config (Zookeeper) |

***

## Part 4: The Resolution (Where Consistent Hashing Is Used)

### 1. Redis Cluster

Redis Cluster uses **hash slots** (0–16383) - a simplified consistent hashing variant.

```
redis-cli cluster info
redis-cli cluster nodes  # See which server owns which hash slots
```

### 2. Cassandra

Uses a full consistent hash ring with virtual nodes ("vnodes"). Each node's token range determines which rows it stores.

### 3. Your Own Load Balancer (Python)

```python
import hashlib
from bisect import bisect_right

class ConsistentHashRing:
    def __init__(self, servers: list, replicas: int = 150):
        self.ring = {}
        self.sorted_keys = []
        
        for server in servers:
            for i in range(replicas):
                # Create 150 virtual nodes per server
                virtual_key = f"{server}:{i}"
                h = int(hashlib.md5(virtual_key.encode()).hexdigest(), 16)
                self.ring[h] = server
                self.sorted_keys.append(h)
        
        self.sorted_keys.sort()
    
    def get_server(self, key: str) -> str:
        h = int(hashlib.md5(key.encode()).hexdigest(), 16)
        idx = bisect_right(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

# Usage
ring = ConsistentHashRing(["server-a", "server-b", "server-c"])
print(ring.get_server("user:123"))  # → "server-b"
print(ring.get_server("user:456"))  # → "server-a"

# Add a new server
ring2 = ConsistentHashRing(["server-a", "server-b", "server-c", "server-d"])
# Only ~25% of keys change their server!
```

***

## Final Mental Model

```
Simple Hashing (% N)    -> School lockers. Add one locker: everyone loses their stuff.
Consistent Hashing      -> Clock Ring. Add a server: only nearby keys are affected.
Virtual Nodes           -> Each server on the ring 150 times. Evenly distributed load.

hash(key) % N           -> 100% remapped when N changes.
Consistent Hashing      -> ~1/N remapped when N changes. (Critical for large caches).
```

**When you need it**:
*   Distributed caches (Redis Cluster, Memcached).
*   Distributed databases (Cassandra, DynamoDB).
*   Load balancing stateful connections (sticky sessions without a lookup table).