Production at Scale · Simulator 03
Consistent hashing & hot keys
Consistent hashing places nodes on a ring so adding or removing one remaps only 1/(N+1) of keys — instead of nearly everything. But with few virtual nodes per server, a lucky cluster of ring points can concentrate load. Drag the sliders to see how vnodes smooth the distribution, and watch what a single hot key does to the busiest node. This is the model behind the load-balancing lesson, made live.
- The Node Load Bars: Each vertical bar represents one of your backend servers (nodes). The height of the bar represents the amount of traffic routed to that server. The horizontal dashed line is the perfect average.
- Imbalance (Red Bar): The server taking the highest load is highlighted in red. If the red bar is far above the dashed line, your cluster is highly imbalanced (some servers are overloaded, others are idle).
- Virtual Nodes (vnodes): Drag the vnodes per server slider. Notice how raising vnodes makes the bars align closely to the average line (balanced distribution).
- Hot Key Share: Drag this slider up. Notice how a single hot key concentrates traffic onto one server (the red bar spikes), showing that virtual nodes cannot solve hot keys.
Each bar is one node's share of total load. The red bar is the hottest node. The dashed line marks average load (1/N). A hot key adds extra load to whichever node owns it.
By the numbers: consistent hashing math
Keys are hashed onto a ring. Each node owns vnodes equally spaced points; a key goes to the next point clockwise. Adding a node only steals keys from its immediate neighbours:
# Remap fraction when adding 1 node to a cluster of N
remap_consistent ≈ 1 / (N + 1) # only the new node's ring neighbours move
remap_modulo ≈ (N) / (N + 1) # nearly everything remaps with hash % N
# Load imbalance (max / avg) improves with more virtual nodes
imbalance ∝ 1 / √vnodes # std-dev of arc lengths shrinks with more points
# Hot key: one key carries hot% of all traffic; it lands on one node
hot_node_load = (node_key_share + hot%) / total_loadWith 1 vnode per node the ring is bumpy — one arc might be 3× the average. With 150 vnodes the worst node rarely exceeds 1.2× average. The hot-key problem is orthogonal: no amount of vnodes helps if a single object (a viral video, a trending product) is fetched millions of times — that key always lands on one node. The fix is key-level sharding or application-level replication.
Remap Comparison Table
| Nodes (N) | Consistent Hashing Remap (1 / N+1) | Modulo Hashing Remap (N / N+1) | Imbalance Std Dev (1 / √vnodes) | Network Node Sequence |
|---|---|---|---|---|
| N = 4 → 5 | 20.0% | 80.0% | 1.0 (vnodes=1) | Hash ring lookup → Add Server 5 → Reassign 20% |
| N = 9 → 10 | 10.0% | 90.0% | 0.32 (vnodes=10) | Hash ring lookup → Add Server 10 → Reassign 10% |
| N = 19 → 20 | 5.0% | 95.0% | 0.08 (vnodes=150) | Hash ring lookup → Add Server 20 → Reassign 5% |
1. Set N = 5, vnodes = 1 → imbalance is often 2–4×; one node dominates. 2. Raise vnodes to 150 → bars level out, imbalance drops below 1.2×. 3. Now add hotKey = 40% with N = 10, vnodes = 150 → one bar turns red and towers over the rest, even though hashing is otherwise perfect. 4. Raise N from 5 → 6 and watch "keys remapped" — it's always close to 1/(N+1) regardless of vnodes.
This is a first-principles model using 2000 sample keys with a deterministic integer hash. Real consistent-hashing libraries (e.g. ketama, Amazon Dynamo) use cryptographic hashes and may differ in exact distribution. The hot-key load is additive and goes to a fixed node for illustration; in production the hot key's node is unpredictable. Treat the numbers as illustrative.
Under the hood: how consistent hashing actually works
At the implementation level, consistent hashing represents servers and keys on a 32-bit integer circle (from 0 to 232-1). The core lookup logic uses binary search trees for low latency:
- Initialize Ring: For each server, generate
Vvirtual node names (e.g.,"node1#vnode1") and hash them onto the circle. In memory, this is stored as a red-black tree mappinghash_code → server_metadata. - Locate Key: When a request arrives, the router hashes the key (e.g.,
md5("user_123")) to a 32-bit integerK. - Search Ring: The router searches the tree for the smallest hash key greater than or equal to
K(using a ceiling lookup):
If no such hash exists, it wraps around to the first node in the tree.const node = ring.ceilingEntry(keyHash) || ring.firstEntry();
How to debug & inspect it
To inspect and troubleshoot routing imbalances, test key distribution patterns and trace node assignment logs using script diagnostics.
Symptom → Cause → Fix:
| Symptom | Likely Cause | Fix |
|---|---|---|
| One server is overloaded while other servers are idle | A single hot key represents a large percentage of total traffic | Implement key replication (add suffix -replica-X) or proxy-layer caching |
| Adding a server triggers cache-miss stampedes on all nodes | Using modulo hashing (hash % N) instead of consistent hashing ring |
Refactor router to use a consistent hashing ring library (e.g., ketama) |
| Requests remap unpredictably on node restart | Ring hash uses dynamic memory address or non-deterministic node IDs | Ensure hash functions use deterministic labels (e.g., IP address or static hostname) |