Track 2 · Module 2.3 · Network & Sharding Architecture

Consistent Hashing

How distributed systems add and remove servers without massive data reshuffling. Master the circular hash ring, clockwise routing, minimal migration (k/N), and virtual nodes through an intuitive step-by-step case study.

⏱️ Reading Time: ~25 min

🎯 Case Study: Distributed Storage (upload / fetch)

🎬 Format: Clock Analogy + Step-by-Step SVGs + Live Lab

📁 1. The Real-World Scenario: Building Distributed Storage

Imagine you are building a simplified distributed cloud storage service like Amazon S3 or Google Drive. Clients use two basic functions:

upload(file_path)

Takes a file name, determines which storage server should hold it, and writes the bytes to that server's disk.

fetch(file_path)

Calculates which server holds the file and retrieves it for the user.

You start with 5 storage servers (Node A through Node E). The simplest, classic way to route files is Modulo Hashing: sum the bytes of the file name, divide by the number of servers N = 5, and use the remainder.

Select Language:

Naive Modulo Router

// The Naive Approach: Modulo Hashing in Python
storage_nodes = [
    StorageNode(name='A', host='10.0.0.1'),
    StorageNode(name='B', host='10.0.0.2'),
    StorageNode(name='C', host='10.0.0.3'),
    StorageNode(name='D', host='10.0.0.4'),
    StorageNode(name='E', host='10.0.0.5')
]

def hash_fn(key: str) -> int:
    # Sum ASCII byte values and take modulo N (5 active nodes)
    return sum(key.encode('utf-8')) % len(storage_nodes)

def upload(file_path: str):
    node_idx = hash_fn(file_path)
    return storage_nodes[node_idx].put_file(file_path)

def fetch(file_path: str):
    node_idx = hash_fn(file_path)
    return storage_nodes[node_idx].get_file(file_path)

// The Naive Approach: Modulo Hashing in C++
#include <iostream>
#include <vector>
#include <string>

struct StorageNode {
    std::string name;
    std::string host;
    void put_file(const std::string& path);
    std::string get_file(const std::string& path);
};

std::vector<StorageNode> storage_nodes = {
    {"A", "10.0.0.1"}, {"B", "10.0.0.2"}, {"C", "10.0.0.3"},
    {"D", "10.0.0.4"}, {"E", "10.0.0.5"}
};

int hash_fn(const std::string& key) {
    int byte_sum = 0;
    for (unsigned char c : key) byte_sum += c;
    return byte_sum % storage_nodes.size();
}

void upload(const std::string& file_path) {
    int node_idx = hash_fn(file_path);
    storage_nodes[node_idx].put_file(file_path);
}

std::string fetch(const std::string& file_path) {
    int node_idx = hash_fn(file_path);
    return storage_nodes[node_idx].get_file(file_path);
}

// The Naive Approach: Modulo Hashing in Java
import java.util.List;

public class DistributedFileStorage {
    private final List<StorageNode> storageNodes = List.of(
        new StorageNode("A", "10.0.0.1"),
        new StorageNode("B", "10.0.0.2"),
        new StorageNode("C", "10.0.0.3"),
        new StorageNode("D", "10.0.0.4"),
        new StorageNode("E", "10.0.0.5")
    );

    public int hashFn(String key) {
        int byteSum = 0;
        for (byte b : key.getBytes()) byteSum += (b & 0xFF);
        return byteSum % storageNodes.size();
    }

    public void upload(String filePath) {
        int nodeIdx = hashFn(filePath);
        storageNodes.get(nodeIdx).putFile(filePath);
    }

    public FileData fetch(String filePath) {
        int nodeIdx = hashFn(filePath);
        return storageNodes.get(nodeIdx).getFile(filePath);
    }
}

// The Naive Approach: Modulo Hashing in Go
package main

type StorageNode struct {
    Name string
    Host string
}

var storageNodes = []StorageNode{
    {"A", "10.0.0.1"}, {"B", "10.0.0.2"}, {"C", "10.0.0.3"},
    {"D", "10.0.0.4"}, {"E", "10.0.0.5"},
}

func hashFn(key string) int {
    byteSum := 0
    for _, b := range []byte(key) {
        byteSum += int(b)
    }
    return byteSum % len(storageNodes)
}

func upload(filePath string) {
    nodeIdx := hashFn(filePath)
    storageNodes[nodeIdx].PutFile(filePath)
}

func fetch(filePath string) string {
    nodeIdx := hashFn(filePath)
    return storageNodes[nodeIdx].GetFile(filePath)
}

// The Naive Approach: Modulo Hashing in TypeScript
interface StorageNode {
    name: string;
    host: string;
    putFile(path: string): void;
    getFile(path: string): Buffer;
}

