Consistency models

The problem it solves

A profile service keeps three copies of every row: a leader and two followers, replicated asynchronously. Followers are usually 5 to 50 ms behind. During a write burst or a long query on a follower, one of them falls 8 seconds behind. Reads go to whichever copy the load balancer picks.

Alice changes her display name and the page reloads. The reload lands on the lagging follower and her old name is back. She changes it again. Now there are two writes in flight and a support ticket.

Nothing is broken. Every copy will hold the new name within 8 seconds. The question is what a read is allowed to return while the copies disagree. That is what a consistency model is. It’s a contract between the store and its callers, about which values a read may return, given the history of writes. Each contract rules out a specific set of things users can see:

What the user sees	The broken guarantee
My own edit vanished on reload	Read-your-writes
A comment appeared, then disappeared on refresh	Monotonic reads
A reply showed up before the question it answers	Causal consistency
My friend said she paid me, my app shows nothing	Linearizability
Two people liked a post, the count went up by one	Isolation (lost update)
Two doctors went off call at once and nobody was on call	Isolation (write skew)

Stronger contracts rule out more, and cost more. A read that must reflect every acknowledged write has to ask the leader, or a majority of replicas. Across regions, that is 70 to 200 ms per read, instead of under 1 ms locally. So real systems pick a contract per operation. The payment state change gets the strongest one. The like counter gets something weaker. The “online” dot gets the weakest.

There are two separate questions here, and mixing them up is the most common error in this topic. Consistency in the distributed sense is about one object with many copies: does a read see the latest write? Isolation is about many objects touched by concurrent transactions: does a transaction behave as if it ran alone? A single Postgres server has no replica problem and every isolation anomaly.

How it works

Step 1: Eventual consistency, the floor

Eventual consistency promises one thing: if writes stop, all replicas eventually hold the same value. It says nothing about what a read returns before then. And it gives no bound on how long “eventually” is. Any old value may be returned. Values may go backwards between two reads. And writes may show up in a different order on different replicas.

It is cheap for a reason. Any replica can answer any read, and accept any write. So latency is local (under 1 ms in the same zone), and every replica keeps working when the network splits. Typical lag is milliseconds in one region, and 100 ms to 1 s across regions. But under a repair backlog or a failed link, it is minutes.

Convergence also needs a rule for concurrent writes to one key. There are three common ones:

• Last writer wins, by timestamp. It’s simple, and it silently drops the other write.
• Siblings, kept for the application to merge.
• CRDTs, whose merges commute.

The replication page covers each. “Eventual” is a statement about the end state only. Everything a user notices happens before that.

Step 2: Session guarantees fix what one user sees

Most complaints about eventual consistency come from one user contradicting themselves: their own edit vanishing, a page going back in time. Terry and others defined four session guarantees for the Bayou system in 1994 to rule these out without strengthening the store for everyone else. A session is one client’s sequence of operations, usually one user on one device.

Guarantee	Promise	The anomaly it removes
Read-your-writes	A read reflects every earlier write in the same session	Alice saves her name, reloads, sees the old one
Monotonic reads	A read never returns an older state than an earlier read in the session	A comment appears, then disappears on refresh
Monotonic writes	A session’s writes are applied everywhere in the order it made them	Alice hides her posts from Bob, then posts a photo; Bob sees the photo
Writes-follow-reads	A write is ordered after every write the session had read before making it	Bob replies to a question; elsewhere the reply shows up without the question

One mechanism gives all four. The client keeps a session token. It’s the highest version it has written or read: a log position, or a vector of positions per partition. Every request carries it. A replica answers a read only if it has applied at least that version. Otherwise it waits briefly, or the request goes to a replica that has. A write carries the token too. A replica applies it only after everything the token covers.

Monotonic reads, broken and fixed with a session token

Scroll or pinch to zoom, drag to pan

• Color key
• Database
• Service

Sticky routing (monotonic reads), and “read from the leader for 10 s after a write” (read-your-writes), are simpler. But they break on failover, or a device switch. A token can live with the account.

Session guarantees promise nothing across users. If Alice tells Bob “I just commented”, Bob’s session has never seen her comment, and his read may legally miss it.

Step 3: Causal consistency fixes cause and effect for everyone

Causal consistency extends session ordering across users. Write B causally depends on write A if the same session made A first, or B’s writer had read A (directly or through a chain). The rule: every reader sees A before B. Writes with no causal link are concurrent, and different readers may see them in different orders.

A reply arriving before its question, the causal anomaly

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

Causal consistency forbids that last read: Bob’s reply carries a dependency on Alice’s post, so replica 2 holds the reply until the post arrives. Carol may see the question alone, or both, never the reply alone.

Implementations take one of two routes. Some attach explicit dependencies to each write (COPS, 2011, and the session token above), and buffer a write until its dependencies are applied. Others stamp writes with a clock that respects causality (step 6). Then they read from a snapshot at or after the session’s highest timestamp. MongoDB’s causally consistent sessions do this, with afterClusterTime.

The four session guarantees together give causal consistency for any one session’s view. That’s why the demo below treats them as one level.

