Introduction
Consistent hashing provides a foundation for distributing data across a cluster of machines without requiring a full redistribution when nodes join or leave.
However, naive consistent hashing, where each physical machine maps to a single point on the hash ring, suffers from significant load imbalance.
A cluster of heterogeneous machines cannot express capacity differences, and the statistical variance of key distribution across a small number of hash positions leads to skewed loads.
Virtual nodes (vnodes) solve this problem by allowing each physical node to claim multiple positions on the hash ring.
Instead of hashing a machine's identifier once, the system generates many hash positions per physical node.
This technique was described conceptually in Karger et al. (1997) as weighted consistent hashing and was prominently operationalized by Amazon's Dynamo paper (2007); it has since become standard in systems like Apache Cassandra, Riak, and Voldemort.
The Problem with Simple Consistent Hashing
Consider a hash ring with positions in the range [0, 2^128) (used here as an illustrative range).
With N physical nodes, each node hashes to one position on the ring.
A key is assigned to the first node found by walking clockwise from the key's hash position.
In expectation, each node owns 1/N of the ring.
But the variance is high.
For N nodes placed uniformly at random on the ring, the expected size of the largest arc is O(log N / N), meaning the most loaded node holds approximately O(log N) times more than the average share of 1/N.
In small clusters this effect is pronounced: empirical simulations with 10 nodes frequently show the most loaded node handling 2–4x the average load.
This imbalance worsens with heterogeneous hardware, since a machine with 4x the RAM gets the same expected ring arc as a machine with 1x.
Additionally, when a single node fails, its entire key range transfers to exactly one successor.
That successor suddenly handles roughly twice its normal load, creating a cascading risk.
How Virtual Nodes Work
The idea is simple: each physical node is represented by V virtual nodes (tokens) on the hash ring instead of one.
A physical node with identifier node_id generates positions by hashing node_id-0, node_id-1, ..., node_id-(V-1).
Each virtual node acts as an independent point on the ring.
This has several effects:
-
Load distribution improves statistically. With V virtual nodes per physical node and N physical nodes, there are N × V points on the ring. The variance in arc sizes decreases as the number of points increases. For large V, each physical node's aggregate share of the ring converges to 1/N.
-
Heterogeneous capacity is expressible. A node with twice the capacity can be assigned twice as many virtual nodes, giving it proportionally more of the ring.
-
Failure recovery is distributed. When a physical node fails, its V virtual nodes are scattered around the ring. The key ranges formerly owned by those virtual nodes are picked up by V different successor nodes (in the best case), spreading the recovery load across the cluster rather than concentrating it on a single successor.
-
Rebalancing on membership changes is incremental. When a new node joins, its V virtual nodes each steal a small slice from V existing owners, resulting in many small data transfers rather than one large one.
Walkthrough
Assigning Virtual Nodes to the Ring
function assign_vnodes(physical_nodes, vnodes_per_node):
ring = new SortedMap() // maps hash position -> physical node
for each node in physical_nodes:
for i in 0 to vnodes_per_node - 1:
token = hash(node.id + "-" + i)
ring[token] = node
return ring
Looking Up the Responsible Node for a Key
function lookup(ring, key):
key_hash = hash(key)
// Find the first token >= key_hash (clockwise walk)
position = ring.ceiling(key_hash)
if position is null:
// Wrap around to the first token on the ring
position = ring.first()
return ring[position] // returns the physical node
Handling a Node Departure
function remove_node(ring, departing_node, vnodes_per_node):
for i in 0 to vnodes_per_node - 1:
token = hash(departing_node.id + "-" + i)
ring.remove(token)
// The keys in this arc now fall to the next clockwise
// token's owner, which is a different physical node
// for each of the V removed tokens (with high probability)
return ring
When a node with 256 virtual nodes departs from a 10-node cluster, its key ranges are absorbed by up to 256 distinct successors (in practice, spread across the other 9 physical nodes, relatively evenly).
Compare this to the non-vnode case where a single successor absorbs the entire departed node's range.
Replication with Virtual Nodes
In a replicated system like Dynamo, each key is stored on R distinct physical nodes.
The lookup walks clockwise from the key's hash position, collecting distinct physical nodes until R unique ones are found, skipping virtual nodes that belong to an already-selected physical node.
function lookup_replicas(ring, key, replica_count):
key_hash = hash(key)
replicas = new OrderedSet()
position = ring.ceiling(key_hash)
if position is null:
position = ring.first()
while replicas.size() < replica_count:
physical_node = ring[position]
if physical_node not in replicas:
replicas.add(physical_node)
position = ring.next(position)
if position is null:
position = ring.first()
return replicas
Trade-offs and Practical Considerations
Choosing the Number of Virtual Nodes
The value of V controls the trade-off between load balance and metadata overhead.
More virtual nodes produce better balance but require more memory for the ring data structure and more metadata to propagate during gossip or membership protocol exchanges.
Empirical results from the Dynamo paper and Cassandra deployments suggest that V = 256 per physical node provides a good balance for clusters of 10–100 nodes.
With N = 100 and V = 256, the ring contains 25,600 tokens.
The token-to-node mapping is small (a few hundred KB at most), so memory is rarely the bottleneck.
The concern is more about the cost of rebalancing: when a node joins or leaves, V ranges must be transferred.
Metadata and Gossip Overhead
Each node must know the full token ring to route requests correctly.
In gossip-based systems, the ring state is replicated across all nodes.
With N × V entries, the gossip payload grows linearly.
At V = 256 and N = 1000, the ring has 256,000 entries.
Each entry is a (token, node_id) pair; assuming roughly 16 bytes for a 128-bit token and 16 bytes for a node identifier, each entry is approximately 32 bytes, and putting the full ring at roughly 8 MB.
This is manageable but nontrivial for gossip convergence times.
Alternatives to Random Token Assignment
Random token placement (the approach described above) is simple but not optimal.
Cassandra moved from random tokens to a vnode-aware token allocation strategy in later versions, where tokens are assigned algorithmically to ensure even spacing, given the current cluster membership.
This reduces the number of virtual nodes needed for the same quality of balance.
Another approach is to fix the total number of virtual partitions at cluster-creation time (e.g., 4096) and assign groups of partitions to physical nodes.
This is the approach taken by Riak and described in the original Dynamo paper.
The ring is divided into a fixed number of equal-sized partitions, and ownership of partitions is reassigned as nodes join or leave.
This avoids the variability of random placement entirely but sacrifices some flexibility.
Note that Amazon DynamoDB is a distinct commercial product from the Dynamo research system, and DynamoDB's internal partitioning details are not publicly documented at this level of specificity.
Impact on Anti-Entropy and Repair
Virtual nodes complicate Merkle tree-based anti-entropy repair.
With simple partitioning, each node owns a contiguous range and can maintain a single Merkle tree per range.
With many small ranges per node (one per virtual node), either each range needs its own Merkle tree (increasing memory and computation), or the system must aggregate ranges into larger units for repair purposes.
Cassandra's experience with this trade-off led to significant engineering investment in its repair subsystem.
Key Points
- Virtual nodes map each physical machine to multiple positions on the hash ring, reducing load variance: the most loaded node goes from holding O(log N) times the average share toward the ideal 1/N.
- Heterogeneous hardware can be accommodated by assigning more virtual nodes to higher-capacity machines.
- Node failure redistributes load across many surviving nodes rather than overloading a single successor.
- Replication with virtual nodes requires walking the ring and deduplicating physical nodes to ensure replicas land on distinct machines.
- Typical deployments use 128–256 virtual nodes per physical node, balancing load uniformity against metadata size and rebalancing cost.
- Gossip protocol overhead scales with N × V, which becomes a design consideration in large clusters.
- Fixed-partition schemes (used by Riak and described in the original Dynamo paper) offer an alternative that avoids random placement variance while retaining the benefits of fine-grained partitioning.
References
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. "Dynamo: Amazon's Highly Available Key-Value Store." Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP), 2007.
Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., and Lewin, D. "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web." Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), 1997.
Lakshman, A. and Malik, P. "Cassandra: A Decentralized Structured Storage System." ACM SIGOPS Operating Systems Review, 44(2), 2010.
Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications." Proceedings of ACM SIGCOMM, 2001.