Distributed Consistency

Linearizability = real-time ordering of single-object operations. Serializability = transaction equivalence to some serial order (no real-time constraint).

Linearizability:
• Guarantees operations respond as if they were executed atomically at a single point in real time
• If operation A completes before operation B starts, B must observe A's effect
• Applies to individual read/write operations on a register/object
• Example: after a write to X completes, any subsequent read from any replica returns the written value
• Where it matters: distributed locks, counters, compare-and-swap, leader coordination

Serializability:
• Guarantees that concurrent transactions produce results equivalent to some serial execution
• Does NOT constrain which serial order — it could be A then B or B then A, regardless of real-time clock order
• Applies to multi-key transactions (databases)
• Example: two concurrent bank transfers may appear to have executed in any order, but the result is internally consistent

Strict serializability (strongest):
• Combines both: transactions appear to execute atomically, AND in real-time order
• Implies both linearizability and serializability
• Achieved by: Google Spanner (TrueTime), FoundationDB, some CockroachDB configurations
• High cost: global coordination, high latency

The consistency hierarchy (strongest → weakest):

Strict serializability (linearizable + serializable)
    ↓
Linearizability (single objects, real-time)
    ↓
Serializability (transactions, no real-time order)
    ↓
Snapshot isolation (reads from consistent snapshot)
    ↓
Read committed (no dirty reads)
    ↓
Eventual consistency (converge, no ordering)

Key vocabulary:
• Linearizability — single-object consistency: operations appear atomic with real-time ordering
• Serializability — multi-object transaction consistency: concurrent transactions equivalent to some serial order
• Strict serializability — combines both; strongest isolation/consistency guarantee
• Consistency model — the contract between a distributed system and its clients about observable behaviour

Eventual consistency is a liveness guarantee with no timing bound — it defines what happens in the limit, not how quickly.

Formal definition:
"If no new updates are made to a data item, eventually all accesses to that item will return the last updated value." — Werner Vogels (Amazon CTO, 2008)

What eventual consistency guarantees:
• Replicas will converge to the same value — eventually ✓
• All writes will propagate to all replicas — eventually ✓
• Under no contention, recent writes will be visible soon (ms to seconds) ✓

What eventual consistency does NOT guarantee:
• No timing bound on convergence ✗
• Read-your-own-writes (you might read a stale value after writing) ✗
• Monotonic reads (a second read may return an older value than the first) ✗
• Causal ordering (effect may be visible before cause) ✗

Stronger variants of eventual consistency:

Model	Adds to eventual
Causal consistency	Causally-related operations appear in order on all nodes
Read-your-writes	After write, you always read your own write (session-level)
Monotonic reads	Once you see value V, you never see an older value
Strong eventual consistency (SEC)	Nodes that have received the same set of updates have the same state (CRDT guarantee)

Real-world examples:
• DynamoDB (default) — eventually consistent reads; replica lag typically < 100ms in practice
• Cassandra — tunable: EVENTUAL (one replica) → QUORUM (majority) → ALL (all replicas)
• DNS — the classic example; changes propagate globally in minutes to 48 hours
• Social media likes/follower counts — eventual consistency acceptable; staleness okay

Key vocabulary:
• Eventual consistency — convergence guarantee with no timing bound; replicas agree given enough time and no new writes
• Causal consistency — causally-related operations appear in causal order on all replicas
• Strong eventual consistency (SEC) — deterministic convergence; nodes with the same updates have identical state
• Staleness — the degree to which a read lags behind the most recent committed write

Snapshot isolation prevents dirty reads and non-repeatable reads, but allows write skew — the "phantom" consistent transaction pair that creates an inconsistency.

Write skew — the canonical on-call example:

Constraint: at least 1 doctor must be on call at all times
State: {doctor_alice: on_call=true, doctor_bob: on_call=true}

T1 (Alice): SELECT * FROM doctors WHERE on_call=true → {Alice, Bob}
T2 (Bob):   SELECT * FROM doctors WHERE on_call=true → {Alice, Bob}

T1: both on call (count=2 ≥ 1) → UPDATE doctor_alice SET on_call=false
T2: both on call (count=2 ≥ 1) → UPDATE doctor_bob SET on_call=false

Commit T1: on_call = {Bob=true}
Commit T2: on_call = {Alice=false, Bob=false}  ← constraint violated!

Why snapshot isolation doesn't prevent this:
• T1 and T2 each read from their own consistent snapshot
• Each sees the constraint satisfied at snapshot time
• They write to different rows (non-conflicting in SI terms)
• SI detects conflicts only when two transactions write to the SAME row; here they don't

Solutions:
• Serializable Snapshot Isolation (SSI) — tracks read/write dependencies; aborts transactions involved in write skew cycles. Used in: PostgreSQL (REPEATABLE READ/SERIALIZABLE), FoundationDB, CockroachDB
• SELECT FOR UPDATE / SKIP LOCKED — acquires a read lock that prevents other transactions from updating those rows. More pessimistic but effective.
• Materialise the conflict — add an explicit "lock row" that both transactions must write, making the conflict detectable by SI

Anomaly taxonomy (ISO SQL isolation levels):

Anomaly	Read Committed	Snapshot Isolation	Serializable
Dirty read	✗ prevented	✗ prevented	✗ prevented
Non-repeatable read	✓ possible	✗ prevented	✗ prevented
Phantom read	✓ possible	✗ prevented (range)	✗ prevented
Write skew	✓ possible	✓ possible	✗ prevented

Key vocabulary:
• Write skew — anomaly where two transactions read overlapping data and write non-overlapping data, violating a multi-row constraint
• Snapshot isolation (SI) — each transaction reads from a consistent point-in-time snapshot; concurrent writes to different rows are allowed
• Serializable Snapshot Isolation (SSI) — optimistic extension of SI that detects and aborts write-skew-causing transaction pairs
• SELECT FOR UPDATE — pessimistic lock that prevents other transactions from updating read rows

Read-your-writes is a session guarantee that can be layered above an eventually consistent store using routing, timestamps, or client-side state.

Pattern 1: Leader-sticky reads (post-write routing)

User writes → Write goes to primary
Service records: user_id → {last_write_timestamp, route_primary_until: now + 5s}
User reads → if route_primary_until > now: read from primary
           → else: read from any replica

• Simple, effective for short sessions
• Problem: adds load to primary

Pattern 2: Replication lag tracking

User writes → Primary returns write sequence number (LSN / replication position)
Service stores: user_id → last_write_lsn
User reads → ask replica: "is your LSN ≥ last_write_lsn?"
           → if yes: serve from replica
           → if no: either wait or route to primary

• More efficient: reads go to replica once it's caught up
• PostgreSQL supports: pg_current_wal_lsn() + pg_last_wal_replay_lsn() for this check
• DynamoDB: Conditional reads with strongly_consistent=true for specific keys only

Pattern 3: Client-side value cache
• After writing user profile, application server caches the new value in a short-TTL Redis entry keyed by user_id
• On read: check Redis first; if hit and TTL not expired, return cached (just-written) value
• Redis entry expires after replication lag period (e.g., 500ms) — subsequent reads fall through to replica
• Advantage: zero load on primary; works even with multiple read replicas

Choosing the right pattern:
• One service instance: Pattern 3 (in-memory) is simplest
• Multiple instances behind load balancer: Pattern 2 (shared Redis for LSN tracking) or Pattern 1 (session affinity at LB level)
• Cross-device sessions (mobile + web same user): Pattern 2 with shared LSN store

Key vocabulary:
• Read-your-writes (RYW) — session consistency guarantee: after a write, the same session/user always reads the written value
• LSN (Log Sequence Number) — monotonic replication position; used to determine how far a replica has advanced
• Replication lag — the delay between a write being committed on the primary and appearing on a replica
• Session guarantee — consistency property scoped to a single client session, not all clients globally

High-throughput counters are a canonical CRDT use case: conflict-free, commutative increment operations that merge without coordination.

Why simple counters fail at scale:
• Single row with UPDATE SET count = count + 1: serialised at one node; only ~10k TPS maximum on fast hardware
• Distributed increment with optimistic locking: high write conflicts at scale; retry storms
• Atomic compare-and-swap: same serialization bottleneck

CRDT approach — G-Counter (Grow-only Counter):

Each node i maintains its own local increment vector:
  Node A: {A:42, B:0, C:0}
  Node B: {A:0, B:73, C:0}
  Node C: {A:0, B:0, C:31}

Merge rule: take max of each position → {A:42, B:73, C:31}
Total = sum of all positions = 146

Node A increments → {A:43, B:73, C:31} → total = 147
No locks, no coordination. Merge is commutative and idempotent.

Practical architecture for 100k writes/second video counter:
1. Edge layer: each CDN PoP maintains a local counter shard (Redis incr or in-memory). Accepts the 100k/s writes with sub-millisecond latency.
2. Periodic aggregation: every 1-5 seconds, edge shards report their delta to a regional aggregator (Kafka → Flink/Spark streaming aggregate)
3. Global count store: streaming aggregate writes final count to a read-optimised store (DynamoDB Global Tables, Redis). Global lag ≈ 1-5 seconds.
4. Read path: read the aggregated count — accurate to within the aggregation window (seconds), well within the 1%/5s requirement.

Cassandra counter columns — another production approach:
• Cassandra has native CRDT counter columns
• UPDATE views SET view_count = view_count + 1 WHERE video_id = ?
• Distributed, high-write-throughput, eventually consistent
• Caveat: counter columns have additional coordination overhead; not suitable for all Cassandra deployments

Key vocabulary:
• CRDT (Conflict-free Replicated Data Type) — data type with merge operations that are commutative, associative, and idempotent — no coordination required
• G-Counter — grow-only counter CRDT; each node has its own increment slot; total = sum of all slots
• PN-Counter — positive-negative counter; combines two G-Counters (increment + decrement); value = P-total − N-total
• Strong eventual consistency (SEC) — nodes that have received the same set of updates have identical state; merge is deterministic