Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 37 ยท Distributed Caching

Virtual Nodes and Load Balance

Measure how unevenly a one-point-per-server hash ring spreads keys, then fix it with virtual nodes and weights for servers of different sizes. Runnable Python.

A hash ring with one point per server is correct but lumpy. Hash functions place points at random, and random points on a circle make arcs of very different lengths. One unlucky server can own three times the keys of another, run out of memory first and start evicting useful data while its neighbours sit half empty.

The cure is to give every physical server many points on the ring, called virtual nodes (or "vnodes", or "points"). The more points, the closer each server's share gets to the ideal. In this lesson you will measure the imbalance, then see how vnode count and server weights change it. All code is Python stand-in logic; real client libraries such as ketama-style clients do the same thing internally.

Measuring imbalance

A useful number is the max-to-average ratio: the load of the busiest server divided by the average load. A perfect cluster scores 1.0. A score of 1.5 means the busiest server holds 50% more keys than it should.

Python One point per server is uneven

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Expect the busiest server to be well above the average with one point and to settle near 1.0 as the number of points grows. The improvement follows a square-root law: halving the imbalance needs roughly four times as many points.

How many virtual nodes are enough?

There is a trade-off:

  • More points give a flatter distribution and a smoother redistribution when a server leaves, because its keys are scattered across all remaining servers instead of dumped on a single neighbour.
  • More points also mean a bigger sorted array to build and search. Building 8 servers x 160 points is only 1,280 entries, which is trivial; a million-point ring would still find a key in about 20 comparisons.

Many Memcached clients use around 100 to 200 points per server. That is a sensible default, and you rarely need to tune it.

Vnodes also soften failures

With one point per server, when a node dies its entire arc moves to a single neighbour, which suddenly receives double the traffic and might fall over too. With many vnodes, the dead node's keys are spread thinly over every survivor, so each takes on a small extra load. Run the next example to see it.

Python Who inherits a failed server's keys?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With one point, the keys go to a single successor. With 150 points they are spread over all five survivors, each taking a share.

Weights for servers of different sizes

Not every server has the same RAM. A common technique is weighting: give a server vnodes in proportion to its memory. A 16 GB node gets twice the points of an 8 GB node and therefore about twice the keys. Weighted points are the same idea you used above, only the loop count per node changes.

Python
weights = {"small": 1, "large": 2}
points_per_unit = 100
for name, w in weights.items():
    for i in range(w * points_per_unit):
        ...  # insert point h(f"{name}#{i}")

Keep in mind that key count is not the same as load. If a few keys are extremely popular (a "hot key"), the server holding them is overloaded no matter how flat the ring is. That problem, and what to do about it, is the subject of Hot Keys and Replication.

When you change a server's weight, you are changing the ring just like adding or removing a node. Expect a proportional slice of keys to move. Do it during low traffic and watch the database.

Deterministic naming matters

Point positions come from strings such as cache3#42. If one client formats it as cache3:11211-42 and another as cache3#42, their rings differ. This is the most common cause of "my cache works from PHP but not from Python" in mixed-language setups. Use the same library, version and settings everywhere, or test that two clients return the same server for a sample of keys.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a virtual node?

    Virtual nodes are extra ring positions for the same physical server. They smooth out the key distribution.
  2. 2. What does a max-to-average ratio of 1.0 mean?

    The ratio compares the busiest server's load with the mean. 1.0 is the ideal; higher means more skew.
  3. 3. Why do virtual nodes reduce the damage of a node failure?

    Each survivor takes a small slice, so no single server suddenly doubles its load.
  4. 4. How would you give a server with twice the RAM twice the share of keys?

    Weighting by vnode count makes the arc total, and therefore the key share, proportional to the weight.

Summary

  • One point per server leaves some servers with far more keys than others.
  • Virtual nodes (often 100 to 200 per server) flatten the distribution.
  • Many vnodes also spread a failed node's keys across all survivors.
  • Weight servers by giving bigger machines proportionally more vnodes.
  • A flat ring balances key count, not request load; hot keys need separate treatment.

Next: Client-Side Sharding and Pools