Skip to content
Tutorials Center
My learning

Topics

Lesson 63 of 79 ยท Distributed Databases, NoSQL and Analytics

Replication, Sharding and Distributed Transactions

Understand leader-replica replication, horizontal and vertical partitioning, consistent hashing and two-phase commit, with runnable Python simulations of each.

One database server eventually hits a wall: it can fail, it may be too slow for the number of readers, or the data no longer fits on its disks. The classic answers are to keep copies of the data on several machines (replication) and to split the data across machines (partitioning, also called sharding). Both bring a new class of problems: copies can disagree, a request may need data from two machines, and a transaction that touches two machines must still be atomic.

This lesson covers leader-based replication, vertical and horizontal partitioning, consistent hashing for choosing a shard, and two-phase commit for distributed transactions. The three Python simulations are teaching models, not real distributed systems; the server configuration shown is read-only because the in-browser runners cannot start database servers. The next lesson, CAP, BASE and consistency models, explains the trade-offs behind these designs.

Two ideas, two goals

Replication Many copies. Availability and read scaling.
Partitioning Many slices. Storage and write scaling.

Real systems combine both.

1 / 2

Replication

Replication keeps copies (replicas) of the same data on several servers. It serves three purposes: availability (another copy takes over when a server fails), read scalability (queries are spread across replicas) and locality (a copy near the users in each region).

Leader and followers

The most common design is single-leader replication, historically called master-replica or primary-standby. All writes go to one server, the leader (primary). It records every change in a log, and the followers (replicas) apply that log in the same order. Reads may go to followers. Because only one server accepts writes, there are no write conflicts, which keeps the design simple.

The key choice is when the leader reports success:

  • Asynchronous: the leader commits locally and answers the client immediately; followers catch up later. Writes are fast, but if the leader dies, the most recent commits that no follower received are lost, and readers on a follower may see old data (replica lag).
  • Synchronous: the leader waits until at least one follower has stored the change. Nothing acknowledged is lost, but a slow or crashed follower stalls writes.
  • Semi-synchronous: one designated follower is synchronous, the others asynchronous. If it falls behind, another takes its role.

The simulation below keeps a log on a primary and two replicas that apply it at different speeds.

Python Asynchronous replication and replica lag

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A reader asking replica-2 sees a balance of 300 although the primary holds 500. A common remedy is "read your own writes": send a user's reads to the leader for a short time after they write.

Failover and leader election

When the leader fails, a follower must be promoted. Doing this safely is hard. The system must detect the failure (a missed heartbeat may just be a slow network), choose the most up-to-date follower, redirect clients and make sure the old leader, if it comes back, steps down instead of accepting writes (split brain). Distributed systems solve the choice with a consensus algorithm such as Raft or Paxos: servers vote, and a candidate needs a majority of votes to become leader, so two leaders can never be elected for the same term. Multi-leader and leaderless designs also exist; they allow writes on several nodes at the price of conflict resolution.

Here is the PostgreSQL and MySQL setup in outline. It is read-only, since it needs real servers.

INI
# PostgreSQL primary (postgresql.conf): read-only illustration
wal_level = replica
max_wal_senders = 10
synchronous_standby_names = 'FIRST 1 (replica1)'   # semi-synchronous: wait for one standby
SQL
-- MySQL 8.4 replica: read-only illustration
CHANGE REPLICATION SOURCE TO
  SOURCE_HOST = '10.0.0.5', SOURCE_USER = 'repl',
  SOURCE_PASSWORD = '********', SOURCE_AUTO_POSITION = 1;
START REPLICA;

Replication types and schemes

The leader-follower design above is one point in a larger space. Replication schemes can be classified in three ways: what is copied and when, which copies accept writes, and how much of the data each site holds.

Snapshot, transactional and merge replication

These three names come from the SQL Server world, but the ideas appear in most products under other names.

  • Snapshot replication copies the whole data set (or a whole table) to the target at scheduled times, replacing what was there. It is simple and needs no change tracking, but it moves everything every time, so it suits small or rarely changing data such as price lists and reference tables, where being hours out of date does not matter.
  • Transactional replication starts from an initial snapshot and then ships each committed change, in commit order, from the source (publisher) to the targets (subscribers) shortly after it happens. Targets are normally read-only. Latency is low and it is the model behind the leader-follower log shipping described above.
  • Merge replication lets every site, including disconnected ones such as laptops or mobile devices, change its own copy independently. Later the changes of all sites are merged, and conflicting changes are detected and resolved by rules. It fits occasionally connected users, at the price of conflict handling.

