CAP & Consistency

Before this

• SQL vs NoSQL — Access patterns decide the store — not fashion, and not scale you don't have.

Why this exists

Before Eric Brewer formalized the CAP theorem, teams tried to build distributed systems that were simultaneously 100% available and globally synchronized across wide-area networks. When real-world fiber cuts occurred, these architectures either silently split-brain corrupted data or hung indefinitely while waiting for unreachable nodes. CAP proved that you cannot eliminate the network partition: during a partition, you must explicitly choose between returning consistent data or returning a response at all.

The mental model

Imagine two bank tellers in different branches with a severed telephone line between them. If a customer deposits $100 at Branch A and a co-owner attempts to withdraw that same $100 at Branch B, Branch B has two choices: refuse the withdrawal until the phone line is restored (sacrificing **Availability** to preserve **Consistency**), or hand over the cash and risk an overdraft if the money was already spent elsewhere (sacrificing **Consistency** to preserve **Availability**).

How it works

The mechanism

1. A network partition isolates Node $N_1$ (in Region A) from Node $N_2$ (in Region B). 2. Client 1 sends `WRITE key=X, val=v2` to $N_1$. $N_1$ cannot replicate the update to $N_2$ across the severed boundary. 3. In a **CP system** (e.g., etcd, ZooKeeper, Spanner), $N_1$ refuses the write or blocks because it cannot achieve quorum, prioritizing state correctness over availability. 4. In an **AP system** (e.g., Cassandra with local quorum, DynamoDB in eventual mode), $N_1$ accepts the write locally and acknowledges success. When Client 2 reads `key=X` from $N_2$, $N_2$ immediately returns the stale value `v1`, sacrificing linearizability to remain available.

sequenceDiagram
    autonumber
    participant C1 as Client 1
    participant N1 as Node 1 (Region A)
    participant N2 as Node 2 (Region B)
    participant C2 as Client 2

    Note over N1,N2: Network Partition Occurs (Link Severed)
    C1->>N1: WRITE x = 2
    N1--xN2: Replicate x = 2 (Fails)
    
    alt CP Decision (Linearizable)
        N1-->>C1: Error / Timeout (Refuse write)
    else AP Decision (Available)
        N1-->>C1: 200 OK (Write accepted locally)
        C2->>N2: READ x
        N2-->>C2: 200 OK (Returns stale x = 1)
    end

What people get wrong

You can design a 'CA' distributed database by buying high-grade enterprise networking gear.

CA distributed systems do not exist on physical networks. A CA database only exists if it runs on a single node with no network boundaries. Network partitions are guaranteed by the laws of physics over time—cables get severed, switches crash, and BGP routes fail. The moment communication breaks, a system must either stop taking requests (giving up A) or accept divergence (giving up C).

The 'C' in CAP is identical to the 'C' in relational ACID transactions.

CAP 'C' is single-copy consistency (Linearizability), whereas ACID 'C' is invariant preservation (Consistency). ACID consistency means that database constraints (like foreign keys or balance >= 0) are maintained across transactions. CAP consistency means every read across a distributed cluster reflects the absolute latest write in real-world time.

Choosing an AP system means you never get read errors or downtime.

AP guarantees that reachable nodes respond without errors, but it does not protect against crashes or guarantee data correctness. AP systems trade away linearizability, meaning different clients may receive wildly conflicting reads, duplicate writes, or stale records during and after a network split.

When not to use it

Financial ledgers, inventory decrementing, and distributed mutual exclusion (locks/leader election).

CP architectures using consensus algorithms like Raft or Multi-Paxos (e.g., etcd, CockroachDB, Spanner).

High-throughput metric ingestion, social media feeds, analytics counters, and shopping cart additions.

AP architectures using conflict-free replicated data types (CRDTs), last-write-wins timestamps, or eventual consistency engines (e.g., DynamoDB, Cassandra).

Terms

Linearizability

— A consistency model where every operation appears to take effect instantaneously at a specific point in time between its invocation and its completion across all nodes.

Network Partition

— A failure state where communication between two or more sets of cluster nodes is delayed or completely dropped, splitting the network into isolated sub-clusters.

Quorum

— The minimum number of cluster members that must explicitly agree on an operation before that operation is considered committed and safe.

PACELC

— An extension of the CAP theorem stating: if there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.

In an interview