Consistent Hashing

The Server Ring guards the monster database, spread over a few servers. It used to pick a server with hash(key) mod 4. Then a fifth server joined, the rule became mod 5, and about four keys in every five suddenly belonged to a different server: nearly the whole database had to move.

So now the servers stand on a ring of positions 0 .. 2^32 - 1. Every server and every key gets a position from the same hash. A key belongs to the first server you meet walking clockwise (upwards) from the key's position: a server at exactly that position, or the next one above it. Past the top of the ring, the walk wraps around to the lowest server. A server that joins only takes the keys in the one arc just before it; a server that leaves only hands its own keys to the next server along.

Build the ring, a class ServerRing:

• ServerRing(): an empty ring.
• add_server(name) -> bool: put the server on the ring at position(name). False (changing nothing) if a server with that name is already on the ring.
• remove_server(name) -> bool: take the server off the ring. False if it isn't on the ring. A removed name may be added again later.
• server_for(key) -> str | None: the name of the server that owns key, or None if the ring is empty.

The hash is fixed (it's 32-bit FNV-1a), so every language gets the same answers. Characters count by their ASCII code ('a' = 97, '0' = 48, '-' = 45):

position(s):
    h = 2166136261
    for each character c of s, from left to right:
        h = h XOR code(c)
        h = (h * 16777619) mod 2^32
    return h

Ties. Two different names can hash to the same position. Order the servers by position, and by name (plain character order) when the positions are equal. A key at position p belongs to the first server in that order whose position is >= p; if there is none, to the first server overall. So of two servers sharing a position, the one with the smaller name gets the keys.

ring = ServerRing()
ring.add_server("ember")     # True    position  438014020
ring.add_server("iron")      # True    position 1269809787
ring.add_server("onyx")      # True    position 2591078921
ring.add_server("opal")      # True    position 3512059719
ring.add_server("iron")      # False   iron is already on the ring
ring.server_for("gob")       # "iron"  gob is at 1109104011
ring.server_for("ogre")      # "onyx"  1758641738
ring.server_for("hag")       # "ember" 3787390207 is past opal: wrap around
ring.server_for("ember")     # "ember" a key at a server's own position belongs to it
ring.add_server("amber")     # True    position 1876213440
ring.server_for("ogre")      # "amber" ogre is the only one of these keys that moved
ring.remove_server("onyx")   # True
ring.server_for("imp")       # "opal"  2481405089: onyx's keys go to the next server
ring.remove_server("onyx")   # False

• Names and keys are 1 to 20 characters from a–z, 0–9, -, : and #.
• Up to 10^5 calls, and up to 2 * 10^4 servers on the ring at once.
• server_for should cost O(length of the key + log n) for n servers. Scanning every server on each lookup is too slow for the speed test.
• In C++ use uint32_t (its multiplication wraps mod 2^32 by itself). In Java use a long and keep the low 32 bits after each step: h = ((h ^ c) * 16777619L) & 0xFFFFFFFFL.