# Consistent Hashing Ring with Virtual Nodes for Shard Rebalancing A distributed key-value store spreads its keys across a set of **shards**. When a shard is added or removed, you want to remap as few keys as possible — naive modulo hashing (`hash(key) % N`) reshuffles almost everything whenever `N` changes. Implement a **consistent hashing ring with virtual nodes**, which bounds the fraction of keys that move when the shard set changes and keeps the load spread evenly. Implement a class `ShardRing` that maintains a hash ring on the integer interval `[0, 2^32)` (positions wrap around: the successor of `2^32 - 1` is `0`). ## Hashing All positions on the ring are produced by the **32-bit FNV-1a** hash of a UTF-8 string. Compute `fnv1a_32(s)` as: ``` hash = 2166136261 # 0x811c9dc5 for each byte b in the UTF-8 encoding of s: hash = hash XOR b hash = (hash * 16777619) mod 2^32 # 16777619 = 0x01000193 return hash # a 32-bit unsigned integer ``` Each shard with id `shard_id` places `vnodes` **virtual nodes** on the ring. The position of virtual node `i` (for `i` in `0 .. vnodes-1`) is: ``` fnv1a_32(shard_id + "#" + str(i)) ``` ## Methods to implement - `__init__(self, vnodes: int)` — create an empty ring. Every shard added later contributes exactly `vnodes` virtual nodes. `1 <= vnodes <= 1000`. - `add_shard(self, shard_id: str) -> None` — add a shard and its `vnodes` virtual nodes. The same `shard_id` is never added twice without first being removed. - `remove_shard(self, shard_id: str) -> None` — remove a shard and all of its virtual nodes. The `shard_id` is guaranteed to be currently present. - `get_shard(self, key: str) -> str` — return the id of the shard that owns `key`. Ownership is the **first virtual node found clockwise** (in increasing position order) starting at `fnv1a_32(key)`; if `fnv1a_32(key)` is greater than every virtual-node position, wrap around to the smallest position on the ring. If the ring currently has no shards, return the empty string `""`. ## Tie-breaking If two or more virtual nodes (from different shards, or different replicas) hash to the **same** ring position, order them at that position by `shard_id` ascending, then by replica index `i` ascending. `get_shard` returns the first such virtual node encountered clockwise under this ordering. ## Requirements - `get_shard` must run in `O(log V)` time, where `V` is the current number of virtual nodes on the ring (binary search over sorted positions). `add_shard` / `remove_shard` may be `O(vnodes * log V)`. - The minimal-movement property must hold structurally: because keys are routed to the nearest clockwise virtual node, removing a shard reassigns only that shard's keys (to their next clockwise shards), and adding a shard only pulls keys off the segments its virtual nodes land on — no other key changes owner. ## Example Suppose `vnodes = 100` and you `add_shard("A")`, then `add_shard("B")`. A key routes to whichever of A's or B's 100 virtual nodes is nearest clockwise from the key's hash, so the keys split between A and B roughly in proportion to how the 200 virtual nodes interleave around the ring (close to 50/50 for well-spread hashes). Now `add_shard("C")`: only the keys whose hashes fall just before one of C's 100 new virtual-node positions move to C; every other key keeps its previous owner. If you then `remove_shard("B")`, only keys that were owned by B's virtual nodes move — each to the next virtual node clockwise (an A or C node) — while keys already on A or C are untouched. ## Constraints - Up to `10^5` total operations across `add_shard`, `remove_shard`, and `get_shard`. - `vnodes` is fixed for the lifetime of a `ShardRing` instance. - `shard_id` and `key` are non-empty ASCII strings up to 64 characters. - All arithmetic on hashes is over unsigned 32-bit integers (`mod 2^32`).