S072 · Consistency Models — Linearizable, Sequential, Eventual

The hierarchy of promises.

Module M08: Distributed Systems · Session 72 of 130 · Track: SYS 📐

What you'll be able to do after this session

Explain Consistency Models to a friend in one minute, out loud, no notes.
Recognise it when you see it in real code / systems / papers.
Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

S071 — Replication — Leader/Follower, Multi-Leader, Leaderless

Pre-read (skim before the session)

🎥 Intuition (5–15 min) · Consistency Models Explained (Hussein Nasser) — 12-minute plain-English tour of the hierarchy.
🎥 Deep dive (30–60 min) · Jepsen · Consistency Models — Kyle Kingsbury (Strange Loop) — the author of Jepsen walks through the map with real examples.
🎥 Hands-on demo (10–20 min) · Linearizability vs Serializability in MongoDB (MongoDB) — see the exact knobs that turn "eventual" into "linearizable."
📖 Canonical article · Jepsen — Consistency Models Map — the interactive lattice every distributed-systems engineer bookmarks.
📖 Book chapter / tutorial · DDIA Ch.9 — Consistency and Consensus — Kleppmann's canonical chapter.
📖 Engineering blog · CockroachDB — Living Without Atomic Clocks — how a real DB achieves serializable + linearizable reads without Spanner's TrueTime hardware.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: The hierarchy of promises.

When you Venmo a friend $20, the instant your phone shows "sent" you expect that if she opens her app a nanosecond later, the money is there. That expectation — every read after a completed write sees that write, everywhere, immediately — is linearizability, the strongest and most expensive consistency model.

Now think Google Docs. You and your co-author type in the same paragraph at once; both changes eventually show up but the order might be weird for a second. That looser promise — all replicas will eventually agree, but not in real time — is eventual consistency. It's cheap, fast, always available, and totally wrong for money but perfect for a shared cursor.

Consistency models are the hierarchy of promises a distributed system makes to your reads: linearizable → sequential → causal → read-your-writes → monotonic reads → eventual. Each step down buys lower latency and higher availability but shifts more headaches onto the application developer.

Gotcha to carry forever: "strong consistency" is not a single thing — it's a family of subtly different promises, and vendors love to overload the word. When someone says "we're strongly consistent," ask which model, then for reads, writes, or both, then across regions or only within one.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Worked example — the classic football score. Alice writes score updates; Bob reads.

Alice:  W(score=1) --- W(score=2) --- W(score=3) ------>
Bob:                                          R(score) = ?

Model	Legal returns for Bob	Illegal
Linearizable	`3` only	`1`, `2`
Sequential	`1`, `2`, or `3` (any real order preserved globally)	out-of-order
Causal	`1`→`2`→`3` order preserved per observer	seeing `3` then later `1`
Eventual	`1`, `2`, `3`, or the previous value	nothing after long enough

Why linearizability is expensive. Every read must either (a) go to the single leader (throughput bottleneck) or (b) contact a quorum and wait for the slowest reply (latency). Google Spanner uses atomic clocks + GPS (TrueTime) to bound clock skew and make cross-region linearizable reads work in ~10 ms — that hardware investment is why Spanner is famous and rare.

The Jepsen litmus test. A test client fires overlapping reads/writes at a cluster while a network partition rages. Jepsen records every operation with timestamps and asks a solver: is there any single-machine execution that could have produced this history? If no, the system violated its claimed model. MongoDB, Redis, Elasticsearch and etcd have all been caught — and most improved because of it.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Simulate a "monotonic read" violation against a Postgres primary + follower, then fix it.

# consistency_demo.py — needs the pg-leader/pg-follower stack from S071
# pip install psycopg2-binary
import psycopg2, time, threading
 
LEADER = dict(host='localhost', port=5432, user='postgres',
              password='secret', dbname='demo')
FOLLOW = dict(host='localhost', port=5433, user='postgres',
              password='secret', dbname='demo')
 
def setup():
    with psycopg2.connect(**LEADER) as c, c.cursor() as cur:
        cur.execute("DROP TABLE IF EXISTS balance;")
        cur.execute("CREATE TABLE balance(user_id int primary key, amount int);")
        cur.execute("INSERT INTO balance VALUES (1, 100);")
        c.commit()
 
