Welcome to the next lesson in our journey through the foundations of distributed systems. In our previous session, we established how to choose appropriate storage solutions like SQL, NoSQL, and caches, and we highlighted the distinct data access patterns for ML training and serving. We concluded by noting that many distributed databases force a trade-off with data consistency.
Today, we will formalize that trade-off by exploring the CAP theorem. This is a fundamental principle that governs all distributed data systems. Understanding the CAP theorem is not just a theoretical exercise; it is a critical tool for making defensible design decisions for any large-scale system. For ML system design, it helps you justify your choices for components like feature stores, model registries, and serving databases. Mastering this concept is also essential for navigating the non-functional requirements discussion in a system design interview.
The Three Pillars of the CAP Theorem
The CAP theorem, first proposed by computer scientist Eric Brewer, states that it is impossible for a distributed data store to simultaneously provide more than two out of the following three guarantees:
- Consistency (C): All nodes in the system see the same data at the same time. This means that after a write operation completes, any subsequent read request from any node will return that new value.
- Availability (A): Every request receives a (non-error) response, without the guarantee that it contains the most recent write. The system remains operational and responsive.
- Partition Tolerance (P): The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes. In essence, the system can sustain a "network partition," where it splits into two or more groups of nodes that cannot communicate with each other.
To start, let's get precise definitions for these three properties.
CAP Theorem for System Design Interviews
This article from Hello Interview provides a clear and practical explanation of the CAP theorem, framed specifically for system design interviews.
Please read the introductory section, What is CAP Theorem?. Focus on understanding the definition of each of the three guarantees. Most importantly, absorb the key insight about partition tolerance.
The crucial takeaway is that for any real-world distributed system that communicates over a network, partition tolerance is not optional. Networks can and do fail. Therefore, a network partition is a reality that must be handled. This simplifies the CAP theorem into a more practical choice: when a network partition occurs, you must choose between Consistency and Availability.
This leads to two main categories of distributed systems:
- CP (Consistent and Partition-Tolerant): These systems choose to sacrifice availability to ensure consistency. If nodes cannot communicate to guarantee the data is up-to-date, the system will return an error or time out rather than serve potentially incorrect data.
- AP (Available and Partition-Tolerant): These systems choose to sacrifice consistency to ensure availability. During a partition, nodes will respond with the best data they have, even if it's stale. The system remains available, but with relaxed consistency guarantees, often referred to as "eventual consistency."
The "CA" (Consistent and Available) category is often mentioned, but it can only exist in systems where network partitions are impossible, such as a single-node database. By definition, a distributed system cannot be CA.
The Trade-off in Practice: CP vs. AP Systems
To make this choice concrete, let's explore it through a simple example and then look at real-world systems.
CAP Theorem for System Design Interviews
This next section of the article illustrates the core trade-off with a simple example and then provides clear criteria for when to choose one over the other.
First, read the example of a website with servers in the USA and Europe. This clearly shows how a partition forces a choice between showing an error (choosing C) or showing stale data (choosing A). Then, read the sections detailing when to choose C and when to choose A.
As the article makes clear, the decision boils down to the business impact of inconsistency.
- You choose Consistency (CP) when inconsistent data would be catastrophic. Examples include financial systems (you cannot show an incorrect bank balance), e-commerce inventory (you cannot sell an item you don't have), and reservation systems (you cannot double-book a seat). In these cases, it's better to be temporarily unavailable than to be wrong.
- You choose Availability (AP) when the user experience of being unavailable is worse than the impact of slightly stale data. Examples include social media feeds (seeing an old profile picture for a few minutes is acceptable), recommendation systems, and content platforms. For these systems, uptime is paramount, and they rely on eventual consistency, where data is replicated asynchronously and will become consistent over time.
You can also watch a video walkthrough of these exact same concepts from the same creators, which may help reinforce the ideas.
CAP Theorem in System Design Interviews
This video covers the same ground as the article you just read, but in a more conversational format.
You can watch the sections explaining the core trade-off with an example, when to choose consistency, when to choose availability, and the corresponding design implications.
Applying CAP to Machine Learning Systems
Now, let's bring this back to our goal of designing ML systems. Different components of an ML system often have different consistency and availability requirements. A single system might contain both CP and AP subsystems.
What Is CAP Theorem and Why It Matters for AI Storage
This article from MinIO directly addresses how CAP trade-offs affect storage decisions for AI and ML workloads.
Please read the section titled Practical Implications for Enterprise AI Infrastructure. As you read, map the different components mentioned to the system design concepts we've discussed.
Let's summarize how CAP applies to common ML system components:
- Online Feature Store: For real-time inference, the model needs to fetch the latest features for an entity (e.g., a user). The primary requirement here is high availability and low latency. It's often better to serve a prediction using slightly stale features than to fail the request entirely. Thus, the online store is typically an AP system (e.g., Redis, Cassandra, or DynamoDB in its default configuration).
- Model Registry & Experiment Tracking: These systems are the source of truth for model artifacts and training metadata. Data integrity is paramount. You cannot risk deploying a corrupted model or losing the results of an experiment. This requires strong consistency. Therefore, these systems are designed to be CP.
- Offline Data Stores (Data Lakes/Warehouses): These stores hold historical data for training. While consistency is important, the access patterns are batch-oriented. The "availability" concern is less about real-time responsiveness and more about the training job being able to access its data without failing. These systems often lean towards consistency but are designed for high throughput over large datasets.
A More Nuanced View: Beyond "Pick Two"
The "pick two out of three" framing is a powerful simplification, but for senior-level design discussions, it's beneficial to have a more nuanced perspective. The CAP theorem is often misinterpreted as a permanent choice, but its trade-off only manifests during a network partition.
A more advanced framework called PACELC extends CAP. It states that if there is a Partition, a system must choose between Availability and Consistency. Else (during normal operation), the system must trade off between Latency and Consistency. This "else" part is crucial: even without failures, achieving stronger consistency often requires more coordination between nodes, which increases latency.
The following video provides an excellent deep dive into these advanced considerations.
Are you Using CAP Theorem Wrong?
This video offers a sophisticated critique of the simple CAP theorem model, introducing concepts that will help you stand out in a design interview.
First, watch the introduction, which explains why the "pick two" model is misleading and incomplete. Next, see why CAP properties are a spectrum and that the trade-off is a runtime decision, not a static label for your system. Finally, watch the explanation of the PACELC framework, which adds the trade-off between Latency and Consistency during normal operation. The DynamoDB example here is particularly insightful: "Something is absent from the CAP theorem. Latency".
The key idea is that "AP" or "CP" is not a permanent identity for your system. It's a description of how your system is configured to behave during a specific failure mode. The rest of the time, you are making a different trade-off: lower latency (by responding from the closest node immediately) versus stronger consistency (by coordinating with other nodes before responding).
Conclusion
In this lesson, we dissected the CAP theorem, a cornerstone of distributed systems design. You've learned how to describe the fundamental trade-off it presents and how to apply it to real-world systems, especially within the context of machine learning.
Here are the key takeaways:
- The Core Trade-off: Since network partitions are inevitable in distributed systems, the CAP theorem forces a choice between Consistency (CP) and Availability (AP) during a failure.
- Use-Case Driven Choice: The decision to prioritize C or A depends on the business requirements. Systems where correctness is paramount (e.g., banking, inventory) choose CP. Systems where uptime is critical (e.g., social media, ad serving) choose AP and settle for eventual consistency.
- ML Systems Have Mixed Needs: A single ML platform will have different requirements for its components. A model registry needs to be CP, while an online feature store for a recommendation engine should be AP.
- Beyond CAP: For a deeper analysis, the PACELC framework extends CAP by adding that during normal operation, systems trade off between Latency and Consistency. This provides a more complete model for the design choices you face.
We have now covered the essential concepts of scaling, architecture, storage, and consistency. We have a solid theoretical foundation for designing the "boxes and arrows" of a system. In our next lesson, we will begin to look at the practicalities of deployment, starting with containerization (Docker) and orchestration (Kubernetes). These tools are the industry standard for packaging, deploying, and managing the applications that run within the architectures we've been designing.