CAP and PACELC: Database Trade-offs

Hello! Welcome to the fourth lesson in our course on Distributed Systems Architecture.

In our last lesson, we explored the spectrum of consistency models, from the strict, real-time guarantees of linearizability to the relaxed, availability-focused model of eventual consistency. We noted that stronger consistency models often come with performance and availability trade-offs.

Today, we will formalize that intuition with one of the most foundational principles in distributed computing: the CAP Theorem. We will dissect its components and then examine its more nuanced successor, the PACELC theorem, to understand the full range of trade-offs you must navigate when designing or choosing a distributed system.

Learning Outcome:

Analyze the trade-offs defined by the CAP theorem and its extension, the PACELC theorem, using real-world database systems as examples.

This lesson will provide you with a critical framework for evaluating system architectures and database technologies, connecting high-level theory to the practical decisions you've encountered in your career.

1. Introduction to the CAP Theorem

The CAP theorem, first conjectured by Eric Brewer, states that a distributed data store can only provide two of the following three guarantees simultaneously:

• 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.

Let's begin with a short, animated video that provides a clear and simple introduction to these three concepts.

2. The Inevitable Trade-off

A common misunderstanding of the CAP theorem is that you can simply "pick any two" properties. In reality, for any system distributed across a network, partition tolerance (P) is not optional. Network failures are a given, so a distributed system must be able to tolerate them.

This means the actual trade-off, when a network partition occurs, is between Consistency (C) and Availability (A).

To understand this fundamental conflict, let's walk through a thought experiment. Imagine a simple distributed database with two nodes, Node 1 and Node 2, that replicate a piece of data, say a user's account balance, which is initially £100.

1. A network partition occurs. Node 1 and Node 2 can no longer communicate.
2. A client sends a request to withdraw £20 to Node 1. Node 1 updates its local value to £80.
3. Simultaneously, another client requests the current balance from Node 2.

Now the system faces a choice:

• Prioritize Consistency (Forfeit Availability): To maintain consistency, Node 2 cannot respond with its local value of £100, as it knows it might be stale. It must either try to contact Node 1 (which will fail due to the partition) or return an error. The system is no longer fully available for reads. This is a CP system.
• Prioritize Availability (Forfeit Consistency): To remain available, Node 2 responds immediately with its local value, £100. The client receives a response, but it's stale data. The system is available but inconsistent across the partition. This is an AP system.

This shows you cannot have both C and A in the presence of P.

The following reading provides a more detailed breakdown of the three pillars and clarifies common misconceptions.

3. CAP in the Real World: CP vs. AP Systems

This trade-off is not just theoretical; it's at the heart of the design of nearly every distributed database.

CP Systems (Consistency + Partition Tolerance)

When faced with a partition, CP systems choose to preserve consistency. This often means that one side of the partition may become unavailable to prevent returning stale or incorrect data.

• Use Case: Financial ledgers, payment processing, and inventory management. In the FX trading platform you built at Revolut, the core order book and trade execution engine must be a CP system. It's unacceptable for a trade to execute at a price that isn't the single, consistent, latest price. It's better to halt trading (reduce availability) than to execute trades on inconsistent data.
• Database Examples:
  • PostgreSQL (in a typical replicated setup): A primary node handles writes. If replicas cannot communicate with the primary during a partition, they may be unable to serve strongly consistent reads or take over as the new primary, thus sacrificing availability.
  • MongoDB: Can be configured as a CP system. By setting a writeConcern of majority, a write must be acknowledged by a majority of replicas before it is considered successful. During a partition, if a majority cannot be reached, write operations will fail.

AP Systems (Availability + Partition Tolerance)

AP systems choose to remain available during a partition, even at the cost of serving stale data. They often rely on eventual consistency, where conflicts are resolved after the partition heals.

