Consistency Models

Consistency models distributed systems use form a strict hierarchy: stronger models give simpler programming but cost latency and availability; weaker models scale better but force the app to handle anomalies. Picking the right level for each operation (not the whole database) is one of the most important design choices in a distributed system.

flowchart TD
  LIN[Linearizable<br/>real-time order, single copy illusion]
  SEQ[Sequential<br/>same order for all, ignores wall clock]
  CAU[Causal<br/>cause-and-effect respected]
  RYW[Read-your-writes<br/>session sees its own writes]
  MR[Monotonic reads<br/>time never goes backward in a session]
  EV[Eventual<br/>converges if writes stop]

  LIN --> SEQ --> CAU --> RYW --> MR --> EV

  classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
  classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class LIN,SEQ datastore;
  class CAU,RYW,MR,EV service;

A simple way to read the ladder: linearizable means the system pretends to be one machine with a global clock. Sequential drops the wall clock but keeps a global order. Causal only enforces order between events that depend on each other. Read-your-writes and monotonic reads are session guarantees, useful for user-facing apps. Eventual just promises convergence given enough time and no new writes.

Choose strong consistency where money or correctness depends on it (account balances, inventory decrement, leader election). Choose causal or session models for social feeds, comments, and shopping carts. Choose eventual for analytics, telemetry, and recommendations.

Problem statement

A user posts a comment, then refreshes the page and the comment is missing. Later, scrolling back, the comment appears, vanishes, and reappears as the load balancer hits different replicas. Walk through the consistency models that explain each of these anomalies, and the ones that would have prevented them.

The hierarchy

Consistency models distributed systems literature usually arranges into a partial order. Stronger models include all weaker guarantees.

flowchart TD
  LIN[Linearizable]
  SEQ[Sequential]
  CAU[Causal]
  PRAM[PRAM<br/>per-process FIFO]
  RYW[Read your writes]
  MR[Monotonic reads]
  MW[Monotonic writes]
  WFR[Writes follow reads]
  EV[Eventual]

  LIN --> SEQ --> CAU --> PRAM
  PRAM --> RYW
  PRAM --> MR
  PRAM --> MW
  CAU --> WFR
  RYW --> EV
  MR --> EV
  MW --> EV
  WFR --> EV

  classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
  classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
  class LIN,SEQ datastore;
  class CAU,PRAM,WFR service;
  class RYW,MR,MW,EV cache;

Linearizable

Every operation appears to take effect at a single instant between its invocation and response, and that instant respects real wall-clock order. Reads always see the most recently committed write. Equivalent to "single copy" semantics.

• Examples: etcd, ZooKeeper, single-leader Raft groups (writes + linearizable reads), Spanner (using TrueTime), DynamoDB strongly-consistent reads.
• Cost: every write needs consensus; reads either go through the leader or use a read-index round trip.

sequenceDiagram
  participant C1 as Client A
  participant C2 as Client B
  participant DB as Linearizable store
  C1->>DB: write x=1
  DB-->>C1: ok
  C2->>DB: read x
  DB-->>C2: 1
  note over C1,C2: B's read started after A's write completed,<br/>so B must see 1

Sequential

All clients see operations in some total order, the same for everyone, but that order is not required to match wall clock. Useful for caches that want a global log without a global clock.

Causal

