CAP Theorem & Consistency Models

Metadata

1. Overview

What problem does it solve?

When you store data on a single machine, life is easy. If a client reads data, they always get the latest version. If the machine goes down, the database is unavailable.

When you shard or replicate data across multiple machines (to improve availability and capacity), you introduce a fundamental problem of physics: The speed of light. It takes time for data to travel from Server A to Server B. If a network cable is cut between them, they cannot communicate at all.

The CAP Theorem is a mathematical proof that states when a network failure happens, a distributed database must choose between two evils:

1. Stop responding to users (Sacrifice Availability).
2. Give users potentially stale/incorrect data (Sacrifice Consistency).

What breaks without it?

• Impossible Expectations: Engineers without CAP knowledge try to build systems that are 100% consistent and 100% available across multiple datacenters. These systems inevitably fail catastrophically during network outages.
• Data Corruption: Choosing Availability without understanding Eventual Consistency leads to irreconcilable split-brain data conflicts.

2. Motivation

Eric Brewer presented the CAP Theorem in 2000. It fundamentally changed how databases were built. Before CAP, relational databases (SQL) heavily favored Consistency (ACID).

When Web 2.0 companies (Amazon, Google) needed to scale globally, they realized that rejecting user shopping carts just because a network switch failed was unacceptable. They willingly sacrificed Strong Consistency to guarantee High Availability, leading to the birth of the NoSQL movement (Cassandra, DynamoDB, Riak).

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The CAP Triangle

• Consistency (C): Every read receives the most recent write, or an error.
• Availability (A): Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
• Partition Tolerance (P): The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network.

Note: You can only pick 2. Because networks (P) will always fail eventually, the real choice is always between C and A.

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef cap fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef highlight fill:#d4edda,stroke:#28a745,stroke-width:3px,color:#155724;

    C(Consistency)
    A(Availability)
    P(Partition Tolerance)
    
    C ---|CP Database<br/>e.g. Postgres, MongoDB| P
    A ---|AP Database<br/>e.g. Cassandra, DynamoDB| P
    C -.-|CA Database<br/>Impossible over a Network!| A

The Network Partition Scenario

Imagine two ATMs connected to Server A and Server B. You have $100.

1. The Partition: A backhoe cuts the fiber optic cable between Server A and B. They cannot communicate.
2. The Conflict: You withdraw 100 at ATM A. Your friend simultaneously withdraws 100 from your account at ATM B.
3. The Choice:
   • CP Choice: The ATMs realize they can't communicate. They refuse the transaction to prevent overdrafting. (Availability is sacrificed. You are angry you can't get your money).
   • AP Choice: The ATMs process both transactions. You both get $100. (Consistency is sacrificed. The bank balance is mathematically incorrect: -$100).

6. Internal Working

PACELC Theorem

The CAP theorem only applies during a network partition. What happens when the network is perfectly fine? The PACELC Theorem extends CAP: "If there is a Partition (P), how does the system trade off Availability and Consistency (A and C); Else (E), when the network is fine, how does the system trade off Latency and Consistency (L and C)?"

For example, DynamoDB is PA/EL: During a partition, it stays Available. During normal operation, it sacrifices strong Consistency to achieve low Latency (Eventual Consistency).

Consistency Models

1. Strong Consistency (Linearizability): Once a write is acknowledged, all subsequent reads (from any node) will see that write.
2. Eventual Consistency: If no new writes are made, eventually all reads will return the last updated value. Used heavily in AP systems.
3. Read-Your-Own-Writes: A user will always see the updates they just made, even if other users don't see them yet (often implemented via session stickiness).

7. Implementation

Why Python? CAP is a conceptual theorem, but resolving the conflicts caused by an AP system requires code. We can easily mock two separated network nodes and demonstrate Last-Write-Wins (LWW), the most common conflict resolution strategy in AP databases like Cassandra.

"""
021 - CAP Theorem & Conflict Resolution
Simulates a network partition between two nodes in an AP system,
and how they reconcile diverging data using Last-Write-Wins (LWW)
once the partition heals.
"""
import time

