Consistent Hashing: Scaling Without Chaos

Scenario context

Standard hashing (key % N) breaks when $N$ changes — adding or removing a server reshuffles almost all keys. Consistent Hashing maps both servers and keys onto a ring (0–360°). When a server is added, only its immediate neighbors' keys move, minimizing data migration.

Suppose you have 3 cache servers and you route requests like this:

server = hash(key) % 3

Works great — until you add a 4th serv…

This walkthrough focuses on The Problem with key % N: Why Normal Hashing Fails at Scale.

Before making a design choice, clarify:

• Suppose you have 3 cache servers and you route requests like this: Works great — until you add a 4th server.
• Now hash(key) % 4 is different for almost every key.
• Nearly all cached data needs to be remapped, causing a cache stampede — every backend database query misses cache simultaneously.

Concepts in play: consistency-replication, caching, hash-tables-and-bloom-filters, load-balancing

Stage 1 — Core Vocabulary: Keys, Hashes, and Rings

• Before diving into the ring mechanics, clarify the key terms: The critical insight: consistent hashing uses the same hash function for both keys and servers , so they share the same address space.

Observable outcome: Before diving into the ring mechanics, clarify the key terms: The critical insight: consistent hashing uses the same hash function for both keys and servers , so they share the same address space.

Stage 2 — The Ring: One Hash Space for Both Servers and Keys

• Consistent hashing fixes this by mapping everything — both servers and keys — onto the same circular hash space (commonly 0 to $2^{32} - 1$).
• Hash each server's name/IP to find its position on the ring.
• Hash each key to find its position on the ring.
• A key belongs to the first server encountered when walking clockwise from the key's position.

graph TD
    subgraph Hash Ring
        direction LR
        A((0)) --> B((ServerA @90))
        B --> C((ServerB @180))
        C --> D((ServerC @270))
        D --> A
    end

Observable outcome: A key belongs to the first server encountered when walking clockwise from the key's position.

Stage 3 — Adding or Removing a Server: Only Neighbors Move

• When you add ServerD at position 135: - Keys previously assigned to ServerB (in the range 91–180) that now fall in range 91–135 are reassigned to ServerD .
• • Everything else is unaffected.
• Before: $N$ servers → adding 1 requires moving approximately $K/N$ keys ($K$ = total keys).
• Naive % N : adding 1 requires remapping most keys.

flowchart LR
    A[Add ServerD at 135] --> B{Which keys move?}
    B --> C[Keys 91-135 move to ServerD]
    B --> D[Keys 0-90  ServerA: unchanged]
    B --> E[Keys 136-180  ServerB: unchanged]
    B --> F[All other keys: unchanged]

Observable outcome: Naive % N : adding 1 requires remapping most keys.

Stage 4 — Deep Dive: Virtual Nodes: Fixing Uneven Distribution

• Raw consistent hashing has a problem: if servers hash to clustered positions on the ring, one server gets most keys and others get few.
• Solution: Virtual Nodes (vnodes) Each physical server is placed at multiple positions on the ring by hashing variants of its name: With 150 virtual nodes per server (Cassandra's default), the distribution becomes statis…
• 📊 Virtual Nodes: Key Assignment on the Ring This diagram shows how a key at hash position 55 is assigned to a physical server using virtual nodes.
• The ring walk proceeds clockwise from position 55, skips ServerA-1's vnode at position 50 (behind the key), and lands on ServerB-0's vnode at position 60 — so the key is owned by ServerB.

ServerA-0 → position 10
ServerA-1 → position 50
ServerA-2 → position 200

ServerB-0 → position 30
ServerB-1 → position 120
ServerB-2 → position 250

flowchart LR
    K["Key hash value (e.g. position 55)"] --> R["Hash Ring (walk clockwise)"]
    R --> V1["vnode ServerA-1 @position 50 (skip)"]
    R --> V2["vnode ServerB-0 @position 60 (first hit)"]
    V2 --> N[Assigned to ServerB]
    Note1[ServerA also at 10, 200 ServerB also at 120, 250]

Observable outcome: The ring walk proceeds clockwise from position 55, skips ServerA-1's vnode at position 50 (behind the key), and lands on ServerB-0's vnode at position 60 — so the key is owned by ServerB.

Stage 5 — Real-World Applications: Where Consistent Hashing Powers Real Systems

• • Apache Cassandra: Uses vnodes (default 256 per server) for token assignment.
• • Amazon DynamoDB: Consistent hashing of partition keys across storage nodes.
• • Memcached / Redis Cluster: Client-side consistent hashing libraries route cache keys to shards.
• • Nginx / HAProxy: Some load balancing plugins use consistent hashing for session affinity.

Observable outcome: - Nginx / HAProxy: Some load balancing plugins use consistent hashing for session affinity.

Stage 6 — Deep Dive: Replication and Token Ring Internals

• Replication Factor Consistent hashing defines which node is the primary owner of a key, but production systems need replication for durability.
• Cassandra uses the ring position to determine replicas: after finding the primary node (the first clockwise match), it walks clockwise to find the next N-1 unique physical servers.
• With replication factor=3 , data lives on 3 servers.
• This means a key is always available even if 2 of 3 replicas are down — the CAP theorem tradeoff made explicit by where you set your read/write quorum ( QUORUM , ONE , ALL ).

flowchart LR
    K["Key K (position 150)"] -->|primary owner| A[ServerB @180]
    A -->|replica 1| B[ServerC @270]
    B -->|replica 2| C["ServerA @90 (wraps)"]

Observable outcome: This means a key is always available even if 2 of 3 replicas are down — the CAP theorem tradeoff made explicit by where you set your read/write quorum ( QUORUM , ONE , ALL ).

End-to-end outcome

Suppose you have 3 cache servers and you route requests like this: Works great — until you add a 4th server.

Alternatives considered

Decision Guide: When to Use Consistent Hashing: Decision Guide

Use consistent hashing when: - Building a distributed cache (Memcached, Redis Cluster) where servers join/leave regularly.

Failure and degraded modes

Trade-offs & Failure Modes: Limits and When It Doesn't Help

• Detection: Virtual nodes help with structural balance but do not fix hot-key problems.
• User or operator impact: Virtual nodes help with structural balance but do not fix hot-key problems.

Lessons Learned: Pitfalls in Production

• Detection: MD5 and SHA-1 are common choices but have distribution quirks.
• User or operator impact: MD5 and SHA-1 are common choices but have distribution quirks.