Consistent Hashing Visualizer — Interactive Ring, Virtual Nodes & Interview Prep

§1

What is Consistent Hashing?

Consistent hashing is a technique for distributing data across a changing set of nodes such that when nodes are added or removed, only a minimal fraction of data needs to move. It was introduced by David Karger et al. (MIT) in 1997 and became the foundation of nearly every large-scale distributed storage system built since — Dynamo, Cassandra, Redis Cluster, Akamai’s CDN, and Memcached client libraries all use variants of the same idea.

§2

The Problem: Naive Modulo Hashing

The simplest way to assign a key to a server is server = hash(key) % N, where N is the server count. This works perfectly when N is fixed. But in any distributed system, servers fail and new capacity is added constantly. Every time N changes, almost every key remaps to a different server. With 100 servers and 1 million keys, removing one server forces ~990,000 keys to migrate — a full data reshuffle that creates a thundering herd across the cluster.

§3

How the Ring Works

Consistent hashing maps both servers and keys onto a circular hash space. Servers are placed at positions on the ring by hashing their identifiers. Keys are hashed to positions on the ring and are owned by the first server encountered when moving clockwise from the key’s position. This tool visualizes the hash space as 0–359° for clarity; production systems use the full 0–2³²−1 range.

When a server is removed, only the keys between that server and its counter-clockwise neighbor need to migrate — they go to the next clockwise server. When a server is added, it only takes keys from one neighbor. In both cases the number of moving keys is K / N on average — the mathematical minimum. For 1 million keys and 100 servers, adding or removing one server moves ~10,000 keys, not ~990,000.

§4

Virtual Nodes Deep Dive

With a small number of servers and basic ring placement, load is uneven by chance — a handful of random points on a circle create unequal arc lengths, meaning some servers own far more of the key space than others. Virtual nodes solve this by giving each physical server multiple positions on the ring, spreading its ownership across many small non-contiguous segments.

Each physical server S gets V virtual node identifiers — S-vn-0, S-vn-1, …, S-vn-V — each hashed to a different ring position. The assignment rule is unchanged: go clockwise to the nearest VN. The result: each server’s load is the sum of V small arc segments spread around the ring, and the statistical variance in load shrinks roughly as 1/√V.

How many virtual nodes?

1 VN/server: severe imbalance; standard deviation of load can exceed 30–40% of the mean
10 VN/server: acceptable balance for small clusters (3–5 servers)
100–150 VN/server: Cassandra’s pre-3.0 default; good for stable-size clusters
150–256 VN/server: modern Cassandra default; enables smooth incremental scaling

The visualizer defaults to 3 VNs/server to make the imbalance problem visible before improvement. Try sliding from 1 to 16 with 40+ keys and 3 servers to see the effect clearly — the imbalance badge goes from red to green.

§5

Algorithm & Complexity

Ring lookup: finding the server for a key

Hash the key to a ring position: O(1)
Binary search the sorted VN list for the successor: O(log(N × V))
Total: O(log(N × V)) — effectively O(log N) with fixed V

Adding a server

Generate V new VN positions via hashing: O(V)
Insert V positions into sorted VN list: O(V log(N × V))
Identify keys to transfer: O(K/N) expected — only one neighbor’s keys

Removing a server

Remove V VN positions from sorted list: O(V log(N × V))
Orphaned keys absorbed by successor VNs: O(K/N) expected key movement

§6

Interview Q&A — 15 Questions

Drawn from actual system design and distributed systems interviews at Google, Meta, Amazon, Uber, Stripe, and DoorDash. Prepping seriously? Grokking the System Design Interview (Educative) covers these in depth.

Level — Fundamentals

Q1What problem does consistent hashing solve?

Consistent hashing solves the problem of minimal disruption when the node count in a distributed system changes. With naive modulo hashing, adding or removing a server remaps nearly all keys and creates a thundering herd. Consistent hashing guarantees only O(K/N) keys need to move — the theoretical minimum.

Q2Walk me through how a key is assigned to a server in a consistent hash ring.

We define a circular hash space (0 to 2³²−1). Each server is assigned a ring position by hashing its identifier. Each key is hashed to a ring position. The key is owned by the first server encountered moving clockwise from the key’s position. If no server exists at a greater angle, we wrap around and take the server with the smallest hash.

Q3What are virtual nodes and why are they needed?

