Consistent Hashing

Sometimes the same key has to reach the same backend every time: cache routing, so each cache node owns a slice of the keyspace instead of every node caching everything; session affinity; database shards. The obvious answer is a modulo: backends[hash(key) mod N]. It works until N changes. Go from 4 backends to 5 and the result moves for about 80% of all keys. In a cache tier that is a stampede with a name: adding capacity makes almost every lookup miss at once, and all the misses land on your database together.

Consistent hashing (Karger et al., 1997, the idea Akamai was built on) bounds the damage. After this lesson your balancer will place backends on a ring and, when the pool changes, move only about K/N of the keys instead of nearly all of them.

The ring

Hash both the backends and the keys onto the same circle of 32-bit numbers. A key belongs to the first backend point at or after its position, going clockwise and wrapping past the top.

ring (positions 0 .. 2^32 - 1, shown as a line that wraps)

   100:b      400:a      700:c      900:b
----|----------|----------|----------|----->  wraps back to 100:b

key at 350  -> next point at or after 350 is 400:a     -> a
key at 700  -> a point exactly at 700 counts           -> c
key at 950  -> nothing above 950, wrap to the first    -> b (100)

Add or remove one backend and only the keys in the arcs it owns move. Everything else keeps its owner. That is the property to test, and the SNAP and MOVED commands let you watch it happen.

Virtual nodes

With one point per backend the arcs are wildly uneven and one unlucky backend can own half the circle. The fix is virtual nodes: hash each backend to many positions by hashing the strings name#0, name#1, and so on. Production rings use 100 to 200 per backend (libketama, the memcached client, uses 160; Cassandra calls them tokens; Envoy's ring-hash policy builds the same thing). Many small arcs average out. This exercise uses 16 per backend so the RING listing stays readable.

A hash that is the same everywhere

Placement hashes must be stable across processes, machines and languages. Do not use your language's built-in string hash: Python randomises it per process, and every runtime does it differently anyway. This exercise fixes MurmurHash3, 32-bit (x86 variant), seed 0, over the UTF-8 bytes of the string; Cassandra's default partitioner uses it. It mixes well: neighbouring inputs such as a#0 and a#1 land far apart. A simple hash like FNV-1a does not. Its outputs for such names form a near-arithmetic progression, so a backend's virtual nodes bunch into one stretch of the circle.

The hash is not the mechanism under study, so the starter gives you the function. The published test vectors are: the empty string hashes to 0, test to 3127628307 and Hello, world! to 3224780355. The HASH command prints the value, so you can check any port of your own. All hash values are unsigned 32-bit numbers; compare and sort them as unsigned.

The old way, for comparison

SNAP n records who owns the keys key0 to key<n-1> right now, both under the ring and under pool[hash(key) mod N] using the pool in the order listed. After you ADD or REMOVE, MOVED prints how many of those keys changed owner under each scheme: ring=<x> mod=<y>. Expect the ring near 1/N and the modulo near (N-1)/N.

Common mistakes

• No wrap. A key above the highest point belongs to the lowest point.
• > instead of >=. A key exactly on a point belongs to that point.
• The vnode key format. It is the name, a #, and the decimal index: a#0, never a0 or a-0.
• Signed comparisons. Hash values are unsigned. If you store them in a signed type, the high half of the circle sorts before the low half and every lookup is wrong.
• Unstable order for ties. If two points share a position, sort them by hash first and backend name second, so every language agrees.

Your exercise

The starter parses the commands, provides the hash, and handles DIST, SNAP and MOVED. You write the two pieces they rest on: the ring construction and the lookup. POOL, ADD and REMOVE (names, space-separated; unknown or repeated names are ignored) print OK and rebuild the ring. LOOKUP <key> prints the owner, or EMPTY when the pool is empty. RING prints every point as <hash>:<backend> in ring order.