Sharding and partitioning data

Partitioning, also called sharding, splits one big data set into parts and puts each part on a different machine. A shop with 100 million customers cannot keep them all on one disk.

You will learn how a key decides which machine holds a record, and why the first obvious method breaks when you add a machine.

Replication copies all the data to each machine. Partitioning is different: each machine holds only part of it, so the whole set can be bigger than any one disk.

The system needs a rule that tells every machine where a record lives, using only its key. A simple rule: turn the key into a number with a hash function, then take the remainder after dividing by the number of machines.

# The lesson's hash: add up the codes of the letters.
def key_hash(key):
    total = 0
    for letter in key:
        total = total + ord(letter)
    return total

for key in ["ada", "bo", "cy", "dee"]:
    number = key_hash(key)
    print(key, number, "goes to machine", number % 3)
# Change 3 to 4 and run again: most keys move.

The remainder rule has a bad habit. Look at the last two columns of the table. Going from three machines to four changes the machine for six of the eight keys.

Moving data across the network is slow and loads every machine. Adding one machine should move about a quarter of the keys, not most of them.

# How many of eight keys change machine when a fourth machine arrives?
def key_hash(key):
    total = 0
    for letter in key:
        total = total + ord(letter)
    return total

keys = ["ada", "bo", "cy", "dee", "eli", "fay", "gus", "hal"]
moved = 0
for key in keys:
    if key_hash(key) % 3 != key_hash(key) % 4:
        moved = moved + 1
print(moved, "of", len(keys), "keys moved")

In consistent hashing the hash numbers are placed on a ring: positions 0 to 359 that wrap round. Each machine is given a position too.

A key goes to the first machine at or after its position, going round. Past the highest machine it wraps to the lowest. A new machine takes keys only from the stretch just before it.

v() ( printf '%s\r\n' "$*" | nc -w 1 valkey 6379 )

v INFO cluster | grep cluster_enabled

v MSET cart:ada 2 cart:bo 5 cart:cy 1

v EXISTS cart:ada cart:bo cart:cy

The command that stored three carts at once is easy on one machine. If the three keys sit on three machines, no single machine can do it in one step.

So partitioned stores limit commands that touch many keys. Or they ask you to give related keys a shared part of their name, so that they land together.