const storageNodes: StorageNode[] = [
    { name: 'A', host: '10.0.0.1', putFile: () => {}, getFile: () => Buffer.from('') },
    { name: 'B', host: '10.0.0.2', putFile: () => {}, getFile: () => Buffer.from('') },
    { name: 'C', host: '10.0.0.3', putFile: () => {}, getFile: () => Buffer.from('') },
    { name: 'D', host: '10.0.0.4', putFile: () => {}, getFile: () => Buffer.from('') },
    { name: 'E', host: '10.0.0.5', putFile: () => {}, getFile: () => Buffer.from('') }
];

function hashFn(key: string): number {
    const byteSum = Buffer.from(key).reduce((sum, byte) => sum + byte, 0);
    return byteSum % storageNodes.length;
}

function upload(filePath: string): void {
    const nodeIdx = hashFn(filePath);
    storageNodes[nodeIdx].putFile(filePath);
}

function fetch(filePath: string): Buffer {
    const nodeIdx = hashFn(filePath);
    return storageNodes[nodeIdx].getFile(filePath);
}

Let's trace 5 files under this initial cluster state (sum(key) % 5):

File Key	Sum of ASCII Bytes	Formula (N = 5)	Assigned Storage Node
`f1.txt`	524	`524 % 5 = 4`	Node E (10.0.0.5)
`f2.txt`	525	`525 % 5 = 0`	Node A (10.0.0.1)
`f3.txt`	526	`526 % 5 = 1`	Node B (10.0.0.2)
`f4.txt`	527	`527 % 5 = 2`	Node C (10.0.0.3)
`f5.txt`	528	`528 % 5 = 3`	Node D (10.0.0.4)

💥 2. Scaling The Cluster: The 100% Data Eviction Collapse

Your storage service grows rapidly. To add more disk space, you add just 1 server (Node F), taking the cluster from N = 5 to N = 6.

The routing formula changes to sum(key) % 6. Now see what happens when clients call fetch() for their files:

File Key	Where File Physically Lives (N = 5)	New Formula (N = 6)	Where fetch() Looks (N = 6)	Result
`f1.txt`	Node E (Index 4)	`524 % 6 = 2`	Node C (Index 2)	❌ 404 NOT FOUND
`f2.txt`	Node A (Index 0)	`525 % 6 = 3`	Node D (Index 3)	❌ 404 NOT FOUND
`f3.txt`	Node B (Index 1)	`526 % 6 = 4`	Node E (Index 4)	❌ 404 NOT FOUND
`f4.txt`	Node C (Index 2)	`527 % 6 = 5`	Node F (Index 5)	❌ 404 NOT FOUND
`f5.txt`	Node D (Index 3)	`528 % 6 = 0`	Node A (Index 0)	❌ 404 NOT FOUND

🔥 The Disaster: 100% of files in the cluster became unfindable!

Because every single divisor changes when N changes from 5 to 6, every file is looked up on the wrong storage server.

1. In File Storage: You must copy hundreds of terabytes across the network to move every file to its new server index before handling requests.

2. In Distributed Caches (Redis / Memcached): 100% of keys miss cache simultaneously. Millions of requests instantly dogpile your backend relational database, crashing it under 100% CPU.

⭕ 3. The Consistent Hashing Ring: Step-by-Step

🕒 The Simple Analogy: A 12-Hour Wall Clock

Think of Consistent Hashing like a standard circular wall clock. If it is 11:00 and you add 2 hours, you don't fall off a number line — the clock simply wraps around 12:00 back to 1:00.

💡 The Key Insight:Instead of using the number of servers N as the divisor, we map both Servers and Files onto a fixed 360° circular "clock face" (ranging from 0 to 2²⁵⁶ - 1).

1 Step 1: Bending the Number Line into a Circular Ring

A hash function (like SHA-256) outputs large integer values between 0 and 2²⁵⁶ - 1. We connect the end back to the start so the numbers loop endlessly like a clock.

2 Step 2: Placing Servers & Clockwise File Routing

1. Place Servers on the Ring: Hash each server's IP address (e.g. hash("10.0.0.1")) to place Node A, B, C, D, and E at fixed angles around the circle.
2. Place Files on the Ring: Hash the file name (e.g. hash("f1.txt")) to get its coordinate.
3. Clockwise Lookup: To find where a file lives, start at the file's position and travel clockwise around the circle until you hit the first server!

⚖️ 4. Zero-Downtime Scaling: Adding Node K

Now observe the magic when you scale the cluster by adding a 6th server, Node K (10.0.0.6), situated on the ring between Node D and Node E:

