CAP Theorem

Defining the CAP Trade-offs

The CAP theorem simplifies distributed systems into three properties: Consistency, Availability, and Partition Tolerance. Consistency ensures that every read receives the most recent write or an error, meaning all nodes return the same data simultaneously. Availability guarantees that every request receives a non-error response, without the guarantee that it contains the most recent write. Partition Tolerance signifies that the system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes. In real-world systems, network partitions are an inevitable fact of life, not a design choice. Therefore, we must choose between consistency or availability once a partition occurs. If we prioritize consistency, we must sacrifice availability to prevent serving stale data while nodes are disconnected. If we prioritize availability, we must accept that different nodes might serve different versions of the data until the partition is resolved and synchronization occurs.

class DataNode:
    def __init__(self, value):
        self.value = value

    # Simulate a read that prioritizes Consistency by checking status
    def read_consistent(self, is_partitioned):
        if is_partitioned:
            raise Exception("Partition detected: Cannot guarantee consistency")
        return self.value

Consistency: The Strong Integrity Model

Consistency in the context of CAP refers to linearizability, where the system acts as if there were only one copy of the data, and all operations are atomic. When a client writes data to one node, that data must be propagated to all other nodes before any subsequent read operation succeeds. This requires a consensus mechanism, such as a protocol that forces nodes to agree on the state before acknowledging a write. The primary cost of this approach is latency, as every operation must wait for network round-trips across all participating nodes. If one node fails or the network link is severed, the system cannot safely acknowledge writes or guarantee current reads, leading to a temporary outage. This model is essential for systems where data integrity is paramount, such as financial transaction processing where an incorrect balance could result in significant economic loss or legal complications for the institution.

def write_with_consensus(nodes, data):
    # Simulate a consensus loop: all nodes must confirm
    for node in nodes:
        try:
            node.value = data # Update node
        except ConnectionError:
            return False # Fail the write if one node is unreachable
    return True # Success only if total consensus reached

Availability: The Fault-Tolerant Model

Availability ensures that the system always remains responsive to client requests, even if the underlying nodes cannot communicate with each other. In this model, the system accepts writes on any node and serves reads from any node, regardless of whether that data is the absolute latest. This is often referred to as eventual consistency. By relaxing the requirement for strict data uniformity, we remove the need for blocking synchronization during every write. If a network partition occurs, each side of the partition continues to accept traffic, effectively allowing the system to remain functional. However, this creates a state where the system may return different answers to the same query depending on which node is contacted. This model is favored by large-scale web applications where user experience depends on immediate responsiveness and the ability to continue browsing or interacting with content, even if some updates are slightly delayed across the global network.

class AvailableNode:
    def __init__(self):
        self.value = None

    # Always return a value, even if potentially stale
    def read(self):
        return self.value # Always succeeds regardless of network state

    def write(self, data):
        self.value = data # No consensus required, just update locally

Partition Tolerance: Managing Reality

Since network partitions are inevitable in any distributed environment, engineers cannot choose to opt-out of partition tolerance. The network is essentially an unreliable medium prone to latency, packet loss, and full disconnection. Partition tolerance requires the system to have a strategy for handling these inevitable events, usually involving timeouts, heartbeats, or background synchronization processes. When a partition occurs, the system must decide whether to stop accepting writes (preserving consistency) or continue accepting writes (preserving availability). Modern systems often attempt to mitigate the harshness of this choice by utilizing 'tunable consistency'. In this architecture, a client can decide on a per-request basis whether to require a majority of nodes to acknowledge a write or if a single node acknowledgement is sufficient. This empowers developers to make informed choices based on the criticality of the specific data being processed, effectively balancing the load between the need for speed and the need for precision within a single application.

def flexible_read(nodes, quorum_size):
    responses = []
    for node in nodes:
        # Collect responses until quorum is met
        responses.append(node.get_data())
        if len(responses) >= quorum_size:
            return max(responses, key=responses.count) # Return majority

Handling Conflict Resolution

In an Availability-prioritized system, we eventually have to reconcile divergent states once the network partition is healed. This process is known as conflict resolution. If two users update the same piece of information on different sides of a partition, the system must decide which update takes precedence or how to merge the changes. Common strategies include Last-Write-Wins (LWW), which uses timestamps to resolve conflicts, or more advanced structures like Vector Clocks, which track causal history to identify if one update happened before another. Vector clocks prevent data loss by allowing the system to detect concurrent writes that are not causally related, leaving the final resolution to the application logic. Choosing a strategy depends entirely on the domain; for instance, a shopping cart might merge contents from different nodes, while a profile update might simply overwrite the old data based on the latest server timestamp.

def resolve_conflict(val1, ts1, val2, ts2):
    # Simple Last-Write-Wins resolution strategy
    if ts1 > ts2:
        return val1
    return val2 # Return the most recent update based on timestamp

Interview questions

All System Design interview questions →

Check yourself

Take the full System Design quiz →