Causal is also, roughly, the strongest model that can stay available on both sides of a network partition. A replica cut off from the others can keep serving its clients’ reads and writes, without violating it. That holds as long as each client stays with a replica it can reach. (Mahajan, Alvisi and Dahlin proved the precise version in 2011.) Everything stronger needs coordination. And coordination stops when the network splits.

Step 4: Sequential consistency, one order for everyone

Sequential consistency (Lamport, 1979) adds a single total order of all operations, which every client agrees on. It’s consistent with each client’s own program order. So concurrent writes are no longer seen in different orders by different readers. What it does not require is that the order match real time. A read may still return a value that, in wall-clock time, was already overwritten.

The usual implementation is a single leader that orders every write, plus followers that apply the log in order. Reads can go to any follower that is at least as far along as this client has seen. ZooKeeper is the textbook case. Writes are linearizable, through the leader. Reads are served locally by whichever server the client is connected to, and may be stale. A client that needs the latest value calls sync first.

The anomaly that remains is the one in the table at the top. Alice sends Bob $50, and tells him by phone. His app shows nothing. There is one order of writes, and Bob’s follower is just behind in it. Nothing in the system knows about the phone call.

Step 5: Linearizability, as if there were one copy

Linearizability (Herlihy and Wing, 1990) is the strongest single-object model. Every operation appears to take effect at one instant, between when it was sent and when it returned. Two consequences make it useful:

• Once a write is acknowledged, every read that starts afterwards sees it, whoever makes it.
• Once any read has returned a new value, no later read anywhere returns the old one.

It is what “strong consistency” usually means, and it is what CAP’s C means. Things that need it: a lock or a leader lease (two holders is a bug). A uniqueness check (one user per username). A compare-and-set on a balance or a seat. And a fencing token that must only go up.

The cost is that a read can no longer be answered from local state alone. A leader that believes it is still the leader may have been replaced 2 seconds ago by a partition it cannot see. So a linearizable read must either confirm leadership with a majority or rely on a time-bounded lease:

A linearizable read in Raft, using ReadIndex

Scroll or pinch to zoom, drag to pan

• Color key
• Database

That is one majority round trip per read, usually batched. A lease read skips it. Followers promise not to elect a new leader for a few seconds. That bets on bounded clock drift, and on the leader never pausing longer than its margin.

Linearizability is per object. It composes across keys but says nothing about transactions, which is step 7.

Pick a level and a scenario and replay it. Each scenario is one anomaly from the table at the top. As the level gets stronger the routing changes: a session token, then dependency buffering, then one leader for writes, then the leader for reads too.

Consistency level

EventualRead your writesCausalSequentialLinearizable

Scenario

Edit, then reloadRefresh twiceHide, then postTold by phoneTwo likes at once

PlayStepReset

At Eventual, which anomalies can users see?

Try “Told by phone” at every level: only linearizable fixes it, because the call is invisible to the system. Then “Two likes at once” at causal: still broken, because concurrent likes have no order to protect.

Each model includes everything below it

Scroll or pinch to zoom, drag to pan

• Color key
• Service

Blue models need coordination and stop on the minority side of a partition. Green ones can stay available, as long as each client keeps reaching the same replica.

Step 6: Clocks that respect causality

Every implementation above needs to order events. Physical clocks cannot do it alone. NTP keeps servers within a few milliseconds in a good datacenter, and within hundreds of milliseconds in a bad one. So a reply stamped on a slow clock can sort before the question it answers. That is exactly how last-writer-wins loses data.

A hybrid logical clock (HLC, Kulkarni and others, 2014) fixes the ordering, without new hardware. A timestamp is a pair: a wall-clock part and a counter. On every local event, take the physical clock if it moved forward. Otherwise, bump the counter. On every message received, jump to the sender’s timestamp if it is ahead.

The result stays within the clock skew of real time. So “read as of 10:00:05” still means something. And if event B saw event A, B’s timestamp is larger, even when B’s clock is behind. CockroachDB and YugabyteDB stamp transactions with HLCs. MongoDB’s cluster time is a close cousin.

JHybridLogicalClock.javaPyhybrid_logical_clock.pyC#HybridLogicalClock.csGohybrid_logical_clock.goTShybrid-logical-clock.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.function.LongSupplier;

// Compared as a pair: wall time first, then the counter.
record Timestamp(long wallMs, int logical) implements Comparable<Timestamp> {
    public int compareTo(Timestamp o) {
        int c = Long.compare(wallMs, o.wallMs);
        return c != 0 ? c : Integer.compare(logical, o.logical);
    }
}

// Hybrid logical clock (Kulkarni and others, 2014). Timestamps stay within the clock skew
// of real time, so "as of 10:00:05" still means something, yet an event that saw another
// event always gets a larger timestamp, even when its own clock runs behind.
class HybridLogicalClock {
    private final LongSupplier physicalMs;
    private final long maxOffsetMs;
    private Timestamp last = new Timestamp(0, 0);

    HybridLogicalClock(LongSupplier physicalMs, long maxOffsetMs) {
        this.physicalMs = physicalMs;
        this.maxOffsetMs = maxOffsetMs;
    }

    // A local event or a send. Take the physical clock if it moved past what we have seen;
    // otherwise keep the wall part and bump the counter, so time never goes backwards.
    synchronized Timestamp now() {
        long pt = physicalMs.getAsLong();
        last = pt > last.wallMs() ? new Timestamp(pt, 0) : new Timestamp(last.wallMs(), last.logical() + 1);
        return last;
    }

