Concept 4: Database Sharding & Partitioning

System Design Bible — File 04 of 10 Difficulty: ★★★☆☆ Prerequisites: Files 01–03 (and ideally File 11, Databases). The essentials are unpacked in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

Sharding is "split the database across many machines." To see why it's necessary and why it's painful, you need three ideas solid first.

Those three are §0.1 (scale up vs scale out), §0.2 (why writes are the wall), and §0.3 (how a row is located by its key). They are the minimum. But "the database is full" and "the database is slow" are not one problem — they are seven different physical problems wearing the same shirt, and a candidate who cannot name which of the seven they are hitting cannot justify sharding to an interviewer. So this section then goes a layer deeper than most treatments: §0.4 teaches what a table, a row, and an index physically are as bytes on a disk, because every ceiling sharding exists to break is a property of those bytes; §0.5 enumerates all seven ceilings of a single database instance individually, with the arithmetic for each; §0.6 lays out the escalation ladder (vertical scaling → caching → read replicas → sharding) and states precisely where each rung snaps; and §0.7 teaches what a hash function actually is, because three of the partitioning strategies in Section 3 are nothing but a hash function with a modulus after it, and a reader who cannot say what "uniformity" and "avalanche" mean cannot evaluate them. Read all seven. Nothing later in this file assumes anything that is not taught here.

0.1Vertical vs horizontal scaling (scale up vs scale out)#

