Splitting the ledger (sharding)

The sequel The copy clerks (database replication) promised. The copy clerks gave the stall many books to read from, and every new order still went into one book, with one pen. This is the story of cutting that book up, and of the 1997 paper that made the cutting survivable.

Before you start. You need the copy clerks: one master book, several clerks holding copies, so a hundred people read at once. That lesson left one thing untouched, and this lesson breaks it - every new line still has to be written into the master, by one hand.

The idea in 30 seconds

Copies scale reads, because any copy can answer one. They do nothing for writes, because every copy takes every write.
Sharding splits different rows across books instead of copying the same rows: two books, two pens.
The shard key is the field that decides which shard a row lives in, and choosing it is the whole job.
Range partitioning keeps neighbours together, so ordered scans read one shard, and lets skewed data pile into a hot shard. Bigtable splits a range automatically once it grows too big.
Hash partitioning spreads evenly and makes every question that is not a look-up by the shard key fan out to all shards.
Remainder-by-server-count re-homes nearly everything whenever that count changes. Consistent hashing puts keys and servers on a circle so only one arc moves, and virtual nodes keep the arcs fair.

Read the story · Skip to the numbers

Continue reading with a plan

The first three lessons of every track are free. This lesson is included with a plan, which unlocks every lesson, board, video, lab and paper for one price.

View plans →Already a member? Sign in

Lab

Names are mostly A–D. You split A–M / N–Z. What happens?

Start on Split by letter, read the load bars under The books, then switch to Scrambled name and press Add a book.

Open Splitting the ledger →

The ring rehomes only 1/N of the keys when a server dies. So why does everyone run two hundred virtual nodes per server?

Drag Points on the ring per server from one upward, stay on Walk clockwise to the next server, and watch What the balance costs.

Open The ring →