    // A receive. The result must exceed both what we had and what the sender stamped:
    // that is what makes "B saw A" imply ts(B) > ts(A).
    synchronized Timestamp update(Timestamp remote) {
        long pt = physicalMs.getAsLong();
        if (remote.wallMs() - pt > maxOffsetMs) {
            // A sender far in the future would drag every clock with it. CockroachDB treats this
            // as a broken clock and refuses, rather than let one node's skew spread.
            throw new IllegalStateException("remote clock is beyond the maximum offset");
        }
        long wall = Math.max(Math.max(last.wallMs(), remote.wallMs()), pt);
        int logical;
        if (wall == last.wallMs() && wall == remote.wallMs()) logical = Math.max(last.logical(), remote.logical()) + 1;
        else if (wall == last.wallMs()) logical = last.logical() + 1;
        else if (wall == remote.wallMs()) logical = remote.logical() + 1;
        else logical = 0; // our physical clock is ahead of both: plain wall time again
        last = new Timestamp(wall, logical);
        return last;
    }
}

class Main {
    public static void main(String[] args) {
        // Node A's clock runs 120 ms ahead of node B's. Real time is 10,000 ms for both.
        HybridLogicalClock a = new HybridLogicalClock(() -> 10_120, 500);
        HybridLogicalClock b = new HybridLogicalClock(() -> 10_000, 500);

        Timestamp question = a.now(); // Alice posts a question on node A
        b.update(question); // Bob's node receives it (Bob reads the question)
        Timestamp answer = b.now(); // Bob replies on node B
        System.out.println("question " + question.wallMs() + ":" + question.logical()); // question 10120:0
        System.out.println("answer   " + answer.wallMs() + ":" + answer.logical()); // answer   10120:2, after the question
        System.out.println(answer.compareTo(question) > 0); // true. B's raw clock says 10,000, which would have put it first
    }
}

An HLC gives causal order, not real-time order. Two transactions on different nodes with no message between them can still be stamped in the wrong real-time order, by up to the clock skew. Closing that gap is what Spanner’s TrueTime is for, in the options below.

Step 7: Isolation is a different axis

Everything above concerns one object. Transactions read and write several, and isolation says how concurrent transactions may interleave. The ideal is serializable: the result equals some serial order of the transactions. Databases default to weaker levels because serializable costs throughput, and each weaker level allows specific anomalies.

Anomaly	Example	Read committed	Snapshot isolation	Serializable
Dirty read	Reading another transaction’s uncommitted write	Prevented	Prevented	Prevented
Read skew	A transfer between two accounts, read halfway: $100 seems to vanish	Possible	Prevented	Prevented
Lost update	Two read-modify-writes of one counter, one increment lost	Possible	Prevented in Postgres, possible in MySQL	Prevented
Write skew	Two doctors each check “someone else is on call” and both leave	Possible	Possible	Prevented
Phantom	Two bookings each check “room free 2 to 3 pm” and both insert	Possible	Possible (as write skew)	Prevented

Read committed is the default in Postgres, SQL Server and Oracle. Snapshot isolation is Postgres’s REPEATABLE READ and what Oracle calls SERIALIZABLE, which it is not.

Go deeperRead committed and snapshot isolation in detail1 min

Read committed only promises you never see uncommitted data. Each statement sees the latest committed state, so two statements in one transaction can see different worlds.

Snapshot isolation (SI) gives each transaction a consistent snapshot as of its start. Reads never block writes, and long reports see a stable picture. Two concurrent writes to the same row conflict, and Postgres aborts the second (first updater wins), which prevents lost updates on one row. MySQL InnoDB’s default REPEATABLE READ does not abort it, so lost updates go through.

Lost update is the like counter from the demo. The fix does not need a stronger isolation level. It needs the read and the write to be one step: an atomic UPDATE posts SET likes = likes + 1, a SELECT ... FOR UPDATE, or a compare-and-set on a version number.

JVersionedRegister.javaPyversioned_register.pyC#VersionedRegister.csGoversioned_register.goTSversioned-register.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// One key with a version number, held in one place: a single leader or a consensus group.
// That is what makes setIf safe. Two replicas that each check the version locally would
// both accept, and the lost update comes back.
record Versioned(int value, int version) {}

class VersionedRegister {
    private Versioned current;

    VersionedRegister(int value) {
        current = new Versioned(value, 1);
    }

    synchronized Versioned get() {
        return current;
    }

    // A blind write: whatever was there is overwritten, read or not.
    synchronized void set(int value) {
        current = new Versioned(value, current.version() + 1);
    }

    // Compare-and-set: the check and the write are one step, so no other writer can slip
    // between them. In SQL: UPDATE ... SET likes = 11, version = 2 WHERE id = 7 AND version = 1,
    // then look at the number of rows changed.
    synchronized boolean setIf(int expectedVersion, int value) {
        if (current.version() != expectedVersion) return false;
        current = new Versioned(value, expectedVersion + 1);
        return true;
    }
}

