When one machine isn't enough: databases that span many computers

1 Why distribute a database?

Up to now in this course, every database we built lived on one machine — one disk, one buffer pool (recall Session 3), one set of indexes (Session 4). A distributed database is a single logical database whose data is stored on many machines (called nodes) that talk to each other over a network and cooperate to look like one database to the user.

The two big reasons to distribute

There are essentially two motivations, and it's worth keeping them separate in your head.

Scale up vs scale out

When a database gets overwhelmed, you have two choices:

• Scaling up (vertical scaling) — buy a bigger machine: more RAM, more CPU, faster disk. Simple, but expensive and capped — there is no infinitely large computer.
• Scaling out (horizontal scaling) — buy more machines and split the work among them. Cheaper commodity hardware, and (in principle) you can keep adding machines forever. Distributed databases are all about scaling out.

The catch: distribution creates brand-new problems

Spreading data across machines sounds great until you realise the machines must talk over a network — and networks are slow and unreliable. Here are the new headaches you sign up for:

2 Partitioning (sharding) & replication

These are the two fundamental techniques for spreading data across nodes. They solve different problems and are almost always used together.

Partitioning (a.k.a. sharding)

Partitioning (in many systems called sharding) means splitting one big dataset into smaller disjoint pieces called shards (or partitions), and putting each piece on a different node. Each row lives on exactly one shard. The goal is scalability: 10 nodes can hold 10× the data and serve roughly 10× the traffic.

The key decision is the partition key — the column whose value decides which shard a row goes to (e.g. user_id). There are two classic strategies:

SELECT * FROM users WHERE user_id = 8821;

// pick the shard for this key
shard = hash(8821) % 4   // e.g. → 1
route query to "shard-1" only

SELECT * FROM users WHERE created_at > '2026-06-13';

How queries find the right shard (routing)

Something has to know the map from "partition key → node". Three common designs:

Rebalancing

When you add nodes (to grow) or one dies, the data has to be moved so the load stays even — this is rebalancing. Naïve hash % N is terrible here: change N from 4 to 5 and almost every key remaps to a different shard, forcing a massive data shuffle.

Replication

Replication means keeping copies of the same data (each shard, or the whole database) on multiple nodes called replicas. Its goal is availability and durability: if one replica dies, another still has the data, so reads and writes can continue and nothing is lost.

The most common pattern is leader–follower (also called primary–replica): one replica is the leader that accepts writes, and it streams those changes to one or more followers that can serve reads.

3 Distributed transactions & Two-Phase Commit

Recall atomicity from our transactions session: a transaction is all-or-nothing. Easy on one machine. But what if a single transaction touches data on several nodes — say, move $100 from an account on shard A to an account on shard B? Now atomicity must hold across machines: either both nodes commit, or neither does. This is the atomic commit problem, and it's genuinely hard because any node (or the network) can fail at the worst possible moment.

Two-Phase Commit (2PC)

The classic solution is Two-Phase Commit (2PC). One node acts as the coordinator; the others are participants. As the name says, it runs in two phases.

The handshake, as a sequence diagram

Coordinator                Participant A        Participant B
     |                          |                    |
     |  ---- PREPARE ------->    |                    |
     |  ---- PREPARE ------------------------------>  |
     |                          | (log, then vote)   |
     |  <------- YES ----------- |                    |
     |  <------- YES ------------------------------   |
     |                          |                    |
   (all YES → decide COMMIT, log the decision)       |
     |                          |                    |
     |  ---- COMMIT -------->    |                    |
     |  ---- COMMIT ---------------------------->     |
     |  <------- ACK ----------- |                    |
     |  <------- ACK ------------------------------   |
     |                          |                    |
   (transaction is now committed everywhere)

The blocking weakness

2PC has one famous, fatal flaw. Suppose participants have all voted YES and are waiting for the decision — and right then the coordinator crashes. The participants are now stuck: they've promised to commit, so they can't unilaterally abort, but they also haven't heard "commit", so they can't proceed. They must hold their locks and wait, possibly for a long time, until the coordinator recovers. This is called blocking, and it makes the coordinator a single point of failure.

Beyond 2PC

Smarter protocols were invented to fix the blocking problem:

• Three-Phase Commit (3PC) — adds an extra "pre-commit" phase so participants can make progress even if the coordinator dies. It's non-blocking in theory, but assumes a more reliable network and is rarely used in practice.
• Consensus protocols — Paxos and Raft — instead of one fragile coordinator, a group of nodes agrees on each decision by majority vote. As long as a majority survives, the system keeps making progress with no single point of failure. Raft is the modern, easier-to-understand favourite and powers systems like etcd, CockroachDB, and TiDB. These protocols are also how a cluster reliably elects a new leader for replication (Topic 2) when the old one dies.

4 The CAP theorem

The CAP theorem (Eric Brewer, 2000) is the single most important idea in distributed databases. It says that during a network partition, a distributed system can guarantee at most two of these three properties:

Why it's really a choice between C and A

Here's the subtle but vital point: in any real distributed system, network partitions will happen — cables break, switches fail. You don't get to opt out of P. So the theorem really forces a choice that only matters during a partition: when two halves of your cluster can't talk, do you prioritise C or A?

CP vs AP databases in the real world

★ Putting it all together

You've reached the end — not just of this session, but of the entire DBMS course. Take a moment: that's a huge accomplishment. 🎉

The journey you just completed

Look back at how far you've come. The whole course was one long climb up the database stack:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• 📘 Class handout: "DBMS Session 16 — Distributed DBs + Final".

Papers, docs & deep dives

• CMU 15-445/645 Database Systems — the gold-standard university course; its distributed databases lectures cover sharding, 2PC, and replication in depth.
• Designing Data-Intensive Applications — Martin Kleppmann — the definitive modern book on partitioning, replication, transactions, and consistency. If you read one thing after this course, read this.
• Mohan, Lindsay & Obermarck — "Transaction Management in R*" (1986) — early, canonical work on the two-phase commit protocol for distributed transactions.
• Gilbert & Lynch — formal proof of Brewer's CAP conjecture (2002) — the paper that turned CAP from a conjecture into a theorem.
• The Raft Consensus Algorithm — the official site (with the paper and an animated visualization) for the modern consensus protocol that replaces fragile single coordinators.
• Amazon's Dynamo paper (2007) — the influential design behind AP systems, consistent hashing, and eventual consistency.