def writer():
    with psycopg2.connect(**LEADER) as c:
        for _ in range(100):
            with c.cursor() as cur:
                cur.execute("UPDATE balance SET amount = amount + 1 WHERE user_id=1;")
            c.commit()
 
def reader(name, dsn):
    last, violations = -1, 0
    for _ in range(500):
        # New connection each time — simulates a load-balanced read
        with psycopg2.connect(**dsn) as c, c.cursor() as cur:
            cur.execute("SELECT amount FROM balance WHERE user_id=1;")
            v = cur.fetchone()[0]
        if v < last:
            violations += 1
            print(f"[{name}] MONOTONIC VIOLATION: {last} -> {v}")
        last = v
        time.sleep(0.01)
    print(f"[{name}] final={last}, violations={violations}")
 
if __name__ == "__main__":
    setup()
    t = threading.Thread(target=writer); t.start()
    reader("follower", FOLLOW)
    t.join()

Observe (checklist):

Reader's amount grows toward 200 with occasional pauses (that's lag).
Within a single connection, Postgres guarantees monotonic reads — you'd see zero violations.
Across new connections (as shown), you may see the value briefly go backwards if reads route across replicas at different lag levels.
Query SELECT pg_last_wal_replay_lsn(); on both — the difference is "how stale."
Set synchronous_commit = remote_apply on the leader and re-run. Writes get slower; the follower now serves linearizable reads.

Try this modification: add a second follower and round-robin reads across them. Watch the violation counter climb — this is exactly the read-your-writes bug that bites every team the first time they add a read replica.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Real teams almost never pick "linearizable everywhere" — the cross-region latency tax is brutal. Instead, they choose per-operation consistency.

Amazon shopping cart (Dynamo paper). The cart is deliberately eventually consistent with "merge on read": if two devices add an item during a partition, both items appear in the merged cart. Amazon decided a customer occasionally seeing an extra item was cheaper than ever telling them "sorry, cart unavailable."

Google Spanner offers global linearizability, but only because it invested in atomic clocks in every DC. CockroachDB and YugabyteDB copy the idea in software with hybrid logical clocks — good, but with a ~1 ms uncertainty window on commit.

MongoDB's journey. Early MongoDB defaulted to fire-and-forget writes and got demolished by Jepsen. Modern Mongo with writeConcern: majority + readConcern: linearizable is genuinely linearizable — but you must opt in, and most tutorials still show the fast, unsafe defaults.

Common bugs:

"Add a cache, break consistency." Redis in front of Postgres — now your app is eventually consistent even though your DB is linearizable. Cache is the weakest link.
Cross-service inconsistency. Service A writes to DB and publishes to Kafka. Service B reads the event and writes to its DB. Between those two writes, a query joining both sees a torn state. Fix: transactional outbox or CDC.
Sticky-session hack. Pin a user to one replica for read-your-writes. Works until the replica dies and re-routing exposes lag.
Vector clocks look elegant, are painful in practice. Riak exposed them to clients; almost everyone got it wrong. Modern systems hide it behind opaque tokens.

Practical rule: for money, use serializable + linearizable on that path; for feeds, notifications, analytics, eventual is fine and much cheaper.

(e) Quiz + exercise · 10 min

Define linearizability in one sentence, in your own words.
What is the difference between sequential consistency and linearizability? Give an example that satisfies one but not the other.
Why does linearizability cost latency, especially across regions?
What is "read your writes" and why do apps commonly implement it with session-pinning?
Name three failure modes eventual consistency can cause that a user might actually notice.

Stretch (connects to S071 · Replication): Explain how you could build a linearizable read on top of a leader/follower Postgres pair without forcing every read to hit the leader. (Hint: pg_last_wal_replay_lsn and a wait loop.)

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

What is Consistency Models? (one sentence, no jargon)
When would you use it? (one concrete example)
When would you NOT use it? (one anti-pattern)

What comes next

Next session (S073): Consensus — Paxos & Raft Intuition
Previous (S071): Replication — Leader/Follower, Multi-Leader, Leaderless
Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.