Intuition The one core ideaA distributed database is just one big table cut into pieces and copied onto many computers , and every symbol in this topic is bookkeeping for two questions: "which computer holds this row?" (sharding) and "how many copies must agree before I trust an answer?" (replication). Master those two questions and the whole chapter is arithmetic.
Before we can talk about sharding or quorums, we have to earn every symbol the parent note throws at you. We build them bottom-up: nothing appears here until the thing it rests on has already been drawn.
Definition Node (machine / server)A node is one physical (or virtual) computer with its own disk, memory, and CPU. Draw it as a box . Everything in this topic is boxes with data inside them and arrows between them.
A table is a grid: each row is one record (one user, one order), each column is one field of that record. A row is what we move around and copy. When we "shard", we deal out rows ; when we "replicate", we photocopy rows .
Look at the figure: one table on the left, three empty node-boxes on the right. The entire topic is about the arrows that connect them — which arrow a row takes (sharding) and how many boxes end up holding the same row (replication).
Everything numeric in the parent note is built from four letters. We define each one on the picture before we ever put it in a formula.
N N counting number : the number of shards, or the number of replicas, depending on context. It is the number of shard-boxes when we split data, and the number of replica-boxes when we copy data. Same letter, two jobs — the context (splitting vs copying) tells you which. (We will build the exact rule that turns a key into a shard number only after we have defined the tools it uses, in Sections 2–3.)
W R W R W how many photocopies I stamp fresh , and R how many photocopies I inspect . Both are counts between 1 N
k k age. It is the input ; the shard number is the output .
Recall Which is which?N W R k
The parent note's very first sharding rule is written hash(k) mod N, and it never explains mod. We fix that here — before we ever use it in that rule — because a 12-year-old has met division but maybe not this notation.
a mod N a mod N the remainder left over when you divide a N . Example: 17 mod 5 = 2 17 = 3 × 5 + 2 2 0 , 1 , 2 , … , N − 1 N
mod and not plain division?
We need a function that takes any number and squashes it into exactly N mod gives you a label in { 0 , … , N − 1 } — precisely a shard number. That is why the topic reaches for mod: it is the natural "put this into one of N
The figure shows the number 17 N = 5 amber bucket labelled 2 — that highlighted bucket is the shard the row goes to. The five boxes underneath are literally the N { 0 , 1 , 2 , 3 , 4 } mod is the right tool for "which of N
Worked example Compute a shard number by handNow that mod is defined, we can safely read the parent's rule shard = hash ( k ) mod N hash ( k ) = 17 N = 5 17 mod 5 = 2 N = 4 17 mod 4 = 1 Same key, different box — that one observation is the entire reason mod N reshards badly.
A hash function hash ( k ) k look random and spread out . Picture a blender: emails go in, unpredictable numbers come out, but the same email always yields the same number.
Intuition Why hash before mod?Raw keys clump: ids 1000, 1001, 1002 are neighbours and would land in nearby buckets, creating a hotspot (one overloaded box). Hashing destroys that neighbourliness — consecutive ids get flung to unrelated numbers, so hash ( k ) mod N Hash Functions for how the blender is built.
Common mistake "Why not just use the id directly,id mod N?"
Why it feels right: ids are already numbers, so skip the blender.
The fix: ids often arrive in order (auto-increment, timestamps). id mod N then sends runs of new rows to the same few boxes → hotspots. Hashing first is what buys you uniform spread.
The left panel shows what a good hash buys you: roughly equal bar heights across boxes — balanced load, no single box drowning. The right panel is a hotspot : range/sequential keys pile onto the last box. This single contrast is why the parent note prefers hashing, and it is also the seed of Load Balancing .
The parent note lives on fractions like N + 1 N ≈ derive why those exact expressions measure how much data must move when you grow from N N + 1
≈ ≈ real number of keys that move depends on the exact random hash values; on average it lands near the clean fraction, so we write ≈ =
Intuition What "resharding cost" even meansWhen you add a shard, some rows have to physically move to a new box (their "which shard?" answer changed). The resharding cost is the fraction of all keys that move . Small = cheap growth; near 100% = a painful full migration. The two fractions below are exactly this cost for the two strategies.
Worked example Put a number on itPlug N = 4 5 N + 1 N = 5 4 = 80% N + 1 1 = 5 1 = 20% 80% 20% is the argument for Consistent Hashing over naive mod.
Recall Fraction sanity checkN + 1 1 N = 4 5 1 = 20% N + 1 N N = 4 5 4 = 80%
Quorum math (W + R > N sets .
Definition Set and overlapA set is just a collection of boxes, e.g. "the W overlap if they share at least one box. Picture two coloured circles: if they touch, there's a shared box in the middle holding the newest data.
Intuition Pigeonhole, in wordsIf you pick W R N W + R more than N cannot avoid each other — they must share a box. That forced-overlap box is where the reader finds the latest write. This is exactly why the topic needs the inequality W + R > N Quorum Consensus and Paxos/Raft and CAP Theorem .
Worked example See the overlap appearN = 3 { A , B } W = 2 { B , C } R = 2 2 + 2 = 4 > 3 B W = 1 , R = 1 { A } { C } 1 + 1 = 2 > 3
Definition Sharding vs Replication (the whole topic in two arrows)Sharding = deal distinct rows to different boxes (each row on exactly one shard) → solves scale . See Horizontal vs Vertical Partitioning .
Replication = photocopy the same row onto several boxes → solves survival . See Replication Lag and Read-Your-Writes .
They are independent choices: real systems shard first, then replicate each shard.
mod = remainder into N buckets
Hash = scramble to spread
Sharding = which box owns a row
Fractions and approx equals
Resharding cost 1 over N plus 1
Quorum rule W plus R over N
Distributed Databases topic
This map feeds directly into the parent topic .
Self-test: can you answer each before reading the topic proper?
What does a mod N The remainder of a ÷ N N 0 N − 1
Why hash a key before taking mod N? Hashing destroys the ordering/clumping of raw keys so mod N spreads them evenly and avoids hotspots.
What do N W R N W R
Why is naive resharding cost N + 1 N A key stays only if it lands back in its one old slot out of N + 1 N + 1 1 1 − N + 1 1 = N + 1 N
Why is consistent-hashing resharding cost N + 1 1 The new node steals only its single arc, which is N + 1 1
When must two subsets of an N When their sizes sum past N W + R > N
In one line, sharding vs replication? Sharding splits distinct rows across boxes (scale); replication copies the same rows onto many boxes (survival).
Evaluate 17 mod 5 17 mod 4 2 1 N