Master-slave, multi-master and peer-to-peer

  • Master-slave (leader-follower) is the single-writer design from earlier in this lesson. Only the master accepts writes, so there are no write conflicts and consistency is easy to reason about. The master is a write bottleneck and a single point of failure until a failover completes.
  • Multi-master lets several nodes accept writes for the same data and exchange the changes. Writes scale and users can write at their nearest site, even when sites cannot reach each other, but two sites may update the same row concurrently, so a conflict resolution policy is mandatory.
  • Peer-to-peer treats all nodes as equals: every node accepts reads and writes and replicates to its peers, with no designated master. Cassandra and Dynamo-style stores work this way, with tunable consistency (see CAP, BASE and consistency models). The model is closely related to multi-master and has the same conflict question.

Typical conflict policies are last-writer-wins (the highest timestamp survives, simple but it silently discards the other update), a site priority, application-specific merge rules, and mergeable data types such as counters or sets (CRDTs). The simulation shows two writable sites editing the same row while disconnected.

Python Multi-master conflict: last-writer-wins and a custom rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The city change did not conflict, because only site B touched it, so the merge keeps it. The phone number did conflict. Last-writer-wins converges (both sites compute the same answer) but loses site A's update without telling anyone, which is why important data needs a smarter rule or a design that avoids concurrent writes.

Full, partial and no replication

The third question is how much of the database each site stores. It is part of the allocation decision described in Distributed database types and fragmentation.

  • Full replication: every site holds a complete copy. Reads are always local and the system survives the loss of all sites but one. Every update must reach every site, so write cost and storage grow with the number of sites.
  • Partial replication: some pieces (fragments, tables) are copied to some sites, usually the ones that read them most. Heavily read reference data is copied widely while big transactional tables are kept in fewer places. This is the common real-world choice, but the system must track where every copy is.
  • No replication: each piece lives at exactly one site (plain partitioning). Storage is minimal and updates touch one site, but a site failure makes its data unavailable.

Finally, copies can be updated synchronously (the write returns after all or a quorum of copies have it: strong consistency, higher latency) or asynchronously (the write returns first and copies follow: low latency, temporary differences). The choice between them is the same trade-off that the CAP discussion in the next lessons formalizes.

Partitioning

Partitioning splits one logical table into parts. It comes in two shapes.

Vertical partitioning splits by columns. A wide table users(id, name, email, bio, avatar_blob) becomes users(id, name, email) plus user_profiles(id, bio, avatar_blob). Frequently used small columns stay together and fit more rows per page, while rarely used large ones live elsewhere. It is a design decision similar to normalization.

Horizontal partitioning splits by rows. Each partition holds a subset of rows with the same columns. Strategies:

  • Range: order_date in January goes to partition 1, February to partition 2. Great for time-series data and dropping old data, but a hot recent range creates a hotspot.
  • Hash: hash(user_id) mod N spreads rows evenly, but range queries touch every partition.
  • List: rows go to a partition by explicit value (country IN ('NO', 'SE')).

Partitions on one server speed up scans and maintenance (the optimizer skips partitions that cannot match, called partition pruning). When partitions live on different servers, we call it sharding. Sharding scales storage and write throughput, because each shard handles only its part, at a large cost in complexity: queries or joins across shards are slow, a cross-shard transaction needs a distributed protocol (below), and choosing the shard key badly (for example by country when most users are in one country) creates hot shards that are hard to repair.

SQL
-- PostgreSQL declarative partitioning: read-only illustration
CREATE TABLE measurements (
  sensor_id int, taken_at timestamptz NOT NULL, reading numeric
) PARTITION BY RANGE (taken_at);

CREATE TABLE measurements_2025_01 PARTITION OF measurements
  FOR VALUES FROM ('2025-01-01') TO ('2025-02-01');

Consistent hashing

With hash(key) mod N, adding a server changes N, so nearly every key moves to a different shard, and a re-sharding becomes a massive data migration. Consistent hashing avoids this. Hash both servers and keys onto the same circular space (a ring). A key belongs to the first server found going clockwise from the key's position. When a server joins, it takes over only the keys between itself and its predecessor; when one leaves, only its keys move. To even out the load, each physical server gets many points on the ring (virtual nodes).

