Consistent Hash Replica Set

On a consistent hash ring with virtual nodes, you must select the replica set for a key by walking the ring clockwise from the key's owner.

Given a list of tokens and a key position, return up to rf distinct NodeIDs in ring order, skipping duplicates (multiple tokens from the same node).

If there are fewer than rf unique nodes, return all unique nodes. If tokens is empty or rf <= 0, return nil.

Types

type Token struct {
    NodeID   int
    Position uint32
}

Function signature

func ReplicaSet(tokens []Token, key uint32, rf int) []int

Example

tokens = [(1,10), (1,40), (2,20), (3,30)]
key = 15, rf = 3
output = [2,3,1]

Constraints

• 0 <= len(tokens) <= 200000
• 0 <= Position <= 2^32-1
• 0 <= rf <= 10^5