systemsadvanced 22m read

Designing for Scale · CAP and the Consistency Spectrum

Why strong consistency is a latency penalty you choose to pay, why eventual consistency is not a defect, and how to use the CAP theorem to end distributed systems arguments.

The problem this post solves

Consistency is the hardest word in system design because it means two different things. In ACID, it means a transaction leaves the database in a valid state. In distributed systems, it means a read returns the most recent write.

This post is entirely about the latter. When data is copied across multiple machines to survive failures, those copies will disagree. The rules governing how and when they agree determine the system's latency, availability, and correctness. Misunderstanding these rules leads to systems that are either too slow to use or too wrong to trust.

First principles

From first principles

Start with the question

Why can't we just have instant, perfect replication?

1
Data must be replicated across nodes to survive a node failure.
forced by · Single points of failure are unacceptable at scale.
2
Replicating data takes time.
forced by · Physics. Light takes time to cross a network, and networks drop packets.
3
If a read arrives during replication, the system must choose between waiting or returning old data.
forced by · The new data has not arrived yet.
4
Waiting hurts availability and latency. Returning old data hurts consistency.
forced by · There is no third option.

⇒ Therefore

Consistency in distributed systems is a trade-off against latency and availability. You cannot have all three.

The CAP Theorem

Eric Brewer's CAP theorem states that a distributed data store can guarantee at most two of the following three properties:

Consistency: Every read receives the most recent write or an error.
Availability: Every request receives a non-error response, without the guarantee that it contains the most recent write.
Partition tolerance: The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.

Common misconception

✗ What most people think

You get to pick two: CA, CP, or AP.

✓ What is actually true

You must pick P. You only choose between CP and AP when a partition happens.

Why the myth is so sticky

Networks will fail. Partitions will happen. Because you cannot prevent partitions, your system must tolerate them. The only real choice is what the system does *during* a partition: does it refuse to answer (CP) to remain correct, or does it answer with potentially stale data (AP) to remain available?

Prove it to yourself

Ask: What does this system do when the network cable between the primary and replica is cut?

CP: Consistency and Partition Tolerance

A CP system chooses to return an error (or time out) rather than return stale data.

If a bank account balance is updated on node A, and a partition prevents that update from reaching node B, a read request to node B will fail. The system sacrifices availability to guarantee that nobody overdraws their account based on a stale read.

AP: Availability and Partition Tolerance

An AP system chooses to return the data it has, even if it might be stale.

If a social media "like" count is updated on node A, and a partition prevents that update from reaching node B, a read request to node B will return the old count. The system sacrifices consistency to ensure the user can still load the page.

The PACELC Theorem

CAP only describes what happens during a network partition. But network partitions are rare. What happens the rest of the time?

PACELC extends CAP to answer this. It states: If there is a Partition, how does the system trade off Availability and Consistency? Else (when running normally), how does the system trade off Latency and Consistency?

This is the trade-off designers actually make every day. When the network is perfectly healthy, you still have to choose: do you want the read to be fast (Latency), or do you want it to be perfectly up-to-date (Consistency)?

The tradeoff

Choosing between Latency and Consistency (the ELC part of PACELC)

Optimize for Consistency

+ you gain Reads are always correct. Logic is simple.

− you pay Reads are slow. The system must coordinate across nodes before answering.

pick when Financial transactions, inventory management, authorization state.

Optimize for Latency

+ you gain Reads are instantly served from the closest node or cache.

− you pay Reads may be stale. Application logic must handle conflict resolution.

pick when Social feeds, product catalogs, comments, metrics.

The Consistency Spectrum

Strong and Eventual consistency are the ends of a spectrum. Between them lie guarantees that are cheaper than strong consistency but safer than eventual consistency.

Strong Consistency

After a write completes, any subsequent read will return that value. It requires synchronous replication. The primary cannot acknowledge the write until the replicas confirm they have it. This is slow.

Eventual Consistency

If no new updates are made, eventually all accesses will return the last updated value. This is the default for most large-scale systems (like DNS or Amazon Dynamo). It uses asynchronous replication. It is fast, but reads immediately after writes may show old data.

Read-Your-Own-Writes Consistency

A user will always see their own updates, but other users might see older versions for a while. This is the baseline expectation for user interfaces. If you update your profile picture, your next page load must show the new picture, even if your friends see the old one for another minute.

Mental modelRead-Your-Own-Writes routing

A router looking at the request session. If the user recently wrote data, route their reads to the primary database. If they haven't, route their reads to the replicas.

Users accept if the rest of the world is a few seconds behind.
Users report a bug if their own action doesn't appear immediately.
Track the timestamp of a user's last write in their session token.

🔔 Fires when you see

Use when someone complains that refreshing the page immediately after submitting a form shows the old form state.

Bounded Staleness

Reads are guaranteed to be no more than N versions or T seconds out of date. This allows replicas to serve reads with bounded error.

Failure modes

Assuming strong consistency is free. It is paid for in latency on every request, and in outages when the coordination mechanism fails.

Assuming eventual consistency is a defect. It is a deliberate engineering choice to buy availability and performance. Most of the physical world operates on eventual consistency (e.g., mail delivery, bank clearing).

Leaking eventual consistency to the user. Failing to provide read-your-own-writes consistency breaks trust. The user assumes the system lost their data.

What to carry forward

Key points

You can now

Explain why the 'CA' in CAP is an illusion.
Use PACELC to explain the everyday latency penalty of strong consistency.
Design a routing strategy that guarantees read-your-own-writes while still using read replicas.
Match the right point on the consistency spectrum to the business requirement.