flowchart LR
  K["key hash"] -->|"first server clockwise"| S["owning server"]
  S -.->|"server added: only a slice of keys moves"| N["new server"]

Keys map to the next server on the ring, so a topology change moves only nearby keys.

Python Consistent hashing versus hash modulo N

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Modulo hashing moves about three quarters of the keys when the fourth server arrives (the ideal for any scheme is one quarter: the new server's fair share). Consistent hashing moves close to that quarter, and every moved key goes to the new server. The last lines show why virtual nodes matter: with a single point per server the busiest server holds more than twice as many keys as the quietest, while 50 virtual nodes bring the ratio close to 1.

Distributed transactions and two-phase commit

Suppose placing an order must update the orders database, the payments database and the stock database, all on different servers. The transaction must still be atomic, as described in ACID properties: all three commit or none does. The standard protocol is two-phase commit (2PC), driven by a coordinator.

  1. Phase 1, prepare (voting). The coordinator asks every participant "can you commit?". Each participant makes the transaction durable in its log, keeps its locks, and answers YES (it has promised it can commit) or NO.
  2. Phase 2, decision. If all voted YES, the coordinator writes COMMIT to its own log and tells everyone to commit. If any voted NO (or timed out), it decides ABORT.

The weak point is the window between the votes and the decision. A participant that voted YES is in doubt: it can neither commit nor abort on its own, and it must hold its locks until it hears the decision. If the coordinator crashes in that window, participants are blocked. That is why 2PC is called a blocking protocol. Three-phase commit and consensus-based commit (Paxos Commit, Raft-backed transactions in systems like Spanner) reduce or remove the blocking at the cost of more messages. Many large systems avoid distributed transactions altogether with designs such as sagas (a sequence of local transactions with compensating actions).

Python Two-phase commit: success, abort and a coordinator crash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Run 1 commits everywhere. In run 2 a single NO forces every site to abort, preserving atomicity. Run 3 shows the blocking problem: all three participants stay PREPARED, holding locks, until the coordinator recovers and tells them what it decided.

What runs where

All three simulations here run live in your browser. Real replication, shard routers and 2PC (for instance the XA protocol supported by MySQL and PostgreSQL's PREPARE TRANSACTION) need several server processes and are shown only as read-only configuration. SQLite is an embedded single-file database and has no built-in replication, sharding or distributed commit.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In asynchronous leader-follower replication, what can happen if the leader crashes right after acknowledging a commit?

    With asynchronous replication the leader answers before followers have the change. If it dies, promoted followers may be missing the latest acknowledged writes.
  2. 2. Why does hash(key) mod N cause trouble when you add a server?

    Changing the divisor reshuffles nearly all assignments. Consistent hashing limits the movement to the keys the new server takes over.
  3. 3. In two-phase commit, a participant has voted YES and then the coordinator disappears. What is the participant's situation?

    A YES vote is a promise that it can commit. It cannot know whether other sites voted NO, so it can neither commit nor abort until the decision arrives.
  4. 4. Which choice describes horizontal partitioning?

    Horizontal partitioning divides the rows (by range, hash or list). Splitting columns is vertical partitioning, and copying is replication.
  5. 5. Two sites accept writes for the same row while disconnected and both change the same column. Which statement is true after a last-writer-wins merge?

    Last-writer-wins keeps the highest timestamp, so every site reaches the same value, but the other update is lost silently. Important data needs a custom rule.

Summary

  • Replication keeps copies for availability and read scaling; single-leader replication is simple, with a trade-off between fast asynchronous and safe synchronous commits, and failover needs consensus to avoid two leaders.
  • Replication schemes differ in what is copied (snapshot, transactional, merge), which nodes accept writes (master-slave, multi-master, peer-to-peer) and how much each site holds (full, partial or no replication); multi-master and peer-to-peer designs need a conflict-resolution rule such as last-writer-wins.
  • Partitioning splits data: vertically by columns, horizontally by rows (range, hash, list); partitions on different servers are shards, and the shard key decides balance and query cost.
  • Consistent hashing with virtual nodes moves only a small slice of keys when servers join or leave, unlike hash modulo N.
  • Two-phase commit gives atomic commits across sites but blocks participants if the coordinator fails at the wrong time.

Next: CAP, BASE and Consistency Models.