Stage 1: The Basic Ring

Objective:Build the ring data structure that assigns keys to nodes with O(log N) lookup and a mathematical guarantee that only 1/N keys migrate when a node joins or leaves.

The ring is a sorted array of { position, nodeId } entries. Positions are integers in [0, 2^32). Nodes and keys both get hashed to positions; the ring is the sorted union of all node positions.

addNode(nodeId): Hash the node ID to a position in [0, 2^32). Insert { position, nodeId } into the sorted array, maintaining sort order.

removeNode(nodeId): Filter out all entries with this node ID.

getNode(key): Hash the key to a position. Find the first ring entry whose position is >= the key position (binary search). If none exists (the key falls past the last node), wrap around to ring[0]. Return that entry's nodeId, or null if the ring is empty.

The hash function provided in the starter code is deterministic but not cryptographic -- good enough for correctness testing and demonstration. In production you would use MurmurHash3 or MD5 (ketama).

Implement createRing() returning:

• addNode(nodeId) -- place the node on the ring
• removeNode(nodeId) -- remove the node and all its positions
• getNode(key) -- return the owning nodeId, or null if the ring is empty
• nodes getter -- the full sorted ring array (for inspection)

Why this matters in production

With naive `hash(key) % N`, adding one server to a 10-node cluster remaps 90% of all keys in a single operation. Every remapped key is simultaneously a cache miss, a thundering herd on the backing database, and a latency spike visible to users. Consistent hashing replaces this with a ring: nodes and keys share the same 0-to-2^32 address space. Each key belongs to the nearest clockwise node. When a node is added, it claims an arc of the ring, and only the keys in that arc migrate -- roughly 1/N. When a node is removed, its keys flow to the next clockwise node. No other nodes are affected. This is not an approximation; it is a provable bound from the geometry of the circle, and it is why DynamoDB, Cassandra, and Memcached all make the same architectural choice.