What you are looking at
The circle is the hash ring: every value a 32-bit hash can take, laid out clockwise from 0 at the top and back round to 0. Each server is hashed onto the ring several times (the coloured ticks, its virtual nodes), and each key is hashed onto it once (the dots). A key belongs to the first server tick clockwise from it, and takes that server's colour.
Finding a key's server means hashing the key and looking up the next tick. With the ticks kept sorted that is a binary search, so a lookup costs O(log n) in the number of ticks.
Why plain hash % N falls apart
The obvious way to spread keys over N servers is to send each to server number hash(key) % N. It spreads them evenly, but N is in the formula. Go from 4 servers to 5 and a key stays put only if its hash leaves the same remainder divided by 4 as by 5, which is true for one key in five. The other 80% move. The lab shows the same: add a server and compare the two numbers.
For a cache, every key that moves is a miss. The cluster forgets most of what it knew in one go, and the load falls on the database at the moment you were adding capacity because of load. For a sharded store it means copying most of the data. On the ring, a new server takes over only the stretch of ring just before each of its ticks, and nothing else changes owner.
Virtual nodes
With one tick per server (move the slider to 1), the gaps between ticks are uneven, so some servers own far more of the ring than others. Look at the bars. Many ticks per server average the gaps out, and by 64 the bars sit close to the fair-share line.
- They spread a departure. When a server leaves, each of its stretches passes to the next tick clockwise. With one tick, a single neighbour inherits everything; with many, the keys spread over every server that is left.
- They give you weights for free. A machine with twice the memory gets twice the virtual nodes, and takes about twice the keys.
In an interview
It comes up whenever data or traffic is split by key: a distributed cache, a sharded database, a URL shortener's storage, routing chat users to connection servers. A strong answer covers four things:
- the problem with
hash % N: most keys move whenNchanges; - the ring and the clockwise rule;
- virtual nodes, for balance and for spreading a departure;
- failure: a dead server's keys move to the next one clockwise, and with replication each key is also stored on the next few distinct servers round the ring, so one of them already has a copy.
Expect follow-ups on hot keys (the ring balances the number of keys, not the traffic, so one very popular key still lands on one server: put a cache in front of it or split it), on where the ring lives (every client keeps a copy, kept current by a membership service or a gossip protocol), and on alternatives such as rendezvous hashing and jump consistent hashing. Amazon's Dynamo paper (2007) made the ring with virtual nodes well known; Cassandra and the ketama library for memcached clients use the same idea.
The code
This is the lab's own ring. hash32 is any well-mixed 32-bit hash; the lab uses FNV-1a with MurmurHash3's final mixing step.
type Point = { at: number; server: string }; // Each server goes on the ring once per virtual node.function buildRing(servers: string[], vnodes: number): Point[] { const ring: Point[] = []; for (const server of servers) for (let v = 0; v < vnodes; v++) ring.push({ at: hash32(`${server}#${v}`), server }); return ring.sort((a, b) => a.at - b.at);} // A key belongs to the first point clockwise from its hash.function ownerOf(ring: Point[], key: string): string { const at = hash32(key); let lo = 0, hi = ring.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (ring[mid].at < at) lo = mid + 1; else hi = mid; } return ring[lo % ring.length].server;}