Shard keys with consistent hashing
Your task
You are sharding keys across a cluster using a consistent-hashing ring with virtual nodes. Each physical node owns vnodes virtual points on a ring of size ring_size; a virtual point for node n at replica index r is placed at position (hash31(n + '#' + str(r))) % ring_size, where hash31 is the deterministic FNV-1a-style hash given in the reference. A key is placed at hash31(key) % ring_size and is owned by the first virtual point found scanning clockwise (increasing position, wrapping past the end). Given the initial node list, a sequence of operations (each either ['add', node] or ['remove', node]), and a list of keys to look up AFTER all operations are applied, return the owning physical node for each key in order.
Examples
ring_owners(nodes: list[str], vnodes: int, ring_size: int, ops: list[list], keys: list[str]) -> list[str]Example 1
Input
ring_owners(["A", "B", "C"], 3, 1024, [], ["user:1", "user:2", "user:3"])Output
["B", "A", "A"]