Operations causally related (Lamport's happens-before) are seen in the same order by all observers. Concurrent operations may be seen in any order. This is the strongest model achievable while remaining available under network partitions (CAP).

• Examples: COPS, Eiger, MongoDB causal-consistent sessions, AntidoteDB.
• Tracking: vector clocks or version vectors per key.

flowchart LR
  A1[A posts: 'fix is in'] --> A2[B comments: 'thanks']
  A3[C unrelated post] -.concurrent.-> A1

  classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class A1,A2,A3 service;

If client D sees B's "thanks" then must also see A's "fix is in" (cause before effect). D may see C's unrelated post in either order.

Session guarantees (PRAM family)

Cheap to provide using sticky sessions or session tokens. They make per-user UX feel sane without paying for full causal consistency.

• Read your writes: a client always sees its own writes. Implementation: route the client's reads to the master, or carry a write timestamp / version token.
• Monotonic reads: a client never sees time go backward. Implementation: pin the client to a replica, or remember the highest version seen.
• Monotonic writes: writes from one client are applied in the order they were issued.
• Writes follow reads: if you read X then write Y, all observers see X before Y.

Eventual

The weakest useful model: if writes stop, all replicas converge to the same value. Order, intermediate states, and visibility lag are unconstrained.

• Examples: DNS, Cassandra default, S3 (used to be), Riak, async-replicated MySQL replicas.
• Anomalies: stale reads, lost updates without LWW or CRDT semantics, "ghost" data that disappears.

Vector clocks: tracking causality

Each replica keeps a vector of counters, one per node. On a local event, increment own slot. On message receive, take element-wise max plus own increment.

# A 3-node vector clock entry per replica
def update_on_receive(local_vc, incoming_vc, my_id):
    merged = [max(a, b) for a, b in zip(local_vc, incoming_vc)]
    merged[my_id] += 1
    return merged

# Comparing two events:
# - A happens-before B  iff  A[i] <= B[i] for all i, and A != B
# - Otherwise A and B are concurrent (write conflict)
def happens_before(a, b):
    return all(x <= y for x, y in zip(a, b)) and a != b

Conflicts (concurrent updates) are surfaced to the application: last-write-wins, merge function, or a CRDT.

Choosing per operation, not per database

Most production systems mix levels:

Operation	Model	Why
Decrement inventory count	Linearizable	Cannot oversell
Charge a credit card	Linearizable + idempotent	Money correctness
Post a comment	Read-your-writes	User must see own action
Render feed	Causal or eventual	Stale by seconds is acceptable
View analytics dashboard	Eventual	Minutes of lag is fine
Leader election	Linearizable	Two leaders is catastrophic

Gotchas

• "Strong" is overloaded. Cassandra's QUORUM is not linearizable, only "monotonic enough most of the time". Read the docs, not the marketing.
• Linearizable reads cost too. They are not free even on followers: see Raft read-index and lease reads.
• Replication lag is not eventual consistency. Lag is a property; consistency is a contract about what observers can see.
• Clocks lie. Without TrueTime or a hybrid logical clock (HLC), wall-clock ordering across nodes is unreliable; many "linearizable" systems are not under clock skew.
• PACELC, not just CAP. Even with no partition, you trade latency for consistency. Document the L and C choices, not only the A and P.

Quick reference

Hierarchy at a glance

• Linearizable: single-copy illusion, respects real time. etcd, Spanner.
• Sequential: same global order for all, no wall-clock guarantee.
• Causal: happens-before respected; concurrent ops in any order. MongoDB causal sessions.
• PRAM (FIFO): per-client order preserved.
• Read-your-writes: client sees own writes after they return.
• Monotonic reads: time never goes backward in one session.
• Monotonic writes: client's writes applied in order.
• Writes follow reads: if read X then write Y, others see X before Y.
• Eventual: replicas converge if writes stop. Cassandra default, async MySQL replicas.

Mapping to popular stores

Store	Default	Strongest available
etcd, ZooKeeper	Linearizable	Linearizable
Spanner	External consistency (linearizable)	Same
DynamoDB	Eventual	Strongly consistent reads (linearizable)
Cassandra	Tunable (CL=ONE eventual)	LOCAL_QUORUM ~ monotonic; not linearizable
MongoDB	Read-your-writes (primary)	Linearizable read concern
Postgres replicas	Async = eventual	Sync replica = linearizable
Riak	Eventual + CRDTs	Causal (with vclocks)

Vector clocks in 30 seconds

• Each node keeps a vector V[1..n] of counters.
• On local op: V[me]++.
• On receive: V = elementwise_max(V, incoming); V[me]++.
• A < B iff A[i] <= B[i] for all i and A != B (happens-before).
• Else concurrent: app must merge or pick LWW.

When to pick what

• Money, inventory, leader election -> linearizable.
• User-facing reads after own writes -> read-your-writes (cheap via session token).
• Social feeds, comments -> causal or session.
• Analytics, logs, recommendations -> eventual.

Anti-patterns

• "Just use strong consistency everywhere" - kills latency and availability under partition.
• Mixing linearizable writes with eventual reads and calling it strong.
• Ignoring concurrent updates ("LWW will sort it") - silent data loss.
• Trusting wall clocks across nodes without HLC or TrueTime.
• Treating replication lag as a tunable rather than a contract.

Common interview probes

• Q: "Difference between linearizable and serializable?" A: Linearizable is about single-object real-time order. Serializable is about transaction order. Strict serializable = both.
• Q: "Can you have causal consistency with availability under partition?" A: Yes, it is the strongest model that is partition-tolerant.
• Q: "How does Spanner achieve external consistency?" A: TrueTime atomic clocks bound clock uncertainty, then waits out the uncertainty interval before commit.
• Q: "When is eventual consistency acceptable?" A: When the app can tolerate stale reads and merge conflicts, or when CRDTs make convergence safe.

Refs

• Werner Vogels, Eventually Consistent (CACM, 2009).
• Doug Terry, Replicated Data Consistency Explained Through Baseball (MSR, 2011).
• Peter Bailis et al., Highly Available Transactions (VLDB, 2014).
• Martin Kleppmann, Designing Data-Intensive Applications (2017), ch. 5 and 9.
• Google Spanner paper, Spanner: Google's Globally-Distributed Database (OSDI, 2012).

FAQ

What is the difference between linearizability and serializability?

Linearizability is about real-time ordering of single-object operations. Serializability is about transactional isolation, where multi-object transactions appear to run one after another.

What is eventual consistency?

Eventual consistency only guarantees that if writes stop, all replicas eventually converge to the same value. It says nothing about what readers see in the meantime, so apps must tolerate stale data.

What is causal consistency?

Causal consistency preserves the order of causally related operations (writes that depend on prior writes). Independent operations can be seen in any order. It is strong enough for most user-facing apps.

What is read-your-writes consistency?

Read-your-writes guarantees that a session always sees its own previous writes. After posting a comment you immediately see it, even if other users do not yet. It is a session-level guarantee.

Which consistency model should I pick?

Pick linearizable for money, inventory, and leader election. Causal or session models for social feeds, carts, and comments. Eventual for analytics and recommendations where staleness is invisible to the user.

Related Topics

• CAP and PACELC theorem: the underlying tradeoff space that shapes which consistency models a system can offer.
• Consensus: Raft and Paxos: the algorithms that provide linearizable writes and reads on top of replicated logs.
• Logical Clocks: Lamport timestamps, vector clocks, and HLCs that make causal consistency implementable.