class Likes {
    // Read, compute, write if unchanged; on a conflict, read again. Under contention every retry
    // costs a round trip, so hot counters use an atomic increment on the server instead.
    static void addLikeWithRetry(VersionedRegister reg, int maxAttempts) {
        for (int i = 0; i < maxAttempts; i++) {
            Versioned seen = reg.get();
            if (reg.setIf(seen.version(), seen.value() + 1)) return;
        }
        throw new IllegalStateException("too much contention, give up and report it");
    }
}

class Main {
    public static void main(String[] args) {
        // Read, then blind write. Alice and Bob both read 10 before either writes.
        VersionedRegister naive = new VersionedRegister(10);
        Versioned alice = naive.get(), bob = naive.get();
        naive.set(alice.value() + 1);
        naive.set(bob.value() + 1);
        System.out.println("blind writes: " + naive.get().value()); // 11: one like is lost

        // The same interleaving with compare-and-set. Bob's write is refused, so he re-reads.
        VersionedRegister cas = new VersionedRegister(10);
        alice = cas.get();
        bob = cas.get();
        System.out.println("alice: " + cas.setIf(alice.version(), alice.value() + 1)); // true
        System.out.println("bob:   " + cas.setIf(bob.version(), bob.value() + 1)); // false: version moved on
        Likes.addLikeWithRetry(cas, 5); // Bob's retry reads 11 and writes 12
        System.out.println("compare-and-set: " + cas.get().value()); // 12: both likes counted
    }
}

Write skew is the anomaly snapshot isolation cannot stop, because the two transactions write different rows. The classic example is from Berenson and others (1995), the paper that defined snapshot isolation. A hospital requires at least one doctor on call per shift. Alice and Bob are both on call and both feel unwell.

Write skew under snapshot isolation: two valid transactions, one invalid result

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

Each transaction is correct on its own snapshot. No row was written twice, so SI sees no conflict. The same shape appears whenever a check reads several rows, and a write changes one of them. Think of two withdrawals from accounts that must jointly stay positive. Or two users claiming the last username variant. Or two meetings booked into one room.

Sometimes the check is “no row matching this condition exists” (no booking overlaps 2 to 3 pm). Then the write inserts a row the other transaction’s check would have found. That is a phantom. You cannot lock a row that does not exist yet, so SELECT ... FOR UPDATE does not help.

The fixes:

• Lock the rows the check reads (SELECT ... FOR UPDATE). This fails for phantoms.
• Materialize the conflict, as one row per shift or per room-slot that every writer must update.
• Use a database constraint.
• Run serializable isolation, and retry the aborts.

Go deeperWrite skew fixes and how serializable is built1 min

Fixes, from most targeted to most general:

Fix	How	Cost
Lock the rows the check reads	SELECT ... FOR UPDATE on both doctors’ rows	Only works when the rows already exist
Materialize the conflict	One row per (room, slot) or per shift, updated by every booking: now a write-write conflict	Extra rows, and the design must foresee the constraint
A database constraint	Postgres EXCLUDE USING gist for overlapping ranges, unique indexes	Only for constraints the database can express
Serializable isolation	Postgres SSI (since 9.1) tracks read-write dependencies and aborts one transaction	A modest throughput cost in the Postgres SSI paper’s benchmarks (Ports and Grittner, 2012), more under contention, plus aborts that callers must retry

Serializable is implemented three ways:

• Two-phase locking. Readers and writers block each other, with predicate or range locks for phantoms. It’s correct, and slow under contention.
• Serializable snapshot isolation (Cahill, 2008). Postgres uses it, and CockroachDB a variant. It runs optimistically on snapshots, and aborts at commit when it detects a dangerous cycle.
• Actual serial execution. VoltDB, Redis Lua scripts, and a single-threaded matching engine run one transaction at a time, on one core per partition. That’s fast when transactions are short and in memory.

TradeoffSerializable isolation instead of hand-placed locks

We gain

Every invariant your code checks holds, including ones nobody thought to lock for: write skew and phantoms are gone without designing for each one.

We give up

Transactions abort under contention, so every caller needs a retry loop with a limit, and a hot row turns into an abort storm. Throughput drops, and on some databases (2PL) long reads block writers.

The two axes combine. Strict serializability is serializable plus linearizable. Transactions take effect in an order that matches real time. A single-node database usually gives it for free. A replicated one does not.

Take Postgres with SERIALIZABLE on the primary, and reads from an async replica. It’s serializable, but not strict. A report on the replica can miss a transaction that committed a second ago. Spanner and FoundationDB provide strict serializability across shards. CockroachDB provides serializable transactions, with linearizable single-key reads.

Options and tradeoffs

CAP, stated correctly

CAP was Brewer’s conjecture in 2000, proved by Gilbert and Lynch in 2002. It says: when the network partitions, a replicated system must choose, for each operation, between answering (availability) and answering correctly (linearizability). A replica cut off from the majority can either refuse the request, or serve one that may be stale.

That statement is narrower than the slogan:

• C means linearizability, nothing weaker. Causal and session guarantees can stay available.
• A means every non-failed node answers, not “the service has 99.99% uptime”. A CP system whose majority side keeps serving is highly available in the everyday sense.
• P is not a choice. Networks partition: a switch fails, a zone loses its link. “CA” only describes a single node.
• The choice is per operation, not per system. A shopping cart can keep accepting “add item” on both sides of a partition, and merge later. Meanwhile “place order” refuses on the minority side. DynamoDB offers eventually consistent and strongly consistent reads on the same table.

