Chapter 41 of 41

Distributed Databases & CAP Theorem

When you book a train ticket, pay with UPI or scroll a social feed, your request is almost never served by one computer. The data lives on many servers, often in several cities, and those servers must cooperate to give you one consistent answer, even when some of them crash or the network between them breaks.

A database spread across multiple machines like this is a distributed database. The previous chapter, NoSQL Databases, showed why large systems scale out. This chapter explains how data is split and copied across sites, how a transaction commits on several machines at once, and the fundamental limit every distributed database faces: the CAP theorem.

A distributed database is a single logical database whose data is stored across multiple sites (computers) connected by a network, managed so that users can query it as if it were one database.


Why Distribute a Database?

  • Scalability: more data and more requests than one machine can handle.

  • Availability and reliability: if one site fails, copies on other sites keep the system running.

  • Locality: keep data close to the users who use it most (Mumbai data in Mumbai, Delhi data in Delhi), reducing latency.

  • Organisational reasons: branches or departments that own their own data but still need a combined view.

The price is complexity: queries may need data from several sites, transactions must commit atomically on many machines, and the network can be slow or fail.

Homogeneous vs Heterogeneous

  • Homogeneous: every site runs the same DBMS software and cooperates closely (for example, a MySQL or Cassandra cluster).

  • Heterogeneous (federated / multidatabase): sites run different DBMSs or schemas, and a middleware layer integrates them. Harder to manage, often with weaker transaction guarantees.

Transparency

A good distributed DBMS hides its distribution from users:

  • Location transparency: users do not need to know which site holds the data.

  • Fragmentation transparency: users query the whole table, not the pieces.

  • Replication transparency: users do not need to know how many copies exist or which copy they read.


Data Fragmentation

Fragmentation splits a relation into smaller pieces (fragments) that can be stored at different sites. Three rules make a fragmentation correct:

  1. Completeness: every tuple (or attribute) of the original relation appears in some fragment. Nothing is lost.

  2. Reconstruction: the original relation can be rebuilt from the fragments (by union or join).

  3. Disjointness: for horizontal fragments, a tuple belongs to only one fragment (vertical fragments deliberately repeat the key).

Horizontal Fragmentation

Split the rows using selection conditions: each fragment is σcondition(R). Reconstruction is the union of the fragments.

Example on the employees table of our company_db sample database (run in a scratch copy): keep Engineering employees at the Bengaluru site and everyone else at another site.

CREATE TABLE emp_eng   AS SELECT * FROM employees WHERE dept_id = 10;
CREATE TABLE emp_other AS SELECT * FROM employees WHERE dept_id <> 10;

SELECT (SELECT COUNT(*) FROM emp_eng)   AS eng_rows,
       (SELECT COUNT(*) FROM emp_other) AS other_rows,
       (SELECT COUNT(*) FROM employees) AS total_rows;
+----------+------------+------------+
| eng_rows | other_rows | total_rows |
+----------+------------+------------+
|        3 |          6 |         10 |
+----------+------------+------------+

3 + 6 = 9, but the table has 10 rows. The fragmentation is not complete! Which row went missing?

SELECT emp_id, name, dept_id FROM employees
WHERE emp_id NOT IN (SELECT emp_id FROM emp_eng UNION ALL SELECT emp_id FROM emp_other);
+--------+--------------+---------+
| emp_id | name         | dept_id |
+--------+--------------+---------+
|     10 | Ishita Gupta |    NULL |
+--------+--------------+---------+

Ishita has no department (dept_id is NULL). NULL = 10 and NULL <> 10 are both unknown in SQL, so she satisfied neither condition. Fixing the second predicate and running the same count query again:

DROP TABLE emp_other;
CREATE TABLE emp_other AS SELECT * FROM employees
WHERE dept_id <> 10 OR dept_id IS NULL;
+----------+------------+------------+
| eng_rows | other_rows | total_rows |
+----------+------------+------------+
|        3 |          7 |         10 |
+----------+------------+------------+

