Adding servers without moving all the data (consistent hashing)

Data grows, so the number of servers that hold it changes. In lesson 43 you saw that a plain hash mod moves most of the data when you add one server. Interviewers ask: "How do you add a server without moving most of the data?" The question is common in designs for key-value stores. It is also common for groups of cache servers.

A weak answer says "we take the hash mod the number of servers" and does not see the cost. Another weak answer says "consistent hashing" and cannot explain it. A strong answer draws a circle, places the servers and the keys on it, and says which keys move when a server joins. It also says why one point per server leaves the load uneven, and how to fix that.

At SDE-1 level you should explain why hash mod moves so much. At SDE-2 level you should explain the circle and what moves. At SDE-3 level you should also choose how many positions each server gets, and say what the method does not fix.

Picture a round road with markers from 0 to 99. After marker 99 the road comes back to 0. Petrol pumps stand at some markers. Every town also has a marker. Each town uses the first pump it reaches when it walks forward along the road. Now someone builds one new pump. Only the towns that lie between the pump just behind the new one and the new pump start to use it. All other towns keep their pump. No town changes from one old pump to another old pump.

This is consistent hashing. The road is the ring.

1. A hash function (lesson 43) turns any text into a number. Take a range of numbers from 0 to 4,294,967,295 (2 to the power of 32 minus 1). Join the end to the start. That is the ring.
2. Each server gets a position on the ring: the hash of its name.
3. Each key gets a position too: the hash of the key.
4. A key belongs to the first server that it reaches when it moves forward from its position. After the largest number it continues from 0.

To find the server, keep the server positions in a sorted list. Use binary search: look at the middle of the list, then keep the half that holds the key position. Each step halves the list, so a list of 800 positions needs about 10 steps (2 to the power of 10 is 1,024).

What moves when a server joins or leaves

A new server takes a position. It takes over the keys between the server just behind it and its own position. Those keys were owned by the server just ahead of it. Nothing else moves. No key moves between two old servers. When a server leaves, all its keys go to the server just ahead of it. If the servers are evenly spread, a new server takes about 1 / (N + 1) of the keys when there are N servers.

Compare the hash mod method of lesson 43. Going from N to N + 1 servers moves N / (N + 1) of the keys. For 4 to 5 servers that is 80%. The ring moves about 20%.

The problem: one position per server is uneven

Positions come from a hash, so they are random. Some servers sit close to each other and own small parts of the ring. Others sit far from their neighbours and own large parts. A server's share of keys is the length of its part. Also, when a server leaves, one neighbour takes all its keys. That neighbour may become overloaded.

The fix: virtual nodes

Give each server many positions, not one. Each position is a virtual node: it acts like a small pretend server that belongs to one real server. (A real server is often called a node.) You make them by hashing "name#1", "name#2", "name#3", and so on. A server now owns many small parts, spread all around the ring. The small differences cancel out, and each server's share comes close to the fair share. More virtual nodes mean a more even share.

Virtual nodes help in three more ways:

• When a server leaves, its keys go to many different servers, not to one.
• A new server takes a little from every old server.
• A bigger server gets more virtual nodes, and so a bigger share.

The cost is a bigger table of positions, and many small moves of data instead of a few large ones.

Copies on the ring

To keep 3 copies of each key (lesson 39), store the key on the first server it reaches. Also store it on the next two different servers after that. Skip virtual nodes that belong to a server you already chose, so that the copies are on different machines. Apache Cassandra describes this placement in its documentation.

The ring in code

import bisect, hashlib

def h(text):  # a position on the ring: 0 to 2**32 - 1 (md5 only spreads the values)
    return int(hashlib.md5(text.encode()).hexdigest(), 16) % 2**32

def build(servers, vnodes):
    ring = sorted((h(f"{s}#{i}"), s) for s in servers for i in range(vnodes))
    return [p for p, _ in ring], [s for _, s in ring]

def owner(ring, key):
    positions, names = ring
    i = bisect.bisect_left(positions, h(key))  # first position at or after the key
    return names[i % len(names)]               # after the last one, go back to the start

SwadKart keeps 9 TB of data on 4 servers, as in lesson 43. A fifth server joins.

Assumptions (made up to teach with, not real traffic):

