The hash ring works, but it comes with machinery: a sorted array of points, virtual nodes to even out the arcs, a knob for how many, and care to skip duplicate servers when choosing replicas. There is an older idea, from 1996, that solves the same problem with almost no machinery at all. It's called rendezvous hashing, or highest random weight (HRW) hashing.
The whole algorithm fits in one sentence: for each key, let every server roll a die that depends on the key and the server, and give the key to whoever rolled highest.
The problem, again
You have a set of servers and a stream of keys. You want:
- every client to map a key to the same server, without talking to each other,
- keys spread evenly,
- adding or removing a server to move as few keys as possible.
Tiffin's example: the image service resizes restaurant photos and keeps the results on local SSD. Requests for photo:8812 should keep hitting the same image server, so its cached sizes get reused. The fleet changes size during the day.