CS Fundamentals Trainer · Guides

Replication, partitioning and sharding

What each of the three tools scales, replication lag and read-your-writes, what an asynchronous failover loses, partition pruning, shard-key choice, hot shards and resharding, run on PostgreSQL and in Python.

26 min read

One database server has limits: it can only serve so many reads, store so much data, and survive only as long as the machine does. Three techniques push past those limits, and they are easy to confuse because they all "split or copy data". Replication keeps copies of the same data on several servers, to serve more reads and survive a failure. Partitioning splits one large table into pieces inside one database. Sharding splits the data across several independent database servers, so that each holds only a part. Each one solves a particular problem and brings a particular new one: stale reads and lost writes for replication, queries that skip the partition key for partitioning, hot shards and cross-shard work for sharding. I ran the replication and partitioning behaviour on PostgreSQL 16 (a primary with a streaming standby on one machine) and simulated the sharding effects in Python. The scripts are in the appendix; every figure is one run on a small machine, so trust the behaviour and not the exact numbers.

1. Three tools for three problems

ReplicationPartitioningSharding
What it doescopies the same data to other serverssplits one table into parts on one serversplits the data across servers
Helps withmore read capacity, availability, a copy to fail over tovery large tables, deleting old data, smaller indexeswrite capacity and data bigger than one machine (within the limits in section 4)
Does not help withwrite capacity (every copy repeats every write)a server that is out of CPU or diskqueries that need all the data
New problemreplicas are behind; a failover can lose writesa query without the partition key touches every parthot shards, cross-shard queries and transactions, resharding

Reach for them in this order, cheapest first: fix the slow queries and add the right indexes, add a cache, buy a bigger server, add read replicas, partition the big tables, and shard last. Each step adds permanent complexity.

2. Replication

In leader-follower (primary-standby) replication one server, the leader, accepts all writes and sends a stream of its changes (in PostgreSQL, the write-ahead log) to followers, which apply them in the same order and can serve reads.

Diagram: Leader-follower replication

Asynchronous replication means stale reads

With asynchronous replication the leader tells the client "committed" as soon as it has saved the write itself, and ships it to the followers afterwards. A follower is therefore always some distance behind, which is called replication lag. Usually that is milliseconds. When a follower is busy, far away or catching up it can be seconds or minutes, and then a user can write something and not see it.

To make this repeatable I set the standby to apply changes two seconds late (recovery_min_apply_delay = '2s'), wrote an order on the primary and read from the standby immediately: 0 rows. The write had committed; the follower had not applied it yet. The anomaly is called a violation of read-your-writes consistency. Related ones: monotonic reads (a user refreshes and sees an older state than before because the second read hit a more delayed follower) and consistent prefix (seeing an answer before the question).

Ways to cope, from simplest:

Synchronous replication buys safety with latency

With synchronous replication the leader waits for a follower before it acknowledges the commit. PostgreSQL lets you pick how far the follower must get:

synchronous_commitThe commit waits untilTime per commit (500 inserts, same machine)
localthe leader has flushed its own log0.35 ms
remote_writethe follower has received and written the log0.46 ms
onthe follower has flushed it to disk0.53 ms
remote_applythe follower has applied it, so reads there see it0.65 ms

On one machine with no network the cost is small and still grows with each stronger guarantee (+30%, +50%, +84% over local); across data centres every commit would also pay the round trip, which is typically milliseconds. remote_apply is the setting that removes stale reads on that follower.

The failover test: what asynchronous replication loses

I broke the standby's connection to the primary (the standby kept running, but could no longer receive changes), and let the primary commit ten more orders. All ten clients were told "committed". Then I crashed the primary and promoted the standby to be the new leader. It had 5 rows, not 15: the ten acknowledged orders existed only on the machine that had died. This is the risk of asynchronous replication: the data not yet shipped when the leader fails is lost (or must be reconciled by hand when the old leader returns).

