Noesis
4.4.27Databases

Distributed databases — sharding strategies, replication

2,423 words11 min readdifficulty · medium
🇮🇳 Yeh note Hinglish mein padho →

WHY does this even exist?

A single database server has hard limits: finite disk, finite RAM, finite CPU, and it can crash. Two different problems fall out of this:

  • Problem of size/throughput → no single box can store 50 TB or serve 1M writes/sec. → Sharding (a.k.a. horizontal partitioning): cut the dataset into disjoint pieces.
  • Problem of failure/availability → if the one box dies, your app dies. → Replication: keep redundant copies on other boxes.

SHARDING — splitting the data

The whole game is: given a row, which shard owns it? That mapping function determines everything.

Strategy 1 — Range sharding

  • WHY good: range queries (WHERE age BETWEEN 20 AND 30) hit few shards.
  • WHY bad: hotspots. If keys are time-ordered (e.g. created_at), all new writes hammer the last shard.

Strategy 2 — Hash sharding

  • WHY good: a good hash spreads keys uniformly → no hotspots.
  • WHY bad: range queries scatter across all shards; and changing NN remaps almost everything.

HOW the resharding pain arises (derive it): With shard = hash(k) mod N, a key kk stays put across the change N→N+1N \to N+1 only if hash(k) mod N=hash(k) mod (N+1).hash(k) \bmod N = hash(k) \bmod (N+1). For "random" hash values, a key keeps its slot with probability only about 1N+1\frac{1}{N+1} (it must land back in the same one of the N+1N+1 residue classes). So the fraction of keys that must move is fmoved≈1−1N+1=NN+1 (nearly all keys move).f_{\text{moved}} \approx 1 - \frac{1}{N+1} = \frac{N}{N+1}\ \text{(nearly all keys move).} That's catastrophic — every shard reshuffles. This is the problem consistent hashing solves.

Strategy 3 — Consistent hashing

Figure — Distributed databases — sharding strategies, replication

REPLICATION — copying the data

Topologies

Synchronous vs asynchronous

  • Synchronous: leader waits for the follower to confirm before acking the client → no data loss on failover, but slower and stalls if a follower is down.
  • Asynchronous: leader acks immediately → fast, but a crash can lose the last un-replicated writes (replication lag).

Quorum math (the heart of leaderless)

The unavoidable trade-off

The 80/20 of this topic

The 20% that buys 80% of understanding:

  1. Sharding = split distinct data (scale); Replication = copy same data (safety).
  2. hash mod N reshards badly; consistent hashing moves ~1/(N+1)1/(N+1) of keys.
  3. Quorum rule W+R>NW+R>N guarantees you read your latest write.

Flashcards

What problem does sharding solve vs replication?
Sharding solves scale (data/throughput too big for one node by splitting distinct data); replication solves availability/durability (copies of the same data survive failures).
Define a shard key.
The attribute whose value is fed into the partition function to decide which shard owns a given row.
Why can range sharding create hotspots?
Sequential/time-ordered keys all fall into the last range, so all new writes hit one shard.
Fraction of keys moved when going from N to N+1 shards under naive hash mod N?
About N/(N+1) — nearly all keys.
Fraction of keys moved under consistent hashing when adding a node?
About 1/(N+1) — only the new node's arc.
How does consistent hashing assign a key to a node?
Place nodes and keys on a hash ring; the key is owned by the first node clockwise from it.
What are virtual nodes for?
Many ring positions per physical node to even out load and smooth rebalancing.
State the quorum consistency condition.
W + R > N guarantees the read set overlaps the write set, so a read sees the latest write.
Derive why W+R>N works.
Two subsets of an N-set overlap by ≥ W+R−N; requiring ≥1 overlap gives W+R>N (pigeonhole).
Synchronous vs asynchronous replication trade-off?
Sync = no data loss on failover but slower / blocks on slow followers; async = fast but can lose recent writes (replication lag).
Single-leader vs multi-leader main difference?
Single-leader has one writer (no conflicts, but bottleneck/SPOF); multi-leader allows writes in many places (low-latency, but write conflicts).
With N=3, why is W=1,R=1 unsafe?
1+1=2 is not > 3, so read and write sets can miss each other → stale reads.
What does CAP force during a network partition?
Choose Consistency (refuse possibly-stale answers) or Availability (answer anyway), not both.
Recall Feynman: explain to a 12-year-old

