Question 1474

One Node Joins

A hash ring covers positions 0 to 1023. A key is owned by the first node clockwise at or after the key's position, wrapping past 1023 back to 0.

A 1024 slot ring; clockwise from position 0 at the top 0 A 100 B 380 C 610 D 900 E 720

Ten keys hash to these positions:

key k1 k2 k3 k4 k5 k6 k7 k8 k9 k10
position 45 150 299 402 555 640 705 880 915 1000

Node E joins at position 720. Which keys change owner?

A

k1, k9 and k10, because inserting a node shifts every wraparound key onto the new position

B

k6 and k7, both moving from D to E; the other eight keys are untouched

C

k6, k7 and k8, all moving from D to E, since E now owns the whole arc from C up to D

D

One key in ten on average, drawn from all four existing nodes, because a join rebalances the ring as a whole