Skip to content
Tutorials Center
My learning

Topics

Lesson 65 of 79 ยท Distributed Databases, NoSQL and Analytics

CAP, BASE and Consistency Models

Understand the CAP theorem, PACELC, BASE, eventual, causal and strong consistency, quorum reads and writes, and linearizability, with runnable Python simulations.

Once data lives on several machines, as in replication and sharding, two questions appear that a single server never had to answer. First: when a client reads, which version of the data may it see? Second: when machines cannot talk to each other, should the system keep answering requests or stop? The CAP theorem and the family of consistency models are the vocabulary for these questions, and they explain why different database products behave so differently.

This lesson explains CAP and its refinement PACELC, contrasts ACID with BASE, ranks the main consistency models from strong to weak, and lets you experiment with quorums, a network partition and a linearizability checker. All simulations are small Python models running in your browser.

The three letters of CAP

Consistency Every read sees the latest write.
Availability Every request gets an answer.
Partition tolerance The system works despite lost messages.

Partitions happen, so the real choice is C or A.

1 / 2

The CAP theorem

Eric Brewer conjectured, and Gilbert and Lynch later proved, that a distributed data store cannot guarantee all three of the following at the same time:

  • Consistency (C): every read returns the most recent successful write (the precise meaning is linearizability, described below). This is not the "C" of ACID, which is about constraints.
  • Availability (A): every request to a non-failing node receives a (non-error) response, without a guarantee that it contains the latest write.
  • Partition tolerance (P): the system keeps working even if the network drops or delays arbitrary messages between nodes.

The popular slogan "pick two of three" is misleading. Network partitions are a fact of life (cables break, switches reboot, whole data centers become unreachable), so a distributed system must tolerate partitions. The real question is what to give up while a partition is in progress:

  • A CP system refuses requests it cannot answer correctly (for example the minority side of the partition rejects reads and writes). It stays consistent but is unavailable for some clients.
  • An AP system keeps answering on both sides. It stays available, but the two sides may diverge and must be reconciled afterwards.

When there is no partition, a system can have both C and A. CAP says nothing about performance in normal times, which is why a second formulation exists.

flowchart LR
  W["Client write"] --> P{"Network partition?"}
  P -->|"no"| N["Consistency and availability both possible"]
  P -->|"yes"| X{"Choose"}
  X -->|"C"| CP["Reject requests on the minority side"]
  X -->|"A"| AP["Answer on both sides, reconcile later"]

During a partition the system must sacrifice either consistency or availability.

Simulating a partition

In the simulation, a cluster of three nodes splits into {A, B} and . Both clients write the same key. The CP variant needs a majority (2 of 3 nodes) for any operation; the AP variant answers from whatever nodes it can reach.

Python CP versus AP during a network partition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The CP cluster rejects everything on the minority side, but nothing is ever inconsistent. The AP cluster serves both clients, yet during the partition client 2 reads v2 while client 1 reads v1. Healing requires a conflict resolution policy: last-writer-wins (simple but can drop updates), version vectors that detect concurrent writes, or application-level merging (CRDTs, shopping-cart union).

PACELC: the rest of the time

CAP only describes behavior during partitions, but trade-offs exist all the time. Daniel Abadi's PACELC says: if there is a Partition, choose between Availability and Consistency; Else, when the system runs normally, choose between Latency and Consistency. Waiting for several replicas to confirm a write (consistency) takes longer than answering after one copy has it (latency). A system can be PA/EL (fast and available, weak consistency: Dynamo-style stores with default settings), PC/EC (always consistent, pays latency and some unavailability: many Raft- or Paxos-based stores), or a mix.

ACID versus BASE

Traditional relational databases promise ACID. Many distributed NoSQL stores favor BASE, a deliberately contrasting acronym:

  • Basically Available: the system answers even when parts of it fail.
  • Soft state: the state of the data may change over time without new input, because replicas are still converging.
  • Eventual consistency: if no new updates arrive, all replicas will eventually hold the same value.

ACID and BASE are two ends of a spectrum rather than rival camps; many systems let you choose per operation, and several modern databases (Spanner, CockroachDB) offer strongly consistent distributed transactions at a latency cost.

Consistency models

