Consistent Hashing Add Node Key Move Fraction

Problem

Measure how many keys move when a node joins a consistent hash ring.

Nodes and keys are hashed with djb2, and each key belongs to the first node whose hash is greater than or equal to the key hash, wrapping around. Compare ownership before and after adding new_node (an empty node list means every key moves).

Return the fraction of keys whose owner changed as a float, or 0.0 when there are no keys.

Hint

Only keys hashing between the new node and its counter-clockwise neighbor change owner.

Test cases

case 1

in: [["a","z"],"m",["f","g","h","z","a"]]

expected: 0.6

case 2

in: [["a","z"],"f",["b","c","m","z"]]

expected: 0.5

case 3

in: [["a"],"z",["a","z","m"]]

expected: 0.6666666666666666

case 4

in: [["a"],"b",[]]

expected: 0

Starter codePython

def key_move_fraction(nodes, new_node, keys):
    # Your code here
    pass

4 test cases · run your code against them in the editor