A cache ring places 20 physical nodes once each on a consistent hash ring. Compute the expected fraction of keys that move when a 21st node joins, explain why the load is still badly balanced, and…

Question

A cache ring places 20 physical nodes once each on a consistent hash ring. Compute the expected fraction of keys that move when a 21st node joins, explain why the load is still badly balanced, and compute the imbalance with 200 virtual nodes per physical node.

Accepted Answer

1/21. Under consistent hashing every key belongs to the first node clockwise, and a joining node takes exactly the keys in the arc between itself and its predecessor, which by symmetry is 1/21 of the ring in expectation, so about 4.8 percent of keys move and only one existing node gives any up. A modulo N hash would have moved 20/21 of them. Load imbalance is a separate question and is severe with one point per node, because the 20 points fall at random and the arcs between them are exponentially distributed with a coefficient of variation of 1, so a node's share has a standard deviation as large as its mean and the largest node typically holds several times the smallest. Virtual nodes fix this by giving each physical node many points, so its load is a sum of v independent arcs and the coefficient of variation falls as 1 / sqrt(v). With 200 virtual nodes per physical node that is 1 / sqrt(200), about 0.071 or 7 percent, which is usually acceptable. The cost is a ring holding 4,000 points, so the routing table and the time to rebuild the ring both grow with v, while the moved fraction stays 1/21 because it depends only on the physical count.