The CAP Theorem in Practice: How Real Distributed Databases Handle Partitions (CP vs AP & PACELC)

In distributed systems theory, Eric Brewer's CAP Theorem is often introduced as a simplistic triangle: "Pick any two: Consistency, Availability, or Partition Tolerance."

In modern cloud computing and real-world distributed engineering, network partitions are not an optional feature you can choose to avoid. Hardware cables get cut, cross-availability-zone latency spikes occur, and switches fail. Therefore, the real question in distributed system design is never "Can we avoid partitions?" but rather: "When a network partition inevitably happens, do we sacrifice Availability or Consistency?"

Furthermore, what trade-offs do databases make during the 99.99% of the time when the network is completely healthy?

This comprehensive guide unpacks the CAP theorem beyond textbook definitions, explores the PACELC Theorem, and analyzes how modern enterprise databases—including Amazon DynamoDB, Apache Cassandra, Google Cloud Spanner, CockroachDB, and MongoDB—navigate partition trade-offs.

1. Deconstructing the CAP Properties#

To evaluate database guarantees accurately, we must use rigorous definitions rather than casual terminology:

The Three Properties Defined#

1. Consistency (Linearizability / Single-Copy Consistency): Every read receives the most recent write or returns an error. All clients see the exact same data at the same logical instant, regardless of which node they connect to.
2. Availability (Liveness): Every non-failing node must return a successful (non-error) response to every request—without guaranteeing that it contains the most recent write.
3. Partition Tolerance: The system continues to function despite an arbitrary number of messages being dropped, delayed, or lost by the network between nodes.

2. The Network Partition Dilemma: CP vs. AP#

Consider a two-node cluster ($\text A$ and $\text B$). A network split severs communication between them:

• In a CP System, Node A rejects the write or blocks until a quorum is reached. This protects your financial invariants, preventing money from being spent twice.
• In an AP System, both nodes accept reads and writes locally. The system remains 100% available, but Client 2 sees stale data until the partition heals and reconciliation occurs.

3. Beyond CAP: The PACELC Theorem#

In 2012, computer scientist Daniel Abadi identified a major limitation of CAP: network partitions are rare exceptions. How does a database behave during normal operational conditions?

The PACELC Theorem expands CAP to address latency:

If Partition (P):
    How do you choose between Availability (A) and Consistency (C)?
Else (E):
    How do you choose between Latency (L) and Consistency (C)?

PACELC Classification Matrix#

4. Real-World Database Deep Dives#

1. Apache Cassandra & Amazon DynamoDB (PA/EL)#

Cassandra and DynamoDB were designed for retail and telemetry systems where a rejected write means a lost customer.

• Quorum Math: Configurable via $R + W > N$ where $N$ is replication factor, $W$ is write quorum, and $R$ is read quorum.
• Conflict Resolution: Uses Last-Write-Wins (LWW) based on timestamps or vector clocks.
• Hinted Handoff: When a node is unreachable, peer nodes store write hints and deliver them once the node recovers.

-- Example: Cassandra Tunable Consistency Query
-- Guarantees strong linearizable read if W + R > N
SELECT * FROM users WHERE user_id = 'usr_90210' 
USING CONSISTENCY QUORUM;

-- Prioritizes sub-millisecond latency over freshness
SELECT * FROM click_telemetry WHERE session_id = 'sess_4102' 
USING CONSISTENCY ONE;

2. Google Cloud Spanner & CockroachDB (PC/EC)#

Modern distributed SQL engines prove that consistency and horizontal scalability can coexist:

• TrueTime Hardware (Spanner): Google integrates atomic clocks and GPS receivers into data centers to bound clock uncertainty ($\epsilon < 7\text$), enabling globally consistent transactions without cross-region locks.
• Raft Consensus (CockroachDB): Partitions data into ranges, each managed by an independent Raft consensus group. If a network split isolates a minority of nodes, the majority continues serving traffic while the minority safely blocks.

5. Architectural Decision Guide: Choosing for Your System#

Use this framework when selecting your database layer:

1. Financial Ledgers & Inventory Balances: Always select PC/EC (Strict CP). It is far easier to handle a momentary timeout than to reconcile duplicate withdrawals across conflicting partitions.
2. Analytics, Logging & IoT Streams: Select PA/EL (AP). Dropping or delaying telemetry events due to a partition is unacceptable; eventual convergence is perfectly sufficient.
3. Session Caches & Social Feeds: Leverage Tunable AP stores. Configure writes with LOCAL_QUORUM to achieve single-digit millisecond latency while maintaining localized fault isolation.

Frequently Asked Questions#

Is PostgreSQL a CP or AP database?#

Traditional single-node PostgreSQL is neither in distributed terms, but in a replicated setup (e.g., streaming replication with patroni):

• With synchronous replication, PostgreSQL operates as CP (rejects writes if sync replicas are unreachable).
• With asynchronous replication, it behaves closer to AP, risking data loss or divergence during automated failover.

Can a database be CA (Consistent and Available)?#

In a single-server setup, yes, because partitions cannot occur between nodes. In any distributed system with more than one physical node, CA is physically impossible over real-world networks because network partitions are inevitable.

How does the Raft consensus algorithm handle network partitions?#

Raft requires a strict majority of nodes ($\lfloor N/2 \rfloor + 1$) to elect a leader and commit log entries. In a 5-node cluster split into a 3-node partition and a 2-node partition, the 3-node side maintains quorum and continues processing writes, while the 2-node minority rejects writes to prevent data corruption.