Replication & Sharding

A single database node has finite capacity. When it can no longer handle your read throughput or your dataset outgrows its storage, you have two escalating options: replicate reads across multiple copies of the full dataset, or shard writes across multiple nodes each holding a slice of it. Replicas are the right first move — sharding is a last resort that introduces significant complexity.

Read Replicas

Most production workloads are read-heavy (often 80–90% reads). A read replica is an asynchronous copy of the primary database that serves read queries, offloading the primary so it can focus on writes.

How replication works

1. The primary writes every committed transaction to a replication log (binlog in MySQL, WAL in PostgreSQL).
2. Replicas tail that log and apply the same changes, typically with a lag of milliseconds to low seconds.
3. Reads are directed to replicas; writes go to the primary. The application or a proxy (ProxySQL, PgBouncer) handles routing.

Replication lag and stale reads

Because replication is asynchronous, a read immediately after a write may return stale data. Strategies to handle this:

1. Read-your-writes consistency — after a user performs a write, route their subsequent reads to the primary for a short window. Other users may still read from replicas.
2. Monotonic reads — ensure a user always reads from the same replica so they never see data "go backwards."
3. Strong consistency — route all reads to the primary. Eliminates stale reads but removes the load-balancing benefit entirely.

Sharding

Sharding (horizontal partitioning) splits a large dataset across multiple database instances — called shards — each holding a subset of the data. When a single database cannot hold 10 TB or sustain 100,000 writes/second, ten shards can each hold 1 TB and handle 10,000 writes/second. Unlike read replicas, every shard holds unique data — there is no full copy of the dataset on any single node.

Sharding strategies

1. Range-based — shard by a contiguous range of the key (e.g. user IDs 1–1M on shard A, 1M–2M on shard B). Simple to implement and supports range queries efficiently. Risk: hotspots if one range is much more active than others — newly registered users all land on the last shard, for example.
2. Hash-based — apply a hash function to the shard key and take the modulus (hash(userId) % numShards). Distributes load evenly and eliminates hotspots. Downside: adding or removing shards requires rehashing and migrating most of the data — solved by consistent hashing (see below).
3. Directory-based — a lookup table maps each key to its shard. Maximum flexibility; any key can be reassigned to any shard without rehashing. Downside: the directory itself is a bottleneck and single point of failure.

Choosing a shard key

The shard key is the most important design decision in a sharded system. A bad key is impossible to fix without a full migration.

1. High cardinality — the key must have enough distinct values to distribute data evenly. A boolean flag is a catastrophic shard key.
2. Write distribution — a monotonically increasing key (auto-increment ID, timestamp) with range sharding funnels all writes to the last shard. Use hash-based sharding or a random prefix to spread writes.
3. Query locality — ideally, most queries touch only one shard. Shard on the dimension you query by most often (e.g. user_id if most queries filter by user).

Challenges

1. Cross-shard queries — a query that spans multiple shards must be executed on each shard and the results merged in the application layer. Joins across shards are especially expensive and often infeasible at scale.
2. Cross-shard transactions — ACID transactions across shards require a distributed transaction protocol (two-phase commit), which is complex, slow, and a potential single point of failure.
3. Hotspots — a celebrity user, viral content, or monotonically increasing key can funnel disproportionate traffic to one shard. Mitigated by compound shard keys or splitting hot shards.
4. Resharding — adding new shards after launch requires redistributing data, which is operationally complex and risky. Consistent hashing minimises the data movement required.
5. Operational overhead — more database nodes means more backups, monitoring, and maintenance. Managed databases (Amazon Aurora, Google Spanner, PlanetScale) abstract much of this away.

Consistent Hashing

Standard hash-based sharding has a fatal flaw: if you change the number of shards, hash(key) % N produces different results for almost every key, requiring a massive data migration. Consistent hashing solves this by mapping both keys and shards onto a circular ring, so adding or removing a shard only relocates the keys that were closest to it — typically 1/N of the total keys.

How it works

1. The hash space is imagined as a circle from 0 to 2³².
2. Each server node is hashed to a position on the ring.
3. Each key is hashed to a position on the ring and assigned to the first node encountered clockwise from that position.
4. When a node is added, it takes over only the keys between itself and its predecessor — all other assignments are unchanged.
5. When a node is removed, its keys move to the next node clockwise.

Virtual nodes

With few physical nodes, consistent hashing can produce uneven load distribution — some nodes end up responsible for large arcs of the ring. Virtual nodes (vnodes) solve this: each physical node is hashed to multiple positions on the ring, making the distribution statistically uniform even with a small cluster. Cassandra and DynamoDB both use this technique.

Consistent hashing is also used in load balancers that need session affinity — the same client always reaches the same backend — and in distributed caches to minimise cache misses when the server pool changes.