Consistent Hash Lookup

A consistent hash ring stores tokens with node ownership. A key is assigned to the first token clockwise whose position is >= key. If none, wrap to the smallest token position.

You are given a list of tokens and a key position. Return the owning node ID.

If multiple tokens share the same position, choose the smallest NodeID. If there are no tokens, return -1.

Types

type Token struct {
    NodeID   int
    Position uint32
}

Function signature

func ConsistentHashLookup(tokens []Token, key uint32) int

Example

tokens = [(1,10), (2,20), (3,30)]
key = 25
output = 3

Constraints

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