CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 5 of 8 · 4 min read

Uneven rings and virtual nodes

Two problems of the basic ring, and the technique that cures them.

Think of four people standing on the clock edge by chance. Three stand close together and one stands far away. The far one gets most of the parcels. It is not fair, and it would not become fairer by waiting.

The book names two problems with the basic approach, which came from Karger and others at MIT.

  1. Uneven partitions. It is impossible to keep the size of partitions equal for all servers when servers are added and removed. In its figure, when one server is removed, the neighbour's partition is twice as large as the others.
  2. Uneven key spread. Keys may not be spread evenly on the ring. With servers at certain positions, most keys can land on one server, and other servers get none.

A worked example. Servers at 10, 20, 30 and 90 on the 0 to 99 ring.

Server Position Owns Share
S0 10 91 to 99 and 0 to 10 20
S1 20 11 to 20 10
S2 30 21 to 30 10
S3 90 31 to 90 60

S3 carries 60 percent of the keys. A cache or database server holding 60 percent of the data, when 25 percent was intended, will be overloaded.

The cure is virtual nodes (also called replicas of the point). Each real server appears at many places on the ring, not one.

Virtual node

A virtual node is one of several positions on the ring that stand for a single real server. A key belongs to the real server that owns the first virtual node found clockwise.

Example: server 0 appears as s0_0, s0_1 and s0_2, at three places on the ring. Server 1 appears as s1_0, s1_1 and s1_2. To find a key's server, walk clockwise to the first virtual node, say s1_1, and use server 1.

With virtual nodes, each server is responsible for several small partitions spread around the ring. The book says the number 3 is arbitrary and real systems use many more. As the number of virtual nodes grows, the spread becomes more even, because the standard deviation gets smaller. The book reports an experiment: with 100 virtual nodes per server, the standard deviation is about 10 percent of the mean, and with 200 about 5 percent. More virtual nodes make it smaller still. The cost is the space needed to store the data about virtual nodes. This is a trade-off to tune.

A worked example of the benefit. 4 servers with 100 virtual nodes each: 400 points on the ring. The ideal load is 25 percent each. With a standard deviation of 10 percent of the mean, a server typically carries 25 ± 2.5 percent, so between about 22.5 and 27.5 percent. Compare with 60 percent in the single-point example.

A second benefit: when a server is removed, its many small territories go to many different neighbours, so no single server takes the whole load. If server 3 of 4 is removed, with its 100 virtual nodes spread around, each of the other three servers takes about a third of its data. Each rises from 25 to about 33 percent, not one of them to 50 percent.

A third benefit: heterogeneity. The book notes that the number of virtual nodes for a server can be made proportional to its capacity. A machine with twice the memory gets twice the virtual nodes. For servers with 200, 100 and 100 virtual nodes, the shares are 50, 25 and 25 percent.

Problem Single point per server Many virtual nodes
Uneven shares Likely Evened out
Removal One neighbour takes all Spread over many servers
Different machine sizes Not handled More virtual nodes for bigger machines
Cost Little metadata More metadata and lookups

Finding the affected keys when a server joins uses the same rule as before, applied to each of its virtual nodes: for each, the range runs anticlockwise to the previous virtual node.

Common mistake

Using only a few virtual nodes (say 3 to 5) and expecting an even spread. The book's numbers are for 100 to 200. With few, the spread stays uneven.

Check yourself:

  • Four servers have 150, 50, 50 and 50 virtual nodes. What share does the first carry?
  • Name two benefits of virtual nodes besides an even spread.