Database Scaling: Sharding & Replication

Indexing — the first lever, before anything distributed#

Before reaching for replication or sharding, most database performance problems are solved (or caused) by indexing. An index is an auxiliary data structure (usually a B-tree) that lets the database find rows without scanning the entire table.

CREATE INDEX idx_users_email ON users (email);

Without this index, SELECT * FROM users WHERE email = 'x@example.com' scans every row (O(n)). With it, the lookup is closer to O(log n) — the difference between milliseconds and seconds once a table has millions of rows. The trade-off: every index speeds up reads on that column but slightly slows down writes (the index must be updated too), and consumes additional storage.

Vertical scaling has a ceiling#

Adding more CPU/RAM/disk to a single database server (vertical scaling) is the simplest first step, but it has hard limits — eventually no single machine is big enough, and it remains a single point of failure regardless of size.

Read replication#

A primary-replica setup has one primary database that accepts all writes, replicating those changes to one or more read-only replicas. Read-heavy traffic (recall: most systems have far more reads than writes) is spread across replicas, while writes stay on the primary.

                     writes
Client -----------------------------> Primary DB
   |                                       |
   |  reads                    replicates  |
   v                                       v
Replica 1  <--------------------  Replica 2

Trade-off: replicas usually lag the primary by a small amount (replication lag), so a read immediately following a write might not see that write yet on a replica — a classic source of "I just saved this and it's not showing up" bugs if the application always reads from a replica.

Sharding (horizontal partitioning)#

Sharding splits a single logical database into multiple physical databases ("shards"), each holding a subset of the data — this is what actually removes the single-machine ceiling for both reads and writes.

Common sharding strategies:

• Range-based — shard by a value range (e.g., user IDs 1–1M on shard A, 1M–2M on shard B). Simple, but can create "hot shards" if traffic isn't evenly distributed across ranges.
• Hash-based — shard by hash(key) % number_of_shards. Distributes load evenly, but resharding (changing the number of shards) requires re-distributing almost all the data.
• Directory-based — a lookup service maps each key to its shard explicitly. Flexible and avoids the resharding problem, but the lookup service itself becomes a critical dependency.

shard = hash(user_id) % 4

user_id=101 -> hash % 4 = 1 -> Shard 1
user_id=205 -> hash % 4 = 3 -> Shard 3

Consistent hashing is a refinement that minimizes data movement when shards are added or removed — instead of nearly all keys remapping (as with plain % N), only a small fraction do. It's why systems like Cassandra and DynamoDB use it internally.

The real cost of sharding#

Sharding solves the scaling problem but introduces real complexity:

• Cross-shard joins/transactions become expensive or impossible — you generally can't JOIN across two physical databases efficiently.
• Choosing the shard key is a one-way door for a lot of systems — get it wrong (e.g., shard by a value that's rarely used in queries) and every query has to fan out to all shards.
• Rebalancing shards as data grows unevenly is genuinely hard operationally.

This is why sharding is usually a later step — reach for indexing, caching, and read replicas first; shard only once write throughput or total data volume on a single primary is the actual bottleneck.

Transactions and ACID, briefly#

• Atomicity — a transaction's operations all succeed or all roll back together.
• Consistency — a transaction moves the database from one valid state to another, respecting all constraints.
• Isolation — concurrent transactions don't see each other's uncommitted intermediate state.
• Durability — once committed, a transaction's changes survive a crash.

Sharded and distributed databases often relax some ACID guarantees (especially cross-shard atomicity) in exchange for scalability — a direct consequence of the CAP/PACELC trade-offs covered earlier in this track.

Common mistakes#

• Sharding before exhausting simpler options (indexing, caching, read replicas) — premature sharding adds enormous complexity for a problem that better indexing might have solved outright.
• Choosing a shard key that doesn't match the application's actual query patterns, forcing expensive cross-shard fan-out on nearly every request.
• Always reading from a replica without considering replication lag for data that was just written by the same user (a common fix: read-your-writes routing to the primary briefly after a write).

Interview questions#

Q: What's the difference between replication and sharding? Replication copies the entire dataset to multiple machines (primarily to scale reads and improve availability); sharding splits the dataset into disjoint subsets across multiple machines (to scale both reads and writes, and total storage, beyond what one machine can hold).

Q: How do you choose a good shard key? Pick a key that matches your dominant query pattern (so most queries hit a single shard) and distributes data (and load) evenly across shards, avoiding "hot" shards that get disproportionate traffic.

Q: What is replication lag and why does it matter? The delay between a write committing on the primary and that write becoming visible on a read replica. It matters because a client that writes and then immediately reads from a replica may not see its own write yet — a common source of confusing bugs in naively-built read/write-split systems.