PACELC: the tradeoff you pay every day

Partitions are rare. Latency is paid on every request. Abadi’s PACELC (2012) adds the other half: if Partition, choose Availability or Consistency. Else, choose Latency or Consistency. Even with a healthy network, a linearizable operation must reach a majority, or the leader. That round trip is the price.

Dynamo-style stores at low consistency settings are PA/EL. Consensus systems, such as Spanner and etcd, are PC/EC.

Go deeperPACELC examples1 min

System behaviour	P: on partition	E: normal operation	Examples
Dynamo-style, low consistency settings	Available (PA)	Latency (EL)	Cassandra at ONE, DynamoDB eventually consistent reads
Consensus per write and read	Consistent (PC)	Consistent (EC)	Spanner, etcd, ZooKeeper writes, CockroachDB
Fast local reads, ordered writes	Consistent (PC)	Latency (EL)	Yahoo’s PNUTS, Abadi’s example; Postgres with async read replicas behaves this way for reads

TradeoffPicking consistency per operation, not per system

We gain

The few operations that need it (money, inventory, uniqueness, locks) get linearizability, and everything else gets local latency and stays up in a partition.

We give up

Every operation needs a stated guarantee, and the code must route each one correctly. A read that should have gone to the leader but went to a replica is a bug that only shows under lag.

Choosing a level

Level	Read cost	Write cost	Survives a partition	Wins when
Eventual	Any replica, local	Any replica, local	Yes, both sides	Counts, feeds, presence, analytics, caches
Session guarantees	Local, or wait or redirect when behind	Local	Yes, while the session’s replica is reachable	User-facing pages where the user’s own actions must stick
Causal	Local, wait for dependencies	Carry dependency metadata	Yes, while the client’s replica is reachable	Comments, chat, social graphs, permissions then content
Bounded staleness	Local if within the bound, else the leader	Leader	Reads yes, writes no	Dashboards, search, “at most 10 s old”
Linearizable	Leader plus a majority check, or a lease	Majority round trip	Majority side only	Locks, leader election, uniqueness, balances, seats, state machines

Go deeperBounded staleness1 min

Bounded staleness is eventual consistency with a number on it. A read is at most 10 seconds, or 1,000 versions, old. Azure Cosmos DB offers it as a named level, and Spanner as stale reads. It is often the honest version of what a design means by “eventual”.

How each level is built, and what it costs

Mechanism	Gives	Cost per operation	Used by
Single leader, reads at leader	Linearizable while the leader holds a valid lease	Writes: replication round trip. Reads: local at the leader	Postgres primary, Redis primary, MongoDB primary
Single leader, follower reads	Eventual; sequential if a client stays on one follower; session with tokens	Reads local, may be stale	Read replicas everywhere
Quorums, R + W > N	Usually sees the latest write; not linearizable alone	R and W replicas per operation	Cassandra, Riak, DynamoDB internals
Consensus (Raft, Paxos) per write	Linearizable writes, reads with ReadIndex or lease	One majority round trip per write; ReadIndex adds one per read batch	etcd, Consul, CockroachDB ranges, Spanner groups
HLC timestamps plus snapshots	Causal, and serializable with uncertainty restarts	Metadata per write; occasional read restarts within the clock offset	CockroachDB, YugabyteDB
TrueTime commit wait	Strict serializability across the planet	Each commit waits about 2ε, a few ms	Spanner

Quorums overlap, but overlap is not linearizability: failed writes, last-writer-wins and sloppy quorums each let a quorum read go backwards.

Go deeperWhy quorums alone are not linearizable1 min

Quorums are the trap. With N = 3, W = 2 and R = 2, every read set overlaps every write set. But overlap is not linearizability. Here’s how it breaks:

• A write that reached one replica and then failed can be returned by one read, and missed by the next.
• Last-writer-wins can discard an acknowledged write, if it has an older timestamp.
• Sloppy quorums write to replicas outside the read set.

Getting linearizable reads from quorums needs synchronous read repair before returning (the ABD algorithm). Cassandra’s lightweight transactions use Paxos instead, at four round trips. The key-value store problem works through each failure.

Spanner’s TrueTime closes the real-time gap that HLCs leave. Every datacenter has GPS receivers and atomic clocks. The API returns an interval [earliest, latest], guaranteed to contain true time, with a width of 2ε. The 2012 paper reports ε between 1 and 7 ms, about 4 ms on average.

A transaction takes the top of the interval as its commit timestamp. Then it waits until that timestamp is certainly in the past everywhere, before releasing locks and replying. So any transaction that starts after the reply gets a larger timestamp. Timestamp order is real-time order. And a read at any timestamp is a consistent snapshot of the whole database, with no coordination.

Commit wait: the reply leaves only once the timestamp is in the past

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

JTrueTime.javaPytrue_time.pyC#TrueTime.csGotrue_time.goTStrue-time.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Real time in ms, plus this machine's error. A real node only ever sees read().
class SimulatedClock {
    long trueMs;
    final long skewMs;

