The stability benefit of consistent hashing appears when cluster membership changes. Removing one node does not recalculate every key against a new node count. It removes one position from the ring, so only the keys owned by that position need a new owner.
Design a ConsistentHashMovementAnalyzer class:
ConsistentHashMovementAnalyzer() creates a stateless analyzer.String[] keysReassigned(String[] nodes, String[] keys, String removed) returns the input keys whose owner changes after removed leaves the ring.
Use this unsigned 32-bit polynomial hash for nodes and keys:
Sort ring entries by (hash, nodeName) in ascending order. A key belongs to the first node whose hash is greater than or equal to the key's hash, wrapping to the first entry when necessary.
Return reassigned keys in their original input order. If the same moved key appears more than once, include every occurrence. The removed node is always present, and at least one node remains after removal.
Example 1:
Input:
Output:
Explanation: Only user:10 is owned by sa-east on the original ring. When sa-east leaves, that key moves to the next clockwise node; the other keys retain their owners.
Example 2:
Input:
Output:
Explanation: doc:100 is the only supplied key owned by eu-west, so it is the only key whose owner changes.
Constraints
2 <= nodes.length <= 1000 <= keys.length <= 200- Node names are unique, and
removed is one of them. - Every node name and key contains
1 to 40 printable ASCII characters. - Use the specified unsigned 32-bit polynomial hash; do not use a built-in hash function.
- If node hashes collide, sort the colliding nodes by name in ascending ASCII order.
- Preserve key order and duplicate occurrences in the returned array.
- At most
100 calls are made to keysReassigned.
Find Keys Reassigned After Node Removalmedium