Implement Virtual Nodes for Uniform Distribution

Virtual Nodes

Consistent hashing alone does not guarantee uniform load. If you hash three nodes onto a 1000-position ring, you might get positions 50, 55, and 900 — leaving one node responsible for positions (55, 900], which is 84.5% of the keyspace.

The Vnode Solution

Instead of one position per physical node, assign each node V virtual positions spread around the ring. As V grows, the statistical variance shrinks:

Vnodes per node	Max load imbalance (3 nodes)
1	can be >3×
10	~1.5×
150	~1.1× (Dynamo's default)

Dynamo's Choice

Amazon Dynamo uses 150 virtual nodes per physical node. This is why when you add a new node, it takes roughly equal slices from every existing node rather than stealing all keys from one neighbor.

Implementation Detail

The only change from the basic ring is that add() inserts multiple positions, all pointing to the same physical node:

def add(self, node_id, *positions):
    for pos in positions:
        bisect.insort(self.sorted_positions, pos)
        self.ring[pos] = node_id   # physical node, not vnode

Lookup is identical — you still return the physical node, not the vnode index.