Now 3 + 7 = 10: complete and disjoint, and emp_eng UNION ALL emp_other rebuilds the table. This is a real design bug that happens in practice: fragmentation predicates must cover every possible value, including NULL.

Vertical Fragmentation

Split the columns using projection: each fragment is πattributes(R). Every fragment must include the primary key, otherwise the pieces cannot be joined back. Reconstruction is a join on the key.

Example: keep public information on one site and confidential payroll data on a more secure site.

CREATE TABLE emp_public  AS SELECT emp_id, name, dept_id, city FROM employees;
CREATE TABLE emp_payroll AS SELECT emp_id, salary, hire_date FROM employees;

-- reconstruct (first four employees)
SELECT p.emp_id, p.name, p.city, s.salary
FROM emp_public p JOIN emp_payroll s ON p.emp_id = s.emp_id
WHERE p.emp_id <= 4 ORDER BY p.emp_id;
+--------+--------------+-----------+-----------+
| emp_id | name         | city      | salary    |
+--------+--------------+-----------+-----------+
|      1 | Aarav Sharma | Bengaluru | 150000.00 |
|      2 | Priya Iyer   | Chennai   |  95000.00 |
|      3 | Rohan Mehta  | Bengaluru |  95000.00 |
|      4 | Sneha Kapoor | Mumbai    | 110000.00 |
+--------+--------------+-----------+-----------+

This is a lossless join for the same reason as in Lossless Join & Dependency Preservation: the common attribute emp_id is a key of both fragments.

Hybrid (Mixed) Fragmentation

Apply both: for example, split employees vertically into public/payroll, then split the public fragment horizontally by region.

In modern systems, horizontal fragmentation is usually called sharding or partitioning, and the condition is often a hash or range of a shard key rather than a hand-written predicate.


Data Replication

Replication stores copies of the same data at multiple sites.

Advantages

Disadvantages

Higher availability: if one copy's site fails, others can serve

Every update must reach every copy

Faster reads: read from the nearest copy

Copies can disagree (inconsistency) if updates are not coordinated

Read load spread across sites

More storage and more concurrency-control complexity

Synchronous vs Asynchronous Replication

  • Synchronous: a write is acknowledged only after the replicas have it. Copies stay consistent, but writes are slower and can stall if a replica is unreachable.

  • Asynchronous: the primary acknowledges first and sends changes to replicas later. Fast writes, but replicas lag behind (replication lag), and recently committed data can be lost if the primary fails before shipping it.

Classic MySQL replication is asynchronous by default (a source server ships its binary log to replicas); semi-synchronous replication and Group Replication offer stronger guarantees.

Primary-Copy vs Multi-Leader

  • Primary copy (single leader): all writes for an item go to one designated copy, which propagates them. Simple ordering of updates.

  • Multi-leader / leaderless: writes can go to several copies. Better availability for writes, but conflicting concurrent updates must be detected and resolved.

Quorums

Leaderless systems (for example Cassandra, and the Amazon Dynamo design) often use quorums. With N copies, a write waits for W acknowledgements and a read contacts R copies.

If R + W > N, every read set overlaps every write set in at least one copy, so a read always contacts at least one copy that has the latest acknowledged write.

For N = 3 (checking every possible choice of copies):

W

R

R + W

Read always sees latest write?

1

1

2

No

2

1

3

No (3 is not > 3)

2

2

4

Yes (common "quorum" setting)

3

1

4

Yes, but any one replica down blocks writes

1

3

4

Yes, but any one replica down blocks these reads

The table shows the core trade-off of this chapter in miniature: stronger guarantees need more copies to respond, which means less tolerance for failures.


Distributed Transactions and Two-Phase Commit (2PC)

