Distributed Systems · 3 of 4

Consistency Models

“Strongly consistent” is not a spec. A consistency model is the exact contract for what a read may return while copies disagree, and the strongest ones cost you availability, latency, or both.

≈ 25 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

The contract

Replicate data and, for some window of time, the copies disagree. A write has reached the leader but not every follower; a message is in flight; a region is cut off. Something has to decide what a read returns during that window. That something is the consistency model: a contract between the data store and the programmer that says which results a read is allowed to give, given the writes that happened around it.

Every replicated store has one, whether it’s documented or not. Replication lag already gave us a few weak guarantees: read-your-writes, monotonic reads and consistent prefix reads. This lesson covers the rest of the spectrum, from “behaves like one copy” down to “converges, eventually”.

A model is a safety property stated over histories, the record of every operation each client issued and the result it got back. A model doesn’t describe the implementation; it says which histories are legal. That makes it testable: record what clients saw, then check the record against the model. Jepsen does exactly this, and has found violations in many of the databases it has tested.

The trade-off runs in one direction. A stronger model rules out more strange histories, so programs on top of it are easier to write. It also forces replicas to coordinate more, which costs latency on every request and, during a network partition, availability.

The ladder of models

The literature is large: one 2016 survey catalogued more than 50 distinct consistency notions. A handful matter in practice, and they nest. Each rung allows every history the rung above it allows.

Strong to weak

strongerweakerLinearizableActs like one copy. Reads see every write that finished before them.SequentialOne order all clients agree on, but it may lag behind real time.CausalCause before effect on every replica; concurrent writes in any order.Session guaranteesread your writesmonotonic readsmonotonic writeswrites follow readsEventualReplicas converge once writes stop. Until then, almost anything goes.
Simplified from Jepsen’s map of non-transactional models. The last step marks which rungs can stay available through a partition.

The availability colouring comes from the same map. Totally available means every non-failing node can keep serving during a partition. Sticky available means the same, as long as each client keeps talking to the same replica. Linearizable and sequential consistency are neither: when the network splits, some node has to stop answering.

Linearizability

Linearizability is the strongest single-object model, defined by Herlihy and Wing in 1990. Informally: the system behaves as if there were one copy of the data, and every operation takes effect atomically at some instant between its request and its reply. Other names for it: atomic consistency, strong consistency, external consistency (Spanner’s term, for its transactional version).

The real-time part is what makes it strong. If operation A finishes before operation B starts, B must see A’s effect, no matter which replicas the two touched. In the hero diagram, Bob’s read started after Alice’s write had returned, so returning 0 is forbidden.

Operations that overlap in time are free to take effect in either order. That gives a precise way to check a history: put one point inside each operation’s interval so that the points, read left to right, behave like a single register. If such a placement exists, the history is linearizable.

Checking a history

Client AClient BClient Creal time →one copy of xwrite x = 1read → 0read → 1read → 1
One lane per client. A bar runs from request to reply; a point marks the instant the operation takes effect.

The failing history is the classic one to remember: a read returns a new value, and a read that starts later returns the old one. Any system that serves reads from replicas without coordination can produce it.

Why you’d pay for this:

  • Locks and leader election. Only one node may hold the lock. “Did anyone else grab it?” has to be answered from the latest state, not a copy that’s a moment behind.
  • Uniqueness constraints. Two users registering the same username at once: exactly one must win, and both must agree on who.
  • Side channels. A web server writes an uploaded photo to storage, then puts “resize it” on a queue. If the resizer reads a stale replica, it resizes the old photo. Queue and storage are different systems, so only a real-time guarantee on the storage makes this safe.

Herlihy and Wing also proved linearizability is local: if every object is linearizable on its own, the whole system of objects is. Sequential consistency doesn’t compose that way.Linearizability is about single operations on single objects. Serializability is about transactions over many objects, with no real-time requirement at all. A serializable database can return stale data. Asking for both gives strict serializability.

Building linearizable systems

The obvious designs don’t deliver it. Two of the most common traps:

Quorums. Leaderless stores read and write a majority, so that with w + r > n every read set overlaps every write set. That guarantees a read can see the latest completed write. It doesn’t stop a read from seeing a write that’s still in flight, and a later read from missing it.

w + r > n is not enough

Reader A ends before reader B starts, yet A sees the new value and B the old one.

