Hello everyone, welcome to the twenty sixth issue of The Main Thread. In the last issue, we talked about how idempotency makes or breaks our distributed systems. In this issue, we are going to talk about a topic that has been the bedrock of distributed systems for years: The good ol' CAP theorem and what is actually means.

Everyone throws CAP theorem here and there but does anyone really understand it?

I have sat in architecture reviews where senior engineers confidently claim that they chose “AP“ over “CP“ without being able to explain what that means. I have read countless blog posts claiming MongoDB is “AP“ and Postgres is “CP“ as if these were fixed properties of the databases themselves.

The CAP theorem is the most misquoted result in computer science. It has become a tribal shibboleth: something we invoke to sound knowledgeable rather than a tool we actually use to make decisions.

Let’s fix that in this article. By the end of this article, we will understand what CAP actually says, why most explanations get it wrong, and what framework we should actually use when choosing databases.

In 2000, Eric Brewer gave a keynote at PODC where he conjectured that a distributed system cannot simultaneously provide all three of these guarantees:

Consistency (C): Every read receives the most recent write or an error. All nodes see the same data at the same time,

Availability (A): Every request receives a non-error response, without guarantee that it contains the most recent write.

Partition Tolerance (P): The system continues to operate despite network partitions - messages being lost or delayed between nodes.

In 2002, Gilbert and Lynch formally proved this conjecture. The proof is remarkable, elegant and worth understanding.

Imagine two nodes A and B, that can’t communicate (a partition). A client writes value v1 to A. Another client reads from B.

If we want consistency, B must return v1. But B doesn’t know about v1 because it can't talk to A. B must either wait (blocking until partition heals) or return an error. Either way, we sacrificed availability.

If we want availability, B must return something, but it doesn’t have v1. Therefore, it returns stale data. We have sacrificed consistency.

This theorem is a logical impossibility not a design tradeoff. During a network partition, we must choose between consistency and availability. There is no third option.

The choice between consistency and availability only matters during partitions. When the network is healthy, when all nodes can communicate, we can have both consistency and availability. There is no tradeoff. The system works normally.

CAP never says “pick two out of three“. It says “when a partition occurs, choose between C and A“.

This changes everything about how we think about the theorem.

The “P“ in CAP is not really a choice. Network partitions happen. We can’t opt out of them. Switches fail. Cables get cut. Cloud availability zones lose connectivity. Always think about the question: “when partitions happen, do we prefer consistency or availability?“

When people say “Redis is AP“ or "Zookeeper is CP”, they are implying these are intrinsic, permanent properties. They are NOT.

Most databases let us choose our consistency/availability tradeoff per operation or per configuration. Let’s see few examples:

The database doesn't make the CAP choice, we do, through configuration and how we use it.

"Consistency” in CAP is binary: either we have linearizability (the strongest form) or we don’t. But real systems offer a spectrum of consistency models, each with different tradeoffs.

Every operation appears to occur instantaneously at some point between its start and end. All clients see operations in the same order.

The system behaves as if there is only one copy of the data. For this, we have to accept the cost of higher latency (must coordinate across nodes), reduced availability during partitions.

We must use this mode for financial transactions, inventory counts, anything where stale reads cause real problems.

In this mode, all clients see operations in the same order but that order doesn’t have to match real-time.

One example is watching a live broadcast with a delay: everyone sees the same thing, but not necessarily “now“. There’s still a cost of coordination but less than linearizability.

We should use it when we need global ordering but can tolerate slight delays.

Operations that are causally related are seen in the same order by all clients. Concurrent (unrelated) operations may be seen in different orders.

If I post a message then edit it, everyone sees the post before edit. But two unrelated posts might appear in different orders to different people. The cost for coordination is less but there’s the cost of tracking causal dependencies.

We should use it for social features, collaborative editing, anything where “makes sense“ matters more than the global order.

In this mode, if no updates are made, all nodes will eventually converge to the same state. No guarantees about what we read during the convergence period.

We might see old data, new data, or a mix. Eventually it sorts itself out. This mode has the lowest latency and highest availability.

We can use it for read-heavy workloads where stale data is acceptable like caches, analytics, activity feeds.

CAP tells us what happens during partitions. But partitions are rare. Most of the time, our network is healthy. What tradeoffs matter then?