CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 4 of 8 · 2 min read

Adding and removing a server

Which keys move, found by looking back along the ring.

Think of the four people on the clock edge again. A fifth person joins and stands between two of them. Only the parcels that lie between the new person and the person just before them (anticlockwise) change hands. Parcels elsewhere stay where they are.

The book's rule for adding a server: the affected range starts at the new server and runs anticlockwise until the next server. Keys in that range move to the new server. For removing a server: the affected range starts at the removed server and runs anticlockwise to the previous server. Those keys move to the next server clockwise.

A worked example with the ring above (S0 at 10, S1 at 35, S2 at 60, S3 at 85). Add S4 at position 45.

  • S4 sits between S1 (35) and S2 (60). Its affected range is 36 to 45, from S4 back to S1.
  • Keys at 36 to 45 used to belong to S2. They now belong to S4.
  • Key k2 at position 50 stays with S2. Keys k0, k1, k3, k4 do not move.
  • The share moved: 10 positions of 100, 10 percent.

Now remove S1 (position 35) from the original ring.

  • The affected range runs from 35 back to S0 (10): positions 11 to 35.
  • Those keys, including k1 at 20, move to the next server clockwise, S2 (60).
  • All other keys stay. Share moved: 25 percent, which was exactly the data S1 held. Nothing else is touched.

Compare with hash mod N from section 1: removal of one of four servers moved 75 percent of the keys. The ring moved 25 percent, the minimum.

For a real ring of many servers, adding the n-th server moves about 1 ÷ n of the keys, and they all come to the new server from its neighbour (with one position per server). A removal pushes the whole load of the removed server to a single neighbour, which can overload it. The next section fixes that.

Event Keys affected Where they go
Add server Those between the new server and its anticlockwise neighbour The new server
Remove server Those the removed server held Its clockwise neighbour

Check yourself:

  • On the ring above, a server is added at position 70. Which keys move, and from whom?
  • Why can removal overload one neighbour?