Labs/Distributed Systems/consistent-hashing

Distributed SystemsAdvanced

~30 min

Consistent Hashing & Ring Partitioning

Distribute keys across a dynamic cluster of nodes so that adding or removing a node rehashes only K/N keys rather than 100% of the dataset.

#Hash Ring Topology#Modulo Hashing Flaw#Virtual Nodes (vnodes)#Key Rebalancing Minimization#Hotspot Mitigation#Dynamo Architecture

Overview

The Problem Statement

When partitioning data across N cache or database servers, traditional hashing uses modulo math: serverIndex = hash(key) % N. However, when server count N changes (a node crashes, or autoscaling scales from 9 to 10 nodes), nearly 100% of all keys map to entirely different servers. In a distributed cache, this causes an instant 100% cache miss rate, triggering a total database collapse.

System Invariant:When the node cluster scales from N to N+1 (or N-1), at most K/N keys must be migrated, where K is the total number of keys and N is the number of nodes.

✓ When To Use

Distributed in-memory caching tiers (e.g. Memcached, Redis clusters).
Distributed key-value stores (Amazon DynamoDB, Apache Cassandra, Riak).
Load balancer sticky session routing across dynamic fleets.
Distributed file systems and object storage chunk allocation.

✕ When NOT To Use

Single-node datastores where data fits comfortably on one machine.
Workloads requiring global ordered range scans (use range-partitioning like Google Bigtable instead).
Systems with static, unchanging node counts where simple modulo hashing suffices.

Why It Exists

Catastrophic Outage Scenario

An image CDN caches 500 million user avatars across 50 origin cache instances. Autoscaling detects slightly elevated traffic and adds 1 new node (50 -> 51 nodes). Under modulo hashing, 98% of all cache lookups miss their target node simultaneously. The origin storage backend is pummeled by 500 million requests, driving bandwidth bills to hundreds of thousands of dollars and causing global 504 Gateway Timeouts.

Downstream System Degradation:

Near-100% cache miss rate upon adding or removing a single node.
Immediate thundering herd hammering underlying persistent databases.
Massive network bandwidth saturation attempting to warm cold nodes.
Inability to dynamically autoscale caching infrastructure during traffic peaks.

How It Works

Consistent Hashing maps both data keys and server nodes onto the same circular integer coordinate space—the 'Hash Ring' (typically 0 to 2^32 - 1).

Each server node's IP address or hostname is hashed to an integer position on the ring. Data keys are hashed using the exact same hash function onto the ring.

To find which server owns a given key, the algorithm walks clockwise from the key's position on the ring until it encounters the first server node. That node is the owner.

When a new node is inserted into the ring, it only takes ownership of the keys located between its position and the preceding node. All other nodes retain 100% of their existing keys. Only K/N keys relocate.

To prevent uneven key clustering (hotspots) due to non-uniform hash distribution, each physical node is assigned multiple 'Virtual Nodes' (vnodes, typically 100-300 points spread randomly around the ring). This ensures near-perfect uniform data distribution.

Single-Node vs Distributed Reality:

Single client routing hashes keys locally using an in-memory sorted binary search tree (O(log M)). Distributed coordinator rings (like Cassandra) use gossip protocols to synchronize node ring memberships and partition ownership across the cluster.

Virtual Nodes (vnodes)

Replicates physical node P across V points on the ring by hashing `node_ip#0`, `node_ip#1`, ..., `node_ip#V`.

+ Provides near-perfect statistical uniformity (+/- 5% variance); handles heterogeneous hardware by varying vnode counts.

- Increases binary search tree size and ring traversal memory.

Binary Search Tree (O(log V) Lookup)

Stores sorted ring token hashes in an array or red-black tree; locates owner node via binary search (upper_bound).

+ Fast O(log V) lookup time; deterministic.

- Requires tree rebuild or sorted insertion on node addition/removal.

Jump Consistent Hash