Imagine your toy collection is too big for one box. Sharding is splitting the toys into several boxes — cars in box 1, dolls in box 2 — each toy lives in exactly one box, so any one box stays light. But boxes can break! So replication means making photocopies of each box's contents and keeping them in other rooms — if one breaks, a copy survives. Now, to find a toy fast we use a magic rule: a ring with arrows, and each toy belongs to the next box clockwise. The cool part: add a new box and only a little slice of toys has to move, not everything. And when friends ask "is this the newest toy?", we make sure the box we saved to and the box we read from always share at least one box — that's the rule W+R>NW+R>N.

Connections

  • Horizontal vs Vertical Partitioning
  • Consistent Hashing
  • CAP Theorem
  • Quorum Consensus and Paxos/Raft
  • Replication Lag and Read-Your-Writes
  • Hash Functions
  • Load Balancing

Concept Map

problem of size

problem of failure

solved by

solved by

orthogonal to

needs

strategy

strategy

strategy

risks

risks

fixed by

only one arc moves

Single server limits

Size/throughput problem

Failure/availability problem

Sharding = horizontal partitioning

Replication = identical copies

Shard key maps row to shard

Range sharding

Hash sharding

Consistent hashing

Hotspots on ordered keys

Resharding moves nearly all keys

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab ek single database server pe data ya traffic itna zyada ho jaata hai ki woh handle hi nahi kar paata, tab hum do alag cheezein karte hain. Pehli hai sharding — yaani data ko tukdo me kaat ke alag-alag machines pe daal dena. Har row sirf ek hi shard pe rehti hai, aur kaun si row kahan jaayegi yeh decide karta hai shard key ke through. Yeh scale ke liye hai. Doosri cheez hai replication — yaani har piece ki copies banake doosri machines pe rakhna, taaki ek machine crash ho to data bacha rahe. Yaad rakho: sharding alag-alag data baant‑ta hai, replication same data ki copy banata hai — dono alag concepts hain.

Sharding me strategy important hai. Range sharding me A–H ek shard, I–P doosra — range queries fast, lekin agar key time-based hai to saare naye writes last shard pe gir‑te hain (hotspot problem). Hash sharding (hash(key) mod N) load evenly spread karta hai, par dikkat tab aati hai jab tum naya shard add karte ho — modulus N se N+1 hote hi almost saare keys move karne padte hain (~N/(N+1), yaani 80% jab N=4). Isi pain ko solve karta hai consistent hashing: nodes aur keys dono ek ring pe rakho, har key apne clockwise wale node ko jaati hai. Naya node add karo to sirf ek chhota arc move hota hai — sirf ~1/(N+1) keys.

Replication me sabse important formula hai quorum rule: W + R > N. Matlab agar tum N copies me se W copies pe likhte ho aur R copies se padhte ho, to jab tak W+R, N se bada hai, tumhara read set aur write set kam se kam ek node pe overlap zaroor karega — aur wahi node latest value rakhta hai. Pigeonhole principle se yeh guarantee hai. Example: N=3 me W=2, R=2 (4>3) — strong consistency aur ek node down bhi chal jaaye. Lekin W=1, R=1 (2, jo 3 se bada nahi) — fast hai par stale data padh sakte ho. Async replication fast hota hai par crash pe last writes loss ho sakte hain; sync safe hai par slow. Yeh sab trade-offs CAP theorem me aate hain — partition ke time Consistency ya Availability, dono ek saath nahi.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,125 wordsD2Visual walkthroughThe derivation in pictures · 2,140 wordsD3Worked examplesEvery scenario covered · 4,174 wordsD4ExercisesGraded, full solutions · 2,455 wordsD5Question bankConcept traps, quick reveals · 1,959 words

Test yourself — Databases

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

CAP theorem — consistency, availability, partition toleranceCoding · 4.4.25Load balancing in MoEAI-ML · 6.1.6