Consistent hashing ring

With cache-02 removed, 274 of 1200 keys changed owner on the hash ring, 22.8%. Plain modulo moved 930, 77.5%. The ideal is 25.0%. Load skew across the remaining servers is 1.13 times the mean.

Only the keys that belonged to the departing server should move - 25.0% of them, one server's share of 4. Plain modulo moves almost everything instead, because hash % 4 and hash % 3 disagree for nearly every key. Skew is the busiest surviving server measured against the average; drag virtual nodes down to 1 and watch it climb.

Each server's virtual nodes sit on their own band outside the ring, so identity is carried by position as well as by colour. The hatched arcs belong to the server that went down - those, and only those, are the key ranges that had to be re-homed. Every other boundary is exactly where it was.

Hashing is FNV-1a 32-bit followed by MurmurHash3's finalizer, computed in this page. The finalizer earns its place: a ring reads its position from the top bits of the hash, and FNV-1a on its own scatters those badly for short similar strings like cache-03#17 - without it the load here stayed at 19/30/18/33 even at two thousand virtual nodes each. A production ring uses a stronger hash again: MD5 in the original Ketama, xxHash in most modern clients. Keys are key-0 through key-1199, so every number here is reproducible.