Suppose a transaction transfers money from an account stored at site A to an account stored at site B. Atomicity (from Transactions & ACID Properties) demands that both sites commit or both abort. But each site decides independently and either could crash at any moment. How do they agree?

The standard answer is the Two-Phase Commit protocol. One site acts as the coordinator (usually where the transaction started); the others are participants.

Phase 1: Prepare (Voting)

  1. The coordinator writes <prepare T> to its log and sends PREPARE to all participants.

  2. Each participant checks whether it can commit. If yes, it force-writes its changes and a <ready T> record to its stable log, then replies READY (vote yes). If not, it writes <abort T> and replies ABORT (vote no).

After voting READY, a participant has promised it can commit even if it crashes and restarts. It can no longer decide on its own.

Phase 2: Commit (Decision)

  1. If all participants voted READY, the coordinator force-writes <commit T> to its log; this log write is the exact moment the transaction commits. It sends COMMIT to all.

  2. If any participant voted ABORT (or did not answer in time), the coordinator writes <abort T> and sends ABORT to all.

  3. Participants apply the decision, log it, and send an ACK. When all ACKs arrive, the coordinator records that T is complete.

Coordinator                 Site A                    Site B
    |                          |                         |
    |------ PREPARE ---------->|                         |
    |------ PREPARE ------------------------------------->|
    |                    log <ready T>             log <ready T>
    |<----- READY -------------|                         |
    |<----- READY ----------------------------------------|
 log <commit T>   (decision point)
    |------ COMMIT ----------->|                         |
    |------ COMMIT -------------------------------------->|
    |<----- ACK ---------------|                         |
    |<----- ACK ------------------------------------------|
 log <end T>

Handling Failures

Situation

What happens

A participant fails before voting

The coordinator times out and aborts T.

A participant recovers and its log has <commit T> or <abort T>

Redo or undo T accordingly.

A participant recovers and its log has no <ready T>

It never voted yes, so it can safely abort T.

A participant recovers and its log has <ready T> only

It is in doubt: it must ask the coordinator (or other sites) for the decision.

The coordinator fails after participants voted READY but before they learn the decision

Participants that voted READY cannot decide alone. They must wait, holding their locks, until the coordinator recovers. This is the blocking problem of 2PC.

Why can't a READY participant just abort after waiting a while? Because the coordinator may already have logged <commit T> and told another site to commit. Aborting would break atomicity.

Beyond 2PC

  • Three-Phase Commit (3PC) adds a "pre-commit" phase so participants can make progress without the coordinator, but it is non-blocking only under assumptions such as no network partitions and bounded message delays, so it is rarely used in practice.

  • Modern systems usually make the coordinator itself fault-tolerant by replicating its state with a consensus protocol such as Paxos or Raft. Google Spanner, for example, runs 2PC across groups that are each replicated with Paxos.

2PC in MySQL: XA Transactions

MySQL exposes 2PC through XA transactions, the interface a transaction manager uses to coordinate several databases. In a scratch copy of company_db, acting as one participant:

XA START 'transfer42';
UPDATE employees SET salary = salary + 5000 WHERE emp_id = 8;
XA END 'transfer42';
XA PREPARE 'transfer42';      -- phase 1: this participant votes READY
XA RECOVER;                   -- list prepared (in-doubt) transactions
+----------+--------------+--------------+------------+
| formatID | gtrid_length | bqual_length | data       |
+----------+--------------+--------------+------------+
|        1 |           10 |            0 | transfer42 |
+----------+--------------+--------------+------------+

The transaction is now prepared: it survives a server crash and waits for the coordinator's decision. Phase 2:

XA COMMIT 'transfer42';
SELECT emp_id, name, salary FROM employees WHERE emp_id = 8;
+--------+------------+----------+
| emp_id | name       | salary   |
+--------+------------+----------+
|      8 | Meera Nair | 53000.00 |
+--------+------------+----------+