• The data is 9 TB, spread evenly over the keys.
• One network link carries 125 MB per second (1 Gbps, lesson 15).
• The ring has the positions 0 to 99, to keep the numbers small. A real ring has 4,294,967,296.

Step 1: hash mod. Going from 4 to 5 servers moves 4 / 5 = 80% of the data. That is 0.8 x 9 TB = 7.2 TB. At 125 MB per second it takes 7,200,000 / 125 = 57,600 seconds, which is 16 hours. If these were cache servers, every moved key would become a cache miss (lesson 31), so 80% of reads would miss at the same time.

Step 2: a small ring, one position each. Servers: A at 10, B at 35, C at 60, D at 85. A key goes to the first server at or after its position, and 99 goes on to 0.

• A owns 86 to 99 and 0 to 10: 25 positions.
• B owns 11 to 35: 25. C owns 36 to 60: 25. D owns 61 to 85: 25.

Add E at 50. E now owns the positions 36 to 50, which is 15 positions. They came from C, the server just ahead of E. C keeps 51 to 60. A, B and D are unchanged. So only 15 of 100 positions, which is 15%, moved. The answer to the predict box is: only C can lose keys, and only E can receive them. No key moves between old servers.

The shares are now A 25, B 25, C 10, D 25, E 15. They are uneven.

Step 3: how uneven is one position each? We use a short program. It places the servers on the ring 100 times with different names and averages the results. For the busiest server, the table shows its share divided by the fair share (1 / N):

With 10 servers and one position each, the busiest server holds on average 2.88 times the fair share. With 100 virtual nodes each it holds only 1.16 times. The gain slows down: 1,000 virtual nodes give 1.05, but make the table 10 times bigger.

Step 4: the real ring with virtual nodes. We run the code above with 200 virtual nodes per server, 100,000 keys, and servers "A", "B", "C", "D", then "E" added.

• 18,527 of the 100,000 keys moved. That is 18.5%. The fair value is 1 / 5 = 20%.
• None of the moved keys went to an old server. All of them went to E.
• E took keys from all four old servers: A 5,193, B 4,182, C 4,504, D 4,648.
• The data moved is 0.185 x 9 TB = 1.67 TB. At 125 MB per second that is 13,360 seconds, which is 3.7 hours. Hash mod needed 16 hours.
• The shares are A 21.9%, B 19.2%, C 19.9%, D 20.4%, E 18.5%. The largest is 21.9 / 20 = 1.09 times the fair share.

Step 5: a server leaves. Take D out of the 4 servers. In the small ring of Step 2, all of D's 25% goes to one neighbour, which then has 50%. That is 2 times its old load. With virtual nodes, the program sent D's keys to A, B and C in the shares 37%, 33% and 30%, about a third each. If every server held 25%, each would go to about 33% (25% + 25% / 3).

Step 6: the lookup. The table has 4 x 200 = 800 positions. Binary search needs about 10 steps.

• It solves moving most of the data when the number of servers changes. In the example it moved 18.5% (1.67 TB) and not 80% (7.2 TB).
• It costs a position table that every app server must have, and more complex code than hash mod. The balance is close to fair, not exact (1.09 times in the example). Many virtual nodes mean many small moves.
• The ring spreads keys evenly by count. It does not look at how many requests each key gets, so a key with very many requests still makes its server busy.
• I would change it when the number of servers never changes: then hash mod is simpler. I would also change it when I must choose where certain keys live: then a directory (lesson 43) is a better fit.

"Consistent hashing means no data moves when a server joins." Some data must move, because the new server starts empty. The ring moves only the share the new server needs: about 1 / (N + 1). In the example that was 18.5%.

"The ring is balanced with one position per server." It is not. The positions are random. In the table the busiest of 10 servers held 2.88 times the fair share. Virtual nodes fix this.

"More virtual nodes are always better." The gain slows down, and the cost grows. From 100 to 1,000 virtual nodes the busiest share moved from 1.16 to 1.05, and the table became 10 times bigger.

1. How does a key find its server on the ring? What problem do virtual nodes fix?
2. A store has 12 TB on 10 servers. An eleventh server joins. How much data moves with (a) hash mod, and (b) a ring with many virtual nodes, on average?
3. A team has 5 servers with one ring position each. One server holds 40% of the keys, and the fair share is 20%. Another server is twice as big as the rest. What do you suggest?