Consistent Hashing

Track: Data consistency. 6 stages. Languages: Go, Python, JavaScript, Rust.

A service with several servers needs a rule for which server owns each key. The simple rule, hash(key) % numberOfServers, breaks badly the moment a server joins or leaves: changing the count changes almost every key's owner at once, and your servers have to move almost everything they hold. Consistent hashing fixes this. Build the piece that picks a server for each key, so that adding or removing one server only moves a small share of the keys, never almost all of them.

Picture a circle of numbers, starting at 0 and going up to a very large number, then wrapping back to 0. Each server gets several points on this circle, not just one, so its share of the circle is made of many small pieces spread around, instead of one big piece in one place. A key also lands on a point on the same circle. The key belongs to the server whose point is the first one you reach walking clockwise from the key's point. If you walk past the last point without finding one, wrap around to the first point on the circle.

                   12
               A's point
            .            .
         9                  3
    key's point       C's point
            .            .
               B's point
                   6

Walking clockwise from the key's point at 9 o'clock, the first point you reach is A's point at 12 o'clock. The key belongs to server A.

If a key's point is past every server's point, it wraps around to the lowest point on the circle instead of stopping.

Both a server's points and a key's point come from the same hash, so this challenge pins it exactly: every language must compute the same numbers. Hash the text with FNV-1a 64 first, then run its result through one more mixing step. Every number below wraps around using unsigned 64-bit arithmetic, meaning a number that would grow past the top wraps back around instead of growing bigger.

Step 1, FNV-1a 64. Start with h = 14695981039346656037. For every byte of the text, in order: combine that byte into h with XOR, then multiply h by 1099511628211, keeping only the lowest 64 bits. Check your work: hashing the single letter "a" this way gives h = 12638187200555641996.

Step 2, the extra mixing step. Take z = h from step 1, then:

z = (z XOR (z shifted right 30 bits)) * 13787848793156543929
z = (z XOR (z shifted right 27 bits)) * 10723151780598845931
z = z XOR (z shifted right 31 bits)

z is now the final hash. Check your work: "a" ends up as z = 198367012849983736.

Place each server's points at the hash of "<server name>#<point number>", for point numbers 0, 1, 2, ... up to however many points per server the stage asks for. Hash a key at the hash of the key's own text. Break an exact tie between two points at the same number by the lower server name.

Example, with one point per server (to keep the numbers small) for three servers n1, n2, n3:

Sorted around the circle, smallest to largest: n2, then n3, then n1, then it wraps back to n2.

Implement New(virtualNodes) to build an empty circle with that many points per server, Add(node) to add a server, Remove(node) to take one away, and Locate(key) -> node to find the key's owner.

For help with the ideas, read the notes.

Where it is used

• Amazon's Dynamo, a storage system that spreads data over many machines, uses consistent hashing with several points per server to decide which machines store each key.
• Cassandra places its nodes on a ring of numbers in the same way. When a node joins, it takes a fair share of data from the others, instead of forcing almost every row to move.
• The Envoy proxy can pick a backend server this way ("ring hash"), so the same user keeps reaching the same server. Removing one of N servers only moves about 1 in N users.

Stages

ch1: one server, every key goes to it (very easy)

A single server (with 64 points) and 200 different keys. Every key must resolve to that one server, since there is nothing else for it to resolve to.

The tester will verify: all 200 located keys return the only server.

ch2: spread keys evenly across several servers (easy)

8 servers, 128 points each, and 4,000 keys. A perfectly even split would give each server 1 in 8 of the keys, or 12.5%. The tester allows the busiest server up to 27%, which is generous: a correct circle measures about 13.6% here, but giving each server only one point instead of many measures about 35.6% and fails by a wide margin.

The tester will verify: over the 4,000 keys, the busiest server owns at most 27% of them.

ch3: the same answer every time, in any order you added servers (medium)

Same 8 servers and 4,000 keys, 128 points each. Locate must always give the same answer for the same set of servers: calling it twice in a row gives the same results both times, and it does not matter whether the servers were added in list order or in reverse order, every key still lands on the same server either way. Anything that depends on the order a map happens to iterate in will fail here.

The tester will verify: repeating the same run gives identical answers for all 4,000 keys, and adding the same 8 servers in reverse order resolves every key the same way.

ch4: adding a server moves only a small share of keys (medium)

The whole point of this challenge. Start from the same 8 servers and 4,000 keys, locate every key, add a 9th server, then locate all 4,000 keys again. A fair share for the new server is 1 in 9, about 11.1%, and the tester allows up to 28% of keys to move. A correct circle moves about 1 in 9 of the keys. Using hash(key) % numberOfServers instead remaps about 8 in 9 of them and fails by a wide margin. Every key that does move must move to the new server, never to another existing one.

The tester will verify: adding the 9th server moves at most 28% of the 4,000 keys, and every moved key now maps to the newly added server.

ch5: removing a server moves only its own keys, even under heavy change (hard)

The other direction. From the same 8 servers, 128 points, and 4,000 keys, remove the server named node3 and locate everything again. The tester allows up to 28% of keys to move (a fair share for 1 of 8 servers is 12.5%), and every key that moves must have belonged to node3, never to one of the others. Then, separately, a long run of 600 mixed actions over a pool of 12 servers and 2,000 possible keys (about 60% locate, 20% add, 20% remove, in a fixed order) is checked against our own solution, one answer at a time.

The tester will verify: removing node3 moves at most 28% of keys, and only its own former keys. The 600-action run matches our solution exactly, with no differences at all.

ch6: make locating a key fast (hard)

Your circle is timed against our solution in the same language you wrote it in, using a circle of 16 servers (64 points each) and a space of 4,096 possible keys. The tester runs 50,000 scored calls to Locate (after 5,000 warm-up calls that are not scored) and takes the middle result of 7 runs. If our solution takes 100 ms for its share of the calls, your limit is 150 ms, which is 1.5 times as long. Your solution must also make no more than 2 times as many memory allocations as our solution. Keeping the points sorted and finding a key's owner with a fast search, rather than checking every point one by one, is what gets you here. Every answer must still be correct, not just fast.

The tester will verify: your circle takes at most 1.5 times as long and makes at most 2 times as many memory allocations as our solution, with every answer still correct.

Rules

• Standard library only. No third-party packages. Write the hash yourself, exactly as specified above.
• The same set of servers must always give the same answer for the same key. No randomness, and nothing that depends on map iteration order.
• Print nothing you don't have to. The last line your program prints belongs to the tester.

Read the Consistent Hashing notes in the wiki