Consistency Guarantees: Eventual, Causal and Linearizable

What a read is allowed to return when data has several copies: eventual, session, causal and linearizable consistency, what each costs, and how CAP fits in.

Overview

When a database keeps several copies of the same data (replicas), the copies do not all change at the same instant. A write reaches one replica first and the others a little later. A consistency model is the promise the database makes about what a read can return while that is happening.

The models form a ladder. The weakest useful one, eventual consistency, only promises that the copies agree in the end. The strongest, linearizability, makes the system behave as if there were a single copy. Each step up removes a kind of surprise for the application, and each step up costs more coordination between replicas: more latency, and less ability to keep working when the network breaks.

Why copies disagree

Most replicated databases copy a write to other replicas in the background (asynchronous replication). A client that reads from a replica the write has not reached yet gets the old value. Nothing is broken; the copy is simply behind. The time it is behind is called replication lag.

Every model below is a rule about which of these stale reads are allowed.

The ladder of models

Eventual — Any recent or older value; copies agree once writes stop — No — Yes, on every replica
Session guarantees — Never older than what this client already wrote or saw — Only per client — Yes, if the client stays with a replica it can reach
Causal — Effects never appear before their causes — Only to track dependencies — Yes, if the client stays with a replica it can reach
Linearizable — The latest completed write, as if there were one copy — Yes — No, the side without a majority must stop

The last column comes from the formal results summarized by Jepsen: causal consistency is 'sticky available' (a client that keeps talking to the same healthy node can make progress during a partition), while linearizability cannot be.

Eventual consistency

Eventual consistency promises one thing: if writes stop, all replicas end up with the same value. It says nothing about how long that takes, and nothing about what a read returns in the meantime. A reader can see a new value, then an older one, then the new one again, if its reads land on different replicas.

That is enough for data where a short delay is harmless, such as a like counter or a cached profile photo. It is not enough when the application acts on what it reads, for example checking a balance before letting a payment through.

Session guarantees

Many surprises users notice come from one person's own actions. The 1994 Bayou paper by Terry and colleagues named four promises that are scoped to one client session and are cheap to provide.

Read your writes — After you write, your reads show that write — Send your reads to the leader for a while, or to a replica that has caught up to your last write
Monotonic reads — Your reads never go back in time — Keep sending your reads to the same replica
Monotonic writes — Your writes are applied in the order you made them — Send them through one leader, or tag them with a sequence number
Writes follow reads — A write you make after reading something is ordered after that thing — Carry the version you read along with the write

A common implementation of read your writes: the client remembers the log position (or timestamp) of its last write, and a replica only answers once it has applied at least that position.

Causal consistency

Two operations are causally related when one could have been influenced by the other: a reply is written after its question was read. Causal consistency promises that everyone sees causes before their effects. Operations that are concurrent (neither could have seen the other) may appear in different orders on different replicas.

Causal consistency stays available during a partition for clients that stay with one replica, which linearizability cannot do. The cost is bookkeeping: each write carries the dependencies it saw, often as version vectors, and a replica holds back a write until its dependencies have arrived.

Linearizability

Linearizability (Herlihy and Wing, 1990) is the strongest single-object model. Every operation appears to happen at one instant somewhere between its start and its end, and those instants respect real time. In practice: once any read has returned the new value, no later read by anyone may return the old one.

Linearizability is what you need for a lock, a leader lease, a uniqueness check (one account per username) or a counter that must not go below zero. Systems provide it with a consensus protocol such as Raft or Paxos, or by sending all reads and writes for a key through one leader that confirms it is still the leader. Each write waits for a majority of replicas, so its latency includes at least one network round trip to them. A read either does the same (the leader checks with a majority that it is still in charge) or relies on a time-based leader lease, which is only safe if clocks drift within known bounds.

A leaderless quorum (write to W replicas, read from R, with W + R > N) is not enough on its own. The overlap guarantees that some replica in the read set has the latest completed write, but while a write is still in flight one reader can see the new value and a later reader the old one, which is exactly the violation drawn above.