With few servers, random ring placement creates unequal arc lengths — some servers own disproportionately large key ranges. Virtual nodes give each physical server multiple ring positions, spreading its ownership across many small segments. This reduces load variance substantially. Cassandra uses 256 virtual tokens per node by default.

Q4What happens to keys when a server goes down?

Only the keys owned by the failed server’s VNs need to migrate. Each VN’s key set is absorbed by the next clockwise VN — which belongs to a different physical server. No other servers are affected. This is the core fault-tolerance property of the design.

Q5What is the time complexity of key lookup?

O(log(N × V)) where N is the server count and V is the VN count per server, because we binary-search a sorted list of VN positions. With V fixed (e.g. 150), this simplifies to O(log N). In practice it’s a small array search — effectively O(1) at typical cluster sizes.

Level — Intermediate

Q6How does Amazon Dynamo use consistent hashing?

Dynamo places both data and nodes on a virtual ring. Each node is responsible for the range between itself and its predecessor. Dynamo uses preference lists — a key’s primary owner plus the next N−1 clockwise nodes — to maintain replication factor N. Quorum-based reads (R) and writes (W) with R+W > N provide tunable consistency on top of the ring topology. The 2007 Dynamo paper is the canonical reference and required reading for distributed systems interviews.

Q7How does Apache Cassandra use consistent hashing differently from Dynamo?

Cassandra uses ‘vnodes’ — 256 random tokens per physical node by default, introduced in Cassandra 1.2 to replace manual static token assignment. The result is automatic load balancing even as nodes join or leave. Cassandra’s NetworkTopologyStrategy places replicas on different racks and DCs by walking the ring clockwise and skipping nodes in the same rack. The key operational advantage: adding a node causes it to steal from 256 different neighbors simultaneously, making scale-out smooth and incremental.

Q8What are the tradeoffs of increasing virtual node count?

More VNs → better load balance but higher metadata overhead. The VN-to-node mapping must be stored and replicated across all nodes; gossip overhead in Cassandra scales with cluster metadata size. In practice, 150–256 VNs/node is the sweet spot — load balance improvement flattens out past 200 VNs due to statistical convergence, while metadata cost keeps growing linearly.

Q9How would you handle heterogeneous servers — some with 2× the capacity?

Assign virtual nodes proportionally to capacity. A server with 2× RAM gets 2× the VN count, so it naturally owns twice the key space. This is the recommended approach in both Cassandra and Redis Cluster. In Redis Cluster, higher-capacity nodes receive a proportionally larger number of the 16,384 hash slots.

Q10How does Redis Cluster implement sharding — is it consistent hashing?

Redis Cluster uses a close relative of consistent hashing called hash slot sharding. The key space is fixed at 16,384 slots; each key maps to a slot via CRC16(key) % 16384. Slots are assigned to primary nodes. Adding a node means migrating specific slots to it. This is functionally similar to consistent hashing but with a fixed bucket count rather than a continuous ring. Advantage: simple client-side routing table (a 16,384-bit bitmap). Tradeoff: less flexible than arbitrary VN counts for heterogeneous clusters.

Level — Advanced

Q11What is rendezvous hashing and how does it compare to consistent hashing?

Rendezvous hashing (also called Highest Random Weight / HRW) assigns a key to the server that produces the highest score for H(key, server_id) across all servers. No ring is needed, and it achieves perfect load balance with no virtual nodes. Adding/removing a server affects only O(K/N) keys. The tradeoff: lookup is O(N) — you compute H for every server — making it slower than O(log N) ring lookup in large clusters. Used in Nginx’s upstream hashing, Varnish, and some CDN implementations.

Q12What is Jump Consistent Hashing?

Jump Consistent Hashing (Lamping & Veach, Google, 2014) maps a key to a bucket in {0, ..., N−1} with perfect balance and minimal redistribution when N changes. It uses a pseudo-random jump loop that converges in O(log N) iterations — the entire algorithm is 5 lines of C++. No ring, no VNs, no metadata. The constraint: bucket IDs must be contiguous, so it only supports adding buckets at the end (not arbitrary node removal). Used in Google’s internal production storage systems.

Q13How does consistent hashing handle hot keys / skewed access patterns?

It doesn’t — consistent hashing distributes keys evenly by hash position, but if 90% of traffic hits 1% of keys, those keys overwhelm their owning servers regardless of ring balance. The standard solution: detect hot keys at the client level (Count-Min Sketch for frequency estimation) and replicate them to multiple servers using key suffixes (user:42_shard1, user:42_shard2). The read client picks a random shard. DynamoDB’s adaptive capacity and Cassandra’s speculative execution address this at the infrastructure level.

