Distributed Databases & CAP Theorem

In modern big-tech systems, data is too large for one server. A Distributed Database (D-DBMS) spreads data across multiple locations (nodes).

This chapter covers the fundamental concepts of distributed databases and the key trade-off every distributed system must face: the CAP Theorem.

---

Learning Objectives

After completing this chapter, you will be able to:

• Explain what a distributed database is and why it’s needed.
• Differentiate between fragmentation (horizontal/vertical) and replication.
• Understand the CAP Theorem and its three guarantees.
• Explain why you can only pick two of C, A, and P.
• Compare CP and AP systems with examples.
• Understand transparency and ACID in distributed systems.
• Answer distributed database interview questions.

---

Why Distribute Data?

Reason	Problem	Solution
Scale	Data too large for one server	Shard across multiple servers
Performance	One server can’t handle all queries	Distribute load across nodes
Availability	Single server is a single point of failure	Replicate data across nodes
Geography	Users worldwide need fast access	Put data closer to users (edge)

---

Fragmentation (Sharding)

Splitting data across multiple databases.

Horizontal Fragmentation (Sharding)

Splitting rows across servers. Each server stores a subset of rows.

Users 1-100,000 → Node A
Users 100,001-200,000 → Node B
Users 200,001-300,000 → Node C

Use case: Scaling write throughput. Most common approach.

Vertical Fragmentation

Splitting columns across servers. Each server stores a subset of columns.

Node A: User_ID, Name, Email
Node B: User_ID, Payment_Info, Billing_Address

Use case: Separating sensitive data (PCI compliance) or different access patterns.

Hybrid Fragmentation

Combination: horizontally shard first, then vertically split each shard.

---

Replication

Storing the same data on multiple nodes.

Synchronous Replication

All replicas are updated BEFORE the transaction commits.

Pros	Cons
Strong consistency	Slower (all replicas must acknowledge)
No data loss	Higher latency

Asynchronous Replication

The primary is updated first; replicas are updated later.

Pros	Cons
Faster writes (no replica wait)	Replicas may be stale
Better availability	Risk of data loss on primary failure

Types of Replication

Type	Description
Master-Slave	One primary (writes), many replicas (reads)
Multi-Master	Multiple nodes accept writes
Peer-to-Peer	All nodes are equal — no single point of failure

---

The CAP Theorem

A distributed system can provide at most two of the following three guarantees:

C — Consistency

Every read receives the most recent write (or an error).

All nodes see the same data at the same time.

A — Availability

Every request receives a (non-error) response, without guarantee that it contains the most recent write.

The system always responds — even if some nodes are down.

P — Partition Tolerance

The system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes.

Network failures happen. P is not optional in distributed systems.

---

The CAP Trade-Off

          Consistency
              │
              │
              ├── CA (RDBMS on one node)
              │
     ┌────────┴────────┐
     │                 │
 CP  │                 │  AP
(MongoDB, │                 │  (Cassandra,
 HBase)   │                 │   DynamoDB)
     │                 │
     └─────────────────┘
        Partition Tolerance

When a network partition occurs (P), you must choose:

Choice	Behavior	Examples
CP (Consistency + Partition Tolerance)	Reject writes that can’t be consistent across all nodes. Some nodes become unavailable.	MongoDB, HBase, Traditional RDBMS with sync replication
AP (Availability + Partition Tolerance)	Accept writes on available nodes. Data may diverge (eventual consistency).	Cassandra, DynamoDB, CouchDB

Key insight: You must ALWAYS have P in a distributed system because network failure is inevitable. The real choice is CP vs AP.

---

Important CAP Clarifications

Myth	Reality
”You can choose all three sometimes”	CAP is about behavior DURING a partition. When no partition exists, all three can work.
”CAP is forever”	You can trade between C and A dynamically based on system state.
”AP means no consistency”	AP systems provide Eventual Consistency — data converges over time.
”CP means no availability”	CP systems are available as long as the partition isn’t happening.

---

ACID vs BASE

Property	ACID (Relational)	BASE (NoSQL)
C	Strong Consistency	Basically Available — system stays up
A	Atomicity	Soft State — data may change over time
I	Isolation	Eventual Consistency — data converges
D	Durability	(Same)

---

Transparency in Distributed Databases

Type	Meaning
Location Transparency	Users don’t need to know where data is physically stored
Replication Transparency	Users don’t need to know how many copies exist
Fragmentation Transparency	Users don’t need to know how data is split
Failure Transparency	Users don’t see system failures
Concurrency Transparency	Multiple users don’t interfere

All of these aim to make a distributed database look like a single, local database to the user.

---

Interview Deep Dive

---

Key Takeaways

• Distributed Database: Data spread across multiple nodes for scale, performance, availability, or geography.
• Horizontal Fragmentation (Sharding): Split rows across nodes.
• Vertical Fragmentation: Split columns across nodes.
• Replication: Copy data to multiple nodes (sync or async).
• CAP Theorem: Pick two — Consistency, Availability, Partition Tolerance.
• P is mandatory in distributed systems (network failures happen). Real choice is CP vs AP.
• CP systems sacrifice availability during partitions (MongoDB, HBase).
• AP systems sacrifice consistency (Cassandra, DynamoDB) — provide eventual consistency.
• Transparency makes distributed databases appear as a single database to users.
• ACID (relational) vs BASE (NoSQL) represent the two ends of the consistency spectrum.