system-design · beginner

CAP Theorem — Consistency, Availability, and Partition Tolerance

The Central Question

Consider an online financial platform running on the TxLab platform (txlab.com) processing 100,000,000 queries per day operating across two cloud datacenters: Region US-East (New York) and Region EU-West (London):

• The platform maintains a distributed ledger database storing account balances.
• Each account (such as acc_alice) must maintain non-negative balances.
• Suddenly, a transatlantic undersea fiber-optic cable cut causes a total Network Partition between US-East and EU-West. The database nodes in New York can no longer communicate with the database nodes in London.

The system faces an unavoidable dilemma:

• Option 1 (CP Choice): Refuse or block the withdrawal in one or both regions until the network partition heals, protecting data correctness but causing API errors for clients (Sacrifice Availability for Consistency).
• Option 2 (AP Choice): Allow both customers in New York and London to withdraw $\$500$, keeping the service 100% operational but creating a double-withdrawal overdraft data corruption anomaly (Sacrifice Consistency for Availability).

This lesson answers one central question: How does the CAP Theorem (and its PACELC extension) force distributed systems to choose between Linearizable Consistency (CP) and High Availability (AP) during network partitions, and how do engineers design partition-tolerant architectures for financial ledgers vs high-throughput social feeds?

Deconstructing CAP: The Three Properties

Formulated by Eric Brewer in 2000 and mathematically proven by Seth Gilbert and Nancy Lynch in 2002, the CAP theorem evaluates three specific system properties:

flowchart TD
  CAP[CAP Theorem Properties] --> C[C: Linearizable Consistency]
  CAP --> A[A: High Availability]
  CAP --> P[P: Partition Tolerance]
  
  C --> CDesc["Every read returns the most recent write or an error.<br/>Behaves as if there is only ONE single copy of data."]
  A --> ADesc["Every non-failing node returns a non-error response<br/>for every request (without guaranteeing latest data)."]
  P --> PDesc["The system continues operating despite dropped<br/>or delayed network messages between nodes."]

Figure 1: Taxonomy of the three core CAP theorem properties.

1. Consistency (Linearizability)

[!IMPORTANT] CAP Consistency is NOT ACID Consistency: - ACID Consistency means preserving database schema invariants (such as foreign keys and CHECK constraints) inside a single relational database. - CAP Consistency means linearizable single-copy read freshness across distributed network nodes.

2. Availability (Non-Failing Node Response)

3. Partition Tolerance (Network Survival)

The Core Impossibility Proof: Why You Cannot "Pick Three"

A common misunderstanding claims that engineers can choose any two properties out of C, A, and P (e.g. "building a CA database").

In real-world cloud networks, Partition Tolerance (P) is non-negotiable. Network cables get cut, top-of-rack switches lock up, and cloud hypervisors drop packets. You cannot opt out of Partitions.

Therefore, the CAP theorem simplifies to a binary choice during a network partition:

$$\text{During a Network Partition (P): Choose } \mathbf{CP} \text{ or } \mathbf{AP}$$

sequenceDiagram
    autonumber
    actor ClientA as Client US
    participant NodeA as Node US (Primary)
    participant Net as Partitioned Network (LINK DOWN)
    participant NodeB as Node EU (Replica)
    actor ClientB as Client EU
    
    ClientA->>NodeA: 1. WRITE balance = 1000
    NodeA->>Net: 2. Sync to Node EU (DROPPED BY PARTITION!)
    
    alt CP Choice (Consistency Over Availability)
        NodeA-->>ClientA: 3. Return Error 503 / Block Write!
        Note over NodeA: Protects data consistency by rejecting un-syncable writes.
    else AP Choice (Availability Over Consistency)
        NodeA-->>ClientA: 3. Return HTTP 200 OK!
        ClientB->>NodeB: 4. READ balance
        NodeB-->>ClientB: 5. Returns Stale balance = 500!
        Note over NodeB: Preserves availability, but returns stale inconsistent data.
    end

Figure 2: Sequence diagram demonstrating CP blocking vs AP stale serving during a network partition.

Beyond CAP: The PACELC Theorem

Daniel Abadi recognized that CAP only describes system behavior during network partitions, which happen infrequently (0.01% of operational time). What happens during normal operation?

The PACELC Theorem extends CAP to model both normal and partitioned states:

$$\mathbf{I\mathbf{f} } \mathbf{P} \text{ (Partition): } [\text{Choose } \mathbf{A} \text{ or } \mathbf{C}] \quad \mathbf{E\mathbf{lse} } \text{ (Normal): } [\text{Choose } \mathbf{L} \text{ or } \mathbf{C}]$$

flowchart TD
  PACELC[PACELC Trade-Off Matrix] --> P[If Partition P?]
  P -->|Yes| PA[A: Availability]
  P -->|Yes| PC[C: Consistency]
  
  PACELC --> E[Else Normal Ops?]
  E -->|Yes| EL[L: Low Latency]
  E -->|Yes| EC[C: High Consistency]
  
  PA & EL --> PAEL[PA/EL: DynamoDB / Cassandra]
  PC & EC --> PCEC[PC/EC: Spanner / CockroachDB / Etcd]

Figure 3: Taxonomy of PACELC classifications for distributed data stores.

PACELC Classification Matrix

Network Partition Healing & State Reconciliation