Q14What is bounded load consistent hashing?

Mirrokni et al. at Google (2017) extended consistent hashing with a capacity constraint: no server can hold more than (1+ε) × (K/N) keys, where ε is a configurable bound (e.g. 0.25). When a server is at capacity, incoming keys are redirected to the next clockwise server that is under its bound. This guarantees near-perfect load balance while maintaining the O(K/N) migration property on topology changes. Published as ‘Consistent Hashing with Bounded Loads’ on arXiv and used in Google’s internal sharding.

Q15Design a distributed cache handling 10 million req/s across 100 servers using consistent hashing.

Key design decisions: (1) Client-side ring — each client holds the VN map locally and routes directly, no proxy hop. (2) 150–200 VNs/server for even load across 100 nodes. (3) Replication factor 3: primary + next 2 clockwise nodes, à la Dynamo. (4) Writes: quorum (2 of 3 ACK). Reads: nearest replica for latency. (5) Gossip protocol for topology propagation — converges within seconds. (6) Hot key detection: track hit rate per key at each server; auto-replicate top 0.1% to all N servers. (7) At 10M req/s / 100 servers = 100k req/s per server. Redis single-threaded handles ~300k ops/s; well within budget at 1ms average hit latency.

§7

Real-World Systems

Amazon Dynamo (2007)

The paper that put consistent hashing on every engineer’s required reading list. Dynamo is Amazon’s highly available key-value store powering the shopping cart, session state, and product catalog. It uses a ring with Q/S virtual nodes per server. Dynamo’s insight: eventual consistency + consistent hashing + quorum replication gives better availability than a strongly consistent system under network partitions.

Apache Cassandra

Cassandra’s vnodes are the production-grade evolution of Dynamo’s ring. Each node gets 256 random tokens by default. The replication strategy walks the ring clockwise, placing replicas on different physical racks. Adding a node triggers token range transfers from 256 different neighbors simultaneously — scale-out is smooth and balanced without manual rebalancing operations.

Redis Cluster

Redis Cluster uses 16,384 fixed hash slots — a discrete ring. Each slot maps via CRC16(key) % 16384 and is assigned to a primary node with one or more replicas. The fixed slot count keeps client routing tables compact: a 16,384-bit bitmap per node is enough. Adding a node means migrating specific slots, which Redis Cluster handles online with MIGRATE commands.

Akamai CDN

Akamai was one of the first commercial deployments of consistent hashing — several of the algorithm’s inventors (Karger et al., MIT) co-founded the company. Content is distributed across edge nodes using ring-based assignment that minimizes cache misses when nodes join or leave. At 350k+ servers across 1,700+ PoPs, the K/N migration property is not academic — a full reshuffle at this scale would be catastrophic.

Nginx Upstream Hashing

Nginx’s hash $request_uri consistent directive uses consistent hashing (Ketama implementation) for upstream proxy load balancing. When a backend server is removed from the pool, only its fraction of traffic redistributes — preventing a cache stampede on the remaining servers that would occur with plain round-robin or modulo hashing.

§8

Follow-Up Concepts

The Chord DHT

Chord (Stoica et al., 2001) is a peer-to-peer lookup protocol built on consistent hashing. Each node maintains a finger table of O(log N) entries pointing to nodes at exponentially increasing ring distances. This gives O(log N) lookup with no central directory — queries hop from node to node, each hop halving the remaining ring distance.

Ketama

Ketama is the consistent hashing implementation popularized by the memcached community (Last.fm, 2007). It uses MD5 to generate 40 VN positions per server. The Ketama ring format is the de facto standard for consistent hashing in memcached client libraries across Ruby, Python, Go, and Java.

CAP Theorem Angle

Systems using consistent hashing (Dynamo, Cassandra) tend to favor AP (Available + Partition-tolerant) over CP. Ring-based replication means reads and writes continue even when some replicas are unreachable — at the cost of potentially stale reads. This is the tradeoff to articulate when an interviewer asks ‘Cassandra or MySQL for this use case?’ — not throughput numbers, but the consistency model.

Consistent Hashing with Bounded Loads

Google’s 2017 extension (Mirrokni et al.) adds a capacity constraint to the ring: no server holds more than (1+ε) × (K/N) keys. Incoming keys that would exceed a server’s bound are redirected to the next clockwise server under its bound. Guarantees near-perfect balance while maintaining minimal key movement on topology changes.