Changing the Shards on the Ring

Let’s see what happens when we add a shard to the ring or remove one from it.

Adding a shard

Suppose we add the fourth shard, D, again. This time we put it on the ring. Its name hashes to 40, so D goes between A at 20 and B at 55.

Before we added D, the codes from 21 to 55 were on B. Now, moving clockwise from a code between 21 and 40, the first shard we reach is D. So D takes over the codes from 21 to 40. B keeps the codes from 41 to 55.

Of our five links, only Qz81fWc, at 30, is between 21 and 40. It moves from B to D:

When we added D with hash(code) mod N, four of the five links moved. With consistent hashing, only one link moved.

Removing a shard

Suppose we remove B. Before we removed B, the codes from 41 to 55 were on B. Now, moving clockwise from a code between 41 and 55, the first shard we reach is C at 85.

So C takes over B’s codes. The codes on A and D stay where they are. Of our five links, only b3Rt9Lm, at 52, is between 41 and 55. It moves from B to C.

Why this works

This works because of how we chose the shards’ positions. Each shard’s position comes from hashing its name, so it does not depend on the number of shards. When we add D, the shards A, B, and C stay where they were. Suppose instead we spaced the shards evenly. With three shards, A would be at 0, B at 33, and C at 66. With four shards, A would be at 0, B at 25, C at 50, and D at 75. Each position would then depend on the number of shards. Adding D would move B and C, and three of our five links would move. That is the same problem we had with mod N.