✨ Only 1 Segment Moves — All Other 4 Nodes Stay 100% Untouched

Arc (Node D ➔ Node K]

Files in this small segment (like f1.txt) previously routed to Node E. Now they route to Node K. Node K only copies this small slice from Node E.

Nodes A, B, C, D

100% UNCHANGED. Files f2, f3, f4, f5 do not move a single byte over the network!

Mathematical Guarantee: On average, only k / N total keys migrate during a scale up or down (where k = total files, N = total nodes).

🎭 5. The Two Flaws & Virtual Nodes (Tokens)

In a basic ring with only 5 physical servers, two production problems occur:

Flaw 1: Unequal Partition Sizes (Hotspots)

Random hashes do not space servers evenly. Node A might get a tiny 15° slice while Node B gets a 160° slice, receiving 10x more traffic!

Flaw 2: Cascading Domino Crashes

If Node B crashes, 100% of its data segment dumps onto Node C (its clockwise neighbor), immediately doubling Node C's load and crashing it too.

✨ The Solution: Virtual Nodes (Tokens)

Instead of placing each physical server on the ring once, we place 100 to 256 Virtual Tokens per node (e.g. NodeA#0, NodeA#1, ... NodeA#199). Tokens from all servers interleave evenly across the entire 360° circle, eliminating hotspots and dropping load variance to under 3%.

Virtual Tokens per Physical Node	Load Variance (Standard Deviation)	Production Recommendation
1 VNode (Raw Physical Server)	~60% – 80%	Unacceptable (Severe Hotspots)
50 VNodes	~10%	Acceptable for small clusters
100 – 256 VNodes	~2% – 4%	Industry Standard (DynamoDB / Cassandra)

💻 6. Low-Level Implementation: O(log N) Binary Search

How do we execute a clockwise lookup in production without allocating a 2²⁵⁶-element array? We maintain a sorted token index and perform O(log N) Binary Search.

Select Language:

Time Complexity: O(log N)

// Python 3.10+ Implementation using Two-Array Binary Search (bisect)
import hashlib, bisect

class ConsistentHashRing:
    def __init__(self, replicas: int = 100, total_slots: int = 2**256):
        self.replicas = replicas
        self.total_slots = total_slots
        self._keys = []   # Sorted array of virtual node hash tokens
        self.nodes = []   # Matching list of physical storage node instances

    def _hash_fn(self, key: str) -> int:
        h = hashlib.sha256(key.encode('utf-8'))
        return int(h.hexdigest(), 16) % self.total_slots

    def add_node(self, node):
        for i in range(self.replicas):
            token_key = f"{node.host}#{i}"
            key = self._hash_fn(token_key)
            # Find insertion position via Binary Search O(log N)
            idx = bisect.bisect(self._keys, key)
            self._keys.insert(idx, key)
            self.nodes.insert(idx, node)

    def remove_node(self, node):
        for i in range(self.replicas):
            token_key = f"{node.host}#{i}"
            key = self._hash_fn(token_key)
            idx = bisect.bisect_left(self._keys, key)
            if idx < len(self._keys) and self._keys[idx] == key:
                self._keys.pop(idx)
                self.nodes.pop(idx)

    def assign(self, item: str):
        if not self._keys: return None
        key = self._hash_fn(item)
        # Clockwise lookup: find smallest token >= key; wrap around to 0 if needed
        idx = bisect.bisect_right(self._keys, key) % len(self._keys)
        return self.nodes[idx]

// C++17/20 Implementation using Red-Black Tree (std::map::lower_bound)
#include <iostream>
#include <string>
#include <map>
#include <vector>

class ConsistentHashRing {
private:
    // Red-Black BST storing: token_hash -> physical_node_name
    std::map<uint64_t, std::string> ring;
    int numberOfReplicas;

    uint64_t hash(const std::string& key) {
        // In production: use MurmurHash3, CityHash, or SHA-256
        return std::hash<std::string>{}(key);
    }

public:
    ConsistentHashRing(int replicas = 100) : numberOfReplicas(replicas) {}

    void addNode(const std::string& node) {
        for (int i = 0; i < numberOfReplicas; ++i) {
            uint64_t token = hash(node + "#" + std::to_string(i));
            ring[token] = node;
        }
    }

    void removeNode(const std::string& node) {
        for (int i = 0; i < numberOfReplicas; ++i) {
            uint64_t token = hash(node + "#" + std::to_string(i));
            ring.erase(token);
        }
    }

    std::string getNode(const std::string& key) {
        if (ring.empty()) return "";
        uint64_t h = hash(key);

        // lower_bound returns iterator to first element >= h in O(log N)
        auto it = ring.lower_bound(h);
        if (it == ring.end()) {
            // Wrap around the 360° circle to index 0
            it = ring.begin();
        }
        return it->second;
    }
};

// Java 17+ Implementation using Red-Black Tree (TreeMap.ceilingEntry)
import java.security.MessageDigest;
import java.util.*;

public class ConsistentHashRing<T> {
    private final TreeMap<Long, T> ring = new TreeMap<>();
    private final int numberOfReplicas;

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

    public void addNode(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            ring.put(hash(node.toString() + "#" + i), node);
        }
    }

    public void removeNode(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            ring.remove(hash(node.toString() + "#" + i));
        }
    }

    public T get(String key) {
        if (ring.isEmpty()) return null;
        long hash = hash(key);
        // ceilingEntry returns least key >= hash (Clockwise Lookup in O(log N))
        Map.Entry<Long, T> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            // Wrap around circle to index 0
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }
}