The synchronous alternative costs availability. With synchronous_standby_names = '*' and the only standby stopped, reads on the primary still worked, but a write hung: my INSERT was still waiting after five seconds (I stopped it myself). The leader would rather wait than acknowledge a write that exists in one place only. That is the consistency-versus-availability trade of the CAP theorem in a single setting. The usual compromise is a quorum: wait for any one of several followers (ANY 1 (a, b, c) in PostgreSQL), so a single slow or failed follower does not stop writes but an acknowledged write still lives on at least two machines.

What a synchronous standby does and does not guarantee

Waiting for a follower improves durability or visibility, but only against the failures you assumed. Read each setting with its failure model:

So state the goal precisely: "no acknowledged write is lost if any one machine fails", or "any one availability zone", and check that the configuration, the promotion procedure and the monitoring all support that exact claim.

Replication slots and operational lag

A replication slot makes the primary keep every log (WAL) segment that a follower has not yet received, so a follower that falls behind or disconnects can catch up. The price is disk. I created a slot with no consumer and wrote about 100 MB of data per round: the primary's pg_wal directory grew from 33 MB to 337 MB in three rounds, and the slot reported 322 MB retained. A forgotten or stalled slot keeps growing until the disk is full, and a full disk stops the primary. After the slot was dropped and checkpoints ran, pg_wal began to shrink (241 MB after two checkpoints, as old segments are recycled gradually).

Operate it deliberately: monitor pg_replication_slots (restart_lsn, wal_status) and the lag columns of pg_stat_replication (write_lag, flush_lag, replay_lag), alert on retained WAL and on lag, drop slots nobody uses, and cap retention with max_slot_wal_keep_size so that a stalled consumer is cut off before it takes the primary down (at the cost of that follower having to be rebuilt). Long queries on a hot standby can also conflict with replay and either get cancelled or delay it (max_standby_streaming_delay), and hot_standby_feedback avoids the cancellations by making the primary keep old row versions, which bloats it.

Other things to know

3. Partitioning

Partitioning divides one logical table into physical parts by a partition key, inside a single database. Applications keep querying events; the database routes each row to the right part.

I created an events table with 1,200,000 rows, partitioned by month on created_at:

QueryPartitions scanned
WHERE created_at in March1 of 12 (the planner skips the rest: partition pruning)
WHERE user_id = 42 (not the key)12 of 12

The first query benefits from partitioning; the second pays for it, because the database cannot know which partition holds user 42, so it checks all twelve (each with its own index). Planning is also work per partition: the query that had to consider all twelve took about 1.2 ms to plan, against about 0.5 ms for the pruned one. So choose the key that most queries filter by, and keep the partition count in the tens or low hundreds, not tens of thousands.

The strongest use is removing old data. Deleting the oldest month (about 100,000 rows) from an unpartitioned copy with DELETE took 85.7 ms, and left dead rows for vacuum to clean up. On the partitioned table, DETACH PARTITION took 2.6 ms and DROP TABLE 7.1 ms: the whole month disappeared as a file, with no dead rows. At larger sizes the difference is much bigger, and retention becomes a scheduled job that creates next month's partition and drops the oldest.

Limits to remember: in PostgreSQL a primary key or unique constraint on a partitioned table must include the partition key, so "unique across all time" needs a different design; and partitioning does nothing for a server whose CPU or disk is full, because everything is still on one machine. It is the right step before sharding for a large time-series or log table.

4. Sharding

Sharding (horizontal partitioning across servers) places each row on one of several independent database servers, the shards, chosen from the shard key. Each shard holds a fraction of the data and handles a fraction of the writes, which makes it the only one of the three tools that can grow write capacity and total size beyond a single machine. It does not do so without limit: aggregate capacity is bounded by coordination overhead, hot keys that one shard must absorb, network bandwidth between the application and the shards, the size of the metadata and routing layer, and the cost of every operation that crosses shards (described below). The application, a router or a proxy layer must know which shard owns a row.

Diagram: Sharding by key

Choosing the shard key is the whole design

