How Consistency Works — CAP, Eventual Consistency, and Linearizability
In a single database, consistency is straightforward: read after write, you see what you wrote. In a distributed system with multiple replicas, this is no longer guaranteed. The write goes to one node and hasn't reached the others yet. Different clients reading from different nodes see different versions of the data.
Consistency models define what a distributed system promises about the freshness and ordering of data you read. Stronger consistency = more guarantees, but higher latency and lower availability. Weaker consistency = fewer guarantees, but faster and more available.
The CAP Theorem
The CAP theorem (Eric Brewer, 2000) states that a distributed system can provide at most two of three properties simultaneously:
Consistency — every read returns the most recent write. All nodes agree on the current value.
Availability — every request receives a response (not an error). The system keeps working even when some nodes are down.
Partition tolerance — the system continues operating when network messages between nodes are lost or delayed.
Network partitions are not optional — they happen in every real distributed system. So the real choice is: during a partition, do you sacrifice consistency (return potentially stale data) or availability (return an error)?
CP systems (consistency over availability) — refuse to serve reads during a partition rather than return stale data. Example: a leader-follower system where followers reject reads if they can't confirm they're up-to-date.
AP systems (availability over consistency) — continue serving reads during a partition, even if the data may be stale. Example: Cassandra, DynamoDB — always accept reads and writes, resolve conflicts later.
In practice, most systems don't operate at the extremes. They offer tunable consistency — you choose per-query or per-operation.
Consistency Models
From strongest to weakest:
Linearizability (Strong Consistency)
Every operation appears to take effect at a single point in time between its start and end. All clients see operations in the same order. A read always returns the result of the most recently completed write.
This is the behavior you'd expect from a single machine. It's the strongest guarantee: the system behaves as if there's only one copy of the data.
Cost: high latency (every write must be confirmed by a quorum before it's visible) and reduced availability (can't serve reads during partitions).
Used by: ZooKeeper, etcd, single-leader databases with synchronous replication.
Sequential Consistency
All clients see operations in the same order, but that order may not match real-time ordering. If client A writes before client B (in real time), the system might order B's write first — as long as all clients see the same order.
Weaker than linearizability (doesn't respect real-time order) but still useful: all clients agree on what happened.
Causal Consistency
Operations that are causally related are seen in the correct order. If A writes a value and B reads it, then writes something based on it, all clients see A's write before B's write. But unrelated operations can be seen in any order.
This captures the intuition "if B could have been influenced by A, B comes after A." Operations with no causal relationship are concurrent and can be ordered differently by different nodes.
Eventual Consistency
If no new writes occur, all replicas will eventually converge to the same value. "Eventually" might be milliseconds or minutes — there's no time bound.
This is the weakest useful guarantee. It says nothing about what you see between the write and convergence. You might read stale data, see operations out of order, or see writes from other clients before your own.
DNS is eventually consistent: update a DNS record, and it propagates through caches over minutes to hours. CDN caches are eventually consistent. Asynchronous replication is eventually consistent.
Read-Your-Writes Consistency
A practical middle ground: after you write, your subsequent reads see your own write. Other clients may not see it yet, but you do.
Implementation: route the user's reads to the node that received their write (the leader, or the same replica), or include a timestamp with the write and reject reads from replicas that are behind that timestamp.
This is what users expect: "I posted a comment, I should see it when I refresh." Without read-your-writes, the comment appears to vanish and then reappear — confusing and broken-feeling.
Monotonic Reads
Once you've read a value at a certain version, you'll never read an older version. Without this, a user might see version 5, refresh, and see version 3 (because the second read hit a more stale replica). With monotonic reads, versions only go forward.
How Do You Choose?
| Consistency model | Guarantee | Latency | Availability | Use case |
|---|---|---|---|---|
| Linearizability | Latest value, real-time order | High | Low during partitions | Leader election, locks, counters |
| Sequential | Same order for all clients | Moderate | Moderate | Collaborative editing, chat |
| Causal | Correct order for related ops | Low | High | Social feeds, comments |
| Eventual | Converges eventually | Lowest | Highest | Caches, DNS, analytics |
The right choice depends on what's being stored. A bank balance needs strong consistency. A social media like counter can tolerate eventual consistency. A collaborative document needs causal consistency at minimum.
Most real applications use different consistency levels for different data: strong for financial transactions, eventual for user activity feeds, causal for chat messages.
Next Steps
- How Consensus Works — how nodes agree on a value, enabling strong consistency.
- How Transactions Work — ACID guarantees on a single node (the foundation consistency builds on).