Plain hash(key) % num_nodes sharding has a brutal failure mode: add or remove ONE node, and num_nodes changes, which means almost every key's % num_nodes result changes too -- nearly your whole dataset has to move. Consistent hashing fixes this by hashing both nodes AND keys onto the same ring (a circular numeric space): a key belongs to the nearest node clockwise from its position. Add or remove one node, and only the keys that were between it and its neighbor move -- everything else stays put.

The node-hashing and ring bookkeeping structure is given (use the provided _hash helper -- not Python's built-in hash(), which is randomized per process and would make every test run non-reproducible). Implement:

• add_node(node) -- add a node to the ring at all self._vnodes virtual positions (no-op for any position already present)
• remove_node(node) -- remove a node from all self._vnodes positions (no-op for any position not present)
• get_node(key) -- return the physical node key maps to: the first ring position at or after key's hash, wrapping around to the smallest position if none is found going forward. Return None if the ring has no nodes.

The missing link: one ring position per node isn't good enough

With exactly one position per physical node, load balance is entirely down to luck -- three nodes hashed onto a ring could easily end up bunched close together, so one of them "owns" a tiny sliver of the ring and the other two split the rest unevenly. Virtual nodes fix this: instead of hashing node once, hash f"{node}#0", f"{node}#1", ..., f"{node}#{vnodes-1}" -- many independent, differently-positioned stand-ins for the same physical node, all of which resolve back to that one node in get_node. With enough virtual positions per node, the law of large numbers takes over and each physical node ends up with close to its fair share of the ring, no matter how the individual hashes happen to fall.

Example

ring = ConsistentHashRing(vnodes=3)
ring.add_node("a")             # 3 ring positions, all resolving to "a"
ring.get_node("some-key")      # -> "a" (only node present)

Constraints

• The defining property, and what the tests actually check: removing one node must only remap the keys that node owned. Every other key must map to exactly the same node it did before.
• add_node/remove_node must add/remove ALL self._vnodes positions for a node, not just one -- a partially removed node would leave orphaned ring entries that still resolve to a node that's supposedly gone.
• Default vnodes=1 must behave exactly like the single-position version (this is what makes it backwards compatible with a ring that doesn't care about virtual nodes at all).

Real-world grounding

Consistent hashing with virtual nodes shows up throughout distributed systems: Cassandra and DynamoDB use it for partitioning (both configure roughly 100-256 virtual nodes per physical node by default), memcached client libraries use it for shard selection, and it's the same idea Kubernetes' EndpointSlice load balancing and consistent-hash-based service routing (e.g. in Envoy/Istio) build on.

• Cassandra's virtual-node token assignment: num_tokens in cassandra.yaml
• DynamoDB's original paper, Section 4.2 ("Partitioning Algorithm"), which introduces exactly this virtual-node refinement over plain consistent hashing: Dynamo: Amazon's Highly Available Key-value Store (DeCandia et al., 2007)