The repair, from the ABD register algorithm of the 1990s, is to make the reader write the newest value back to a quorum before it returns. That works for plain reads and writes, but not for compare-and-set, which needs consensus. And any store that resolves conflicts by wall-clock timestamps (last write wins) can reorder writes under clock skew regardless.

Reading from the leader. A single leader that takes every write sounds linearizable for reads too. It is, as long as the leader really is the leader. A leader that’s been cut off and replaced doesn’t know it yet.

The leader that isn’t

Stale reads from the old leader are possible for as long as it hasn’t noticed it was replaced.

So a linearizable read must prove its node is current: confirm leadership with a majority (Raft’s approach, which etcd implements as ReadIndex), route the read through the replicated log, or rely on a time-based lease that assumes bounded clock drift. MongoDB’s "linearizable" read concern does the first. Its docs say these reads “may be significantly slower” than "majority" or "local" reads, and that you should always set maxTimeMS, because if a majority is unreachable the read would otherwise block forever.

Sequential consistency

Sequential consistency is Lamport’s 1979 model for multiprocessor memory: the result is as if all operations ran in some single order, and each client’s operations appear in that order in the sequence it issued them. What’s missing is real time. A client may be served old state, as long as it never goes backwards once it’s seen something newer, and everyone agrees on the same order.

The failing history in the figure above is sequentially consistent: order C’s read first, then the write, then B’s read. No client can tell, unless clients talk to each other outside the database. That’s precisely the side-channel case, and why the gap matters.

ZooKeeper is the well-known example of this shape. Its writes are linearizable, and each client’s requests run in the order it sent them, but reads are served from whatever replica the client is connected to and can be stale. A client that needs the latest value calls sync before reading.

Causal consistency

Most anomalies people actually notice are causal: an answer shown before its question, a reply before the post, a photo shown to someone who’d just been removed from the audience. Causal consistency promises that if one operation could have influenced another (the same client did both, or the second client read the first’s result), every replica shows them in that order. Operations that are concurrent, with no such link, may appear in different orders on different replicas.

Cause before effect

Region USRegion EU
Each write arrived. The order didn’t. Causal consistency restores the order without a cross-region round trip.

The mechanism is dependency tracking. Each write carries what it depends on (version vectors, or the client’s last observed versions), and a replica delays making a write visible until its dependencies are visible. There’s no wait on a remote region in the common case: each region answers from its own replicas.

That’s why causal consistency matters so much: it’s about as strong as a model can be while staying available. A slightly stronger variant, real-time causal, has been proved the strongest model achievable in an always-available, convergent system. Everything above it on the ladder has to stop somewhere during a partition. The catch is metadata: tracking dependencies costs bytes on every write and state on every replica, and it only captures causality that flows through the database. A phone call between users is invisible to it.

Eventual consistency

Eventual consistency promises only convergence: if writes stop, all replicas eventually return the same value. It’s a liveness property, not a safety one. It says nothing about what a read returns before then, or how long “eventually” is. In practice it’s paired with a conflict rule (last write wins, CRDTs, application merges) and background repair (read repair and anti-entropy).

It’s weak, and it’s also the model behind much of the internet, because most reads tolerate a little staleness and availability is worth a lot.

0.0004%of reads to vertices in Facebook’s TAO cache would have returned a different result under linearizability (2015 study)
Dec 2020when Amazon S3 moved from eventual to strong read-after-write consistency, at no extra cost
50+distinct consistency models catalogued in one 2016 survey

Facebook’s 2015 measurement is the useful kind of number: for its workload, anomalies were rare enough that weaker consistency was a good trade. S3’s change is the other side. For years, a LIST could miss a new object and a GET could return an overwritten one, and tools like Hadoop’s S3Guard existed only to paper over that. Since December 2020, every GET, PUT and LIST is strongly consistent.

The CAP theorem

Eric Brewer conjectured it in a keynote at PODC 2000; Seth Gilbert and Nancy Lynch proved it in 2002. Stated precisely: in a system that may suffer network partitions, you can’t have both linearizability and availability, where availability means every request to a non-failing node gets a response.

The only choice

During a partition, a replica that can’t reach the other side must either refuse or risk a stale answer.