    SimulatedClock(long trueMs, long skewMs) {
        this.trueMs = trueMs;
        this.skewMs = skewMs;
    }

    long read() {
        return trueMs + skewMs;
    }

    void sleep(long ms) {
        trueMs += ms;
    }
}

record Interval(long earliest, long latest) {}

record Commit(long timestamp, long waitedMs) {}

// Spanner's clock API: not a time but an interval that contains real time. epsilon is the
// worst-case error, kept small by GPS and atomic clocks in every datacenter (the 2012 paper
// reports 1 to 7 ms). If a node's error could exceed epsilon, the guarantee is gone.
class TrueTime {
    private final SimulatedClock clock;
    private final long epsilonMs;

    TrueTime(SimulatedClock clock, long epsilonMs) {
        this.clock = clock;
        this.epsilonMs = epsilonMs;
    }

    Interval now() {
        long t = clock.read();
        return new Interval(t - epsilonMs, t + epsilonMs);
    }

    static Commit commit(TrueTime tt, SimulatedClock clock) {
        // Pick the commit timestamp at the top of the interval: it is not in the past anywhere.
        long s = tt.now().latest();
        // Commit wait: hold the locks and the reply until s is certainly in the past everywhere.
        // Any transaction that starts after the client hears "committed" then gets a timestamp
        // above s, so timestamp order matches real-time order: external consistency.
        long waited = 0;
        while (tt.now().earliest() <= s) {
            clock.sleep(1);
            waited++;
        }
        return new Commit(s, waited);
    }
}

class Main {
    public static void main(String[] args) {
        // Node 1's clock is 3 ms fast, node 2's is 4 ms slow, epsilon is 4 ms on both.
        SimulatedClock c1 = new SimulatedClock(1_000, 3);
        Commit t1 = TrueTime.commit(new TrueTime(c1, 4), c1);
        System.out.println("T1 commit ts " + t1.timestamp() + ", waited " + t1.waitedMs()
                + " ms, acked at real time " + c1.trueMs);
        // T1 commit ts 1007, waited 9 ms, acked at real time 1009: about 2 x epsilon of waiting

        // T2 starts on node 2 right after T1's ack, on a slow clock.
        SimulatedClock c2 = new SimulatedClock(c1.trueMs, -4);
        Commit t2 = TrueTime.commit(new TrueTime(c2, 4), c2);
        System.out.println("T2 commit ts " + t2.timestamp() + ", after T1: " + (t2.timestamp() > t1.timestamp()));
        // T2 commit ts 1009, after T1: true
    }
}

The wait overlaps with Paxos replication, so its visible cost is usually small. The real price is the clock infrastructure. Without bounded ε, the guarantee is gone. CockroachDB has no special clocks. It assumes a configured maximum offset (hundreds of milliseconds). It restarts a read that finds a value inside its uncertainty window. And it shuts a node down if its clock drifts too far.

TradeoffCommit wait for external consistency

We gain

Strict serializability across regions, and lock-free consistent snapshot reads at any past timestamp, which makes backups, analytics and cross-shard reads simple.

We give up

Every read-write commit waits about 2ε, and correctness rests on clock bounds that need GPS and atomic clocks to keep small. Cross-region commits still pay the Paxos round trip on top.

Choosing per data path

Find the operations where a wrong answer costs money, safety or trust. Make those linearizable, on as small a scope as possible: one row, one key, one partition. Give everything else the weakest guarantee that keeps its promise to users, with a number.

Go deeperThe guarantee per data path in this site's problems1 min

Data path	Guarantee	Why that and no stronger
Payment state change	Linearizable per payment: compare-and-set on the primary	Two racing outcomes must change the state once; dashboards may lag a minute
Seat hold	Linearizable per seat: one conditional UPDATE	One seat, one buyer; the seat map is eventual at about 2 s
Chat messages	Total order per conversation, eventual presence	Order matters inside a conversation only; a green dot is not worth a cross-region round trip
News feed	Read-your-writes for the author, eventual (~1 s) for followers	Nobody can tell 1 s from 3 s, but authors notice their own post missing
Typeahead	Eventual with bounds: a day for ranking, minutes for removals	Suggestions only need to be plausible; removal has a legal clock
Rate limiter counters	Linearizable per key on one shard; rules eventual	Exactly the limit per key; a new rule may take 10 s to reach every gateway

Go deeperOther named levels you will meet1 min

Name	Where	What it actually is
Consistent prefix	Cosmos DB, Bayou	Readers see some prefix of the write order, never a gap: monotonic writes for everyone
Session	Cosmos DB default	The four session guarantees, scoped to a session token the SDK carries
Strongly consistent read	DynamoDB	Read from the partition leader; twice the read capacity of an eventual read, not on global secondary indexes
serializable read	etcd	Confusingly, a local, possibly stale read; the default linearizable read uses ReadIndex
Read concern majority	MongoDB	Data acknowledged by a majority, so it cannot roll back; still possibly stale
Read concern linearizable	MongoDB	Primary confirms with a majority before replying; single document only
Repeatable read	ANSI SQL, Postgres, MySQL	Snapshot isolation in Postgres; snapshot reads with locking writes in MySQL
Strong read-after-write	Amazon S3 since December 2020	A read after a successful PUT or DELETE returns the new state, including list operations

