CAP Theorem and Distributed Data Stores

What is the CAP Theorem?

The CAP theorem, first conjectured by computer scientist Eric Brewer in 2000, states that it is impossible for a distributed data store to simultaneously provide more than two of the following three guarantees:

1. Consistency (C): Every read request receives the most recent write or an error. In simpler terms, all clients see the same data at the same time. Any client reading from any node in the system gets an up-to-date view of the data.

2. Availability (A): Every request receives a (non-error) response, without the guarantee that it contains the most recent write. The system is always available to respond to requests, even if some nodes are down.

3. Partition Tolerance (P): The system continues to operate despite the network being partitioned. A network partition means that messages are being dropped or delayed between nodes, creating a communication breakdown.

To get a clear and concise explanation of these three properties, let's watch the beginning of an excellent video on the topic.

The Inevitable Trade-off: C vs. A

In any real-world distributed system, network failures—partitions—are a fact of life. Links can fail, routers can crash, and network latency can spike. Because we cannot wish away network failures, Partition Tolerance (P) is not optional. A system that is not partition-tolerant would be extremely fragile.

This means that for any practical distributed system, you must have 'P'. The actual trade-off, therefore, is between Consistency and Availability. When a network partition happens, you must choose:

• Do you sacrifice Consistency to maintain Availability? (An AP system)
• Or do you sacrifice Availability to maintain Consistency? (A CP system)

A CA system (Consistent and Available, but not Partition-Tolerant) can only exist in theory or in systems that run on a single node, which by definition cannot be partitioned. Most traditional, single-node databases like PostgreSQL or MySQL (before replication is configured) are effectively CA systems.

To see this trade-off in action, let's watch another segment of the same video, which walks through a fantastic example.

Practical Implications: Choosing a System

The choice between CP and AP is not a technical one but a business one. It depends entirely on the requirements of the application you are building.

Choosing CP (Consistency over Availability)

You should prioritize consistency when data correctness is absolutely critical and stale data could lead to catastrophic problems.

• Use Cases: Banking systems (you can't have two ATMs give you money from the same-but-now-empty account), e-commerce inventory management (you can't sell the last item twice), reservation systems (you can't double-book a flight seat or hotel room).
• Behavior during partition: The system will refuse to serve requests that it cannot guarantee are consistent. For example, if a write cannot be confirmed by a majority of nodes, it will fail. A read request might be blocked or return an error if the node cannot contact other nodes to ensure the data is up-to-date.
• Example Databases:
  • RDBMS like PostgreSQL or MySQL in strongly consistent replication modes.
  • Google Spanner and HBase, which are designed for strong consistency across distributed nodes.
  • Coordination services like Zookeeper and etcd.

Choosing AP (Availability over Consistency)

You should prioritize availability when the system being responsive is more important than every user seeing the absolute latest data. In these systems, we accept that data will become consistent over time, a model known as eventual consistency.

• Use Cases: Social media feeds (it's okay if you don't see a friend's new post for a few seconds), view counts on a video (an eventually correct count is fine), user profile updates (seeing a slightly older profile picture for a minute is not a critical failure).
• Behavior during partition: The system will always respond, even if it means serving stale data from a node that is isolated from recent writes. The system will later reconcile these differences once the partition is resolved.
• Example Databases:
  • Apache Cassandra and CouchDB are fundamentally designed around availability and eventual consistency.
  • Amazon DynamoDB (in its default configuration) prioritizes availability.

This video segment provides more excellent examples to solidify your understanding.

A Deeper Dive: Beyond CAP with PACELC

As you might have guessed, the "pick two" mantra of CAP is a simplification. It only describes the trade-off that occurs during a network partition. But what about when the system is operating normally? This is where the PACELC theorem provides a more complete picture.

Proposed by Daniel Abadi, PACELC states:

If there is a Partition, how does the system trade off Availability and Consistency? Else (when the system is running normally), how does it trade off Latency and Consistency?

The "Else" part is the key extension. Even without partitions, achieving strong consistency requires coordination between nodes (e.g., waiting for a write to be replicated to a majority of nodes before confirming it to the client). This coordination adds latency. Therefore, systems must also make a trade-off between lower latency and stronger consistency during normal operation.

Using PACELC gives us a more nuanced way to classify databases:

• PC/EC (e.g., HBase): Prioritizes Consistency, both during partitions and normal operation.
• PA/EC (e.g., MongoDB): Prioritizes Availability during partitions but Consistency (at the cost of higher latency) during normal operation.
• PA/EL (e.g., Cassandra, DynamoDB): Prioritizes Availability during partitions and Latency (at the cost of weaker consistency) during normal operation. This is a common choice for systems that need to be highly available and very fast.
• PC/EL (e.g., some configurations of PNUTS): This is a rarer category. Such a system prioritizes consistency during a partition but opts for lower latency (and weaker consistency) in normal operation.

This more detailed framework is incredibly useful when evaluating which database truly fits your application's needs across all operating conditions.

Consistency as a Spectrum

Finally, it's important to recognize that "Consistency" isn't a single, monolithic concept. The 'C' in CAP specifically refers to linearizability, which is the strongest form of consistency. In practice, there's a whole spectrum of weaker consistency models that are very useful.

I encourage you to read the following article to get a sense of this depth. You don't need to memorize every term, but understanding that this is a spectrum is key to advanced system design.

As the article and previous video hinted, other models like causal consistency (ensuring related events are seen in order) and read-your-writes consistency (ensuring a user sees their own updates immediately) offer valuable guarantees without the high cost of full linearizability.

Conclusion

Today we've unpacked one of the most important principles in distributed systems. You've gone from the simple "pick two" of CAP to the more nuanced PACELC framework, giving you a powerful lens through which to analyze and choose data stores.

Key Takeaways:

• The CAP theorem states that a distributed system must trade off between Consistency (C) and Availability (A) in the event of a Partition (P).
• Because network partitions are inevitable, Partition Tolerance is mandatory. The real choice is between building a CP or an AP system.
• The choice is a business decision: CP is for systems where correctness is paramount (e.g., finance), while AP is for systems where being responsive is more critical (e.g., social media).
• The PACELC theorem extends CAP by adding the trade-off between Latency (L) and Consistency (C) during normal operation, providing a more complete model for evaluating databases.
• Consistency is a spectrum, with many useful models weaker than the strict linearizability implied by CAP.

Preview of the Next Lesson

We've now discussed scaling our services and the fundamental trade-offs in the databases they rely on. However, in a large distributed system, services can be overwhelmed by too many requests, whether from legitimate traffic spikes or malicious actors.

In our next lesson, we will explore rate limiting and throttling. We'll cover the core algorithms, like token bucket and sliding window, that are used to protect your backend services from being overloaded, ensuring they remain stable and available for all users.