CAP Theorem & PACELC: What Real Databases Choose

Q: What does the CAP theorem actually say?

Something much narrower than its whiteboard reputation. The theorem uses three precise definitions: Consistency means linearizability — every read returns the most recent completed write, as though a single copy of the data existed; Availability means every request to every non-failed node receives a response; and Partition tolerance means the system keeps its guarantee while the network drops messages between nodes. The proof shows you cannot have all three simultaneously during a network partition: if two sides of a partition both keep answering (availability), they cannot agree on the latest write (consistency), and vice versa. Three things the theorem does not say, which cause most of the confusion: it says nothing about latency, which in practice dominates design decisions far more than rare partitions; it says nothing about normal, partition-free operation, which is almost all of a system's life; and it does not classify whole products as CP or AP — those properties attach to specific configurations and operations (a quorum setting, a read mode, a replication choice), which is Kleppmann's well-known correction. It also treats consistency as binary, when real systems occupy a dozen distinct levels between linearizable and eventual — the Jepsen consistency hierarchy is the practical map. The theorem is true and useful; the triangle diagram asking you to "pick two" is neither, because partition tolerance was never a menu option.

Q: What is PACELC and how is it different from CAP?

PACELC is the extension that covers the part of a system's life CAP ignores. It reads: if Partition, choose Availability or Consistency; Else — during normal, partition-free operation — choose Latency or Consistency. The insight is that the consistency-versus-latency trade exists every millisecond, not just during rare network failures. Keeping replicas strongly consistent means coordinating before acknowledging a write: a quorum round trip, which within a region costs single-digit milliseconds but across continents costs 60 to 150 ms — per write, forever. Relaxing consistency lets writes acknowledge locally and replicate asynchronously, which is fast but means a reader elsewhere can briefly see stale data. That everyday trade shapes p99 latency, multi-region architecture, and cloud bills far more than partition behavior does, because partitions might sum to an hour a year while the Else clause runs continuously. The classification also describes real systems more honestly: DynamoDB defaults and Cassandra are PA/EL (available during partitions, fast normally); Spanner, CockroachDB, and etcd are PC/EC (consistent during partitions, paying coordination normally); MongoDB with majority write concern leans PC/EC. And the same system often moves between cells based on configuration — which is the deeper point: PACELC positions are chosen per configuration and per workload, not stamped on a product.

Q: Is MongoDB CP or AP? Is Cassandra AP?

The honest answer is that the question is malformed, and the labels move with configuration. MongoDB with majority write concern and majority read concern behaves PC/EC-ish: writes coordinate through a primary, a partitioned minority stops accepting writes, and failover pauses writes rather than forking history — but run it with weaker write concerns and acknowledged writes can be lost on failover, which is not what anyone means by CP. Cassandra is marketed AP, and with ONE/ONE consistency levels it is emphatically PA/EL — but set QUORUM reads and writes on N=3 and the R+W>N overlap gives you read-your-writes behavior at the cost of latency and some availability, which is not what anyone means by AP either. This is Kleppmann's point in "please stop calling databases CP or AP": under the theorem's strict definitions, many systems are technically neither (a primary-based system is not CAP-available, because clients partitioned from the primary get refused; a quorum system with R+W>N is not linearizable in every failure interleaving), and the letters attach to specific operations under specific settings. The practical discipline: instead of asking what a database is, ask what this configuration guarantees for this operation — what happens to acknowledged writes on failover, what a read can see during replication lag, what the minority partition refuses. Vendors answer those questions in their tuning documentation, not their marketing pages.

Q: What is quorum consistency and what does R + W > N mean?

Quorum systems replicate each piece of data to N nodes and let you choose how many must participate in each operation: W nodes must acknowledge a write, R nodes must answer a read. The arithmetic that matters: if R + W > N, every read set overlaps every write set in at least one node, so a read always touches at least one replica holding the latest acknowledged write — giving you read-your-writes behavior and, with careful implementation, something close to strong consistency. The canonical setup is N=3, W=2, R=2: writes survive one node failure, reads see the latest write, and both pay one extra replica's worth of coordination. Drop to R=1 and reads get faster and more available — and can return stale data, because the one replica answering may not have the latest write yet; that is eventual consistency, deliberately purchased for latency. W=1, R=1 on N=3 is the fully loose end of the dial: fastest, most available, and staleness-prone — legitimate for telemetry, dangerous for anything with an invariant. Two traps worth naming: quorum overlap is weaker than true linearizability under some failure interleavings (sloppy quorums and hinted handoff weaken it further, trading consistency for availability during node failures); and "we use quorums" means nothing without the numbers — R=1, W=1 with three replicas is eventual consistency wearing a quorum costume. The dial is per-query in systems like Cassandra, which is the right granularity: strong for the account balance, loose for the activity feed.

Q: How does Google Spanner get strong consistency across regions?