A good shard key has high cardinality, spreads load evenly, and is present in most queries, so that most requests go to one shard. Typical choices: the user id, the tenant id (see designing a multi-tenant system), or the order id. Three common ways to map a key to a shard:

Problems that appear

Adding a shard moves data. With hash(key) mod N, changing N changes the home of most keys. In the simulation (an illustration of key movement, not a forecast), going from 4 to 5 shards moved 79.7% of 100,000 keys, and from 10 to 11 shards 91.1%. A consistent-hash ring moved only 20.2% and 8.1%, close to the ideal 1/(N+1) (see consistent hashing). Real rebalancing also depends on how much data must be copied, where the virtual nodes land, shards of unequal capacity, and how the copy is kept consistent while writes continue. It is done in steps: copy the data to its new shard, keep the two in sync (dual writes or change capture), verify, switch reads, then delete the old copy.

Load is not as even as the key space. Even with a perfect hash, popularity is skewed. With 1,000,000 requests over 100,000 keys and a Zipf-like popularity (a few keys are very popular), the busiest of eight shards received 1.89 times the average load, and the single hottest key alone took 13.5% of all requests, all on one shard. Hashing cannot split one key. Mitigations: cache the hot key, split it into sub-keys (celebrity#1 to celebrity#16) with a read-time merge, or isolate it on its own shard.

Queries without the shard key must ask every shard (scatter-gather). The latency of the combined answer is that of the slowest shard, so the tail grows with the number of shards: if each shard is slow 1% of the time, the chance that at least one of them is slow is 1.0% for one shard, 7.7% for eight, 27.5% for thirty-two and 72.4% for 128. The same arithmetic as in observability. Design the data model so the common queries carry the shard key, and use a separate search index or a replicated copy for the others.

Joins, transactions and unique constraints cross shards. A join between rows on different shards must be done in the application or moved to a different place. A transaction that touches two shards needs two-phase commit or a saga (distributed transactions). A unique constraint (an email address) is only enforced inside one shard. Global auto-increment ids need a scheme (ranges handed to each shard, or time-ordered ids), and secondary indexes become either local (queried by scatter-gather) or global (maintained on another shard).

Because of this, many teams use a system that does the routing, the rebalancing and sometimes distributed transactions for them: Vitess (MySQL), Citus (PostgreSQL), or a distributed SQL database such as CockroachDB, YugabyteDB or Spanner. They remove most of the plumbing and none of the design decision: the shard key still has to suit your queries.

5. Choosing, in order

SymptomFirst thing to try
Slow queriesindexes, query plans
Same reads over and overa cache
Reads exceed one serverread replicas (decide which reads may be stale)
One table is huge, old data piles uppartitioning by time, with a retention job
Need a copy ready after a failurereplication with a failover process, and a tested restore from backup
Writes or total data exceed the largest serversharding, with a well-chosen shard key
Customers must be isolated or placed in regionssharding by tenant (cells)

6. Common mistakes

  1. Reading from a follower right after a write and expecting to see it.
  2. Treating replication as a backup.
  3. Promoting a follower without checking how far behind it was, or without fencing the old leader.
  4. Using synchronous replication to one follower and no plan for when that follower is down.
  5. Partitioning by a key that most queries do not filter on.
  6. Thousands of partitions, or no job that creates the next partition in time.
  7. Sharding too early, when an index, a cache or a replica would have been enough.
  8. A shard key that grows (timestamp, auto-increment) with range sharding, so one shard gets all the writes.
  9. hash(key) mod N with no plan for adding shards.
  10. Queries and transactions that need every shard on the hot path.

7. Things to mention in an interview

Questions interviewers like to add:

Quick recap

  1. Replication copies data (reads and availability), partitioning splits a table inside one server (manageability), sharding splits across servers (writes and size). Go in that order, cheapest first.
  2. Asynchronous followers are behind: a write was invisible on a standby for 2 s in the test, and the fix is to read your writes from the leader, pin the session, or wait for the log position.
  3. Stronger synchronous settings cost latency (0.35, 0.46, 0.53 and 0.65 ms per commit across four settings) and a down follower blocks writes.
  4. An asynchronous failover lost 10 acknowledged orders. Quorum replication protects them without waiting for every follower.
  5. A query filtered by the partition key scanned 1 of 12 partitions; one that was not scanned all 12. Dropping a month took about 10 ms against 86 ms to delete the same rows.
  6. The shard key is the design: a growing key piled every new order on one shard ([0, ..., 12500]), a hash spread them evenly.
  7. In the simulations, hash mod N moved 80% to 91% of keys when a shard was added and a consistent-hash ring moved about 1/(N+1); real rebalancing depends on data volume, node placement and the copy procedure. Skew still left one shard at 1.89 times the average, and scatter-gather queries make the tail worse with every shard.

Appendix: the experiment code

The replication scripts need the PostgreSQL 16 binaries and run as a non-root user; paths are the ones I used, so change B and R. Run setup.sh first and, for each experiment, run it again to start from a clean primary and standby.

Primary and standby on one machine (setup.sh)

B=/usr/lib/postgresql/16/bin; R=/var/tmp/repl
$B/pg_ctl -D $R/primary -m immediate stop >/dev/null 2>&1; $B/pg_ctl -D $R/standby -m immediate stop >/dev/null 2>&1
rm -rf $R/primary $R/standby
$B/initdb -D $R/primary -A trust >/dev/null
echo "host replication all 127.0.0.1/32 trust" >> $R/primary/pg_hba.conf
$B/pg_ctl -D $R/primary -o "-p 55433 -k $R -c listen_addresses=127.0.0.1" -l $R/primary.log -w start | tail -1
$B/pg_basebackup -h 127.0.0.1 -p 55433 -D $R/standby -R -X stream >/dev/null
chmod 700 $R/standby
$B/pg_ctl -D $R/standby -o "-p 55434 -k $R -c listen_addresses=127.0.0.1" -l $R/standby.log -w start | tail -1
psql -h $R -p 55433 -d postgres -At -c "select client_addr, state, sync_state from pg_stat_replication"
psql -h $R -p 55434 -d postgres -At -c "select pg_is_in_recovery()"

Stale reads and waiting for the log position (r1.sh)

R=/var/tmp/repl; P="psql -h $R -p 55433 -d postgres -X -q -At"; S="psql -h $R -p 55434 -d postgres -X -q -At"
$P -c "create table orders(id int primary key, note text)"
echo "== 1. a standby that is 2 seconds behind (recovery_min_apply_delay = 2s)"
$S -c "alter system set recovery_min_apply_delay = '2s'" -c "select pg_reload_conf()" >/dev/null; sleep 1
t0=$(date +%s.%N)
$P -c "insert into orders values (1, 'first')"
LSN=$($P -c "select pg_current_wal_lsn()")
echo "primary wrote order 1; read from the standby right away: [$($S -c 'select count(*) from orders where id=1')] rows"
echo "== 2. read-your-writes: wait until the standby has replayed the write's WAL position, then read"
until [ "$($S -c "select pg_last_wal_replay_lsn() >= '$LSN'::pg_lsn")" = "t" ]; do sleep 0.05; done
t1=$(date +%s.%N)
echo "waited $(echo "$t1 - $t0" | bc -l | cut -c1-4) s, then standby has: [$($S -c 'select count(*) from orders where id=1')] row"
$S -c "alter system reset recovery_min_apply_delay" -c "select pg_reload_conf()" >/dev/null
R=/var/tmp/repl; B=/usr/lib/postgresql/16/bin; P="psql -h $R -p 55433 -d postgres -X -q -At"; S="psql -h $R -p 55434 -d postgres -X -q -At"
$P -c "create table orders(id int primary key, note text)" -c "insert into orders select g, 'ok' from generate_series(1,5) g"
sleep 1
echo "== 3. asynchronous replication and a failover"
echo "standby has $($S -c 'select count(*) from orders') rows, primary has $($P -c 'select count(*) from orders')"
echo "the link between them breaks (standby loses its connection to the primary)"
$S -c "alter system set primary_conninfo = ''" -c "select pg_reload_conf()" >/dev/null; sleep 1.5
echo "streaming clients seen by the primary: $($P -c 'select count(*) from pg_stat_replication')"
$P -c "insert into orders select g, 'written after the link broke' from generate_series(6,15) g"
echo "10 more orders committed on the primary; the clients were told OK. Primary now has $($P -c 'select count(*) from orders') rows"
echo "the primary crashes"; $B/pg_ctl -D $R/primary -m immediate stop >/dev/null 2>&1
$B/pg_ctl -D $R/standby promote -w >/dev/null
echo "standby promoted to primary: it has $($S -c 'select count(*) from orders') rows, so 10 acknowledged orders are gone"

Synchronous commit levels and a missing standby (r4.sh)

R=/var/tmp/repl; B=/usr/lib/postgresql/16/bin; P="psql -h $R -p 55433 -d postgres -X -q -At"; S="psql -h $R -p 55434 -d postgres -X -q -At"
$P -c "create table t(n int)" -c "alter system set synchronous_standby_names = '*'" -c "select pg_reload_conf()" >/dev/null; sleep 1
echo "sync_state seen by the primary: $($P -c 'select sync_state from pg_stat_replication')"
echo "== 4. cost of waiting for the standby: 500 single-row commits per setting (one connection, same machine)"
for lvl in local remote_write on remote_apply; do
  { echo "set synchronous_commit = $lvl;"; for i in $(seq 1 500); do echo "insert into t values ($i);"; done; } > /var/tmp/repl/c.sql
  t0=$(date +%s.%N); $P -f /var/tmp/repl/c.sql >/dev/null; t1=$(date +%s.%N)
  echo "   synchronous_commit = $(printf '%-12s' $lvl) $(echo "($t1 - $t0) * 1000 / 500" | bc -l | cut -c1-5) ms per commit"
done
echo "== 5. the synchronous standby goes away"
$B/pg_ctl -D $R/standby -m fast stop >/dev/null 2>&1
echo "a plain read still works: $($P -c 'select count(*) from t') rows"
( time timeout 5 $P -c "insert into t values (-1)" ) 2>&1 | grep -E "real|ERROR|WARNING" ; echo "exit code of the insert (124 = still waiting after 5 s): ${PIPESTATUS[0]}"

Partitioning: pruning and dropping old data (part.sh)

This runs against a single server with a database called idem (change the -h, -p and -d options).

P="psql -h /var/tmp/pgscratch -p 55432 -d idem -X -q -At"
$P <<'S' >/dev/null
drop table if exists events, events_plain cascade;
create table events (id bigserial, user_id int not null, created_at timestamptz not null, payload text) partition by range (created_at);
do $$ begin
  for m in 1..12 loop
    execute format('create table events_2026_%s partition of events for values from (%L) to (%L)', lpad(m::text,2,'0'), make_date(2026,m,1), make_date(2026,m,1) + interval '1 month');
  end loop; end $$;
insert into events (user_id, created_at, payload)
select (random()*100000)::int, timestamptz '2026-01-01' + (random()*364 || ' days')::interval, repeat('x', 50) from generate_series(1,1200000);
create index on events (user_id); create index on events (created_at);
create table events_plain as select * from events; create index on events_plain (created_at);
analyze events; analyze events_plain;
S
echo "rows per partition (first 3): $($P -c "select string_agg(tableoid::regclass::text || '=' || c, ' ') from (select tableoid, count(*) c from events group by 1 order by 1 limit 3) x")"
echo "== partition pruning"
echo "WHERE created_at in March:        scans $($P -c "explain select count(*) from events where created_at >= '2026-03-05' and created_at < '2026-03-10'" | grep -o 'events_2026_[0-9]*' | sort -u | tr '\n' ' ')"
echo "WHERE user_id = 42 (not the key): scans $($P -c "explain select * from events where user_id = 42" | grep -o 'events_2026_[0-9]*' | sort -u | wc -l) of 12 partitions"
for q in "select count(*) from events where created_at >= '2026-03-05' and created_at < '2026-03-10'" "select count(*) from events where user_id = 42"; do
  echo "   $q"; $P -c "explain analyze $q" | grep -E "Execution Time|Planning Time"
done
echo "== removing the oldest month (about 100,000 rows)"
$P -c "\timing on" -c "delete from events_plain where created_at < '2026-02-01'" | grep Time
$P -c "\timing on" -c "alter table events detach partition events_2026_01" -c "drop table events_2026_01" | grep Time
echo "rows left: plain $($P -c 'select count(*) from events_plain') partitioned $($P -c 'select count(*) from events')"

Sharding simulations (shard.py)

Python 3, standard library only.

import bisect, collections, hashlib, random
random.seed(11)
h = lambda s: int.from_bytes(hashlib.sha256(str(s).encode()).digest()[:8], "big")

print("1. adding a shard: how many of 100,000 keys change shard?")
keys = range(100_000)
def ring(n, vnodes=100):
    pts = sorted((h(f"shard-{i}-{v}"), i) for i in range(n) for v in range(vnodes))
    hs = [p[0] for p in pts]
    return lambda k: pts[bisect.bisect(hs, h(k)) % len(pts)][1]
for n in (4, 10):
    a, b = (lambda k, n=n: h(k) % n), (lambda k, n=n: h(k) % (n + 1))
    moved_mod = sum(a(k) != b(k) for k in keys) / len(keys)
    ra, rb = ring(n), ring(n + 1)
    moved_ring = sum(ra(k) != rb(k) for k in keys) / len(keys)
    print(f"   {n} -> {n + 1} shards: hash(key) mod N moves {moved_mod:5.1%}; a consistent-hash ring moves {moved_ring:5.1%} (ideal {1 / (n + 1):5.1%})")

print("2. the shard key decides where the load lands: the newest 12,500 of 100,000 orders, with increasing ids, 8 shards")
ids = range(1, 100_001)
by_hash = [0] * 8
for i in range(87_501, 100_001): by_hash[h(i) % 8] += 1
by_range_new = [0] * 8
for i in range(87_501, 100_001): by_range_new[min(7, (i - 1) // 12_500)] += 1
print("   range sharding (ranges of 12,500 ids), orders 87,501 to 100,000 land on shards:", by_range_new)
print("   hash sharding, the same orders 87,501 to 100,000 land on shards:", by_hash)

print("3. skewed access: 1,000,000 requests over 100,000 keys, 8 shards, Zipf-like popularity")
weights = [1 / (r ** 1.1) for r in range(1, 100_001)]
reqs = random.choices(range(100_000), weights=weights, k=1_000_000)
load = [0] * 8
for k in reqs: load[h(k) % 8] += 1
print(f"   requests per shard {load}: busiest shard {max(load) / (sum(load) / 8):.2f}x the average")
top, topn = collections.Counter(reqs).most_common(1)[0]; print(f"   the single hottest key got {topn:,} requests ({topn / len(reqs):.1%}), all on shard {h(top) % 8}; hashing cannot spread one key across shards")

print("4. a query that does not include the shard key must ask every shard (scatter-gather)")
for n in (1, 8, 32, 128):
    print(f"   {n:>3} shards: chance that at least one answers slowly (1% slow each) = {1 - 0.99 ** n:5.1%}")

Sources

  1. PostgreSQL documentation, High availability, load balancing and replication, including log-shipping standby servers and synchronous replication.
  2. PostgreSQL documentation, Table partitioning. Range, list and hash partitioning, pruning and limitations.
  3. Martin Kleppmann, Designing Data-Intensive Applications, chapters 5 (replication) and 6 (partitioning). Replication lag anomalies, failover, and rebalancing.

Practise this topic: Databases

More guides