The popular version, “pick two of consistency, availability and partition tolerance”, misleads in three ways. Brewer himself wrote in 2012 that it “was always misleading”.

  • Partitions aren’t optional. You don’t choose P; the network chooses it for you. The real choice is what to do during one: refuse (CP) or answer possibly stale (AP). “CA” just means “a system that breaks when the network does”.
  • It’s not system-wide. The choice can differ per operation and per piece of data. A shop can serve its catalogue available-and-stale and run checkout consistent-and-blocking, in the same database.
  • The terms are narrow. C is linearizability only, A is total availability, and the theorem says nothing about latency, crashed nodes or anything outside a partition. Most real systems are neither C nor A in the theorem’s sense, which is why calling a database “CP” or “AP” tells you little.

Brewer’s more useful framing: a partition is just a timeout. When a replica can’t reach its peers within the time it’s willing to wait, it decides, at that moment, between failing the request and proceeding without them. Good designs detect partitions, enter an explicit partition mode that limits risky operations, and run a recovery step afterwards to reconcile.

PACELC

CAP only describes the rare moment of a partition. Daniel Abadi’s 2012 PACELC adds the case that’s always there: if there’s a Partition, choose Availability or Consistency; else, choose Latency or Consistency.

The everyday trade-off

FrankfurtVirginia
No fault in sight, and still a choice: wait for the far replica, or answer now.

The else branch is the one you pay for on every request. Synchronous replication across regions makes every write wait for the slowest acknowledgement it needs. Abadi classified systems as they shipped in 2012: Dynamo, Cassandra and Riak as PA/EL (available in partitions, low latency otherwise); fully ACID systems like VoltDB/H-Store and Megastore as PC/EC; PNUTS as PC/EL. Many modern stores let you pick per request, so treat the labels as defaults rather than identities.

Trade-offs

Model Forbids Needs per operation During a partition
Linearizable stale reads, new-then-old, any real-time reordering a round trip to a majority, or a lease minority side must stop
Sequential disagreement on order, a client going backwards one agreed order (usually a log) some nodes must stop
Causal effects before causes dependency metadata; local reads available, if clients stick to a replica
Read-your-writes, monotonic reads losing your own write, time going backwards a session token or a sticky replica available (sticky)
Eventual permanent divergence nothing on the request path fully available

In the real world

  • etcd serves linearizable reads by default, confirming leadership through Raft, and offers a serializable flag that reads the local copy and may be stale. Jepsen’s 2020 analysis found its key-value operations strict serializable under partitions, pauses and clock skew.
  • Amazon DynamoDB gives every read a choice. Strongly consistent reads go only to the partition’s leader replica; eventually consistent reads can be served by any replica and cost half the read capacity.
  • Cassandra exposes the choice per query through consistency levels, and offers linearizable compare-and-set through lightweight transactions, which run Paxos.
  • MongoDB has read and write concerns per operation, causally consistent sessions, and the "linearizable" read concern for single-document reads on the primary.
  • Spanner offers external consistency, the strictest guarantee, using TrueTime and commit wait. CockroachDB, without atomic clocks, promises “no stale reads”: a read that starts after a write commits sees it. It stops just short of strict serializability (unrelated transactions can rarely appear reversed to a concurrent reader), and it relies on clocks staying within a maximum offset, 500 ms by default.
  • NATS JetStream: Jepsen’s December 2025 analysis noted that the docs described its consistency model as linearizable while also saying the system must “always be available”. Jepsen’s response: linearizable systems can’t be totally available in an asynchronous network. When a vendor claims both, read the fine print.

Pitfalls

  • “Strongly consistent” with no definition. Ask which model, for which operations, under which failures. Many “strong” systems are linearizable for single keys only, or only for reads that go to the leader.
  • Trusting w + r > n. Quorums alone are not linearizable. Neither are leader reads, unless the leader confirms it still leads.
  • Forgetting side channels. A message queue, a webhook or a user’s phone call creates causality the database can’t see. If the reader learns about a write out-of-band, it needs a real-time guarantee or an explicit version to wait for.
  • “We’re AP, so we’re always up.” Total availability is only useful if the stale or conflicting answers are acceptable and you’ve written the code that merges them.
  • Taking vendor labels on faith. Jepsen’s analyses have repeatedly found stores violating their own documented models. Test the guarantee you rely on, under partitions and pauses.

Recall

Go deeper

Keep going

The atomic notes for this lesson live in the knowledge graph:

Next on the map: Consensus (how a cluster agrees on one leader and one log, which is what linearizability is built on) and Serializability (the same questions, for transactions).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Next in Distributed SystemsConsensus