class APNode:
    def __init__(self, name):
        self.name = name
        self.data = {}           # The actual data
        self.timestamps = {}     # Metadata for LWW resolution

    def write(self, key, value, timestamp):
        """In an AP system, a node always accepts writes, even if disconnected."""
        print(f"[{self.name}] WRITE: {key}='{value}' at T={timestamp}")
        self.data[key] = value
        self.timestamps[key] = timestamp

    def read(self, key):
        return self.data.get(key, None)

    def sync_with(self, other_node):
        """
        The partition has healed! 
        Nodes exchange data and resolve conflicts using Last-Write-Wins.
        """
        print(f"\n--- Network Healed: Syncing {self.name} <-> {other_node.name} ---")
        
        # We must look at ALL keys from both nodes
        all_keys = set(self.data.keys()).union(set(other_node.data.keys()))
        
        for key in all_keys:
            t_self = self.timestamps.get(key, 0)
            t_other = other_node.timestamps.get(key, 0)
            
            # Conflict Resolution: Last-Write-Wins (Highest Timestamp wins)
            if t_self > t_other:
                print(f"Conflict on '{key}': {self.name}'s write wins (T={t_self} > T={t_other})")
                other_node.data[key] = self.data[key]
                other_node.timestamps[key] = t_self
            elif t_other > t_self:
                print(f"Conflict on '{key}': {other_node.name}'s write wins (T={t_other} > T={t_self})")
                self.data[key] = other_node.data[key]
                self.timestamps[key] = t_other


# ── Test Harness ──

if __name__ == "__main__":
    node_us = APNode("US-East")
    node_eu = APNode("EU-West")
    
    print("1. Normal Operation (Network is fine)")
    node_us.write("shopping_cart", "Apple", 100)
    node_eu.sync_with(node_us) # They are in sync
    
    print("\n2. 🔥 NETWORK PARTITION OCCURS 🔥")
    print("US and EU datacenters can no longer communicate.")
    
    # Because it is an AP system, both nodes STILL accept writes!
    # User in US changes cart to "Banana" at time 105
    node_us.write("shopping_cart", "Banana", 105)
    
    # Same user travels to EU, reads stale data, and changes cart to "Orange" at time 110
    node_eu.write("shopping_cart", "Orange", 110)
    
    print("\n3. During Partition, Data is Inconsistent:")
    print(f"US Node sees: {node_us.read('shopping_cart')}")
    print(f"EU Node sees: {node_eu.read('shopping_cart')}")
    
    print("\n4. Network Restored")
    # They sync and must resolve the conflict
    node_us.sync_with(node_eu)
    
    print("\n5. After Sync (Eventual Consistency achieved):")
    print(f"US Node sees: {node_us.read('shopping_cart')}")
    print(f"EU Node sees: {node_eu.read('shopping_cart')}")
    
    print("\nWarning: The US write of 'Banana' was completely lost! This is the danger of LWW in AP systems.")

Sample Output

1. Normal Operation (Network is fine)
[US-East] WRITE: shopping_cart='Apple' at T=100

--- Network Healed: Syncing EU-West <-> US-East ---
Conflict on 'shopping_cart': US-East's write wins (T=100 > T=0)

2. 🔥 NETWORK PARTITION OCCURS 🔥
US and EU datacenters can no longer communicate.
[US-East] WRITE: shopping_cart='Banana' at T=105
[EU-West] WRITE: shopping_cart='Orange' at T=110

3. During Partition, Data is Inconsistent:
US Node sees: Banana
EU Node sees: Orange

4. Network Restored

--- Network Healed: Syncing US-East <-> EU-West ---
Conflict on 'shopping_cart': EU-West's write wins (T=110 > T=105)

5. After Sync (Eventual Consistency achieved):
US Node sees: Orange
EU Node sees: Orange

Warning: The US write of 'Banana' was completely lost! This is the danger of LWW in AP systems.

8. Complexity

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. Explain the CAP theorem. Hint: In the event of a network partition (P), a distributed system must choose between returning an error to ensure Consistency (C) or returning potentially stale data to ensure Availability (A).

2. Is it possible to have a CA distributed database? Hint: No. Network partitions are a physical reality (cables get cut, switches die). You cannot choose "no partitions". You must choose how to react to them.

3. What is Eventual Consistency? Hint: A guarantee that if no new updates are made, all replicas will eventually converge to the same value.

4. Why is Last-Write-Wins dangerous? Hint: It fundamentally requires throwing away data. If two users edit different parts of a document during a partition, the last one to click "Save" overwrites the other person's work entirely.

13. Used By (Downstream Blocks)

• 022 Leader Election — A CP system mechanism to ensure only one node accepts writes during a partition.
• 040 Vector Clocks & CRDTs — Advanced mathematical models to solve the conflict resolution problem in AP databases without losing data.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Implement CRDT-style Merge

Modify the sync_with function. Instead of LWW throwing away the older write, change self.data to be a Python set. When a conflict occurs, merge the two sets together (e.g., {"Banana", "Orange"}).

Exercise 2: Tunable Consistency

Create a cluster_read(key, nodes, consistency_level) function. If consistency_level == 1, return the value from the fastest node. If consistency_level == "QUORUM", query all nodes and only return a value if the majority of nodes agree on it.

Website Metadata