There are exactly two ways to make a system handle more load. Vertical scaling (scale up) = make the single machine bigger: more CPU cores, more RAM, faster/bigger disks. It's wonderfully simple (no code changes, one machine to reason about) but it has a hard ceiling (you can't buy an infinitely large server), a brutal price curve (top-end hardware costs disproportionately more), and it leaves you with a single point of failure (that one big box dies → everything's down). Horizontal scaling (scale out) = add more machines and spread the load across them. It's effectively unlimited and uses cheap commodity hardware, but it introduces coordination problems (how do requests and data get distributed and kept consistent?). From File 01 you know the stateless app tier scales out trivially. Sharding is what it takes to scale out the stateful database — much harder, because data can't just be duplicated freely. Hold the vocabulary: up = bigger box (simple, capped); out = more boxes (unlimited, complex).

0.2Why the write path is the wall (replicas and cache don't help writes)#

From File 02 you learned to absorb read load with caches and read replicas. So why can't the same tricks handle a database that's overloaded? Because they only help reads. A read replica is a copy of the database that serves read queries — you can add many, scaling reads linearly. A cache answers repeated reads from RAM. But every write (INSERT/UPDATE/DELETE) must ultimately go to the primary (the authoritative copy) and then propagate to all replicas — you can't split writes across replicas, because they'd diverge (File 08). So a single primary has a hard write throughput ceiling set by its disk, transaction log, and lock contention, and no amount of caching or read replicas raises it. When your write volume (or the raw data size) exceeds what one machine can take, your only option is to split the data across multiple primaries — which is sharding. Internalize this: caching/replicas scale reads; sharding is the answer when writes or data volume exceed one machine.

0.3Primary keys and how a row is located#

A primary key is the column that uniquely identifies each row in a table (e.g., user_id) — it's how you address a specific record, and databases automatically build an index (a sorted lookup structure, see File 11 §5) on it so "get the row with user_id = 42" is near-instant rather than a scan of every row. This matters for sharding because sharding asks a new question: with the data spread across 10 machines, *which machine holds user_id = 42?* The answer is computed from a shard key (often the primary key) via a function shard = f(shard_key). So sharding is essentially "extend the idea of locating a row by its key from within one machine to across many machines." If "primary key," "index," and "locate a row by key" aren't crisp, skim File 11 §2 and §5 before continuing — the entire shard-key discussion depends on them.

0.4What a table, a row, and an index physically are on disk#

Everyone can picture a table as a grid on a whiteboard. That mental model is the reason most people cannot explain why a database has a ceiling — a grid has no size, no seek time, and no memory footprint. Here is what is actually on the disk, because every wall in §0.5 is a property of these bytes.

The block/page is the atom. A disk does not store bytes; it stores fixed-size blocks. A database inherits this and organizes all of its storage into fixed-size pages (also called blocks): 8 KB in PostgreSQL, 16 KB in InnoDB (the default storage engine behind MySQL), 4 KB in many others. The page is the unit of every I/O the database performs. If you ask for a single 200-byte row, the database does not read 200 bytes — it reads the entire 8 KB or 16 KB page that contains it, into memory. If you update one byte of that row, the database eventually writes the whole page back out. Hold that: the smallest read a database can do is one page, so a query's true cost is measured in pages touched, not rows returned.

A row (tuple/record) is a byte string inside a page. A row is laid out as a small header followed by its column values packed end to end. Concretely, a PostgreSQL row's header is 23 bytes and includes xmin and xmax — the transaction IDs that created and deleted this version of the row, which is how PostgreSQL implements MVCC (Multi-Version Concurrency Control): rather than overwriting a row in place and locking readers out, an UPDATE writes a new version of the row and marks the old one dead, so readers that started earlier keep seeing the old version and never block. (MVCC's cost is that dead row versions accumulate and must be reclaimed by a background process — VACUUM in PostgreSQL, the purge thread in InnoDB — which is one of the operational chores that gets worse as a single table gets bigger, and one of the quiet reasons very large single tables become miserable.) After the header come the column values: a 4-byte INTEGER is literally four bytes; a VARCHAR(50) holding "alice@example.com" is a 1- or 4-byte length prefix followed by 17 bytes of text; a TIMESTAMP is 8 bytes. So a user row with id BIGINT (8) + email VARCHAR (~25) + name VARCHAR (~20) + created_at TIMESTAMP (8) + header (23) is roughly 85 bytes. An 8 KB page holds about 95 such rows after subtracting the page header and the per-row line pointers. One hundred million users is therefore about 1.05 million pages, about 8.6 GB — and that is just the table, before any index. This arithmetic is how you answer "how big is your data?" in an interview instead of guessing.

A table is a heap or a clustered index — and the difference matters enormously for sharding.

Sub-Concept: the B-tree, in one paragraph, because everything below rests on it. A B-tree (specifically a B+tree in every real database) is a balanced, high-fan-out search tree stored in pages. The leaf pages hold the sorted keys (and, in a clustered index, the rows); the internal pages hold only separator keys and pointers to child pages. "High fan-out" means one 8 KB internal page holds hundreds of separator keys — with 8-byte keys and 8-byte child pointers, roughly 500 children per page. That fan-out is what makes the tree shallow: 500 children per node means 500 leaves at depth 1, 250,000 at depth 2, 125 million at depth 3, 62 billion at depth 4. So a lookup of one row in a 100-million-row table costs 3–4 page reads, and the top two levels are almost always already cached in RAM, so in practice it is one physical disk read. The B-tree also keeps the leaves in a linked list, which is why a range scan (WHERE id BETWEEN 1000 AND 2000) is cheap: find the first leaf, then walk sideways reading sequential pages. The tie-back to sharding: this shallow-and-sequential property is exactly what range partitioning (§3.1) preserves and what hash partitioning (§3.2) destroys — hashing scatters logically adjacent keys into physically distant leaves, so a range scan becomes thousands of random reads instead of one sequential walk.

A non-clustered (secondary) index is a second B-tree. When you CREATE INDEX idx_email ON users(email), the database builds another B-tree whose keys are email values and whose leaf entries point back to the row — by CTID in PostgreSQL, by primary key value in InnoDB. That InnoDB detail has a consequence people get wrong: looking up a row by a secondary index in MySQL costs two B-tree descents, one in the secondary index to get the primary key and one in the clustered index to get the row (this second step is called a bookmark lookup). It also means every secondary index in InnoDB is inflated by the size of your primary key — which is why using a 16-byte random UUID as a primary key bloats every index in the table, a mistake File 17 (distributed ID generation) discusses in detail.

Indexes are not free — they are the hidden multiplier. An index on a BIGINT column over 100 million rows stores 8 bytes of key plus ~8–14 bytes of pointer/header per entry, plus B-tree overhead, plus the default fill factor (databases deliberately leave pages ~10% empty so future inserts can slot in without splitting the page). Call it ~2.5 GB per simple index. Five indexes on that table is 12.5 GB of index against 8.6 GB of table — indexes commonly outweigh the data. And every INSERT must write not just the row but an entry into every index, each of which is a random write into a different B-tree at a different place on disk. This is the mechanism behind the write ceiling of §0.5: one logical insert is six physical writes plus a WAL append.

Hold this: a table is pages of rows in a heap or a B-tree; an index is another B-tree; every read costs whole pages; every write costs one WAL append plus one write per index; and the size of your working set is table pages plus index pages, not just "the data."

0.5The anatomy of the single-instance ceiling (seven separate walls)#

"The database can't take it any more" is not one condition. It is seven, and they arrive in different orders for different workloads. Naming which wall you are hitting is how you justify sharding — and, just as often, how you discover that you should not shard because the wall you hit has a cheaper fix.

Wall 1 — Disk capacity. The most obvious and the least common as the first wall. A single cloud instance's attached storage has a hard maximum: an AWS EBS gp3 volume tops out at 16 TiB, io2 Block Express at 64 TiB, a physical NVMe-packed server maybe 100 TB. But the honest number is lower than the sticker, because you need room for the WAL, for index bloat, for the temporary space a large ALTER TABLE or index rebuild consumes (often a full second copy of the table), and for the free space MVCC vacuuming needs. Rule of thumb: you are in trouble at ~60% full, not 95%. Diagnosis: df -h on the data directory, plus the database's own size views (SELECT pg_size_pretty(pg_database_size('mydb')) in PostgreSQL, information_schema.TABLES in MySQL).

Wall 2 — IOPS (I/O operations per second). An IOP is one read or write request to the storage device. This is usually the real first wall, and it is invisible if you only watch CPU. A spinning disk delivers ~100–200 random IOPS because it must physically move a head (~10 ms seek). A consumer SSD delivers ~50,000–100,000. An AWS gp3 EBS volume gives you 3,000 IOPS baseline, provisionable to 16,000; io2 Block Express up to 256,000. Now do the arithmetic that matters: if your working set does not fit in RAM, a primary-key point lookup costs ~1 random read, and a query using a secondary index in InnoDB costs ~2. At 16,000 IOPS with an average of 2 random reads per query, your ceiling is 8,000 queries/second — and no amount of CPU changes it. Diagnosis: iostat -x 1 and look at %util pinned near 100 with a rising await; in PostgreSQL, a collapsing pg_stat_database.blks_hit / (blks_hit + blks_read) cache-hit ratio.

Wall 3 — Write throughput, and why it is stricter than read throughput. Every committed write must be durable, which means it must survive an immediate power loss. Databases achieve this with the WAL (Write-Ahead Log) — an append-only file to which the change is written before the data pages are modified — and durability requires an fsync: the system call that forces the operating system to push its in-memory copy of that file all the way down to the physical device, past every volatile cache. An fsync to a network-attached volume costs ~0.5–2 ms. Naively, that caps you at 500–2,000 commits/second per instance. Databases dodge this with group commit (batching many transactions' WAL records into a single fsync — MySQL's binlog_group_commit_sync_delay, PostgreSQL's commit_delay), which lifts real-world numbers to the 10,000–50,000 writes/second range on good hardware. But notice what you cannot dodge: the WAL is a single serial stream, written by one process, on one machine. You cannot parallelize a total order. Add to that the write amplification of §0.4 — one logical insert becomes one WAL record plus N index writes plus eventual page flushes — and you have the fundamental reason writes, unlike reads, cannot be scaled by adding copies. Diagnosis: rising WAL generation rate, Innodb_os_log_written climbing, commit latency p99 rising while CPU sits idle.

Wall 4 — RAM and the working set. The database keeps recently used pages in a memory cache — the buffer pool in InnoDB (innodb_buffer_pool_size, conventionally set to ~70% of the machine's RAM), the shared buffers plus OS page cache in PostgreSQL. As long as your working set (the pages actually touched by live traffic, which is far smaller than the whole database) fits in that cache, reads are nanosecond-scale memory hits. The moment the working set exceeds it, you fall off a cliff — not a slope, a cliff — because you go from ~100 ns memory access to ~100 µs–10 ms disk access, a factor of a thousand or more, and simultaneously you start paying Wall 2's IOPS budget for traffic that used to be free. Worked example: 8.6 GB of table plus 12.5 GB of indexes is 21 GB; on a 32 GB instance with a 22 GB buffer pool you are fine. Double the data to 42 GB and the hit ratio falls from 99.9% to perhaps 85%, meaning 15% of page requests go to disk — at 10,000 queries/sec × 2 pages × 15%, that is 3,000 IOPS appearing out of nowhere, and you slam into Wall 2 as a consequence of Wall 4. This coupling is why database performance degrades non-linearly and why "it was fine last month" is the classic on-call story. Diagnosis: buffer pool hit ratio, Innodb_buffer_pool_reads (physical) versus Innodb_buffer_pool_read_requests (logical).

Wall 5 — Connections and CPU. Every client connection to PostgreSQL is a separate OS process costing several MB of private memory plus a scheduler slot; in MySQL it is a thread costing ~256 KB–1 MB of stack. Both degrade badly past a few hundred concurrent connections — not because of memory alone, but because of context switching and, in PostgreSQL, because internal structures like the lock table and the snapshot-visibility computation scale with the number of live backends. PostgreSQL's practical ceiling is a few hundred active connections, which is why connection pooling is mandatory at scale: a pooler such as PgBouncer (for PostgreSQL) or ProxySQL (for MySQL) sits between the app and the database, accepts thousands of cheap client connections, and multiplexes them onto a small fixed set of expensive server connections. If you have 200 application containers each holding a pool of 20 connections, you are demanding 4,000 database connections; a pooler turns that into 100. This is a wall you should hit and fix with a pooler, not with sharding — a very common misdiagnosis. Diagnosis: SHOW STATUS LIKE 'Threads_connected', pg_stat_activity counts, "too many clients already" errors.

Wall 6 — Backup, restore, and recovery time. This is the wall nobody puts on the slide and everybody hits. A full backup of a 10 TB database at a realistic sustained 200 MB/s takes ~14 hours; the restore takes at least as long, and then you must replay the WAL accumulated since the backup started, which can take as long again. Your RTO (Recovery Time Objective — the maximum time the business will tolerate being down) is probably measured in minutes. A single 10 TB database simply cannot meet a 1-hour RTO by restore; it can only meet it by failing over to a replica, which means your disaster recovery story now depends entirely on replication being healthy. Related: a single-instance crash requires crash recovery — replaying the WAL from the last checkpoint — whose duration scales with how much WAL accumulated, and a very large busy instance can take many minutes to come back. Sharding fixes this arithmetically: ten 1 TB shards back up in parallel in 1/10 the wall-clock time, and restoring one failed shard restores 10% of the service instead of 100%. Diagnosis: time an actual restore. Not a theoretical one. The number is always worse than people believe.

Wall 7 — Lock and latch contention on the single writer. Even with infinite disk and infinite RAM, a single instance serializes on shared in-memory structures. Concrete mechanisms: row locks — two transactions updating the same row must queue, and a hot row (a global counter, an inventory count for a viral product, a leaderboard total) serializes everything that touches it; index page latches — when many inserts land on the same B-tree page, they contend on the short-lived internal lock protecting that page, which is exactly what happens when your primary key is auto-increment, since every insert targets the rightmost leaf page (this specific pathology is called right-hand index contention or index tip contention); the WAL insert lock, the mutex protecting the append point of the single log; and deadlocks, where transaction A holds row 1 and wants row 2 while B holds row 2 and wants row 1, forcing the database to detect the cycle and kill one of them — a phenomenon whose frequency grows super-linearly with concurrency. Why sharding helps: ten shards means ten independent WALs, ten independent lock tables, ten independent B-tree tips. Contention that was quadratic in one place becomes ten smaller quadratics. Diagnosis: SHOW ENGINE INNODB STATUS for lock waits and deadlocks, pg_locks joined to pg_stat_activity for blockers, rising Innodb_row_lock_time_avg.

Hold this: the seven walls are disk capacity, IOPS, write/fsync throughput, RAM working set, connections/CPU, backup-and-recovery time, and lock contention. Sharding divides all seven by N simultaneously — that is its entire value proposition. But walls 4 and 5 usually have far cheaper fixes (more RAM, a connection pooler), and reaching for sharding when the real problem is a missing index or an absent pooler is the single most common expensive mistake in this topic.

0.6The escalation ladder: vertical scaling → caching → read replicas → sharding#

There is a canonical order in which you respond to database load, each rung cheaper and less irreversible than the next. You must be able to walk an interviewer up it and say precisely where each rung snaps, because "just shard it" as a first answer is a junior tell.

Rung 0 — Fix the query. Before any architecture: is there a missing index turning a point lookup into a full table scan (a sequential scan of every page)? Is there an N+1 query pattern where the application issues one query per row of a previous result, turning one page load into 500 round trips? Is a query returning 100,000 rows to discard 99,900 of them in the application? Where it snaps: when the query plans are already optimal and the load is genuinely there. Honestly, a large fraction of "we need to shard" ends here — an EXPLAIN ANALYZE and one index. Cost: hours. Downside: none. Interview line: "First I'd confirm this isn't a query-plan problem, because sharding a badly-indexed schema just gives you N badly-indexed schemas."

Rung 1 — Vertical scaling (a bigger box). Move from a 16-core/64 GB instance to a 96-core/768 GB one; move from gp3 to io2 for 10× the IOPS. This buys you all seven walls at once with zero code changes, which is an enormous and underrated property. Where it snaps: at the top of the instance catalogue (AWS's largest memory-optimized instances reach roughly 24 TB of RAM and 128+ physical cores, and no bigger machine is for sale at any price), and economically much earlier — the price curve is super-linear: doubling the specification typically more than doubles the price, so at the top end you pay 4× the money for 2× the capacity. It also does nothing for blast radius: it is still one machine, one failure domain, one maintenance window. Cost: money, plus a restart. Mitigation of the downtime: fail over to a replica, promote it, resize the old primary. Interview line: "Vertical scaling is the highest-leverage move available because it costs no complexity; I'd exhaust it deliberately, not sheepishly."

Rung 2 — Caching (File 02). Put Redis or Memcached in front and serve repeated reads from RAM, never touching the database. This attacks Walls 2 and 4 directly by removing read pages from the database's I/O and buffer-pool budget entirely. Where it snaps: three places. (a) Write-heavy workloads — a cache does nothing for INSERT/UPDATE; a 50/50 read/write workload can be at best 2× improved. (b) Low-locality reads — caching only helps if the same keys are read repeatedly; a workload that reads a billion distinct keys uniformly has a hit rate near zero no matter how big the cache is, because a cache is a bet on skew. (c) Consistency requirements — a cache introduces staleness, and the invalidation problem (File 02's "three cache killers": stampede, penetration, avalanche) is real work. Cost: a new stateful system to run, plus the correctness burden of invalidation. Interview line: "Caching converts a read problem into an invalidation problem; it is the right trade until writes or data volume are the constraint, at which point it stops helping at all."

Rung 3 — Read replicas. Stream the primary's WAL to N copies and route read queries to them (File 08). This scales read throughput almost linearly and gives you a hot standby for failover, which is also your answer to Wall 6. Where it snaps: (a) writes are unaffected — every replica must apply the same write stream as the primary, so if the primary cannot keep up with writes, neither can any replica; adding replicas actually adds load to the primary (each replication stream costs network and WAL-sender CPU). (b) Replication lag — replicas are asynchronous by default, typically milliseconds behind but seconds-to-minutes behind under load or during a long transaction, which produces the classic read-your-own-writes violation: a user posts a comment, the write goes to the primary, the subsequent read goes to a lagging replica, and the comment appears to have vanished. Mitigations are real but fiddly: route reads for a user to the primary for N seconds after their write ("sticky reads"), or use replication-position tokens (MySQL GTIDs, PostgreSQL LSNs) so the client can demand a replica that is caught up. (c) Storage is not divided — every replica holds the entire dataset, so replicas do nothing whatsoever for Wall 1. Interview line: "Replicas multiply reads and divide nothing."

Rung 4 — Functional/vertical partitioning (§3.6). Before full sharding, split the database by feature: users in one database, orders in another, analytics events in a third. This is genuinely easier than sharding because each resulting database is a normal, whole, single-node database with its own transactions and joins intact — you have merely lost cross-domain joins, which are usually the ones you care least about. Where it snaps: when a single one of those domains is itself too big — you have divided the problem by 3, not by N, and it does not divide again. Interview line: "Functional partitioning is the cheapest form of splitting and buys you a year; it does not scale with growth because the biggest table stays whole."

Rung 5 — Horizontal sharding (this file). Split the biggest table's rows across N primaries. This is the only rung that divides all seven walls by an arbitrary N. It is also the only rung that is effectively irreversible, that removes cross-shard joins and transactions, and that multiplies your operational surface by N. Interview line, and this is the sentence to memorize: "I'd shard when write throughput or raw data volume exceeds what one machine can hold, after exhausting query tuning, vertical scaling, caching, read replicas, and functional partitioning — because sharding is the only one of those I can't undo."

Hold this: the ladder is tune → scale up → cache → replicate → split by feature → shard, each rung is cheaper and more reversible than the next, and each one snaps at a specific, nameable place. Knowing the snap points is the difference between a candidate reciting a list and one who has run a database.

0.7What a hash function is, and the four properties that make one usable for sharding#

Three of the strategies in Section 3 — hash partitioning, consistent hashing, and composite keys — are built entirely on hash functions, and the file's entire argument about "even distribution" is an argument about hash function properties. So: what is one?

Plain definition. A hash function takes an input of arbitrary size (a string, a number, a byte array — here, your shard key) and deterministically produces a fixed-size number called the hash or digest. md5("alice") = 6384e2b2184bcbf58eccf10ca7a6563c — a 128-bit number, no matter that the input was 5 characters. crc32("alice") = 0x8B3E9A2F — 32 bits. The point is that an unbounded, structured, clumpy input space is mapped onto a bounded, uniform-looking output space.

Why it exists here. Real shard keys are not uniformly distributed. User IDs are sequential and monotonically increasing; email addresses cluster heavily on gmail.com; usernames cluster on the letters a, s, m; timestamps march forward in lockstep. If you assign shards by looking at the raw key you inherit every one of those clumps as a hot shard. A hash function's job is to destroy the structure of the input so that whatever clumps existed become noise. That is the whole idea, and it is also the whole cost — you cannot destroy structure and keep it.

The four properties, each one individually.

What breaks, and how you'd see it. Three classic failures: (a) A non-deterministic hash → rows written under one hash cannot be found under another; symptom is "the data is gone" for a random subset of keys, and the diagnosis is to compute the shard for a missing key in two separate processes and compare. (b) A non-avalanching hash on sequential keys → shard-size histogram shows a staircase rather than a flat line; diagnosis is a SELECT COUNT(*) GROUP BY shard. (c) Changing the hash function or the modulus → every key relocates at once (§5.5); symptom is a total cache/lookup miss storm, and there is no fix except a full migration, which is why the hash function and the partition count are part of your data format, not configuration you may casually tune.

Hold this: a hash function is a deterministic scrambler that converts clumpy real-world keys into uniform bucket numbers; you want determinism, uniformity, avalanche, and speed, you want non-cryptographic (Murmur3/xxHash/CRC) unless keys are adversary-controlled, and you must treat your choice of hash and modulus as immutable parts of your data layout.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

Partitioning is splitting a large dataset (a table, a collection) into smaller pieces called partitions (or shards) so that each piece can be stored and processed independently. Sharding is specifically horizontal partitioning across multiple machines — each shard lives on a separate database server, so the total data and load are spread across many nodes.

The goal: a single logical database that is physically many databases, so you can store more data and handle more throughput than any one machine could.

1.2"The Why" — The Single-Database Wall#

In File 01 we scaled the stateless app tier trivially by adding servers behind a load balancer. But the database holds state, and state cannot be duplicated freely without consistency problems. As data and traffic grow, a single database server hits hard walls:

Vertical scaling (bigger DB server) delays these walls but never removes them — and the price curve is brutal, and you still have a SPOF. The only way past the write/storage ceiling is sharding: split the data across N servers so each holds 1/N of the data and serves 1/N of the writes. Now capacity grows (roughly) linearly with server count.

Connecting to prior files: Caching (File 02) and read replicas absorb read pressure. Sharding is the answer when writes and/or raw data volume exceed one machine — the part caching can't fix.

1.3What Sharding Solves (and the price it charges)#

Sharding buys you near-unlimited storage and write scalability. But it charges a steep price: you lose the convenience of a single database — cross-shard joins, global transactions, global unique constraints, and simple aggregations all become hard or impossible. Shard only when you must, and choose the shard key carefully, because it's very hard to change later. This tension is the soul of File 04.

Stated as a ledger, so you can reproduce it on a whiteboard — every row is "here is a wall from §0.5, here is exactly how splitting the rows across N machines removes it, and here is the bill":

1.4The vocabulary map — partitioning, sharding, replication, federation#

Four words get used interchangeably in casual conversation and mean four different things in an interview. Getting them right is cheap signal.

A precise sentence you can say: **"We partition the orders table by hash of customer_id into 4,096 logical partitions, shard those across 16 physical MySQL instances, and replicate each instance three ways for availability."** That one sentence contains a partitioning scheme, a logical-to-physical mapping, a shard count, and a replication factor — it is exactly the shape of answer a Staff interview is fishing for.

2The Recursive Sub-Concept Tree#

2.1Sub-Concept: Vertical vs. Horizontal Partitioning#

Mnemonic: Vertical = fewer columns; Horizontal = fewer rows. Sharding is horizontal partitioning across machines.

Why the two exist at all is a consequence of §0.4. Remember that the unit of I/O is a page and that rows are packed into pages end to end. Suppose your users table has id, email, name, created_at (about 60 bytes together) plus bio TEXT and profile_json JSONB (about 4 KB together). Every row is now ~4 KB, so an 8 KB page holds two rows instead of ninety-five. A query that scans a million users to count signups per day must now read 500,000 pages (4 GB) to look at 60 bytes per row — it is dragging 4 KB of bio through the buffer pool for every 60 bytes it wants. Vertical partitioning fixes exactly this: move bio and profile_json into a user_profiles table keyed by the same id. The users table shrinks back to ~95 rows per page and the same scan reads ~10,500 pages (86 MB) — a 46× reduction in I/O with zero change to the total data stored. The cost is that any query wanting both halves now performs a join (or two round trips), and if the halves live on different servers, that join is a network call the database cannot optimize. This is also, incidentally, the whole argument for column-oriented storage in OLAP systems (§2.14) — a column store is vertical partitioning taken to its logical extreme: every column is its own file.

Horizontal partitioning's mechanism, with concrete values. Take the same users table with 100,000,000 rows and shard by user_id into 8 shards using user_id % 8. Shard 0 receives every user whose id ends in 0 modulo 8 — user 8, 16, 24, … — roughly 12,500,000 rows, about 1.1 GB of table plus ~1.6 GB of indexes. Every shard has the identical schema: same columns, same indexes, same constraints. A SELECT * FROM users WHERE user_id = 8675309 computes 8675309 % 8 = 5 and goes to shard 5 alone; the other seven shards do not know the query happened. A SELECT COUNT(*) FROM users WHERE country = 'JP' cannot be resolved that way and must ask all eight (§2.5).

Where each sits in the stack. Vertical partitioning is a schema design decision — you make it in your DDL and your ORM, and the database is unaware anything unusual is happening. Horizontal sharding is a topology decision that lives above or inside the database: something must know the shard map (§2.4) and route. That difference in where the decision lives is why vertical partitioning is cheap and reversible (an ALTER TABLE and a deploy) and sharding is not.

What breaks. Vertical partitioning breaks when you get the split wrong and the "cold" columns turn out to be read on every request anyway — now every request is two lookups instead of one, and you have added latency for nothing; the diagnostic is that your join rate equals your read rate. It also silently destroys transactional atomicity across the halves the moment the halves live on different servers: updating users.name and user_profiles.bio together is no longer one commit. Horizontal partitioning breaks when the shard key is absent from the query (§2.5) or unevenly distributed (§2.6).

Tie-back: the entire rest of this file is about horizontal partitioning, because that is the only one of the two that scales without bound — you can only split a table so many times by column (you have a finite number of columns), but you can split it by row forever.

2.2Sub-Concept: Shard / Partition / Node#

This logical/physical indirection is the single most important structural idea in operational sharding, and it deserves the full treatment because half of Section 5 depends on it.

What it is. Instead of one mapping (key → machine), you build two: key → logical partition (a pure function, fixed forever) and logical partition → physical node (a small mutable table, changed whenever you rebalance). The first mapping is data format; the second is configuration.

Why it exists. If you map keys directly to machines, then the number of machines is baked into your data layout, and changing the machine count changes where every key lives (§5.5 does this arithmetic). By inserting a fixed intermediate layer, you decouple how the data is divided from how many boxes you own. The partition count never changes; only the assignment table does.

How it works, with concrete values. Choose 1,024 logical partitions. Compute partition = murmur3(user_id) % 1024. Start with 4 nodes and assign 256 partitions each:

 partition_map (the only mutable state):
   p0000–p0255  -> node A        p0512–p0767  -> node C
   p0256–p0511  -> node B        p0768–p1023  -> node D

 add node E:  move 51 partitions from each of A,B,C,D  ->  ~205 each, 204 on E
 the function murmur3(user_id) % 1024 NEVER CHANGES.

Adding node E moves 1/5 of the data — exactly the minimum possible — and requires zero recomputation of any key's partition. User 8675309 was in partition p0731 before the move and is in partition p0731 after; only the row in partition_map saying where p0731 lives changed. Compare this to hash % 4 → hash % 5, which relocates ~80% of all rows (§5.5).

The exact numbers to choose. Pick the partition count to be (a) far larger than your maximum expected node count — 1,024 or 4,096 partitions is typical for a fleet that may reach dozens of nodes, and Elasticsearch's guidance of "shards of 10–50 GB each" is the same rule expressed in size terms; and (b) ideally a power of two if you plan to split partitions later, because splitting p731 of 1,024 into two halves of a 2,048-partition space is the clean operation partition = h % 2048, where the new partitions p731 and p1755 between them hold exactly the old p731's keys. Choosing too few partitions caps your maximum node count forever (you cannot have more nodes than partitions, and Elasticsearch users hit exactly this: shard count is fixed at index creation and changing it requires a full reindex, §10.5). Choosing far too many costs per-partition overhead — every partition is a file handle, a memory structure, a metadata entry, and in Elasticsearch an entire Lucene index with its own heap cost, which is why "thousands of tiny shards" is a well-known ES anti-pattern.

What breaks. (a) Partition count too low → you can never grow past it without a reshard. (b) Partition map inconsistency → two routers disagree on where p0731 lives, so writes go to one node and reads to another; diagnosis is comparing the map version each router holds (§5.1). (c) Uneven partition sizes → the map balances partition counts but the data is unevenly spread across partitions, so 256 partitions each is not 1/4 of the data each; the fix is to balance by measured bytes/QPS, not by count, which is what MongoDB's balancer and CockroachDB's allocator actually do.

Tie-back: without this indirection, every capacity change is a full data migration. With it, capacity changes are a table update plus a background copy — which is the difference between sharding being operable and sharding being a once-a-year crisis.

2.3Sub-Concept: Shard Key (Partition Key)#

The shard key is the column(s) whose value determines which shard a row lives on (e.g., user_id). A function shard = f(shard_key) maps every row to exactly one shard. This choice governs everything — data distribution, which queries are fast (single-shard) vs slow (scatter-gather), and whether you get hot spots. Section 4 is dedicated to it.

Where it sits, precisely. The shard key is not a new column you add; it is a designation you place on one or more existing columns, and that designation lives in three places at once. (1) In the routing layer's configuration — Vitess calls it the vindex, MongoDB stores it in the config servers' config.collections document, Cassandra encodes it in the PRIMARY KEY ((partition_key), clustering_key) declaration in your CREATE TABLE, DynamoDB fixes it at table creation as the HASH key. (2) In every query your application writes, implicitly: a query that includes the shard key in its WHERE clause is routable, and one that does not is a fan-out. (3) In the physical layout on disk, because rows sharing a shard key value are guaranteed to be co-located on the same node, and in most systems physically adjacent within that node.

A worked routing example, end to end. Schema: orders(order_id, customer_id, total_cents, created_at), shard key customer_id, 8 shards, hash strategy.

  App:   SELECT * FROM orders WHERE customer_id = 40021 AND created_at > '2026-01-01'
  Router: murmur3(40021) = 0x9C4A1B77 = 2621578103
          2621578103 % 8 = 7          ->  shard 7  (node db-07)
  db-07:  index scan on (customer_id, created_at), 12 rows, 3 page reads, 0.4 ms

versus the query that has no shard key:

  App:   SELECT * FROM orders WHERE total_cents > 100000
  Router: shard key absent -> cannot route -> broadcast to shards 0..7
          8 parallel queries, merge 8 result sets, latency = max(8 latencies)

That contrast — 0.4 ms versus the slowest of eight — is the shard key's entire significance, and §2.11 gives the arithmetic of why the second one is so much worse than it looks.

Single-column vs compound. The shard key may be one column (customer_id) or several ((tenant_id, user_id)). With a compound key the routing function consumes the columns in order, which means a query supplying only the prefix may still be routable in a range scheme (all tenant_id = 9 rows are contiguous) but is not routable in a hash scheme (hashing (9, ?) is impossible without the second column). This prefix asymmetry is one of the sharpest practical distinctions between range and hash partitioning and it catches people constantly.

What breaks. (a) The shard key is immutable in most systems — MongoDB only allowed updating a document's shard key value from version 4.2, and even then it is an expensive internally-distributed transaction that may move the document between shards; DynamoDB and Cassandra simply do not permit it (you delete and re-insert). So choosing a mutable attribute (a user's country, a subscription plan_tier) as a shard key is a design error that surfaces months later as "we cannot let users change their region." (b) A null or missing shard key value has to go somewhere, and systems differ: MongoDB treats missing as null and puts all such documents in one chunk, which is an instant hot spot. (c) A shard key with low cardinality caps your shard count at the number of distinct values (§4.6).

Tie-back: the shard key is the function argument in shard = f(shard_key). Everything else in this file — strategy choice, hot spots, cross-shard pain, resharding cost — is downstream of what you put in that argument.

2.4Sub-Concept: Routing / The Shard Map#

Something must translate "I want user_id = 42" into "go to shard 3 on node db-07." This mapping is the routing layer, and where it lives is a design decision (client-side, a proxy, or a coordinator — Section 5.1). The shard map (which shards exist, on which nodes, which key ranges) is critical metadata that must be highly available and consistent.

What the shard map physically contains. It is a small table — kilobytes to a few megabytes, never gigabytes — with roughly this shape:

| partition | key_range_start | key_range_end | primary_node | replicas          | state    | version |
|-----------|-----------------|---------------|--------------|-------------------|----------|---------|
| p0731     | 0x9C00...       | 0x9CFF...     | db-07        | db-12, db-19      | ACTIVE   | 4471    |
| p0732     | 0x9D00...       | 0x9DFF...     | db-07        | db-12, db-19      | MOVING   | 4471    |
| p0733     | 0x9E00...       | 0x9EFF...     | db-03        | db-08, db-15      | ACTIVE   | 4471    |

Every field earns its place. **partition is the logical id from §2.2. key_range_start/end** exist because most real systems route by hash range rather than by modulus — the router does a binary search over sorted ranges rather than a division, which is what allows a range to be split in two later without touching any other range (§5.6). **primary_node is where writes go. replicas is where the copies live (Section 6). state** is the field that makes online migration possible: values like ACTIVE, MOVING, SPLITTING, READ_ONLY tell the router to behave differently — a partition in MOVING may need writes sent to both source and destination, and a partition in READ_ONLY rejects writes for the few hundred milliseconds of a cutover (§5.7). **version is a monotonically increasing epoch number stamped on the whole map; every request a router sends carries the version it believes in, and a data node that holds a newer version rejects the request with a "stale routing" error, forcing the router to refresh. That last mechanism — MongoDB calls it the shard version** / StaleConfig error, and it is genuinely how mongos avoids sending a query to a shard that no longer owns the data — is the difference between a rebalance being safe and a rebalance silently losing writes.

Where the map is stored. It cannot live in the sharded database itself (chicken and egg: you would need to route to find the routing table), so it lives in a small, strongly consistent, separately replicated store:

Sub-Concept: consensus, in one paragraph, because "strongly consistent metadata store" is doing a lot of work above. A consensus protocol (Raft, Paxos — File 18) lets a group of machines agree on an ordered log of decisions such that a majority (quorum) must acknowledge each decision before it counts, and any subsequent read that also touches a majority is guaranteed to see it. With 3 nodes, a quorum is 2, so the system tolerates 1 failure; with 5 nodes, a quorum is 3 and it tolerates 2. The practical property you are buying for your shard map is: there is never more than one valid version of the map, and a surviving majority always knows the latest one. That is why you do not store your shard map in a plain replicated cache — an async replica can serve a stale map, and a stale map is the mechanism by which a rebalance corrupts data.

How routers stay current. Every router caches the map in memory (a lookup must be nanoseconds, not a network hop) and refreshes it by one of three mechanisms: watch/subscribe (etcd and ZooKeeper both offer a watch that fires on change — lowest latency, used by Vitess), periodic poll (simple, bounded staleness equal to the poll interval), or lazy invalidation on error (the StaleConfig mechanism above — the router only learns the map changed when a data node tells it off, which is beautifully economical because it costs nothing in the common case).

What breaks. (a) Map store unavailable → new routers cannot start and existing ones run on their cached copy; a well-built system degrades to "keeps working until the topology changes," a badly built one takes an immediate outage. Mitigation: cache aggressively, treat the map as available-if-stale for reads, and never make the map store a synchronous dependency of the read path. (b) Split-brain in the map → two routers with different maps write the same key to two nodes; this is the data-loss scenario, and versioning + consensus is the defense. (c) Map too big → if you keyed the map per-user rather than per-partition, it stops being kilobytes and becomes a database of its own, which is precisely the directory strategy of §3.4 and comes with the costs described there.

Tie-back: routing is the layer that makes N databases look like one. Everything about how invisible sharding is to your application is a property of this layer.

2.5Sub-Concept: Scatter-Gather (Fan-out Query)#

A query that cannot be answered by one shard (e.g., "find all orders over $1000" when sharded by user) must be sent to every shard, and the results merged. This is a scatter-gather (or fan-out) query. It's slow (as slow as the slowest shard — tail latency), resource-heavy, and doesn't scale. Good shard design minimizes scatter-gather by aligning the shard key with the common query pattern.

The mechanism, step by step. A scatter-gather has four phases, and each has its own cost. (1) Scatter: the router opens (or reuses from a pool) a connection to all N shards and dispatches the query to each — N network sends, and if the router is single-threaded that is N sequential syscalls before the first shard even starts working. (2) Execute: each shard plans and runs the query independently against its own slice. Note that each shard must do the full work — a WHERE total_cents > 100000 with no index is a full scan on every shard, so the total I/O is identical to the unsharded case, merely spread out; sharding did not make this query cheaper in aggregate, it only parallelized it. (3) Gather: the router waits for all N responses. It cannot return early, because any shard might hold a matching row. (4) Merge: the router combines the results — a union for a plain filter, a k-way merge if there is an ORDER BY (walk N sorted streams, repeatedly emit the smallest head — O(R log N) for R total rows), a sum-of-sums for COUNT, and something much nastier for AVG, DISTINCT, GROUP BY, or LIMIT ... OFFSET (§5.10).

Worked example with real numbers. 16 shards. A single-shard point read takes 1 ms at p50 and 20 ms at p99 (the p99 being caused by a GC pause, a checkpoint flush, a cold page, or a noisy neighbour — every real system has this tail). A scatter-gather across all 16 waits for the slowest of 16 independent samples. The probability that all 16 come back under the p99 is 0.99¹⁶ ≈ 0.851, so 14.9% of your fan-out queries are dragged to ≥20 ms — that is, the fan-out query's p85 is your single-shard p99. §2.11 develops this properly, but hold the shape of it: fan-out converts a rare tail event into a common one.

Resource cost, which is the part people miss. A scatter-gather to 16 shards consumes 16 shards' worth of CPU, 16 connections, and 16 query-planner invocations to serve one user request. If 5% of your traffic is fan-out at 1,000 QPS, that is 50 fan-out queries/sec × 16 = 800 shard-queries/sec of pure overhead, and it grows with both your traffic and your shard count. This is the precise sense in which "scatter-gather doesn't scale": adding shards makes single-shard queries cheaper and fan-out queries more expensive, so the fraction of fan-out traffic sets a ceiling on how far you can usefully shard.

What breaks, and how to see it. The pathology is a fan-out query that becomes a cluster-wide amplifier: one expensive analytical query issued from a dashboard hits all 16 shards, saturates their buffer pools by pulling in cold pages, and degrades every unrelated single-shard query on every node simultaneously — a single query causing a total outage. Mitigations, in order of preference: (a) design the shard key so the query is single-shard (§4); (b) maintain a global secondary index on the filtered column (§5.4) so the query becomes single-shard-per-lookup; (c) send analytical queries to an OLAP store (§2.14) instead of the OLTP shards; (d) enforce per-query shard limits and timeouts in the router, returning partial results rather than letting one query touch everything; (e) hedge the stragglers (§12.2). Diagnosis: instrument every query with "number of shards touched" and alert on the ratio — a healthy sharded system has a fan-out ratio close to 1.0.

Tie-back: scatter-gather is the tax you pay for every query that does not name the shard key, and the entire art of §4 is arranging for your frequent queries not to pay it.

2.6Sub-Concept: Hot Spot / Data Skew#

A hot spot is a shard that receives disproportionate data or traffic while others sit idle — defeating the purpose of sharding. Caused by a poorly chosen shard key (e.g., sharding by country when 60% of users are in one country) or a celebrity/whale (one user with billions of rows). Data skew is uneven data distribution; load skew is uneven request distribution. Both are enemies.

Why they are different, and why the difference decides the fix. Data skew means shard 3 holds 400 GB while shard 5 holds 40 GB. Its symptom is a disk filling up, a buffer-pool hit ratio falling on one node, and slow backups for one shard. Its fix is rebalancing — move partitions, or split the big one (§5.6). Load skew means shard 3 serves 8,000 QPS while shard 5 serves 400, even if they hold identical amounts of data. Its symptom is CPU and I/O saturation on one node while the fleet averages 15% utilization. Its fix is not necessarily rebalancing, because moving the hot partition just makes a different node hot — the fix is to split the hot key's traffic (salting, §4.8), cache in front of it (File 02), or add read replicas for that shard specifically. Confusing the two produces the classic wrong action: running a rebalancer against a load-skew problem, which moves terabytes across the network to achieve nothing. Always ask: is the imbalance in bytes or in requests?

Quantifying skew so you can alert on it. Two numbers are worth computing. The imbalance ratio = max_shard_metric / mean_shard_metric; 1.0 is perfect, and anything above ~1.5 is worth investigating. The Gini coefficient or simply the p99/p50 ratio across shards captures whether one shard is an outlier versus the whole distribution being lumpy. Worked example: 16 shards, total 1.6 TB. Perfect balance is 100 GB each. Observed max is 340 GB → imbalance ratio 3.4 → you are effectively running a 16-node cluster with the capacity ceiling of a 4.7-node one, because your cluster is full when the biggest shard is full, not when the average is.

The four distinct causes, because the cure differs for each.

What breaks. The failure mode is not gradual. A hot shard's latency stays flat as utilization climbs to about 70%, then rises hyperbolically — this is basic queueing theory: with arrival rate λ and service rate μ, the wait time is proportional to ρ / (1 − ρ) where ρ = λ/μ, so at 70% utilization the queue multiplier is 2.3, at 90% it is 9, and at 95% it is 19. Utilization is not linear in pain. The practical consequence is that a hot shard looks fine on a dashboard right up until it does not. Diagnosis: per-shard dashboards (never fleet averages — an average hides exactly the thing you are looking for, §7.6), per-shard p99 latency, and top-K key sampling on the hot shard to find whether one key is responsible.

Tie-back: you sharded to divide work by N. Skew is the failure of that division, and a cluster with an imbalance ratio of 4 has bought you a quarter of the capacity you paid for.

2.7Sub-Concept: Resharding / Rebalancing#

Over time you add nodes (growth) or a shard gets hot. Resharding is redistributing data across a changed set of shards/nodes. This is one of the hardest operational problems in databases — moving live data while serving traffic without downtime or inconsistency. The sharding strategy (Section 3) largely determines how painful resharding is.

3Partitioning Strategies — Exhaustive Breakdown#

How do you map a shard key to a shard? Four canonical strategies.

3.1Range-Based Partitioning#

Mechanism: Assign contiguous ranges of the shard key to shards. E.g., user_id 1–1M → shard 1, 1M–2M → shard 2. Or by date: Jan → shard 1, Feb → shard 2.

3.2Hash-Based Partitioning#

Mechanism: Compute hash(shard_key) and assign by hash mod N (or by hash ranges). Hashing scrambles keys so they distribute uniformly.

3.3Consistent Hashing (preview → File 06)#

Mechanism: Map shards and keys onto a hash ring; a key belongs to the next shard clockwise. Adding/removing a node remaps only ~1/N of keys instead of nearly all. Virtual nodes smooth out distribution.

3.4Directory-Based (Lookup Table) Partitioning#

Mechanism: Maintain an explicit lookup service / directory that maps each key (or key range, or tenant) to its shard. Routing consults the directory.

3.5Strategy Comparison#

4Choosing a Shard Key (the whole ballgame)#

The shard key decision is the most consequential and least reversible decision in a sharded system. A good key is judged on three criteria:

4.1The Three Criteria#

4.2The Classic Trade-off: Even Distribution vs. Query Locality#

These two pull against each other:

The art is picking a key (often composite) that keeps your dominant query single-shard while distributing evenly. Example: an e-commerce orders table queried mostly "give me all of this user's orders" → shard by user_id (or hash(user_id)): every user's orders co-locate (locality) and users spread evenly (distribution). But "all orders in the last hour, globally" now scatters — accept that, or serve it from a separate analytics store.

4.3Composite / Compound Shard Keys#

Combine columns to get both properties: e.g., shard by hash(tenant_id) to distribute tenants evenly, then **cluster/sort within the shard by created_at so a tenant's recent-orders query is a fast in-shard range scan. Cassandra formalizes this as partition key (which shard) + clustering key** (sort order within the shard) — a crucial pattern to name in interviews.

4.4Handling the Whale / Celebrity Problem#

If one tenant/user is 1000× bigger than the rest, no single-key scheme spreads their data. Options:

4.5Why You Can't Easily Change It#

Once petabytes are laid out by f(shard_key), changing the key means re-reading and re-writing the entire dataset into a new layout — a massive, risky, often multi-month migration (double-writing, backfilling, cutover). This is why teams agonize over the shard key up front. "Choose your shard key like you can never change it."

5Deep-Dive Mechanics: Routing, Rebalancing, Cross-Shard Ops#

5.1Where Routing Lives#

5.2Rebalancing Done Right — Fixed Partitions#

Naive hash mod N rebalancing is catastrophic (change N → move almost everything). The professional technique: create many more logical partitions than nodes up front (e.g., 1024 partitions across 4 nodes = 256 each). To add a node, move whole partitions (not individual keys) from existing nodes to the new one until balanced. The number of partitions is fixed; only their node assignment changes. This is how DynamoDB, Elasticsearch, Riak, and Kafka-style systems rebalance with minimal disruption. Consistent hashing (File 06) is the other main answer.

During a move, the system typically: (1) copies the partition to the new node while still serving from the old, (2) catches up deltas, (3) atomically flips the shard map, (4) drops the old copy. All while live — hard, which is why you use battle-tested systems rather than hand-rolling.

5.3The Hard Part: Cross-Shard Operations#

Once sharded, several once-trivial operations become hard. Interviewers dig here.

Sub-Concept: Two-Phase Commit (2PC). 2PC coordinates an atomic commit across multiple databases. A coordinator asks all participants to PREPARE (do the work, lock, promise you can commit); if all vote yes, it sends COMMIT to all; if any votes no, it sends ABORT to all. Pros: gives atomicity across shards. Cons: it's blocking — if the coordinator crashes after PREPARE, participants are stuck holding locks indefinitely ("in doubt"); it's slow — each phase costs a network round trip to every participant plus an fsync (the syscall that forces a write from the OS's in-memory buffers all the way down to the physical disk — required so the "I promised to commit" record survives a crash, and expensive: ~ms on disk, the slowest single operation a database does) — and it hurts availability. Because of this, large-scale systems usually avoid cross-shard transactions entirely (design so transactions stay within one shard) or use Sagas (compensating transactions — full treatment in File 10) for eventual consistency instead.

5.4Secondary Indexes in a Sharded World#

An index on a non-shard-key column is a problem: the index entries for one value are spread across all shards.

6Replication vs. Partitioning (don't confuse them)#

A frequent interview trap. These are orthogonal and used together.

Real systems do both: shard the data into N partitions, and replicate each partition across (say) 3 nodes. So you get write scalability (sharding) and fault tolerance + read scaling (replication) simultaneously. Cassandra/DynamoDB/MongoDB all combine them. When you draw this: N shards × R replicas = a grid. (Replication consistency — sync vs async, quorums, leader/leaderless — is File 08's domain.)

7Operational Realities — Running a Sharded Fleet#

Everything up to here has been design. This section is what it is actually like to operate the result, and it is the part that decides whether sharding was a good idea. Interviewers at staff level probe here specifically, because a candidate who has only read about sharding talks about shard keys, while a candidate who has lived with it talks about schema migrations and backups.

7.1Schema migrations across N shards#

On one database, ALTER TABLE users ADD COLUMN locale VARCHAR(8) is one statement. On 256 shards it is 256 statements that must all succeed, that will each take a different amount of time (shards differ in size), and that will leave your fleet in a mixed-schema state for the duration — some shards with the column, some without.

Why that mixed state is dangerous: your application is a single codebase talking to all shards. If the new code assumes the column exists, it breaks against shards not yet migrated. If the old code is still running when the migration lands, it must tolerate a column it does not know about. Both directions must work simultaneously.

The discipline that makes it safe is the expand/contract pattern, and it is worth learning as a general rule rather than a sharding trick:

Each step is independently reversible, which is the entire point. The cost: a one-statement change becomes a multi-day, five-deploy procedure. The benefit: at no moment is there a state where a rollback loses data. This is the price of a sharded fleet and it must be in your estimate when someone asks "how long will this feature take?"

The other trap: on MySQL and Postgres, some ALTER TABLE operations take a full table lock and rewrite the table, which on a 500 GB shard means hours of downtime for that shard. The tools that avoid it — pt-online-schema-change, gh-ost, or Postgres's concurrent index builds — work by creating a shadow table, copying rows in batches while capturing ongoing changes via triggers or the binlog, then swapping atomically. Know that these exist and why; "I'd use gh-ost so the migration doesn't lock the table" is a concrete, credible answer.

7.2Backups and restores#

The problem nobody thinks about until they need it. A backup of a sharded system is not one file — it is N backups, taken at N slightly different moments. If a customer's data spans shards (it usually does — the user is on shard 7, their orders on shard 7, but the global product catalogue on shard 2), a restore reassembles a set of snapshots that were never simultaneously true. There is no global consistent point in time unless you built one.

What you actually do about it, in increasing order of effort:

Restore time is the metric that matters, not backup time. A 20 TB dataset spread over 40 shards restores in parallel — that is sharding helping — but only if you have the spare capacity to restore onto and have rehearsed it. Rehearse restores; an unrehearsed backup is a hypothesis, not a safeguard.

7.3Monitoring a fleet instead of a machine#

With one database you watch one dashboard. With 256 shards, averages lie: mean CPU across the fleet at 40% can hide one shard pinned at 100% while the rest idle — and that one shard is a full outage for every user who lives on it.

Monitor distributions, not aggregates. The specific things to watch per shard, and why each matters:

Alert on the outlier, not the average. The alert that matters is "any shard above X," never "the fleet average above X."

7.4Capacity planning and when to split#

The question "when do we add shards?" has an arithmetic answer, and you should be able to give it. You are bounded by whichever of these arrives first, per shard:

That last one is the under-appreciated constraint and worth saying out loud in an interview: maximum shard size is often set by how long you can afford to spend rebuilding one, not by performance.

Plan the split before you need it. Splitting a shard is a data-movement operation that itself consumes I/O on a shard that is by definition already stressed. Doing it at 95% full during an incident is how a capacity problem becomes an outage.

7.5The organizational cost#

Sharding is not only a technical decision; it changes what your engineers can do without help. Ad-hoc queries stop working ("just run a SELECT COUNT(*)" now means fanning out to 256 machines and summing). Foreign keys across shards do not exist, so referential integrity moves into application code where it can be forgotten. Debugging requires knowing which shard a user is on before you can even look. New engineers need to learn the routing layer before they can ship.

This is the real content of the senior rule "don't shard prematurely." It is not that sharding is technically hard — it is that it permanently taxes every future piece of work. Exhaust the alternatives first, in this order, and say them in this order in an interview: query and index optimization → caching (File 02) → read replicas (File 08) → vertical scaling → archiving cold data out → functional/vertical partitioning by table → and only then horizontal sharding. Each of those is reversible in an afternoon. Sharding is not.

8Pros, Cons & Trade-offs#

8.1Benefits#

8.2Costs & Trade-offs#

The senior rule: Don't shard prematurely. Exhaust vertical scaling, read replicas, and caching first. Shard only when write throughput or data volume genuinely exceeds one machine — because you can't un-ring the complexity bell.

9Interview Diagnostic Framework (Symptom → Solution)#

10Real Implementations & Product Landscape#

"Shard the database" is a design; this is what you actually deploy. The most important distinction in this whole section, and the one most candidates miss, is who does the sharding: a proxy layered on top of ordinary databases, or a database that shards itself natively. That choice determines your operational life far more than the partitioning strategy does.

10.1Family 1 — Sharding middleware over existing databases#

These sit between your application and a fleet of ordinary MySQL or Postgres instances, presenting the illusion of one database.

Vitess. Built at YouTube in 2010 to shard MySQL when a single instance could no longer hold the video-metadata workload, later open-sourced and now a CNCF project; it is the engine underneath PlanetScale. Its architecture is the thing to understand: vtgate is a stateless proxy that speaks the MySQL wire protocol (so your application and your ORM believe they are talking to plain MySQL), parses each query, consults the topology service for the shard map, and routes or scatters accordingly; vttablet sits beside each MySQL instance managing connection pooling, query rewriting, and health. Sharding is described by a VSchema declaring each table's sharding column and its vindex (the function mapping a column value to a keyspace ID — Vitess's abstraction over hash/lookup strategies). It supports online resharding by splitting keyspace ranges with live traffic, using replication to catch the new shards up and then cutting over.

ProxySQL is a lighter-weight MySQL proxy whose primary talents are connection pooling, read/write splitting, and query routing by rule. It can shard by routing rules, but it does not manage the shard map, resharding, or cross-shard queries for you — calling it a sharding solution overstates it; it is a routing and pooling layer that you can build simple sharding on top of.

Apache ShardingSphere is a JDBC-layer (or proxy-mode) sharding framework for the Java ecosystem, configuring sharding rules declaratively and adding read/write splitting, encryption, and distributed transactions. Best at: Java shops that want sharding inside the application's data-access layer with no new network hop. Limits: language-bound in JDBC mode, and the configuration surface is large.

10.2Family 2 — Postgres-family distribution#

Citus (acquired by Microsoft, now also the engine behind Azure Cosmos DB for PostgreSQL) is a Postgres extension, not a fork — which is its defining advantage: you keep real Postgres, its types, its extensions, and its SQL. It introduces three table kinds, and understanding them is understanding Citus: distributed tables (sharded by a distribution column across worker nodes), reference tables (replicated in full to every worker, so joins against them are always local — this is how you handle small dimension tables), and local tables (on the coordinator only). The critical concept is co-location: two distributed tables sharded on the same column have matching shards placed on the same node, so a join between them — and a transaction across them — is local and fast. Getting co-location right is the whole art of Citus modelling.

A distinction you must not blur: PostgreSQL's own declarative partitioning (PARTITION BY RANGE/LIST/HASH) and MySQL's partitioning split a table into pieces within a single server. That is partitioning, not sharding — it helps query pruning, bulk deletion of old data (drop a partition instead of a slow DELETE), and index size, but it does not add CPU, RAM, disk, or write throughput, because it is all still one machine. Candidates who answer "I'd partition the table" to a scaling question have answered a different question, and interviewers notice.

10.3Family 3 — Natively sharded operational databases#

MongoDB. Sharding is a first-class cluster mode with three component types: config servers (a replica set holding the authoritative chunk map), mongos (stateless routers the application connects to), and shards (each itself a replica set). Data is divided into chunks by shard-key range, and a balancer migrates chunks between shards to even out distribution. You choose ranged or hashed sharding: ranged preserves locality for range queries but a monotonically increasing key (a timestamp, an ObjectId) sends every insert to the same "max" chunk and creates the classic hot shard; hashed guarantees even write distribution and destroys range-query locality. Since 5.0 you can reshard a collection online, which historically you could not — this used to be the sharpest edge in MongoDB and is worth knowing as history.

Cassandra and ScyllaDB. Sharding is not a feature here, it is the architecture: every table's primary key splits into a partition key (which determines, via consistent hashing onto the token ring, which node holds the row — File 06) and clustering columns (which determine the sort order within the partition). Every node is equal; there is no coordinator tier. The consequence you must internalize: you model the schema per query, denormalizing aggressively, because a query that does not name the partition key becomes a cluster-wide scan and is effectively forbidden. Watch for large partitions (a partition key with unbounded rows — "all events for a customer" — grows until compaction and reads degrade; bucket it by time) and hot partitions. ScyllaDB is a C++ rewrite with a thread-per-core, shard-per-core design that materially improves per-node throughput and tail latency while keeping the Cassandra data model and protocol.

Amazon DynamoDB. Fully managed and sharded by design: items are placed into partitions by a hash of the partition key, with an optional sort key ordering items inside a partition. The limits that decide designs are concrete and worth memorizing: roughly 3,000 read units and 1,000 write units per partition per second, and 10 GB per partition for tables with local secondary indexes. Exceed a partition's throughput and you are throttled even though the table as a whole is far below its provisioned capacity — the hot-partition failure, made visible in your error rate. Adaptive capacity now shifts throughput toward hot partitions automatically and splits them, which softens but does not remove the problem. Also teach single-table design here: because there are no joins, experienced DynamoDB users store multiple entity types in one table with composite keys so that related items share a partition and are retrieved in one query. It is powerful and it is genuinely hard to learn.

HBase and Bigtable shard by contiguous row-key range into regions/tablets that split automatically as they grow. Range-sharding gives excellent scan locality and the same monotonic-key hot-spotting hazard (the standard fix is salting or field-swapping the row key). Best at: enormous tables with scan-heavy access; limits: operational weight (HBase brings HDFS and ZooKeeper with it).

10.4Family 4 — Distributed SQL (sharding you do not configure)#

These shard automatically and preserve SQL and ACID transactions across shards — the category exists precisely to remove the trade-off that the rest of this file describes.

CockroachDB splits data into ranges (~512 MB) that split and merge automatically, replicates each range by Raft (File 18), and designates a leaseholder per range to serve reads. Google Spanner does the same with Paxos groups plus TrueTime — an API exposing clock uncertainty as an interval, which lets Spanner order transactions globally with external consistency (File 19). YugabyteDB and TiDB occupy the same space (TiDB separating SQL from the TiKV storage layer with a Placement Driver managing regions).

10.5Family 5 — Search and analytics#

Elasticsearch/OpenSearch shards an index by hashing the document ID into a fixed number of primary shards chosen at index creation — and that number cannot be changed afterwards without reindexing into a new index (the _split and _shrink APIs relax this only by integer factors and require the index to be read-only during the operation). This makes shard-count planning uniquely consequential here: too few and you cannot spread load; too many and you pay per-shard overhead (each shard is a full Lucene index with its own memory and file handles) for nothing. The standard guidance is to size shards in the tens of gigabytes and to use time-based indices with aliases for log-style data so that "resharding" becomes "make tomorrow's index different."

ClickHouse uses a Distributed table as a routing façade over local shard tables, with the sharding expression chosen by you; queries are executed in parallel per shard and merged. Best at: analytical scans; limits: you own the sharding decision and rebalancing is a manual data-movement exercise.

10.6Comparison table#

10.7Decision rules#

10.8Anti-recommendations#

11Real-World Engineering Scenarios#

11.1Instagram — Sharding Postgres by User with Logical Shards#

Instagram (early, famous engineering post) sharded Postgres to scale user data:

11.2Discord — Cassandra (then ScyllaDB) for Trillions of Messages#

Discord stores messages in a Cassandra-family store:

11.3Uber — Schemaless / Sharded MySQL for Trips#

Uber built Schemaless, a sharded datastore on top of MySQL:

12Interview Gotchas & Failure Modes#

12.1Classic Questions#

12.2Failure Modes & Mitigations#

13Whiteboard Cheat Sheet#

        Single DB hits a wall:  storage full | writes maxed | working set > RAM
                                        │
                                        ▼  SHARD (horizontal partition across servers)
   ┌─────────── Router / Shard Map (HA) ───────────┐   f(shard_key) -> shard
   ▼                 ▼                 ▼            ▼
[Shard 1]        [Shard 2]        [Shard 3] ... [Shard N]     each also REPLICATED x3
 rows A-block      B-block          C-block        ...          (availability + read scale)

STRATEGY:   Range (fast scans, hot spots) | Hash (even, no ranges, mod-N pain)
            Consistent Hash (even + cheap resharding -> File 06) | Directory (flexible, extra hop)
SHARD KEY:  high cardinality + even + query-aligned (single-shard) + no monotonic hot spot
            composite = hash(tenant) partition-key + created_at clustering-key
HARD PARTS: cross-shard JOIN -> denormalize/app-join ; cross-shard TXN -> avoid / 2PC / Saga
            global IDs -> Snowflake/UUID ; analytics -> offload to OLAP warehouse
REBALANCE:  many fixed partitions, few nodes; move whole partitions (NOT mod N)
RULE:       don't shard until vertical scaling + replicas + cache are exhausted

One-sentence summary for an interviewer:

"Sharding is horizontal partitioning across machines to scale writes and storage past one server; the shard key is the make-or-break choice — it must be high-cardinality, evenly distributed, and aligned to your dominant query so reads stay single-shard — use hashing/consistent-hashing for even distribution, avoid cross-shard joins/transactions by co-locating related data (falling back to Sagas, not 2PC), always replicate each shard for availability, and don't shard until caching and read replicas are exhausted."

End of File 04. Next → File 05: Content Delivery Networks (edge caching, anycast, origin shielding).