Day 05 · System Design
Consistent Hashing & Virtual Nodes
Add or remove servers while moving only a small fraction of keys, instead of reshuffling almost everything.
01Overview & core concept
In traditional hash-based partitioning (hash(key) % N), changing the number of server nodes N (due to scaling out or server failures) changes the modulo for almost every key. This forces a massive data migration of roughly (N-1)/N (often 80–90%+) of all keys, causing cache stampedes and database overloads. Consistent hashing maps both data keys and server nodes onto a circular hash ring (typically 0 to 2^32-1). When a node is added or removed, on average only K/N keys need to be remapped (K total keys, N servers).
Minimal remapping
Only keys near the changed node on the ring move, so scaling does not invalidate the whole dataset.
Virtual nodes
Each physical server owns many positions on the ring, which evens out load and smooths rebalancing.
02Architecture & request flow
[0 / 2^32-1]
│
Node A (V1) ● ◄──── Key 1 mapped to Node A
(Hash: ~500) / \
/ \ Node B (V1)
/ \ (Hash: ~1.5B)
Key 3 ──────►● ●
mapped to │ │
Node C │ │ ◄── Key 2 mapped to Node B
\ /
\ / Node C (V1)
Node A (V2) ● ─ ● (Hash: ~3B)
(Hash: ~2.5B)How it works
1. The Hash Ring
A fixed hash space (e.g., 0 to 2^32-1 using SHA-1 or MurmurHash3) is treated as a continuous logical circle.
2. Node Placement
Servers are hashed by their IP or identifier and placed at specific positions along the ring.
3. Key Lookup
To store or retrieve a key, hash the key and traverse the ring clockwise until the first server node is reached.
4. Node Addition / Removal
Node added: only keys between the new node and its counter-clockwise neighbor move to it. Node removed: only that node's keys are reassigned to the next clockwise neighbor.
The non-uniform distribution problem & virtual nodes
The problem
With few physical nodes, keys can cluster unevenly on the ring, leading to severe hotspots.
Virtual Nodes (VNodes)
Each physical node is assigned multiple (e.g., 100–256) pseudo-random locations on the ring by hashing variants like NodeA#1, NodeA#2, and so on.
Benefits
Balances key distribution across the cluster, supports heterogeneous hardware (more VNodes for higher-capacity servers), and spreads a failed node's load across all remaining nodes instead of overwhelming one neighbor.
03Real-world example: Amazon DynamoDB & Apache Cassandra
Token Ring Topology
Cassandra uses consistent hashing to partition data across a cluster. Each node owns a set of tokens (ranges) on the ring.
Replication on the Ring
With replication factor RF=3, the coordinator hashes the partition key, locates the primary replica on the ring, and forwards the write clockwise to the next 2 distinct physical nodes (skipping co-located VNodes).
Zero-Downtime Scaling
When a new node joins, it claims specific token ranges and streams only the required partitions from existing replicas without taking the cluster offline.
04Architectural trade-offs
| Dimension | Standard Modulo Hashing (hash % N) | Consistent Hashing with VNodes |
|---|---|---|
| Data Movement on Scale/Failure | About (N-1)/N of keys remapped (massive reshuffle). | About 1/N of keys remapped (minimal disruption). |
| Lookup Time Complexity | O(1) direct array index. | O(log M) binary search across M virtual node tokens. |
| Memory Overhead | Negligible (stores a single integer N). | Requires maintaining and synchronizing the token ring state (e.g., via gossip protocols or config servers). |
| Hotspot Susceptibility | High if the hash function is poor. | Low when the virtual node factor (V >= 100) is tuned properly. |
Failure modes & mitigations
Cascading Failures
When a high-traffic node dies, its immediate successor on the ring inherits 100% of its traffic if VNodes are not used, potentially causing a domino effect of node crashes.
Ring Topology Desynchronization
If client-side routing libraries have stale views of the ring during rapid node additions/removals, requests may route to incorrect nodes, requiring internal forwarding proxies or gossip-based hinted handoff.
05Interview question & approach
Design a distributed, in-memory caching tier (like a distributed Memcached cluster) that can dynamically scale from 10 to 50 nodes without invalidating or relocating the entire cached dataset.
Client-Side vs. Proxy-Based Routing
Propose a client library (or lightweight proxy like Envoy) that maintains a local sorted array of token hashes (the consistent hash ring).
Virtual Node Implementation
Configure ~128–256 virtual nodes per physical instance using a uniform hash function (e.g., Murmur3 or MD5). Use binary search (bisect_right in Python, std::upper_bound in C++) for lookups in O(log(nodes x vnodes)), which is effectively O(1) in practice.
Handling Node Additions/Removals
Only about 1/total-nodes of cache entries miss when a node scales up or down. Propose a replication strategy or dual-reading during transition windows to avoid cache stampedes.
Ring Metadata Management
Use Apache ZooKeeper, Consul, or etcd as the source of truth, with distributed watchers notifying clients of node topology changes.