Meera's salary went from 48,000 to 53,000, and running XA RECOVER again returns an empty result because nothing is in doubt any more.


Distributed Query Processing (In Brief)

In Query Processing & Optimization we counted disk block transfers. In a distributed database, the cost of shipping data over the network often dominates. The optimizer therefore tries to:

  • Run selections and projections at the site holding the data, and send only the reduced result.

  • Ship the smaller relation to the site of the larger one for a join.

  • Use a semijoin strategy: send only the join-column values of R to S's site, find the matching S tuples there, and ship back only those, instead of shipping all of S.

Distributed concurrency control extends ideas from earlier chapters: locks may be managed at each site, and a deadlock may span sites (T1 waits at site A for T2, while T2 waits at site B for T1). Neither site's local wait-for graph shows the cycle, so a global detector or timeouts are needed (see Deadlocks in DBMS).


The CAP Theorem

Now for the most famous result about distributed data. It was presented as a conjecture by Eric Brewer in 2000 and formally proved by Seth Gilbert and Nancy Lynch in 2002.

Consider a system that stores replicated data on several nodes, and three desirable properties:

  • C – Consistency: every read returns the result of the most recent completed write (all nodes behave like a single up-to-date copy; formally, linearizability).

  • A – Availability: every request received by a non-failed node gets a (non-error) response.

  • P – Partition tolerance: the system keeps operating even if the network drops or delays messages between nodes, splitting them into groups that cannot talk to each other.

CAP theorem: a distributed data system cannot simultaneously guarantee Consistency, Availability and Partition tolerance. When a network partition happens, it must choose between consistency and availability.

Why? A Two-Node Story

   Users in Mumbai                         Users in Delhi
         |                                       |
   +-----------+        network link       +-----------+
   |  Node M   | <-------- X BROKEN X ----> |  Node D   |
   | balance=5k|                           | balance=5k|
   +-----------+                           +-----------+

Both nodes hold a copy of an account with balance 5,000. The link between them breaks (a partition). A user in Mumbai withdraws 4,000 at Node M. Then a user in Delhi asks Node D for the balance. Node D has two options:

  1. Answer with 5,000: the system stays available, but the answer is stale, so it is not consistent. (AP choice)

  2. Refuse or wait until it can contact Node M: the answer will be correct (consistent), but the system is not available to this user right now. (CP choice)

There is no third option: Node D cannot know about a write it cannot hear about. That is the whole theorem in one picture.

The Common Misunderstanding: "Pick Any Two"

CAP is often summarised as "choose 2 of 3", suggesting you could pick "CA" and give up P. In a real distributed system, partitions are not optional: networks do fail. So the real meaning is:

  • When there is no partition, a system can provide both consistency and availability.

  • When a partition occurs, it must sacrifice either C or A, at least for the affected data.

A "CA" system is really just a system that is not distributed across an unreliable network, such as a single-server database. Brewer himself wrote in 2012 that the "2 of 3" framing is misleading.

CP vs AP Systems

CP (consistency over availability)

AP (availability over consistency)

During a partition

Some requests fail or wait, but no one reads stale or conflicting data

Every node keeps answering; data may be stale and conflicting writes are reconciled later

Typical examples (default configurations)

HBase, ZooKeeper, etcd, Google Spanner, most distributed SQL databases

Cassandra, Amazon DynamoDB (eventually consistent reads), CouchDB, DNS

Good for

Bank balances, inventory counts, seat booking, leader election, configuration

Social feeds, likes, shopping carts, product views, metrics

Many databases let you choose per operation. Cassandra lets each query pick a consistency level (ONE, QUORUM, ALL...), and DynamoDB offers strongly consistent reads as an option. So "Cassandra is AP" really means "Cassandra is AP with its common default settings".

CAP Consistency ≠ ACID Consistency

A frequent interview trap:

  • C in ACID = a transaction takes the database from one valid state to another, respecting integrity constraints.

  • C in CAP = all replicas appear as one up-to-date copy (every read sees the latest write).

