Consistency Models, CAP and PACELC

Early in my career, I sat in a design review where someone said, “We’ll use eventual consistency for the wallet balance, it’s fine, it’ll be consistent in a few milliseconds.” Nobody objected, because nobody in the room could explain precisely what would go wrong.

What goes wrong is this: a user with ₹500 in their wallet opens two phones (or one phone and a slow network that retries) and buys a ₹400 item on each. Both requests read the balance from replicas that haven’t seen the other purchase. Both see ₹500. Both succeed. The user gets ₹800 worth of goods for ₹500, and “a few milliseconds” was enough for it to happen.

“Consistent” is one of the most overloaded words in our field. This lesson gives you precise words for it, so you can say exactly which guarantee each piece of your data needs.

What a Consistency Model Is

A consistency model is a promise from a system about what a read is allowed to return, given the writes that have happened. Stronger models make fewer surprises possible. Weaker models allow more surprises, and in exchange the system can be faster and stay available during failures.

Here’s the spectrum, from strongest to weakest, with the ones you’ll actually meet:

Linearizable (strong consistency)

The system behaves as if there were only one copy of the data, and every operation happens instantly at some point between when it was sent and when it returned. In practice:

• Once a write has been acknowledged, every read that starts after that sees it (or something newer). From any client, any replica.
• Once any client has seen a new value, no client will later see the old one.

This is what you intuitively expect, and it’s what you need for things like:

• Uniqueness: only one user can get the username rahul_k; only one person can book seat 14C.
• Balances and stock: never sell more than you have.
• Leader election and locks: everyone must agree who the leader is (Lessons 6 and 8).

Linearizability needs coordination: a single leader or a quorum has to be involved in every read and write. That costs latency and, as we’ll see, availability during partitions.

Sequential consistency

Everyone sees all operations in the same order, and each client’s own operations appear in the order it issued them. But the order doesn’t have to match real time: a read may return a slightly old value, as long as everyone agrees on the sequence. Think of a replicated log that every reader consumes in order but at their own pace.

Causal consistency

If one operation depends on another, everyone sees them in that order. Unrelated operations can appear in different orders to different people.

The classic example: Priya posts “Has anyone tried the new biryani place?” and Amit replies “Yes, it’s great!“. With causal consistency, nobody ever sees Amit’s reply without Priya’s question. But two unrelated posts might appear in different orders to different users, which is fine.

Causal consistency is the strongest model that can stay available during network partitions, which makes it attractive. MongoDB offers it with causally consistent sessions, and it’s the natural model for many CRDT-based systems.

Session guarantees: read-your-writes and monotonic reads

These are weaker, but they fix the most visible user complaints:

• Read-your-writes: after you save something, you will always see it. (Other users might not yet.) This fixes “I updated my address and the app shows the old one”.
• Monotonic reads: once you’ve seen a value, you won’t later see an older one. This fixes “the order status went from Delivered back to Out for delivery when I refreshed”, which happens when consecutive reads hit replicas with different lag.

You can get these on top of eventually consistent replicas with tricks like sticky sessions (always read from the same replica), reading from the primary for a few seconds after a write, or tracking the replication position (LSN) of the user’s last write.

Eventual consistency

If writes stop, all replicas will eventually converge to the same value. That’s the whole promise. It says nothing about when, and nothing about what you see in the meantime: any read may be stale, and consecutive reads can go backwards in time.

It’s perfectly fine for many things: like counts, view counts, “people also bought” recommendations, search indexes, analytics dashboards, DNS, CDN caches. Nobody is hurt if the like count is 1,203 instead of 1,205 for a few seconds.

It’s not fine for the wallet balance in my story.

CAP, Without the Myths

The CAP theorem is probably the most quoted and most misunderstood idea in distributed systems. Here it is in plain words.

When there’s a network partition (some nodes can’t talk to others), a node that receives a request has two options:

• Consistency (C): refuse to answer (return an error or time out), because it can’t be sure its data is current.
• Availability (A): answer anyway with what it has, which might be stale, and accept writes that might conflict with writes on the other side.

It can’t do both. That’s all CAP says.

The common myths:

