CAP Theorem in Distributed Databases: Consistency, Availability, Partition Tolerance

When building distributed systems, you'll eventually face the CAP theorem. Coined by Eric Brewer in 2000, it describes the fundamental trade-offs between Consistency, Availability, and Partition Tolerance. In a world where network failures are inevitable, understanding CAP is crucial for designing robust databases. This tutorial dives deep into each property, explores real-world database choices (e.g., Cassandra, MongoDB, PostgreSQL), and shows how to apply CAP in production. You'll learn why many modern databases are 'AP' or 'CP' and how to choose based on your application's needs. We'll also walk through a production incident where CAP ignorance caused a major outage.

What is the CAP Theorem?

The CAP theorem states that a distributed data store can only provide two of the following three guarantees simultaneously: Consistency (C), Availability (A), and Partition Tolerance (P). Consistency means every read receives the most recent write or an error. Availability means every request receives a (non-error) response, without guarantee that it contains the most recent write. Partition Tolerance means the system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes. In practice, network partitions are unavoidable, so you must choose between CP and AP. This trade-off is fundamental to distributed database design.

-- Example: Simulating a partition in a distributed SQL database
-- Assume two nodes: node1 and node2
-- On node1:
INSERT INTO orders (id, amount) VALUES (1, 100);
-- Network partition occurs between node1 and node2
-- On node2, the insert is not visible
-- If we query node2:
SELECT * FROM orders WHERE id = 1; -- Returns empty (inconsistent)
-- To maintain consistency, node2 would need to reject the read or wait for partition to heal.

Consistency Models in Depth

Consistency in CAP refers to strong consistency: after a write, all subsequent reads see that write. This is similar to ACID consistency in single-node databases. In distributed systems, achieving strong consistency often requires coordination (e.g., Paxos, Raft) which can reduce availability. Weaker consistency models include eventual consistency (updates propagate eventually), causal consistency, and read-your-writes consistency. For example, Amazon DynamoDB offers eventual consistency by default but can be configured for strong consistency at higher latency. SQL databases like PostgreSQL with synchronous replication can provide strong consistency but may become unavailable during a partition.

-- PostgreSQL synchronous replication example
-- Ensure all replicas acknowledge writes
SHOW synchronous_commit; -- 'on'
-- During a partition, if replicas are unreachable, writes will fail.
INSERT INTO accounts (id, balance) VALUES (1, 500);
-- If partition occurs, this insert may timeout or error.

Availability and Its Trade-offs

Availability means every request gets a response, even if it's not the latest data. This is critical for systems that must always be up, like e-commerce catalogs or social media. To achieve high availability, databases often replicate data across multiple nodes and allow reads from any replica. However, during a partition, replicas may diverge. For example, Cassandra is AP: it accepts writes on any node and resolves conflicts later via last-write-wins. The trade-off is that reads may return stale data. Availability is often measured in 'nines' (e.g., 99.999% uptime).

-- Cassandra (AP) example: write to any node
-- Even during partition, write succeeds
INSERT INTO orders (id, amount) VALUES (2, 200) USING TIMESTAMP 123456;
-- Read from another node may not see this write immediately
SELECT * FROM orders WHERE id = 2; -- May return empty or old value

Partition Tolerance: The Non-Negotiable

Partition Tolerance means the system continues to function despite network failures that prevent communication between nodes. Since network partitions are inevitable in distributed systems (e.g., due to hardware failure, network congestion), you must tolerate them. This is why CAP is often framed as a choice between CP and AP: you cannot sacrifice partition tolerance. A system that is not partition-tolerant would simply stop working during a network split. Most distributed databases are designed to be partition-tolerant by replicating data and handling splits via strategies like quorum-based decisions or conflict resolution.

-- MongoDB (CP by default) handles partition via primary election
-- If primary is isolated, a new primary is elected, but writes to old primary fail
-- Example: replica set with 3 nodes
-- During partition, if primary is isolated, it steps down
rs.status() -- shows primary change
-- Writes to old primary will fail with 'not master' error

Real-World Database Choices: CP vs AP

Different databases make different CAP trade-offs. CP databases: HBase, MongoDB (with default settings), Redis (with replication), and traditional SQL with synchronous replication. They prioritize consistency over availability during partitions. AP databases: Cassandra, DynamoDB (eventual consistency), CouchDB, and Riak. They prioritize availability. Some databases offer tunable consistency (e.g., Cassandra allows you to set consistency level per query). Choosing the right database depends on your application's requirements. For example, a banking system needs CP, while a social media feed can use AP.

-- Cassandra: tunable consistency per query
-- Strong consistency: require all replicas to acknowledge
SELECT * FROM orders WHERE id = 1 USING CONSISTENCY ALL;
-- Eventual consistency: only one replica needed
SELECT * FROM orders WHERE id = 1 USING CONSISTENCY ONE;

Beyond CAP: PACELC and Modern Trade-offs

CAP is a simplified model. The PACELC theorem extends it: if a partition occurs (P), trade off between consistency (C) and availability (A); else (E), trade off between latency (L) and consistency (C). This acknowledges that even without partitions, there are trade-offs. For example, DynamoDB offers low latency by default but can sacrifice consistency. Google Spanner uses TrueTime to provide strong consistency with low latency, but at complexity cost. Understanding PACELC helps in designing systems that balance all factors.

-- Spanner: strong consistency with low latency using TrueTime
-- Example: read with strong consistency
SELECT * FROM orders WHERE id = 1;
-- Spanner ensures all replicas agree on timestamp
-- Even without partition, it chooses consistency over latency

Practical Guidelines for Choosing Your Database

When selecting a distributed database, consider: 1) Consistency requirements: do you need strong consistency? 2) Availability requirements: can you tolerate downtime? 3) Partition tolerance: assume partitions will happen. 4) Latency: how fast must reads/writes be? 5) Operational complexity: can your team manage the database? Start by listing your application's critical paths. For example, an e-commerce site might use a CP database for inventory and an AP database for product reviews. Also consider using a multi-model database or a combination of databases. Always test under partition scenarios.

-- Example: decision flow in SQL-like pseudocode
-- IF strong consistency required THEN
--   USE CP database (e.g., PostgreSQL with sync replication)
-- ELSE
--   USE AP database (e.g., Cassandra)
-- END IF;
-- For mixed requirements, use separate databases or tunable consistency.