Consistent Hashing

Sometimes you need the same key to reach the same backend every time: cache routing (so each cache node owns a slice of the keyspace instead of all nodes caching everything), session affinity, database sharding. The obvious answer is:

It works — until N changes. Go from 4 backends to 5 and hash(key) % N changes for roughly 80% of keys. In a caching tier that is a catastrophe with a name: adding capacity causes a stampede, because almost every key now routes to a node that has never seen it, and the misses all land on your database at once.

Consistent hashing (Karger et al., 1997 — the idea Akamai was built on) bounds the damage. Map both backends and keys onto the same circular hash space. Each key belongs to the first backend at-or-after its position, wrapping past the top:

ring positions: ... 272:c ... 311:b ... 350:a ...
key at 300 -> owned by b   (first backend >= 300)
key at 560 -> wraps -> owned by c (first entry on the ring)

Add or remove one backend and only the keys in the arc it owned move — about K/N of the keys instead of nearly all of them.

Virtual nodes

With one point per backend, the arcs are wildly uneven — one unlucky backend can own half the circle. The fix is virtual nodes: hash each backend to many ring positions ("s1#0", "s1#1", ...). Real systems use 100–200 per backend (libketama, the classic memcached client, uses 160; Cassandra and Riak call them tokens; Envoy's RING_HASH builds the same structure). Many small arcs average out, so each backend owns close to its fair share. This exercise uses 5 vnodes so the ring stays small enough to test by hand.

The determinism trap

The exercise mandates a specific polynomial hash:

Do not substitute Python's built-in hash(). Since Python 3.3, string hashing is randomized per process (PYTHONHASHSEED) as a DoS defense — your ring would come out different on every run, and the grader runs your program in a fresh process per submission. This bites real systems too: any hash used for placement must be stable across processes, machines, and versions, which is why production rings use explicit algorithms (ketama uses MD5) rather than a language's default hash.

Walk the real ring

With POOL a b c and vnode keys a#0...a#4 etc., the mandated hash gives: c at 272–276, b at 311–315, a at 350–354. RING prints exactly those 15 hash:backend lines in sorted order. Now LOOKUP key1 (hash 498): the first vnode ≥ 498 doesn't exist (the ring tops out at 354), so it wraps to the first entry — with pool a b that means b at 311. After ADD c, the ring's first entry becomes 272:c, and the same key routes to c: a remap caused by the new backend taking over an arc, exactly the K/N behavior the structure promises.

Your exercise

Implement _rebuild() and lookup() in the starter. Rebuild: for each pool backend, insert 5 entries hashed from f"{backend}#{v}" for v in 0..4, and keep the ring sorted by (hash, backend). Lookup: hash the key with the same function, binary-search (or scan) for the first entry with hash >= key_hash, and wrap to the ring's first entry if none exists.

Grader traps:

• Forgetting the wrap: POOL s1 s2 s3 then LOOKUP user1 must print s3 — user1 hashes to 566, above every vnode, so it wraps to the lowest position (109, owned by s3). No-wrap implementations crash or print nothing here.
• Wrong vnode key format: it is name#v — a#0, not a0 or a-0. The RING test pins the exact hashes (272:c through 354:a for pool a b c).
• Using > instead of >= when searching: a key that lands exactly on a vnode belongs to that vnode.