Google's ultra-fast O(ln N) memory-less consistent hash algorithm: `h = (h + 1) * 2862933555777941757ULL + 1`.

+ Zero memory footprint; extremely fast; mathematically optimal key movement.

- Only supports appending/removing nodes from the end; cannot remove arbitrary interior nodes.

Engineering Prediction Challenge

Prove It: Predict the System Behavior

Reason before simulating

System State Given

A cluster has 3 storage nodes (A, B, C) and 1,000 keys distributed across a 360° hash ring. Node D is added to the cluster.

Prediction Question:

Under Consistent Hashing, approximately how many keys must be migrated across the network to rebalance?

All 1,000 keys must be rehashed and moved to new locations.

Only roughly K / (N + 1) keys (approx. 250 keys, 25%) are migrated; the remaining 750 keys stay on their existing nodes.

Zero keys are moved; Node D only handles new writes.

Interactive Visualizer

Interact with a 360° SVG hash ring. Add or remove Node D to inspect clockwise key reassignment and verify that only K/N keys migrate.

Consistent Hash Ring & Rebalance Simulator

Clockwise token routing. Adding a node moves only keys in its immediate counter-clockwise sector.

360° SHA-1 / Murmur3 Hash Space • Clockwise Key Traversal

ACTIVE STORAGE NODES (3)KEY ALLOCATION

Node A(45°)

3 keys[user:101, user:106, user:107]

Node B(165°)

2 keys[user:102, user:103]

Node C(285°)

2 keys[user:104, user:105]

Topology Change Telemetry0 / 7 Keys Migrated (0%)

Topology stable. Add or remove Node D to inspect minimal key movement.

Build It Step-by-Step

The engineering blueprint. Expand each sequential milestone to examine requirements, architectural impacts, common pitfalls, and blueprint pseudocode.

Choose Consistent Hash Function

Cryptographic hashes like MD5 or SHA-256 provide excellent distribution. Fast non-cryptographic hashes like MurmurHash3 or xxHash are ideal for high throughput.

function hash(key: string) -> uint32:
  return murmur3_32(key)

Design Hash Ring Data Structure

Maintain a sorted array of 32-bit token integers paired with a lookup map linking token -> physical node ID.

struct HashRing {
  sortedTokens: Array<uint32>
  tokenToNode: Map<uint32, string>
  vnodesPerNode: int
}

Implement Virtual Node Generation

For node 'node-1', hash 'node-1#0', 'node-1#1', ..., 'node-1#150'. Insert each token into the sorted array and map to 'node-1'.

Implement Key Lookup (Clockwise Walk)

Binary search for the first token >= hash(key). If hash(key) is greater than the largest token on the ring, wrap around to token 0 (the ring property).

function getNode(key):
  if ring is empty: return nil
  keyToken = hash(key)
  idx = binarySearchFirstGreaterOrEqual(sortedTokens, keyToken)
  if idx == sortedTokens.length:
    idx = 0 // Wrap around clockwise
  token = sortedTokens[idx]
  return tokenToNode[token]

Implement Node Addition & Key Rebalancing

Insert new vnodes into the ring. Only keys between each new vnode and its counter-clockwise predecessor move to the new node.

Implement Node Removal & Failover

Remove all vnodes belonging to the failed server. Any keys previously managed by that node automatically fall clockwise onto the next surviving node.

Weighted Node Allocations

Give a 64GB server 200 vnodes and a 16GB server 50 vnodes. The 64GB server automatically receives 4x the key volume.

Code Implementation

Production-ready, idiomatic reference implementations across Go, TypeScript, Python, and Java with sticky language switching, copy-to-clipboard, and source download.

Core Architectural Design Decisions

Invariants & Mechanics

Decision 01

bisect library provides C-speed binary searches in Python standard library.

Decision 02

MD5 32-bit truncation ensures uniform spatial distribution.

Algorithmic Complexity:O(log(V * N)) lookup time.

consistent_hash.py•51 LOC