A consistency model is a contract about which histories of reads and writes the system may show you. From strongest to weakest:

  • Linearizability (strong consistency). Every operation appears to take effect at a single instant between its start and its end, and all clients agree on the order. The system behaves like one copy. Once a write completes, every later read, by anyone, sees it.
  • Sequential consistency. All operations are seen in one order that respects each client's own program order, but that order need not match real time.
  • Causal consistency. Operations that are causally related (a reply after the message it answers) are seen in that order by everyone. Unrelated, concurrent operations may appear in different orders on different nodes.
  • Session guarantees. Weaker, per-client promises: read your writes, monotonic reads (never go back to older data), monotonic writes and writes follow reads. They are cheap and fix the most visible anomalies.
  • Eventual consistency. Only the promise that replicas converge when updates stop. In between, anything goes.

Stronger models are easier to program against and slower and less available. Choose the weakest model your application can tolerate for each piece of data: a "like" counter can be eventually consistent; a bank balance should not be.

Quorum reads and writes

Leaderless stores in the Dynamo tradition (Cassandra, Riak, DynamoDB) keep N replicas of each key and let the client choose how many must take part in each operation: W replicas must acknowledge a write and R replicas are asked on a read. The reader takes the value with the highest version. The rule is

TEXT
R + W > N   =>   every read set overlaps every write set in at least one replica

If the sets overlap, at least one replica in the read set has the latest write, and the version number identifies it. Typical settings with N = 3: W = 2, R = 2 (balanced and tolerates one failed node); W = 3, R = 1 (fast reads, writes need all nodes); W = 1, R = 1 (fastest, may read stale data).

The program tries every possible write set and every possible read set for N = 5 and counts the stale reads.

Python Quorum overlap: when can a read be stale?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Whenever R + W > N the count is zero; whenever R + W <= N some combination of sets misses the new value. For example W = 2 and R = 2 on five nodes can give a stale read in 30 of 100 combinations. Quorums alone do not make a store linearizable: with sloppy quorums, concurrent writes, clock problems or failed writes that reached only some replicas, anomalies still occur. They give you a tunable dial between latency, availability and staleness.

Besides quorums, eventually consistent stores use background repair: read repair (a reader that notices a stale replica writes the newer value back) and anti-entropy (replicas periodically compare data, often with Merkle trees, and exchange differences).

A first look at linearizability

Linearizability is defined on a history of operations, each with a start and end time. A history is linearizable if the operations can be arranged in one sequence such that (1) every read returns the value of the most recent write in the sequence, and (2) if operation A finished before operation B started, A comes first. Operations that overlap in time may be ordered either way.

The checker below tries every ordering of a few histories on a single register that starts at 0.

Python A brute-force linearizability checker

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cases A and B are both allowed: the read overlaps the write, so either result is fine. Case C is the textbook violation: the write had completed before the read began, yet the read returned the old value. Case D shows the "going back in time" anomaly: once any client has seen the new value, no later read may return the old one. These are exactly the guarantees that eventually consistent stores do not give, and that Raft-based or Spanner-like systems pay latency to provide.

Choosing in practice

Ask what a stale or conflicting read costs. Money, inventory counts and uniqueness constraints usually need strong consistency (possibly just for these rows). Timelines, counters, caches and recommendations tolerate eventual consistency. Many applications mix both, with a strongly consistent store for the core data and weaker stores for derived data. We look at the families of such stores in NoSQL databases.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. During a network partition, a CP system will typically

    CP means consistency is preserved at the cost of availability for some clients. The minority side cannot safely answer and refuses.
  2. 2. With N = 3 replicas, which setting guarantees that a read sees the latest acknowledged write?

    R + W must exceed N. 2 + 2 = 4 > 3, so every read set overlaps every write set. 1 + 1 and 1 + 2 do not exceed 3.
  3. 3. What does PACELC add to CAP?

    PACELC: if Partition, choose A or C; Else, choose Latency or Consistency. Waiting for more replicas costs time.
  4. 4. A write completes. Afterwards, a different client starts a read and gets the old value. Which model is violated?

    Linearizability requires that a read starting after a write has finished sees that write (or a later one). Eventual consistency allows such stale reads for a while.

Summary

  • CAP: when the network partitions, a distributed store must choose between consistency (reject some requests) and availability (answer, possibly with divergent data); PACELC adds the latency-versus-consistency trade-off during normal operation.
  • BASE (basically available, soft state, eventually consistent) is the loosely stated opposite of ACID; many systems let you choose per operation.
  • Consistency models range from linearizable and sequential through causal and session guarantees to eventual consistency; stronger means simpler to program but slower.
  • Quorums with R + W > N make read and write sets overlap; they reduce staleness but are not a full guarantee of linearizability.
  • Linearizability means every operation appears to take effect instantly at some point between its start and end, in an order that respects real time.

Next: NoSQL Databases: Key-Value, Document, Column and Graph.