• “Pick two of three.” You can’t pick “CA” in a real distributed system, because you don’t get to choose whether partitions happen. Networks fail. The real choice is only what to do during a partition: C or A.
• “System X is a CP system.” Most real systems let you choose per operation. etcd, as we’ll see in a moment, gives you a consistent read or a possibly-stale read depending on a flag. Cassandra’s consistency level is set per query.
• “CAP is about normal operation.” It’s only about behaviour during partitions. Which leads to PACELC.

PACELC: The Trade-Off You Pay Every Day

PACELC (pronounced “pass-elk”) extends CAP with the part that matters most of the time:

If there’s a Partition, choose Availability or Consistency. Else (normal operation), choose Latency or Consistency.

Even when the network is perfectly healthy, a strongly consistent read needs to check with the leader or a quorum, which costs a round trip. A weakly consistent read can be answered by the nearest replica immediately. You pay this trade-off on every request, not just during rare failures.

A Real Test: Both Choices in One System

etcd lets you choose per read. A linearizable read (the default) makes sure the answer reflects all committed writes, by confirming with the leader and a majority. A serializable read (--consistency=s) is answered from the node’s local copy, without checking.

I paused two of the three etcd nodes with kill -STOP, so the remaining node was cut off from the majority, and tried each operation against it:

PUT city=Mumbai                      -> TimeoutError after 3.0 s
GET city   (linearizable, default)   -> TimeoutError after 3.0 s
GET city   (serializable)            -> 'Pune'  in 2 ms

This is CAP in action, inside one system:

• The write and the linearizable read chose consistency. Without a majority, the node can’t be sure it’s still part of the “real” cluster (maybe the other two elected a new leader and accepted newer writes), so it refuses.
• The serializable read chose availability. It answered instantly, with the value it had. That value was Pune, and as we saw in Lesson 2, Mumbai was about to become the real value.

Then I let the nodes recover and measured the “else” part of PACELC: 2,000 reads of each kind from a follower on a healthy cluster:

follower, linearizable   p50 1.87 ms   p99 4.63 ms
follower, serializable   p50 1.07 ms   p99 2.80 ms

Even with all three nodes on the same machine, the consistent read costs about 75% more, because the follower has to check with the leader first. Put the nodes in different availability zones and that extra hop becomes 1-2 ms of network; put them in different regions and it becomes 50-150 ms.

I also caught a stale read in the act. I paused one follower, made 200 writes through the leader, then resumed the follower and immediately hammered it with serializable reads:

reads from resumed follower: 4   stale: 3   stale for 5.2 ms

For 5.2 milliseconds, the follower served old values (Mumbai-1, Mumbai-2, Mumbai-119) while it caught up. A linearizable read can’t do this: before answering, the follower asks the leader for the latest commit position and waits until it has applied everything up to that point.

Choosing Consistency Per Piece of Data

The practical skill is to stop thinking about “the system’s consistency” and instead decide per piece of data:

Notice the wallet fix in the first row: the bug in my story wasn’t really about replication settings. It was about reading the balance from one place and writing it somewhere else. A single atomic conditional update on the leader makes the overdraft impossible, whatever the read replicas show.

Pitfalls to Avoid

1. Saying “eventually consistent” without saying what can go wrong in the meantime.
2. Reading from a replica and writing based on that read. Check-then-act on stale data causes double-spends and overselling.
3. “Our database is CP, so we’re safe.” Check what each operation actually does; many default to weaker reads.
4. Ignoring PACELC. Strong consistency costs latency on every request, not just during failures.
5. One consistency level for everything. Over-paying for view counts, under-protecting balances.
6. Missing session guarantees. Users notice going “back in time” far more than they notice small delays.

Quick Recap

• A consistency model describes what reads may return. Linearizable = behaves like one copy; eventual = converges someday.
• Causal, read-your-writes and monotonic reads are useful middle grounds that fix most user-visible weirdness.
• CAP: during a partition, choose between refusing (C) and answering possibly stale (A). PACELC: in normal times, choose between latency and consistency.
• Real etcd test: a cut-off node refused writes and linearizable reads, but answered a serializable read with old data in 2 ms. A follower served stale reads for 5.2 ms after rejoining.
• Decide consistency per piece of data, and do check-then-act operations atomically on the leader.

Next lesson: how a cluster of machines actually agrees on anything. Raft’s leader elections and log replication, and what happened when I killed the leader of a live etcd cluster.