Same letter, different meanings.

PACELC: The Rest of the Story

CAP only talks about what happens during a partition. Daniel Abadi's PACELC formulation extends it:

If there is a Partition (P), choose between Availability (A) and Consistency (C); Else (E), when the system is running normally, choose between Latency (L) and Consistency (C).

Even with a healthy network, keeping replicas strongly consistent means waiting for other nodes (sometimes in other cities) before answering, which adds latency. Systems like Cassandra and DynamoDB are typically described as PA/EL (favour availability and low latency), while systems like Spanner or HBase are PC/EC (favour consistency in both cases).


Common Mistakes

  • Saying a system can be "CA" while being distributed. Partitions happen; the choice during a partition is C or A.

  • Confusing CAP consistency with ACID consistency.

  • Vertical fragments without the primary key. They cannot be joined back losslessly.

  • Horizontal fragmentation predicates that miss values, especially NULLs, breaking completeness.

  • Thinking 2PC is non-blocking. If the coordinator fails after participants vote READY, they block until it recovers.

  • Saying R + W ≥ N guarantees reading the latest write. It must be strictly greater than N.

  • Calling replication and fragmentation the same thing. Fragmentation splits data; replication copies it. Systems usually do both.


Interview Questions

1. What is a distributed database? Give its advantages.

A single logical database stored across multiple networked sites. Advantages: scalability, availability through replicas, data placed near users, and support for decentralised organisations.

2. Difference between fragmentation and replication?

Fragmentation splits a relation into parts (by rows or columns) stored at different sites; replication stores identical copies of data at multiple sites. Fragmentation spreads data; replication improves availability and read performance.

3. Explain horizontal and vertical fragmentation.

Horizontal: subsets of rows chosen by a condition, reconstructed with UNION. Vertical: subsets of columns, each including the primary key, reconstructed with a JOIN on that key.

4. Explain the Two-Phase Commit protocol.

Phase 1: the coordinator asks all participants to prepare; each force-logs its changes and votes READY or ABORT. Phase 2: if all voted READY the coordinator logs and sends COMMIT, otherwise ABORT; participants apply the decision and acknowledge.

5. What is the blocking problem in 2PC?

If the coordinator crashes after participants have voted READY but before they receive the decision, they cannot safely commit or abort on their own and must wait, holding locks, until the coordinator recovers.

6. State the CAP theorem.

A distributed data system cannot guarantee consistency, availability and partition tolerance at the same time. Because partitions cannot be ruled out, during a partition it must choose between consistency and availability.

7. Is MongoDB/Cassandra CP or AP?

It depends on configuration. Cassandra with its common low consistency levels behaves as AP; with QUORUM reads and writes it behaves more like CP for those operations. MongoDB with majority write and read concerns behaves as CP. Always state the configuration.

8. What does R + W > N mean in quorum systems?

With N replicas, if every write is acknowledged by W replicas and every read contacts R replicas, then R + W > N ensures every read overlaps with the latest write on at least one replica.


Summary

  • A distributed database spreads one logical database over several sites, ideally with location, fragmentation and replication transparency.

  • Fragmentation (horizontal, vertical, hybrid) must be complete, reconstructible and (for horizontal) disjoint. Vertical fragments must include the key.

  • Replication improves availability and read speed but makes updates harder; it can be synchronous or asynchronous, single-leader or multi-leader; quorums need R + W > N.

  • Two-Phase Commit makes distributed transactions atomic (prepare/vote, then commit/abort) but can block if the coordinator fails; MySQL exposes it as XA transactions.

  • CAP theorem: during a network partition, a distributed system must choose between consistency and availability. "Pick any two" is misleading.

  • PACELC adds: even without partitions, there is a trade-off between latency and consistency.

In a distributed database, the network will fail at some point. The real design question is what your system should do when it does.