CAP Theorem Real-World Examples: CP vs AP Databases

Question

Design Gurus · Accepted Answer

During a network partition, a distributed database must choose between two behaviors. A CP system (consistent and partition tolerant) refuses or delays some requests until it can confirm that the answer is current. An AP system (available and partition tolerant) answers every request, but some answers may be stale. Every real database makes one of these choices by default. Many also let you change it per request.

CP by default: ZooKeeper, etcd, HBase, MongoDB, Google Spanner.
AP by default: Cassandra, Amazon DynamoDB with eventually consistent reads, Riak, CouchDB.

The theorem itself is explained in What is the CAP theorem and what trade-offs does it imply for distributed databases?. This page stays with the systems and what each one does when the network breaks.

What each system chooses by default

System Default Why
ZooKeeper CP Writes go through one leader and need a majority of servers to agree before they are confirmed.
etcd CP Uses the Raft protocol; the minority side of a partition cannot keep a leader and stops serving writes.
HBase CP Each region is served by exactly one region server; if that server is unreachable, its rows are unavailable until reassigned.
MongoDB CP One primary per replica set; the default write concern of majority waits for most members before confirming.
Google Spanner CP Paxos groups and synchronized clocks; a partitioned minority stops answering rather than serve stale data.
Cassandra AP Any replica accepts writes; a partitioned node keeps serving its own copy of the data.
Amazon DynamoDB AP Reads are eventually consistent by default and may return data that is up to about a second old.
Riak AP Modeled on Amazon's Dynamo design; conflicting writes are both kept and returned to the client to merge.
CouchDB AP Each node accepts writes on its own, and replication merges them later, keeping conflicts as revisions.

A third group is tunable. Cassandra has consistency levels such as ONE, QUORUM, and ALL. Each level sets how many replicas must respond before a read or write succeeds. DynamoDB accepts a strongly consistent read flag, which costs twice the read capacity of an eventually consistent read. Azure Cosmos DB offers five levels, from strong down to eventual. A tunable system is therefore CP or AP per request, not per database.

Four failure scenarios

etcd during a partition. A five-node cluster splits into a group of three and a group of two. The group of three still holds a majority, so it keeps a leader and accepts writes. A client connected to the group of two gets an error or a timeout on every write until the partition heals. Nothing stale is returned, and nothing confirmed is lost.

MongoDB during a partition. The primary is on the minority side and can no longer reach a majority of the replica set. It steps down within about ten seconds, and the majority side elects a new primary. A write confirmed with w: 1 but not yet replicated is rolled back when the old primary rejoins. With the default majority write concern, every confirmed write survives.

Cassandra during a partition. Two data centers lose their link. With consistency level ONE, a client in each data center keeps writing the same row, and each side confirms at once. When the link returns, Cassandra keeps the write with the latest timestamp and discards the other. This rule is called last write wins. The client whose write was discarded never learns that it was lost.

DynamoDB with eventually consistent reads. A client updates an item and reads it back a millisecond later from a different replica. The read can return the previous value, because that replica has not yet applied the write. Within about a second all replicas agree. A strongly consistent read would have returned the new value, at twice the cost.

PACELC: the trade-off when there is no partition

PACELC extends CAP with a second clause. If there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Even on a healthy network, a write that waits for a majority of replicas pays a round trip. That costs 1 to 5 milliseconds inside one region and 50 to 150 milliseconds across continents.

Spanner and etcd accept that delay in exchange for consistency. Cassandra and DynamoDB answer from the nearest replica and accept staleness in exchange for speed. What the stale side means for readers is described in What is Strong vs Eventual Consistency?.

How to answer "pick CP or AP for this system"

Use a two-line rule. Money, inventory, and anything with a uniqueness rule lean CP. A stale answer there produces a double spend, an oversold item, or a duplicate username. Feeds, counters, likes, and recommendations lean AP. A reader who sees a count that is a few seconds old loses nothing, while a refused request loses the reader.

State the rule, then name the partition behavior you accept. For a payment ledger: "I choose CP; during a partition the minority side returns errors and the client retries". For a like counter: "I choose AP; counts may differ by region for a few seconds and then converge". A mixed answer is often the right one. A store can keep stock levels CP and product reviews AP. How each service in a larger system makes its own choice is covered in How does the CAP theorem apply to microservices architecture?.

How to Prepare

Memorize the two lists above with one sentence of reasoning for each system. The interviewer usually asks for the reason, not the label.
Practice the partition story for one CP and one AP system out loud, in four sentences each. End with what the client sees.
Learn the consistency levels of Cassandra and DynamoDB. You should be able to explain that one database can be CP for one request and AP for the next.
Work through the consistency chapters in Grokking System Design Fundamentals, which cover CAP, PACELC, and consistency models with diagrams.
Design one ledger and one feed end to end in Grokking the System Design Interview, and justify the CP or AP choice in each.

System	Default	Why
ZooKeeper	CP	Writes go through one leader and need a majority of servers to agree before they are confirmed.
etcd	CP	Uses the Raft protocol; the minority side of a partition cannot keep a leader and stops serving writes.
HBase	CP	Each region is served by exactly one region server; if that server is unreachable, its rows are unavailable until reassigned.
MongoDB	CP	One primary per replica set; the default write concern of majority waits for most members before confirming.
Google Spanner	CP	Paxos groups and synchronized clocks; a partitioned minority stops answering rather than serve stale data.
Cassandra	AP	Any replica accepts writes; a partitioned node keeps serving its own copy of the data.
Amazon DynamoDB	AP	Reads are eventually consistent by default and may return data that is up to about a second old.
Riak	AP	Modeled on Amazon's Dynamo design; conflicting writes are both kept and returned to the client to merge.
CouchDB	AP	Each node accepts writes on its own, and replication merges them later, keeping conflicts as revisions.