To close that gap, a reader must write the value it is about to return back to a write quorum before answering (synchronous read repair), and with several writers each write must first read the current version from a quorum. That is the ABD algorithm (Attiya, Bar-Noy and Dolev). A sloppy quorum, which accepts writes on substitute nodes during a failure, gives up the overlap altogether.

CAP, stated precisely

The CAP theorem (proved by Gilbert and Lynch in 2002) says that when the network drops messages between two groups of nodes, a system cannot be both linearizable and available, where available means every request to a working node gets a non-error response. Network partitions are not optional, so the real choice is what to do during one.

Kleppmann argues that labeling whole databases CP or AP is misleading: CAP uses narrow definitions, and many systems meet neither. A single-leader database with read replicas cannot accept writes on the minority side (not CAP-available) and serves stale reads from replicas (not linearizable). ZooKeeper serves reads from the server a client is connected to, so reads can be stale unless the client calls sync first. A better interview answer names the guarantee each operation gets.

etcd — Linearizable reads and writes by default; a serializable read option trades that for lower latency
ZooKeeper — Writes in one total order; reads may be stale unless preceded by sync
Amazon DynamoDB — Eventually consistent reads by default; strongly consistent reads on tables and local secondary indexes, never on global secondary indexes
Apache Cassandra — Chosen per request: ONE, QUORUM, ALL and others; W + R > RF makes read and write sets overlap, which alone is not linearizability; lightweight transactions (Paxos) are needed for that

Consistency is not isolation

The word consistency means different things in different places. The C in ACID means the application's rules hold after a transaction. The C in CAP means linearizability. Isolation levels answer a different question: how concurrent transactions that touch several rows see each other.

Consistency model — What can a read of one object return while copies disagree? — Eventual, causal, linearizable
Isolation level — How do concurrent multi-row transactions interact? — Read committed, snapshot isolation, serializable
ACID consistency — Do the application's invariants hold? — A balance never below zero

Defaults differ by product: PostgreSQL uses Read Committed and implements Repeatable Read as snapshot isolation; MySQL's InnoDB defaults to Repeatable Read. The strongest combination, strict serializability, is serializable transactions that also respect real time.

What you will be able to do

Explain why replicas return stale data and name the model that rules out each kind of surprise.
Choose a consistency level per feature in a design and say what it costs.
State the CAP theorem precisely and explain why CP and AP labels mislead.
Implement read your writes and monotonic reads on top of asynchronous replicas.
Keep consistency models, isolation levels and ACID consistency apart in an interview.

Key concepts

Replication lag: The delay between a write reaching one replica and reaching another. Stale reads happen inside that window.
Eventual consistency: If writes stop, all replicas converge to the same value. No bound on how long it takes or on what reads return meanwhile.
Read your writes: A session guarantee: after a client writes, that client’s reads include the write. Other clients get no such promise.
Monotonic reads: A session guarantee: a client’s successive reads never return older data than an earlier read did.
Causal consistency: Operations that may have influenced one another are seen in the same order by everyone. Concurrent operations may be seen in any order.
Linearizability: Every operation appears to take effect at one instant between its start and end, in an order that respects real time. The system behaves as if it had one copy.
CAP theorem: During a network partition, a system cannot be both linearizable and available to every working node. It must refuse some requests or risk stale answers.
Quorum: A group of replicas large enough that any two groups overlap. With W + R > N, a read quorum shares at least one replica with the last completed write quorum. Overlap alone does not make reads linearizable.
Strict serializability: Serializable transactions whose order also respects real time. It combines the strongest isolation with linearizability.

When to use it

Deciding, feature by feature, which reads in a design may be stale and which may not
Answering a CAP or PACELC question with precise terms instead of CP and AP labels
Explaining a user-visible bug such as a comment that disappears after a refresh
Choosing a consistency level per request in DynamoDB or Cassandra
Deciding when a lock, lease or uniqueness check needs a consensus-backed store

Interview questions

What does the CAP theorem mean in practice when you design a distributed system?
A user edits their profile, refreshes, and sees the old version. What is happening and how do you fix it?
What is the difference between linearizability and serializability?
Why is causal consistency interesting if linearizability is stronger?
How would you choose consistency levels for the parts of a social app?