import bisect
import hashlib
from typing import Optional, List, Dict

class ConsistentHashRing:
    def __init__(self, vnodes: int = 100):
        self.vnodes = vnodes
        self.sorted_tokens: List[int] = []
        self.token_to_node: Dict[int, str] = {}
        self.nodes = set()

    def _hash(self, key: str) -> int:
        md5_bytes = hashlib.md5(key.encode("utf-8")).digest()
        return int.from_bytes(md5_bytes[:4], byteorder="big")

    def add_node(self, node: str):
        if node in self.nodes:
            return
        self.nodes.add(node)

        for i in range(self.vnodes):
            token = self._hash(f"{node}#{i}")
            bisect.insort(self.sorted_tokens, token)
            self.token_to_node[token] = node

    def remove_node(self, node: str):
        if node not in self.nodes:
            return
        self.nodes.remove(node)

        self.sorted_tokens = [
            token for token in self.sorted_tokens
            if self.token_to_node[token] != node
        ]
        self.token_to_node = {
            t: n for t, n in self.token_to_node.items() if n != node
        }

    def get_node(self, key: str) -> Optional[str]:
        if not self.sorted_tokens:
            return None

        key_token = self._hash(key)
        # bisect_right finds first element strictly greater
        idx = bisect.bisect_right(self.sorted_tokens, key_token)

        if idx == len(self.sorted_tokens):
            idx = 0 # Wrap around clockwise

        token = self.sorted_tokens[idx]
        return self.token_to_node[token]

Implementation Strategy: Python implementation using bisect.insort and bisect.bisect_right for C-optimized logarithmic binary search over the hash ring.

O(log(V * N)) lookup time.

Edge Cases & Failure Modes

Investigate real-world production incidents. Expand each failure mode to analyze symptoms, root causes, and defensive engineering mitigations.

Scenario: Non-Uniform Hash Distribution (Hotspot Clustering)

Consequence: With only 3 physical nodes and 0 virtual nodes, random hash variance places Node A and Node B close together, forcing Node C to own 80% of the ring.

Engineering Solution: Configure at least 150 to 300 virtual nodes per physical machine to guarantee balanced spatial dispersion.

Scenario: Cascading Node Failure Domino Effect

Consequence: Node B fails. All of Node B's keys fall directly onto Node C. Node C cannot handle 2x its normal traffic, crashes, and dumps 3x traffic onto Node D.

Engineering Solution: Virtual nodes solve this! Because Node B's virtual nodes were interleaved with all other servers, Node B's keys are distributed evenly across ALL surviving nodes (1/N to each), rather than crushing a single neighbor.

Production Considerations

Production checklist covering observability metrics, horizontal sharding, reliability fail-open patterns, and client identity security.

Scaling to 10x / 100x Traffic:

Cache the sorted tokens array and use Read-Copy-Update (RCU) on node mutations to keep lookups lock-free.
Assign dynamic vnode counts proportional to individual server hardware capacity (e.g. RAM/CPU).

Telemetry & Observability:

PROMETHEUS METRICS:

➔ hash_ring_physical_nodes_gauge

➔ hash_ring_total_vnodes_gauge

➔ hash_ring_key_distribution_stddev

DISTRIBUTED TRACES & LOGS:

➔ Record target node selection in trace tags: 'storage.node: cache-04'.

Trade-offs

Select an algorithm below to dynamically compare memory footprints, burst tolerance, boundary precision, and distributed suitability.

Approach	Advantages	Disadvantages	Use When
Consistent Hashing with Vnodes	Only K/N keys rehashed on topology change; uniform load distribution; hardware weighting.	Requires in-memory sorted ring; slightly higher lookup complexity O(log V*N).	Dynamic distributed caching and sharded database storage tiers.
Naive Modulo Hashing (hash % N)	Instantaneous O(1) computation; zero memory overhead.	Nearly 100% of keys relocate whenever N changes; disastrous for caching.	Completely static node clusters with zero runtime autoscaling.