Weighted Ring

Real fleets are not uniform: this rack has 64 GB boxes and that one has 128 GB, and the new generation takes twice the traffic of the old. A uniform ring hands every machine the same share and lets the small ones fall over first. Your ring will give each node a weight, and you will use that weight to drain a node gradually.

One multiplication

Give each node points in proportion to its weight. This course uses 128 points per unit of weight, with the same labels as before, name#0, name#1, and so on. A node of weight 2 places name#0 to name#255. Twice the points means twice the expected share of the keyspace, and nothing else about lookup changes.

weight 1:  small#0 .. small#127     (128 points)
weight 2:  medium#0 .. medium#255   (256 points)
weight 4:  large#0 .. large#511     (512 points)

libketama does exactly this: each memcached server's point count is scaled by its share of the configured memory. Cassandra expresses the same idea as num_tokens.

Weights are expectations, not contracts

We placed small, medium and large (weights 1, 2, 4) and routed 70,000 keys. The ideal split is one seventh, two sevenths and four sevenths. The measured error of the worst node, as the points per unit of weight grow:

points per unit :     4     16     64    128    512
worst node off  :  57%    36%    13%    13%   1.5%

The error shrinks as points grow, but it is a random draw, not a smooth curve: 64 and 128 happened to land at the same error. Weighting tracks the configured ratio only with enough points and a hash that mixes.

Changing a weight, and draining

Because labels are name#0 upward, lowering a weight just removes the highest-numbered points. Points #0 to #127 stay exactly where they were, so only the keys that lived on the released points move, and they move to the other nodes. Raising the weight again re-creates the same positions. The ring after "weight 2, then 4, then back to 2" is identical to the ring that was built with weight 2 in the first place.

That makes a gradual decommission possible. Step a node from weight 4 to 3 to 2 to 1 to 0 over hours and each step drains a slice of its arcs instead of remapping everything in one spike. With 7,000 keys, draining large (the node above) moved 548, then 654, then 918, then 1,774 keys. Every moved key came from large, and the four steps add up to the 3,894 keys it owned at the start. A weight-0 node stays registered but has no points, so it owns nothing. The reverse, warming a new node in with a small weight, is the same trick.

Common mistakes

• A missing weight. ADD_NODE A with no weight means weight 1. Indexing the third token without checking for it crashes, and a default of 0 gives the node no points at all.
• Different labels after a change. If SETWEIGHT numbers the points differently from ADD_NODE, raising and lowering a weight scrambles the ring and moves far more keys than it should. Re-place the node with the same name#i labels.
• Dropping zero-weight nodes. A drained node is still a node: LOAD prints B: 0, WEIGHTS prints B: 0, and a ring where every weight is 0 answers NONE to lookups.
• Drain steps that move too much. In DRAIN, each step may only move keys that the draining node owned.

Your exercise

The ring and LOAD are in the starter. You write weighted adding, changing a weight, listing weights and the gradual drain.