By paying the Else-clause cost deliberately, with hardware assistance to keep it as low as physics allows. Spanner provides external consistency (linearizability across the whole system, globally) using two mechanisms. First, synchronous replication through Paxos: a write commits only after a quorum of replicas across zones or regions accepts it, so an acknowledged write is durable and visible everywhere that matters — this is the coordination round trip that PA/EL systems skip. Second, TrueTime: Google equips datacenters with GPS and atomic clocks so every node knows the current time within a small explicit uncertainty bound, and Spanner uses that bound to order transactions globally — a transaction waits out the clock uncertainty before committing, ensuring timestamps reflect real time ordering without a global coordinator. The result is a PC/EC system: during partitions, minority partitions refuse writes (consistency over availability); during normal operation, every write pays coordination latency (consistency over latency). CockroachDB follows the same architectural position using Raft and software clock management without the specialized hardware, accepting somewhat different latency characteristics. The lesson for everyone not running Google's infrastructure: global strong consistency is achievable but never free — the coordination cost is real, measured in tens of milliseconds per cross-region write, and the honest question is which of your workloads actually carry invariants that justify paying it, versus which are riding along because someone chose one database for everything.

Q: When is eventual consistency good enough?

Whenever a briefly stale read costs less than the latency and availability you would spend preventing it — which describes far more workloads than teams assume, and fewer than eventual-consistency enthusiasts assume. It is comfortably good enough for telemetry, analytics events, activity feeds, view counters, recommendation inputs, caches, and search indexes: staleness windows of seconds are invisible, volumes are high, and the latency budget is real. It is conditionally acceptable for user-facing state like profiles and carts if you add session guarantees — read-your-writes for the user who just made the change (via sticky routing, session tokens, or quorum reads for that user), because the staleness users actually notice is their own missing update, not someone else's. It is not acceptable where an invariant must hold at all times: uniqueness (two users claiming one username), floors and ceilings (inventory that cannot go negative, spending caps), and anything where money moves — these need strong consistency, single-writer designs, or explicit locking, because "eventually" is exactly when the double-spend happens. The design discipline is to classify workloads by what breaks when a read is stale: nothing visible → eventual, user confusion → session-consistent, broken invariant → strong. And when the invariant spans services rather than one database, no consistency level rescues you — that is saga-and-outbox territory, where you replace coordination with explicit compensation. The failure mode in both directions is a blanket policy: all-strong pays coordination tax on telemetry; all-eventual runs billing on hope.

Q: Does the CAP theorem apply to a single Postgres database?

Not while it is genuinely single-node — and understanding why clarifies both the theorem and Postgres deployments. CAP is about distributed state: it needs at least two nodes that can be partitioned from each other. One Postgres instance has no partition to tolerate; its trade-offs live on other axes entirely (the ACID isolation-level dial, durability via WAL fsync, vertical scaling limits). This is the honest reason single-node Postgres remains the right default for most applications: it dodges the entire distributed-consistency problem class. The theorem arrives the moment you add a second copy of the data. Add an asynchronous read replica and you have chosen PA/EL without a meeting: replica reads can be stale (replication lag is your consistency window), and if you fail over to an async replica, commits the primary acknowledged but had not yet shipped are gone — meaning some writes you told users were durable, were not. That failover data-loss window is a CAP position wearing operational clothes. The mitigations are the standard menu: synchronous replication for writes that must survive failover (paying the round trip — the EC choice), bounded-lag monitoring with routing rules for reads that must be fresh, and honest documentation of which reads may lag. The broader pattern: you do not adopt distributed-systems trade-offs when you pick a "distributed database" — you adopt them the moment data exists in two places, including the humble replica bolted onto the monolith.

Q: How should I choose a consistency model for my system?

Per workload, by invariant, starting from what breaks when a read is stale — never per company or per architecture diagram. The procedure that works in practice has four steps. First, inventory invariants: walk the data model and name every rule that must hold at all times — uniqueness constraints, non-negative balances, capacity limits, money conservation — and separately list the workloads where staleness is merely cosmetic (feeds, counters, telemetry). Second, map each class to the cheapest level that protects it: strong consistency (or single-writer designs) for the invariants; session consistency or quorum reads for the user-facing middle where people must see their own writes; eventual consistency for everything whose staleness nobody can observe. Third, respect the boundary rule: consistency levels apply within one system — an invariant spanning two services gets no protection from either one's settings, and needs sagas, outboxes, and idempotency instead; similarly, prefer keeping a critical invariant inside one database transaction over distributing it and buying it back at 10x complexity. Fourth, price the Else clause: for each workload you marked strong, ask whether it tolerates the coordination latency (and, multi-region, the 60-150 ms round trips); for each you marked eventual, ask who notices the staleness window at p99 replication lag. Then write the positions down and drill the partition case, because an untested failover story is a hypothesis. The most common outcome of this exercise is relief: most workloads are cheaper than feared, and the two that are not now have names and owners.

Satyam Kumar

Retour au blog

ai-architecture

The CAP Theorem, PACELC, and What Real Databases Actually Choose

By Satyam KumarJuly 12, 20269 min read

cap theorem pacelc distributed systems eventual consistency linearizability quorum reads writes dynamodb consistency google spanner cassandra consistency consistency models partition tolerance multi-region architecture read replicas database architecture system design interview 2026

The CAP Theorem, PACELC, and What Real Databases Actually Choose

Frequently Asked Questions

Partager l'article

Twitter LinkedIn WhatsApp

Satyam Kumar

Founder & AI Architect, AppScale LLP

Architecte AI & Cloud. J'aide les équipes à construire des systèmes qui scalent pour des millions.

LinkedIn GitHub

The CAP Theorem, PACELC, and What Real Databases Actually Choose

Frequently Asked Questions

Partager l'article

Comments

Leave a comment