🎓 A1Learner
🔍
0 of 42 lessons completed

Splitting the Store: Consistent Hashing

Consistent hashing is a way to place keys on a ring of servers so that most keys stay put when a server joins or leaves. This lesson deep-dives one part of the design, splitting the store across servers.

Keys belong to the next server clockwise

Servers and keys sit at fixed positions on the ring. Each key belongs to the first server met clockwise from its position, wrapping to the start after the last server.

servers = [(10, "server A"), (40, "server B"), (70, "server C")]
keys = [("key-1", 5), ("key-2", 15), ("key-3", 35), ("key-4", 50), ("key-5", 65), ("key-6", 85)]

def owner(position):
    for server_position, name in servers:
        if position <= server_position:
            return name
    return servers[0][1]

counts = {}
for key, position in keys:
    name = owner(position)
    counts[name] = counts.get(name, 0) + 1
    print(key, "at", position, "->", name)

for name in sorted(counts):
    print(name, "owns", counts[name], "keys")

Only the leaving server's keys move

Server C leaves the ring and its keys pass to the next server clockwise. Every other key keeps the same owner.

servers = [(10, "server A"), (40, "server B"), (70, "server C")]
keys = [("key-1", 5), ("key-2", 15), ("key-3", 35), ("key-4", 50), ("key-5", 65), ("key-6", 85)]

def owner(position, ring):
    for server_position, name in ring:
        if position <= server_position:
            return name
    return ring[0][1]

before = {key: owner(position, servers) for key, position in keys}
remaining = [entry for entry in servers if entry[1] != "server C"]
moved = []
stayed = []

for key, position in keys:
    if owner(position, remaining) != before[key]:
        moved.append(key)
    else:
        stayed.append(key)

print("moved keys:", moved)
print("moved:", len(moved))
print("stayed:", len(stayed))

Virtual nodes spread one server around the ring

This small demo uses 3 virtual nodes per server and says so. Each server appears at several positions, so the keys spread evenly across the servers.

ring = [(5, "server A"), (20, "server B"), (35, "server C"), (50, "server A"), (65, "server B"), (80, "server C"), (88, "server A"), (93, "server B"), (98, "server C")]
keys = [("key-1", 3), ("key-2", 18), ("key-3", 33), ("key-4", 48), ("key-5", 63), ("key-6", 78)]

def owner(position):
    for node_position, name in ring:
        if position <= node_position:
            return name
    return ring[0][1]

counts = {}
for key, position in keys:
    name = owner(position)
    counts[name] = counts.get(name, 0) + 1
    print(key, "at", position, "->", name)

for name in sorted(counts):
    print(name, "owns", counts[name], "keys")

Example

ring = [(10, "server A"), (25, "server B"), (40, "server C"), (55, "server A"), (70, "server B"), (85, "server C"), (100, "server A"), (115, "server B"), (125, "server C")]
keys = [("key-1", 5), ("key-2", 20), ("key-3", 35), ("key-4", 50), ("key-5", 65), ("key-6", 80), ("key-7", 95), ("key-8", 110), ("key-9", 120)]

def owner(position, nodes):
    for node_position, name in nodes:
        if position <= node_position:
            return name
    return nodes[0][1]

before = {key: owner(position, ring) for key, position in keys}
remaining = [entry for entry in ring if entry[1] != "server B"]
moved = []
stayed = []

for key, position in keys:
    if owner(position, remaining) != before[key]:
        moved.append(key)
    else:
        stayed.append(key)

print("moved keys:", moved)
print("moved:", len(moved))
print("stayed:", len(stayed))

Key points

  • Consistent hashing: the placing of keys and servers on one ring, where a key belongs to the next server clockwise.
  • Ring: a circle of positions, ordered clockwise, that holds both servers and keys.
  • Owner: the first server met clockwise from a key position owns that key.
  • Virtual node: one of many positions a single server places on the ring, so its keys spread around the circle.
  • Demo value: the design demo ring uses 100 virtual nodes per server, a chosen demo value.

In this example, a ring with virtual nodes loses server B and only its 3 keys move to a new owner. The other 6 keys stay with the server that already held them.

Note

hash values in these demos are written as plain data, never worked out inside the program.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

In consistent hashing, which keys change owner when one server leaves the ring?