CAP and PACELC

The moment data lives on more than one machine, those machines must stay in agreement over a network that can be slow, lose messages, or split into islands. A single machine never faces this, which is part of why one database is so appealing. Once you replicate or shard, you inherit a hard tradeoff, and two short theories describe it: CAP and its refinement PACELC.

Consistency (C): every read sees the most recent successful write, as if there were a single copy. This is the strong form, called linearizability.

Availability (A): every request to a working node gets a real response, not an error or a timeout.

Partition tolerance (P): the system keeps working even when the network drops messages between nodes, splitting them into groups that cannot talk.

The CAP theorem says that during a network partition, a system must choose between consistency and availability. It cannot provide both.

The reason is short. Suppose a link is edited on replica A while replica B is cut off. A client asks B for that link. B has two honest options. It can answer with what it knows, which is possibly stale, giving up consistency. Or it can refuse until it can confirm with A, which keeps the answer correct but gives up availability. There is no third option, because B cannot know what A holds.

The common phrase "pick two of three" misleads. You do not get to pick whether partitions happen. Networks fail, so any real distributed system must tolerate partitions. The real choice is what to do when one occurs.

• CP systems stay correct and may refuse some requests. They suit money, inventory and anything where a wrong answer is worse than no answer. Examples include systems built on consensus.
• AP systems stay responsive and may return stale or conflicting data, reconciling later. They suit feeds, caches, counters and carts, where a slightly old answer is acceptable.

When there is no partition, a system can offer both, which is the usual case. CAP only describes the bad moment.

Between strong and weak sit several useful models.

• Strong: reads always see the latest write. Simple to reason about, slower, and less available.
• Eventual: if writes stop, all copies converge. Fast and available, but readers may see old data meanwhile.
• Read your writes: after you write, you see your own write, even if others do not yet.
• Causal: if one event could have influenced another, everyone sees them in that order.

Most real systems offer a choice, often per operation.

With N replicas of each item, a write waits for acknowledgement from W of them and a read consults R of them. If R + W > N, every read set overlaps every write set, so a read always meets at least one replica that saw the latest write. With N = 3, choosing W = 2 and R = 2 gives 4 > 3 and strong behavior. Choosing W = 1 and R = 1 gives fast but possibly stale reads. You tune consistency against latency without changing the system.

CAP says nothing about normal operation, yet the tradeoff continues. PACELC completes it: if there is a Partition, choose Availability or Consistency, Else, when running normally, choose Latency or Consistency.

Even with a healthy network, keeping replicas strongly consistent means waiting for them to confirm each write, which costs time. Answering from one nearby replica is faster but may be stale. So every replicated store sits somewhere on both axes.

• A store that stays available during partitions and favors low latency otherwise is PA/EL, such as Dynamo style and Cassandra by default.
• A store that insists on consistency in both cases is PC/EC, such as a classic relational database with synchronous replication.
• Mixed designs exist, such as available during partitions but consistent otherwise.

Decide per operation, not per system.

• Redirects are reads where an older mapping is harmless, and downtime is costly. Choose availability and low latency, and accept eventual consistency.
• Creating a link must never hand the same key to two different URLs. Choose consistency for the key allocation, and accept that it may fail briefly during a partition.
• Click counts can be approximate and merged later.

• CAP consistency is not the same as the C in ACID, which concerns rules on data inside one database.
• Availability here is strict: every non-failing node must answer. Real systems talk about uptime in nines, which is a different measure.
• Systems are not simply "CP" or "AP". Many allow each request to choose.
• A partition can be a slow network, not only a cut cable, since a reply that takes too long is the same as no reply.