The names are not portable. Before relying on one, read what that product’s documentation says it prevents, and check whether Jepsen has tested it.

How it fails

Failure	What you see	Blast radius	Fix
Replica lag spike	Edits vanish, comments flicker, support tickets about “lost” changes	Every read routed to the lagging replica	Session tokens; take replicas out of the read pool above a lag limit
Clock skew under last-writer-wins	A node with a fast clock wins every conflict; correct writes vanish	Every key that node writes, for hours	HLCs or version vectors instead of wall time; alert on clock offset
Leader lease outlives leadership	A paused or partitioned old leader serves “linearizable” stale reads	Reads at that node until it notices	ReadIndex instead of leases, or lease margins well above clock drift; fencing tokens on writes
Quorum treated as linearizable	A value read once, then the older value read again	Keys with failed or concurrent writes	Linearizable operations through Paxos/Raft or conditional writes
Write skew under snapshot isolation	An invariant across rows broken: overdraft, nobody on call, double booking	Every invariant checked by reading other rows	Serializable, materialized conflicts, or constraints
Lost update under read committed	Counters short, edits overwritten	Every read-modify-write in application code	Atomic updates or compare-and-set
Session token not carried across devices	Edit on the phone, missing on the laptop	Users with several devices	Store the token with the account, or read the user’s own data from the leader
Failover with asynchronous replication	Acknowledged writes gone after a new leader takes over	The last seconds of writes	Synchronous or semi-synchronous replication for paths that need it

Go deeperClock skew under last-writer-wins1 min

Clock skew is the silent one. Under last-writer-wins, a server whose clock runs 30 seconds fast stamps every write 30 seconds in the future. For the next 30 seconds, every other server’s write to the same keys loses. And the losing writes were acknowledged. No error is logged, because nothing failed. Detect it by exporting each node’s clock offset, and alerting at a fraction of the tolerance. Avoid it by not resolving conflicts on wall-clock time.

Go deeperWhy advertised guarantees need testing1 min

A database’s claims are not proof. Jepsen’s tests have found that many databases did not provide the guarantee their documentation stated. Often that was only during partitions, failovers or clock jumps. The design lesson: the operations that need linearizability should be few and well tested. And they should be fenced at the write (a version check or a fencing token), so a stale read cannot turn into a wrong write.

Common mistake

"Eventual consistency means a few milliseconds of staleness"

Eventual consistency has no bound. Replicas are milliseconds apart when healthy and minutes apart during a repair backlog or a failed link, and the model allows both. It also says nothing about reads going backwards or writes arriving out of order. If a design depends on “usually under a second”, state the bound, measure it, and say what happens past it.

At scale

Operation	Typical latency
Local read from any replica	0.1 to 1 ms
Majority round trip, one region, three zones	1 to 3 ms
Majority round trip, us-east to us-west	About 65 to 70 ms
Majority round trip, US to Europe	About 75 to 90 ms
Majority round trip, US to Southeast Asia	About 200 to 230 ms
Spanner commit wait	About 2ε, a few ms, overlapped with replication
Postgres SSI against snapshot isolation	A modest throughput cost in published benchmarks, worse under contention

At 10 times the read traffic, linearizable reads at the leader become the bottleneck. One node per partition serves them all. Move reads to followers, without losing correctness:

• ReadIndex on a follower. Ask the leader for the commit index, and apply up to it locally.
• Bounded-staleness reads, such as Spanner’s stale reads and CockroachDB’s AS OF SYSTEM TIME.
• A cache, for reads that never needed linearizability.

Go deeperAt 100 times: leaders across regions1 min

At 100 times, the data spans regions. The question becomes where the leader of each key lives. Place each user’s leader in their home region. That keeps their writes local, and makes only cross-region interactions pay 70 to 200 ms. Global uniqueness (usernames, seat inventory for a world tour) becomes the expensive path. So designs shrink it. Reserve blocks of inventory per region. Or check uniqueness in one place, and everything else locally.

What to monitor:

• Replication lag per replica, in seconds and log positions.
• A staleness probe: write a timestamp to a canary key every second, read it from every replica, and graph the age. It measures what users see.
• Session-token redirects and waits per second: reads that would have been stale.
• Clock offset per node, alerting well before the configured maximum.
• Serialization failures, retries, and transactions that exhaust their retries.
• Last-writer-wins overwrites and sibling counts: concurrent writes you may not know you have.

In the interview

Interviewer asksIs your design CP or AP?

Per operation, not per system. CAP only applies during a partition. The choice is whether a replica cut off from the majority refuses a request, or answers it possibly stale. For the payment state change, it refuses. That path is linearizable through the primary, and the minority side returns an error the client retries. Feeds, counts and presence keep answering, eventual with stated bounds. Outside partitions, the tradeoff is latency (PACELC). So I keep linearizable operations on the smallest scope, one row or key.

Interviewer asksA user edits their profile and sometimes sees the old version. Fix it.

That is read-your-writes, broken by a lagging read replica. The cheap fix: after a write, return the write’s log position to the client. The client sends it on later reads. Route the read only to a replica that has applied that position, or to the leader. That one number also gives monotonic reads. Simpler: read the user’s own profile from the leader for a few seconds after a write. Keep the token with the account, for multi-device users.

