CAP Theorem and Database Scaling

The CAP theorem defines the fundamental tradeoff in distributed databases. Scaling strategies determine how databases handle growth.

This chapter covers the CAP theorem (and its extension PACELC), plus practical scaling techniques used by every major internet company.

---

Learning Objectives

After completing this chapter, you will be able to:

• Explain the CAP theorem and its three properties.
• Understand why you can have at most two of three.
• Apply CAP to choose databases.
• Explain PACELC (CAP + latency tradeoff).
• Describe sharding, replication, and partitioning strategies.
• Understand read replicas and write scaling.
• Answer CAP and scaling interview questions.

---

The CAP Theorem

The CAP theorem states that a distributed data system can provide at most two of three properties:

       Consistency
         /    \
        /      \
       /        \
  Availability —— Partition Tolerance

C — Consistency

Every read receives the most recent write or an error.

In a consistent system, 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 remains operational even if some nodes are down.

P — Partition Tolerance

The system continues to function despite network failures (partitions) between nodes.

A partition is when two nodes cannot communicate with each other.

---

CAP Tradeoffs

CP (Consistency + Partition Tolerance)

• On network partition: the system stops accepting writes until the partition heals.
• Sacrifices: Availability during partitions.
• Examples: HBase, MongoDB (default), Zookeeper, etcd.

AP (Availability + Partition Tolerance)

• On network partition: the system continues accepting writes on all sides; reads may return stale data.
• Sacrifices: Strong consistency.
• Examples: Cassandra, DynamoDB, CouchDB.

CA (Consistency + Availability)

• Cannot survive network partitions.
• Only works: On a single-node system (no partitions possible).
• Examples: Single-node PostgreSQL, MySQL.

---

CAP in Practice

In a distributed system, network partitions are inevitable. Therefore, you must choose between CP and AP.

System	CAP Choice	Why
Banking	CP	Every transaction must be consistent
Social media	AP	Showing slightly stale data for a moment is OK
DNS	AP	Availability is critical; stale DNS records are acceptable
E-commerce cart	AP	Users should always be able to add items
Inventory system	CP	Over-selling is worse than temporarily blocking sales

---

PACELC

The CAP theorem only considers partitions. PACELC extends it with latency tradeoffs during normal operation.

P (Partition):
  If partition → Choose A or C (per CAP)

Else (normal operation):
  Choose L (Latency) or C (Consistency)

Example

System	Partition	Normal
DynamoDB	AP	Prefers L over C (eventual consistency by default)
Spanner	CP	Prefers C over L (TrueTime for global consistency)

---

Database Scaling

Scaling is how a database handles increasing load.

---

Vertical Scaling (Scale Up)

Add more resources to a single server: more CPU, RAM, faster disks.

Before: 1 server (4 CPU, 16GB RAM)
After:  1 server (32 CPU, 256GB RAM)

Pros	Cons
Simple (no architecture changes)	Expensive (hardware cost grows non-linearly)
All data remains in one place	Hard limit (max specs for a single machine)
No application changes needed	Single point of failure

---

Horizontal Scaling (Scale Out)

Add more servers to distribute the load.

Before: 1 server
After:  5 servers (each handles part of the data)

Pros	Cons
Cost-effective (commodity hardware)	Complex architecture
Near-linear scaling	Data distribution is hard
Fault-tolerant (no single point of failure)	May sacrifice consistency

---

Sharding

Sharding splits data across multiple databases (shards) based on a shard key.

How It Works

Shard Key: User_ID (hash: user_id % 4)

Shard 0: User_ID 0, 4, 8, 12...
Shard 1: User_ID 1, 5, 9, 13...
Shard 2: User_ID 2, 6, 10, 14...
Shard 3: User_ID 3, 7, 11, 15...

Shard Key Selection

Good Shard Key	Bad Shard Key
User_ID (even distribution)	Country (India → 70% of data on one shard)
Order_ID (auto-increment)	Status (most orders are “Completed”)
Hash of primary key	Date (hot shard for today’s data)

Challenges

• Cross-shard queries: Joins across shards are slow.
• Resharding: Moving data when a shard grows too large is complex.
• Hot spots: Some shards may receive more traffic.

---

Replication

Replication copies data to multiple servers for fault tolerance and read scaling.

Master-Slave Replication

Master: Handles all writes.
Slaves: Handle reads. Replicate from master asynchronously.

-- Master: Write
INSERT INTO Users VALUES (101, 'Rahul');

-- Slave (replicated): Read
SELECT * FROM Users WHERE User_ID = 101;  -- May lag slightly

Advantages

• Read scaling (many slaves can handle read traffic).
• Fault tolerance (if master fails, promote a slave).

Disadvantage

• Replication lag (slave may be behind master by milliseconds or seconds).

---

Multi-Master Replication

Multiple nodes accept writes and replicate to each other.

Pros	Cons
No single point of write failure	Conflict resolution is hard
Write scaling	Need conflict detection (last-writer-wins, CRDTs)

---

Read Replicas

Read replicas are copies of the database that only handle read queries.

Architecture

                ┌─────────┐
                │  Master  │  ← Write traffic
                └────┬────┘
                     │
        ┌────────────┼────────────┐
        ▼            ▼            ▼
    ┌───────┐   ┌───────┐    ┌───────┐
    │Replica│   │Replica│    │Replica│  ← Read traffic
    └───────┘   └───────┘    └───────┘

Use Cases

• Reporting dashboards (heavy read queries on replicas).
• Caching layers (read replicas in multiple regions).
• Geographic distribution (replicas closer to users).

---

Connection Pooling

Connection pooling reuses database connections instead of opening a new one for each request.

Without Pooling

Request 1 → Open connection → Query → Close connection
Request 2 → Open connection → Query → Close connection

With Pooling

Connection Pool: [conn1] [conn2] [conn3] ... [conn50]

Request 1 → Borrow conn1 → Query → Return conn1
Request 2 → Borrow conn2 → Query → Return conn2

Benefits

• Reduces connection overhead.
• Limits peak connections to the database.
• Prevents database from being overwhelmed (connection storms).

---

Caching for Scaling

Cache Layer	Tools	Use Case
Application cache	Redis, Memcached	Store query results, reduce DB load
CDN	CloudFront, Cloudflare	Serve static content near users
Database cache	InnoDB buffer pool	Cache database pages in memory

Cache-Aside Pattern

def get_user(user_id):
    # 1. Try cache
    user = redis.get(f"user:{user_id}")
    if user:
        return user

    # 2. Cache miss → query database
    user = db.query("SELECT * FROM Users WHERE id = %s", user_id)

    # 3. Store in cache
    redis.set(f"user:{user_id}", user)

    return user

---

Interview Deep Dive

---

Key Takeaways

• CAP theorem: A distributed system can have at most 2 of Consistency, Availability, Partition Tolerance.
• Partitions are inevitable → choose CP or AP.
• PACELC extends CAP with the latency vs consistency tradeoff during normal operation.
• Vertical scaling is simple but has hard limits.
• Horizontal scaling (sharding) distributes data but adds complexity.
• Shard key selection is critical — poor keys cause hot spots.
• Replication provides fault tolerance and read scaling.
• Read replicas serve reads but may have replication lag.
• Connection pooling prevents database connection overload.
• Caching reduces database load for frequently accessed data.