• AP Systems (Cassandra/DynamoDB): Nodes exchange Merkle tree hashes and execute Hinted Handoff playback to reconcile divergent writes accumulated during the partition.
• CP Systems (Etcd/Spanner): The isolated minority partition (which rejected writes during the outage) re-syncs its Write-Ahead Log (WAL) from the majority quorum leader before accepting new client queries.

Quorum Loss & Read-Only Fallback Modes

• INSERT and UPDATE mutations are rejected with clear error codes.
• SELECT queries are served from local snapshots, maintaining partial availability for readers without risking un-synchronizable writes.

Automated Partition Alerting Thresholds

Complete Worked Example: Go CAP Partition Detector & Circuit Breaker

Let's inspect a complete Go implementation of a CAP Partition Detector and Circuit Breaker for the TxLab platform (txlab.com).

package main
import (
	"context"
	"errors"
	"fmt"
	"sync"
	"time"
)
type CAPMode int
const (
	ModeCP CAPMode = iota // Reject writes on partition
	ModeAP                // Allow stale writes/reads on partition
)
type PartitionCircuitBreaker struct {
	mu           sync.RWMutex
	mode         CAPMode
	isPartitioned bool
	lastHeartbeat time.Time
}
func NewPartitionCircuitBreaker(mode CAPMode) *PartitionCircuitBreaker {
	return &PartitionCircuitBreaker{
		mode:          mode,
		isPartitioned: false,
		lastHeartbeat: time.Now(),
	}
}
func (cb *PartitionCircuitBreaker) ProcessWrite(ctx context.Context, key string, val interface{}) error {
	cb.mu.RLock()
	defer cb.mu.RUnlock()
if cb.isPartitioned {
		if cb.mode == ModeCP {
			fmt.Printf("[CP REJECTION] Network partition active! Rejecting write for key '%s' to preserve Consistency.\n", key)
			return errors.New("503 Service Unavailable: CP Mode partition protection active")
		} else {
			fmt.Printf("[AP DEGRADED WRITE] Network partition active! Accepting write for key '%s' locally (Eventual Consistency).\n", key)
			return nil
		}
	}
fmt.Printf("[NORMAL WRITE] Executing synchronized write for key '%s'\n", key)
	return nil
}
func (cb *PartitionCircuitBreaker) UpdateHeartbeat(success bool) {
	cb.mu.Lock()
	defer cb.mu.Unlock()
if !success && time.Since(cb.lastHeartbeat) > 3*time.Second {
		if !cb.isPartitioned {
			cb.isPartitioned = true
			fmt.Println("[NETWORK ALERT] Network Partition Detected! Engaging CAP Circuit Breaker.")
		}
	} else if success {
		if cb.isPartitioned {
			cb.isPartitioned = false
			fmt.Println("[NETWORK ALERT] Network Partition Healed! Restoring normal cluster operation.")
		}
		cb.lastHeartbeat = time.Now()
	}
}

Failure Modes and Engineering Mitigations

What You Should Remember

1. CAP forces a binary choice during partitions: Choose Linearizable Consistency (CP) or High Availability (AP) during network partitions.
2. Partition Tolerance (P) is mandatory: Network failures are inevitable in distributed systems; you cannot choose "CA" without partitions.
3. PACELC models normal operation latency: PACELC models both partition choices (A vs C) and normal operation choices (Latency vs Consistency).
4. CP for Financial Ledgers, AP for Social Feeds: Use CP databases (Google Spanner, Etcd) for accounts and inventory; use AP databases (Cassandra, DynamoDB) for social posts.
5. Enforce Quorum Majority for CP writes: Ensure CP clusters require a majority quorum ($\lfloor \frac{N}{2} \rfloor + 1$) to prevent split-brain write divergence.

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

• Driver location updates (100,000 QPS): Needs high write throughput and low latency.
• Passenger payment transactions (1,000 QPS): Requires zero data loss and no double-charging.

1. Formulate the CAP/PACELC classification for driver location updates vs passenger payment transactions.
2. Design the fallback behavior when the network partition cuts connectivity between US and EU regions.

Interactive Self-Assessment

Network partitions are an unavoidable physical reality. When a partition occurs, systems MUST choose between CP or AP.

CA databases cause hardware electrical short-circuits in server power units.

CA databases revoke edge HTTPS TLS encryption certificates on load balancers.

CA databases cut physical CPU hardware clock speeds in half.

PACELC models system behavior during normal operation, trading off Latency (L) against Consistency (C) when no partition exists.

PACELC automatically converts relational database primary key indexes into un-indexed CSV files.

PACELC replaces public DNS nameservers with local hosts file entries.

PACELC reboots operating system hypervisors across all database nodes.

What to Learn Next

• Strong vs Eventual Consistency: Explore linearizability vs eventual consistency models.
• Consensus Algorithms — Raft and Replicated State Machines: Learn Raft quorum leader elections.
• Active-Active Conflict Resolution — CRDTs and Vector Clocks: Master multi-region write conflict resolution.

Track: Distributed Systems

Previous: System Design Foundations — How Large Software Fits Together

Next: CAP, Consistency & Idempotency

Series: CAP, Consistency & Quorums

1. CAP Theorem — Consistency, Availability, and Partition Tolerance (this guide)
2. Consistency Models — From Strong to Eventual
3. Strong vs Eventual Consistency — Trade-offs in Distributed Systems
4. CAP, Consistency & Idempotency
5. Quorum Reads vs Quorum Writes

All series

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab