Consistency
and ordering
From “eventually” to “as if there were one copy”, and the ordering ideas underneath.
→ next · ← back · N notes · F full screen
Eventual consistency is a very weak promise.
It only says replicas converge at some point. It says nothing about what you read in the meantime. Stronger guarantees exist; they cost performance and availability.
Linearizability
Make it look like there’s only one copy.
Once anyone sees the new value, everyone must.
Linearizable ≠ serializable.
Both together: strict serializability. Two-phase locking and actual serial execution give you that.
When you really need it.
Locks and leader election
Only one node may believe it’s leader. ZooKeeper and etcd provide linearizable operations for this.
Uniqueness constraints
One username per user, no negative balance, each idempotency key used once.
Cross-channel timing
Write a file to storage, send a message to resize it. If the resizer reads a stale replica, it gets the old file.
Single-leader replication can be linearizable (reading from the leader). Consensus is. Multi-leader isn’t. Leaderless with quorums usually isn’t.
CAP, said precisely.
When the network is partitioned, you must choose: stay linearizable (some nodes refuse requests) or stay available (answers may be stale).
Why CAP is unhelpful
It covers only one consistency model and one kind of fault. It ignores delays, dead nodes, and everything else.
The real cost is speed
Even RAM on a multi-core CPU isn’t linearizable, for performance. Linearizable reads and writes are slow whenever network delays are uncertain.
Ordering
Cause before effect.
Causality is a partial order.
A question comes before its answer. A row is created before it’s updated. If A could have influenced B, A happened before B.
Concurrent events have no order. Linearizability puts everything in one total order, which implies causality but costs more.
Causal consistency
The strongest model that doesn’t slow down for network delays and stays available during partitions.
Lab: Lamport timestamps
Total order of all events (sort by counter, then node ID):
Total order broadcast.
Reliable delivery
If a message reaches one node, it reaches all.
Same order everywhere
Every node delivers messages in exactly the same sequence.
Equivalent to consensus
Linearizable storage can be built on it, and vice versa.
It’s how ZooKeeper and etcd work, and it’s state machine replication: every replica applies the same writes in the same order.
Now, our system.
Uniqueness
Idempotency keys and settlement IDs: are they enforced by a unique constraint on the PostgreSQL primary? That’s linearizable. Anything enforced on replicas or in caches isn’t.
Cross-channel races
Do we publish an event and then expect the consumer to read the database? Could it read a replica that hasn’t caught up?
Ordering of events
Do consumers process related events, like created then updated, in the order they happened?
Leader election
How do our schedulers decide who runs a job? Is that decision linearizable?
Distributed transactions and consensus
Two-phase commit, Raft and Paxos, and what ZooKeeper is really for. Chapter 9.