// Go 1.20+ Implementation using sort.Search
package main

import (
    "crypto/sha256"
    "encoding/binary"
    "sort"
)

type HashRing struct {
    keys    []uint64          // Sorted hash tokens
    nodes   map[uint64]string // hash -> node address
}

func (h *HashRing) Get(key string) string {
    if len(h.keys) == 0 { return "" }
    val := hashVal(key)
    // Binary Search (O(log N)) to find smallest key >= val
    idx := sort.Search(len(h.keys), func(i int) bool {
        return h.keys[i] >= val
    })
    // Wrap around to 0 if past the end of the slice
    if idx == len(h.keys) { idx = 0 }
    return h.nodes[h.keys[idx]]
}

// TypeScript / Node.js Implementation with Binary Search
import * as crypto from 'crypto';

export class ConsistentHashRing<T> {
    private keys: bigint[] = [];
    private nodes: Map<bigint, T> = new Map();

    private hash(val: string): bigint {
        const hex = crypto.createHash('sha256').update(val).digest('hex');
        return BigInt('0x' + hex);
    }

    getNode(key: string): T | null {
        if (this.keys.length === 0) return null;
        const target = this.hash(key);
        // Binary Search O(log N)
        let low = 0, high = this.keys.length - 1;
        let idx = 0;
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            if (this.keys[mid] >= target) { idx = mid; high = mid - 1; }
            else { low = mid + 1; }
        }
        return this.nodes.get(this.keys[idx])!;
    }
}

🏢 7. Production Systems Powered by Consistent Hashing

Amazon DynamoDB & Cassandra

Both databases use consistent hash rings (Token Rings) to partition data by Partition Key. For replication, a write is stored on the coordinator node and replicated to the next N-1 distinct physical nodes clockwise on the ring.

Discord Guild Routing

Routes millions of active voice channels and chat servers (Guilds) to backend Elixir beam processes. When new voice nodes autoscale during peak evening hours, existing voice calls remain 99% uninterrupted.

Akamai & Cloudflare Web Caches

Originally invented at MIT for Akamai's web caches. If an edge proxy server reboots for a kernel upgrade, neighboring edge proxies take over only its slice of cached videos without purging global cache memory.

Google Maglev Load Balancer

Google's custom packet load balancer uses consistent hashing with lookup permutation tables so packet streams belonging to existing TCP connections always hit the same backend without synchronization.

🧪 8. Interactive Lab: Hands-On Hash Ring Simulator

⚡ Real-Time Ring Canvas

Hands-On Cluster Rebalancing Simulator

Experiment with node addition, virtual nodes, and clockwise key lookups

1. Storage Node Cluster Count:

5 Nodes

2. Virtual Nodes (VNodes):

3. Upload File to Cluster:

Total Files Stored on Cluster:

5 Files

Storage Node File Distribution:

🚀 Clockwise Routing: When a file is uploaded, SHA-256 determines its angle. It travels clockwise around the continuum until it hits the first physical storage node.

🎯 9. Test Your Understanding

Scenario 1: The Midnight Cache Meltdown

You have 8 Memcached servers partitioned with simple hash(key) % 8. During Black Friday, you scale out by adding 2 new servers (now 10). Within 5 seconds, your backend MySQL databases crash under 100% CPU load. Why?

Scenario 2: The Hotspot Domino Effect

A developer creates a Consistent Hash Ring with 4 physical servers but DOES NOT configure Virtual Nodes (vnodes=1). During a traffic spike, Server 2 crashes, and 30 seconds later Server 3 crashes, followed by Server 4. What caused this cascading failure?

← Module 2.2: DNS + CDN Basics Track 2 Complete — Curriculum Hub →

Full Deep-Dive Locked