• Use Case: Social media feeds, product catalogs, and user session data. A "like" count on a post doesn't need to be perfectly consistent globally; it's more important that users can interact with the site without errors.
• Database Examples:
  • Amazon DynamoDB & Apache Cassandra: These are classic AP systems. They use techniques like "optimistic replication" where writes are accepted by any available replica and propagated to others later. During a partition, different clients can write to different replicas, creating data conflicts that must be reconciled later.

4. Beyond CAP: The PACELC Theorem

The CAP theorem is a powerful mental model, but it has limitations. Its primary focus is on system behavior during a network partition. But what about when the system is operating normally, which is most of the time?

This is where the PACELC theorem, proposed by Daniel Abadi, provides a more complete picture. It states:

• If there is a Partition, a system must choose between Availability and Consistency (the CAP part).
• Else (i.e., during normal operation), a system must choose between Latency and Consistency.

The "ELC" part addresses a crucial, everyday trade-off:

• To achieve lower Latency (L): A system can respond to a request from the closest replica immediately, without waiting to coordinate with other nodes. This is faster but risks the data being slightly stale (weaker consistency).
• To achieve stronger Consistency (C): A system must coordinate with other replicas (e.g., to acquire locks or ensure a quorum of nodes has seen a write). This coordination adds network round-trips, increasing latency.

The following article provides an excellent critique of CAP's limitations and introduces PACELC as a more comprehensive framework.

5. Classifying Systems with PACELC

PACELC gives us a more nuanced way to describe distributed systems. Instead of just CP or AP, we can use four categories:

PACELC Type	During Partition (P)	Else (Normal)	Description & Examples
PC/EC	Prioritizes Consistency	Prioritizes Consistency	The system always favors consistency, both during partitions and normal operation. This often means higher latency. Examples: PostgreSQL, CockroachDB.
PA/EL	Prioritizes Availability	Prioritizes Latency	The system always favors responsiveness, accepting weaker consistency. Examples: Cassandra, DynamoDB, Riak.
PC/EL	Prioritizes Consistency	Prioritizes Latency	A hybrid approach. The system wants low latency but will sacrifice it to ensure consistency if a partition occurs. Example: MongoDB can be configured this way.
PA/EC	Prioritizes Availability	Prioritizes Consistency	Another hybrid. The system wants to be consistent but will sacrifice it to stay available during a partition. Example: Google's Spanner is sometimes described this way, as it provides very strong consistency guarantees (EC) but is designed to be highly available (PA).

Many modern databases are also tunable. For example, Cassandra allows you to request a "quorum" read or write, effectively shifting it from a pure PA/EL system towards PA/EC for a specific operation, trading lower latency for stronger consistency.

---

Conclusion

In this lesson, we formalized the fundamental trade-offs in distributed systems using the CAP and PACELC theorems. These are not just academic concepts; they are frameworks that explain the core design philosophies of the databases and platforms you use daily.

Key Takeaways:

• The CAP Theorem states that during a network partition, a distributed system must choose between Consistency and Availability.
• Because Partition Tolerance is mandatory for any real-world distributed system, the choice is effectively between being a CP system (prioritizing consistency) or an AP system (prioritizing availability).
• The PACELC Theorem extends CAP by adding that during normal operation (no partition), a system must trade off between Latency and Consistency.
• This gives us a more nuanced classification (PC/EC, PA/EL, etc.) that better describes the behavior of modern databases like PostgreSQL, Cassandra, and MongoDB.
• The choice of where to be on the CAP/PACELC spectrum is a critical architectural decision driven by business requirements. A financial ledger requires a PC/EC system, while a social media feed is well-served by a PA/EL system.

Preview of the Next Lesson:
We've established that CP systems choose consistency during a partition. But how do they do that? How does a group of distributed nodes agree on the "single truth" when messages can be lost or delayed? The answer lies in consensus algorithms. In our next lesson, we will compare the roles and high-level mechanisms of foundational consensus algorithms like Paxos and Raft, which are the engines that power CP systems.