Consistent Hashing

The Problem

With 1000 keys and 3 nodes, how do you decide which node stores which key?

Naive Approach: key % N

key "user:1001" → hash("user:1001") % 3 = 0 → Node 0
key "user:1002" → hash("user:1002") % 3 = 1 → Node 1
key "user:1003" → hash("user:1003") % 3 = 2 → Node 2

Problem: When you add/remove a node, MOST keys need to be moved.

3 nodes → 4 nodes: 66% of keys redistributed!

The Solution: Hash Ring

Consistent hashing arranges nodes on a ring (0 to 2^32):

          Node 0 (hash: 150)
            ↓
    ┌───────────────────┐
    │                   │
    │      ● Node 1     │
    │     (hash: 800)   │
    │                   │
    └───────────────────┘
            ↑
          Node 2 (hash: 500)

How it works:

1. Hash each node's ID → place on ring
2. Hash each key → walk clockwise until you find a node
3. Key lands between Node 0 and Node 1 → stored on Node 1

Benefit: Adding a node only moves ~1/N of keys.

3 nodes → 4 nodes: only 25% keys redistributed!

Virtual Nodes

Real nodes create multiple virtual nodes for better distribution:

Node 0: virtual nodes at hash 150, 1150, 2150
Node 1: virtual nodes at hash 800, 1800, 2800
Node 2: virtual nodes at hash 500, 1500, 2500

More virtual nodes = more even distribution.

Implementation

import { ConsistentHash } from "distributed-cache";

const hash = new ConsistentHash({ virtualNodes: 150 });

hash.addNode({ id: "node-0" });
hash.addNode({ id: "node-1" });
hash.addNode({ id: "node-2" });

// Find which node handles a key
const node = hash.getNode("user:123");
console.log(node?.id); // "node-1"

// Add new node — only ~25% keys move
hash.addNode({ id: "node-3" });

// Remove node — keys redistribute to neighbors
hash.removeNode("node-1");

Real-World Usage

System	Hash Ring Usage
Redis Cluster	16384 hash slots
Amazon DynamoDB	Consistent hashing for partitioning
Apache Cassandra	Token ring for data distribution
Memcached	Client-side consistent hashing