CAP, ACID, BASE, PACELC

Vocabulary for talking about distributed-system trade-offs.

CAP

Pick two of three when a network partition occurs:

• Consistency — every read sees the most recent write (linearizability).
• Availability — every request gets a non-error response.
• Partition tolerance — system keeps working when network drops messages between nodes.

The trick: P isn’t really optional. Networks partition. So in practice:

• CP system — under partition, refuses requests on the minority side to keep consistency. (Postgres single-primary, Spanner, ZooKeeper, etcd, MongoDB with majority writes.)
• AP system — under partition, both sides keep accepting requests; reconciles later. (Cassandra default, DynamoDB, Riak, CouchDB.)

CA (no partition tolerance) means “single machine” — not really distributed.

What CAP isn’t

• It’s not a steady-state choice. When the network is healthy, CP systems are also available. The trade-off only fires under partition.
• It’s not a binary. Real systems offer tunable consistency: e.g., Cassandra QUORUM reads from a majority of replicas (more consistent), ONE from any (more available).

The dial is per query, not per database:

-- AP end: any replica answers, may be stale.
CONSISTENCY ONE;
SELECT balance FROM accounts WHERE id = ?;

-- CP end: R + W > N, so a read sees the last write.
CONSISTENCY QUORUM;

The rule is R + W > N. With three replicas, writing to two and reading from two guarantees an overlap, so the read touches at least one node that has the write. Set both to ONE and you have saved a round trip and given up the guarantee — which is the correct choice for a view counter and the wrong one for a balance.

PACELC — the missing piece

CAP only describes partition behavior. PACELC adds: even when there’s no Partition, you choose between Latency and Consistency.

If Partition: choose Availability or Consistency. Else: choose Latency or Consistency.

Most distributed systems trade some consistency for latency in normal operation: replicating async (low write latency, stale reads possible) vs sync (high latency, fresh reads). Cassandra is PA/EL by default; Spanner is PC/EC.

ACID vs BASE

ACID (transactional databases):

• Atomicity, Consistency, Isolation, Durability.
• Strong guarantees, lower throughput in distributed settings.

BASE (eventually-consistent stores):

• Basically Available
• Soft state — state can change without input
• Eventually consistent — given no new updates, all replicas converge

BASE was coined as a deliberate antonym to ACID by Eric Brewer’s group. The point: when scale forces you to give up ACID, name what you actually have.

Examples

Eventual consistency in practice

In an AP system, reads can be stale. To bound the staleness:

• Read repair — when a read sees inconsistent replicas, reconcile in the background.
• Hinted handoff — node A is down; node B holds writes destined for A and replays when A recovers.
• Anti-entropy — periodic background gossip to reconcile divergent replicas (Merkle trees in Cassandra).
• Vector clocks — track causality so concurrent updates can be detected (Riak).
• CRDTs — data types that mathematically converge (counters, sets) without coordination.
• Last-write-wins — simplest, but loses concurrent updates.

Linearizability vs serializability

Two different “strong consistency” guarantees often conflated:

• Linearizability — single-object: every read returns the most recent write, in real-time order.
• Serializability — multi-object: result of concurrent transactions equals some serial order (not necessarily real-time).
• Strict serializability — both. What ACID + linearizable gives you. What Spanner provides.

A system can be serializable without being linearizable (PostgreSQL serializable mode does not guarantee real-time ordering across separate transactions). And linearizable without being serializable (single-key linearizable KV store).

Choosing your model

Cheat-sheet for “what consistency do I need”:

Most apps need strong consistency for some data, eventual consistency for the rest. Putting everything in a single CP store is overkill; putting everything in AP is asking for incidents.

Session consistency is the row people skip and the one that fixes the most visible bug: a user saves their profile, the read goes to a lagging replica, and their change appears to have vanished. Route them to the primary until the replica has caught up:

async def read_profile(user_id, wrote_at):
    lag = await replica.replication_lag()
    conn = primary if wrote_at > now() - lag else replica
    return await conn.fetch_profile(user_id)

Read-your-writes for the one user who wrote, eventual consistency for everyone else. That is almost always the right split, and it costs one comparison.