Interviewer asksWhat is write skew, and does snapshot isolation prevent it?

It does not. Two transactions read an overlapping set of rows, check an invariant, and each writes a different row. The classic case is two doctors on call. Both read that two are on call. Each takes themselves off. Both commit, because no row was written twice. Snapshot isolation only detects write-write conflicts on the same row. Fixes: FOR UPDATE on the rows the check reads, a materialized row per shift that both must update, a constraint, or serializable isolation (SSI in Postgres aborts one), with retries.

Interviewer asksHow does Spanner offer strong consistency across continents?

Two parts. Each shard is a Paxos group, so writes are durable, and ordered by a majority. That costs a cross-region round trip when replicas span regions. For ordering across shards, it uses TrueTime. These are clocks with GPS and atomic references. They return an interval guaranteed to contain true time, a few milliseconds wide. A transaction takes the top of the interval as its timestamp. It waits until that time has certainly passed, before replying. Any transaction that starts later gets a larger timestamp. So timestamp order matches real-time order, which is strict serializability.

Common mistake

"CAP means pick two of consistency, availability and partition tolerance"

Partitions are not optional, so there is no “CA” distributed system. CAP says that during a partition, each operation either stays available or stays linearizable. Most of the time there is no partition, and the real tradeoff is latency against consistency (PACELC). Systems also choose per operation: the same database can offer eventual and strong reads on the same table.

Common mistake

"Serializable and linearizable are the same thing"

Serializable is about transactions on many objects: the outcome equals some serial order, which need not match real time. Linearizable is about single operations on one object, in real time. A serializable database read from an async replica can return a snapshot from a second ago, which is serializable and not linearizable. Both together is strict serializability.

Mid-level covers

Names eventual and strong consistency. Explains read-your-writes with a lagging replica, and a fix. States CAP as a choice during partitions. Knows the database’s isolation level matters for lost updates.

Senior adds

Assigns a guarantee per data path, with a bound. Uses session tokens for user-facing reads. Knows quorums are not linearizable. Separates isolation from replica consistency. Explains write skew and phantoms, and how to fix each. Prices linearizable reads (ReadIndex, leases, cross-region round trips). Explains HLCs and TrueTime commit wait.

Seen in

• Payment system: compare-and-set per payment on the primary. Agreement with the PSP is eventual, bounded by reconciliation.
• Ticket booking: one conditional UPDATE per seat under read committed, no SERIALIZABLE needed.
• Hotel reservation: nights locked in order, plus a conditional update. Search availability is eventual.
• Chat: one order per conversation, monotonic receipts, eventual presence.
• News feed: read-your-writes for the author, eventual for followers, deletes enforced on read.
• Instagram: eventual post delivery and approximate counts, with bounds.
• Key-value store: tunable quorums, what R + W > N does not promise, Paxos for compare-and-set.
• Distributed cache: read-your-writes through deletes and leases.
• Rate limiter: linearizable per key on one shard, rules eventual.
• Stock exchange: one total order per symbol from the sequencer.
• Ride hailing: linearizable claims and trip states, eventual positions.
• Collaborative editor: one linearizable order per document, causal order per sender.
• Dropbox: conditional commits per namespace, eventual propagation to devices.
• Message queue: order per partition only, reads below the high watermark.
• Ad click aggregator: eventual counts, monotonic per bucket.
• Video streaming: eventual visibility of new videos and renditions.
• Search autocomplete: eventual everywhere, with a fast path for removals.

Recap

Two axes. Consistency: what a read of one replicated object may return. Isolation: how concurrent transactions over many objects may interleave. Different problems, different fixes.

The ladder, from weakest to strongest:

1. Eventual: converges, with no bound.
2. Session guarantees (read-your-writes, monotonic reads, monotonic writes, writes-follow-reads). These are about equal to causal: cause before effect for everyone, still available in a partition.
3. Sequential: one order, but not real time.
4. Linearizable: one copy, in real time.

Strict serializable adds transactions.

CAP and PACELC. In a partition, each operation chooses availability or linearizability. The rest of the time, latency or consistency. Choose per operation.

Isolation. Read committed allows lost updates. Snapshot isolation allows write skew and phantoms. Serializable allows neither, at the cost of aborts. Lost updates are fixed with atomic or conditional writes.

Mechanisms. Session tokens, dependency tracking, one leader, consensus with ReadIndex or leases, quorums (not linearizable alone), HLCs, TrueTime commit wait.

Numbers. Local read under 1 ms. Majority in a region, 1 to 3 ms. Cross-region, 70 to 230 ms. Commit wait about 2ε, a few ms.

Further reading

• Replication, for leaders, lag and quorums. Partitioning, for why order holds only within a partition. Consensus, for Raft and leases. And distributed transactions, for transactions across services.
• Jepsen: Consistency Models: a map of the models with a precise definition of each and which are available in a partition.
• A Critique of ANSI SQL Isolation Levels, Berenson and others, 1995: defines snapshot isolation, write skew and the anomalies the SQL standard missed.
• Spanner: Google’s Globally-Distributed Database, OSDI 2012: TrueTime, commit wait and external consistency.