28.5 What are virtual nodes?

At the table: If each host has one seat, the gaps between hosts are random: one host might cover half the table. So each host sits in many seats, scattered all around. Now each host covers many small stretches that add up to about the same total. And when a host leaves, their guests spread across many other hosts instead of all landing on one neighbour.

In the system: Place each server at many points on the ring by hashing "cache-1#0", "cache-1#1" ... "cache-1#99". These are virtual nodes (vnodes).

Figure: many small arcs average out; one big arc is a lottery.

Benefits:

• Even load. In the chapter's code, with 4 servers and 1 point each, the busiest server gets 1.95× its fair share of keys; with 100 points each, 1.16×. More points make it even smoother.
• Even spreading on failure. A removed server's keys scatter across all remaining servers, not one neighbour.
• Weighted servers. A server with twice the memory gets twice as many vnodes and so about twice the keys.

Costs: a bigger sorted list (servers × vnodes points) and slightly more work when membership changes. With tens of servers and a few hundred vnodes each, that's still tiny.

Dynamo used virtual nodes on its ring, and Cassandra assigns each node multiple tokens for the same reason.

Memory code: "Give every host many seats, and the work evens out."

---