In the previous article, you learned about databases, replication, and sharding. You saw that replicated databases can have “replication lag” where followers temporarily have stale data.

This brings us to one of the most important concepts in distributed systems: the CAP Theorem. It explains why you cannot have everything in a distributed system. You must make trade-offs.

What is the CAP Theorem?

The CAP Theorem was introduced by computer scientist Eric Brewer in 2000. It states that a distributed system can only guarantee two out of three properties at the same time:

  • C — Consistency: Every read receives the most recent write. All nodes see the same data at the same time.
  • A — Availability: Every request receives a response (success or failure). The system never refuses to answer.
  • P — Partition Tolerance: The system continues to work even if network communication between nodes is lost.
The CAP Triangle:

        Consistency (C)
           /\
          /  \
         /    \
        /  ??  \
       /________\
Availability    Partition
    (A)         Tolerance (P)

You can pick two. But in practice, you must always pick P.

Why Partition Tolerance is Not Optional

In a distributed system, machines communicate over a network. Networks are unreliable. Cables get cut. Switches fail. Data centers lose connectivity. Network partitions will happen — it is not a question of if, but when.

Since you must handle partitions (P is mandatory), the real choice is between:

  • CP (Consistency + Partition Tolerance): When a partition happens, the system stops accepting writes to stay consistent. Some requests get errors.
  • AP (Availability + Partition Tolerance): When a partition happens, the system continues serving requests but may return stale data.
The real choice during a network partition:

  CP System:                           AP System:
  ┌─────────┐    X    ┌─────────┐     ┌─────────┐    X    ┌─────────┐
  │ Node A  │----X----│ Node B  │     │ Node A  │----X----│ Node B  │
  │ (write) │  SPLIT  │ (read)  │     │ (write) │  SPLIT  │ (read)  │
  └─────────┘         └─────────┘     └─────────┘         └─────────┘
  Node B returns       Node B stays    Node B returns      Both nodes
  ERROR (refuses       consistent      STALE DATA          stay available
  to serve stale                       but keeps
  data)                                responding

A Simple Example

Imagine you have two database nodes in different data centers. A user updates their profile name from “Alex” to “Sam” on Node A.

CP behavior: Node B refuses to serve the profile until it confirms the update from Node A. If the network is down between the nodes, Node B returns an error instead of showing “Alex” (the old name).

AP behavior: Node B continues to serve the profile, showing “Alex” (the old name). Once the network recovers, it gets the update and shows “Sam.” The data was temporarily inconsistent, but the system was always available.

CP Systems — Consistency First

CP systems guarantee that all nodes always return the same, most recent data. When a partition happens, they sacrifice availability — some requests fail or wait.

Real-World CP Systems

  • ZooKeeper — used for distributed coordination (leader election, configuration management). If ZooKeeper cannot guarantee consistency, it stops serving reads. Used by Kafka, Hadoop, and many distributed systems.
  • etcd — key-value store used by Kubernetes for storing cluster state. It uses the Raft consensus algorithm to keep all nodes in sync.
  • HBase — column-family database built on HDFS. Guarantees strong consistency for reads and writes.
  • MongoDB (with strong read concern) — by default, MongoDB prioritizes consistency. With “majority” write concern and “linearizable” read concern, it acts as a CP system.

When to Choose CP

Choose CP when incorrect data is worse than no data:

  • Banking systems: Showing a wrong account balance is unacceptable. It is better to show an error than a wrong number.
  • Inventory systems: If two people try to buy the last item, only one should succeed. Showing incorrect stock leads to overselling.
  • Booking systems: Two people should not book the same hotel room. Consistency prevents double bookings.
  • Distributed locks: If a lock service returns inconsistent results, multiple processes may think they hold the lock.

AP Systems — Availability First

AP systems guarantee that every request gets a response, even during network partitions. The response may contain stale data, but the system never refuses to answer.

Real-World AP Systems

  • Cassandra — designed for availability and partition tolerance. Uses eventual consistency by default. If a node is down, other nodes handle the request.
  • Amazon DynamoDB — highly available NoSQL database. Uses eventual consistency for reads by default (you can opt into strongly consistent reads at higher cost and latency).
  • CouchDB — document database designed for availability. Uses multi-version concurrency control (MVCC) for conflict resolution.
  • DNS — the Domain Name System is an AP system. DNS records are cached and may be stale, but DNS always returns an answer.

When to Choose AP

Choose AP when stale data is acceptable but downtime is not:

  • Social media feeds: If a post shows 999 likes instead of 1000, no one notices. But if the feed is down, users leave.
  • Shopping carts: Amazon’s shopping cart is AP. If you add an item during a partition, it may temporarily appear on one node but not another. After the partition heals, the carts merge.
  • Content delivery: A CDN serves cached content. The content may be a few seconds old, but it is always available.
  • Search results: A search engine showing slightly outdated results is fine. A search engine that is down is not.

Consistency Patterns

Now let us look at the different levels of consistency you can choose from. It is not just “consistent” or “not consistent” — there is a spectrum.

Strong Consistency

After a write completes, every subsequent read returns the updated value. All nodes agree on the same data at all times.

Strong Consistency:

  Time -->
  T1: Client writes "Sam" to Node A
  T2: Node A replicates to Node B (blocks until confirmed)
  T3: Client reads from Node B --> gets "Sam" (guaranteed)

  The write at T1 is not acknowledged until ALL nodes have the data.

Trade-off: Higher latency. Every write must wait for confirmation from multiple nodes before it is considered successful.

Used by: PostgreSQL (single node), ZooKeeper, etcd, Google Spanner.

Eventual Consistency

After a write, replicas will eventually have the same data. There is a window where different nodes may return different values.

Eventual Consistency:

  Time -->
  T1: Client writes "Sam" to Node A
  T2: Client reads from Node B --> gets "Alex" (old value!)
  T3: Replication completes
  T4: Client reads from Node B --> gets "Sam" (correct)

  Between T1 and T3, the system is inconsistent.

Trade-off: Lower latency, higher availability. But reads may return stale data.

Used by: Cassandra, DynamoDB (default), DNS. (Note: Amazon S3 now provides strong read-after-write consistency for all operations, including overwrites and deletes, since December 2020.)

Causal Consistency

If operation B depends on operation A, then everyone sees A before B. Unrelated operations can be seen in any order.

Causal Consistency:

  Alex posts: "I got a new job!"          (Operation A)
  Alex comments: "Starting next Monday"   (Operation B, depends on A)

  Every user sees the post BEFORE the comment.
  But unrelated posts from other users can appear in any order.

Trade-off: Stronger than eventual consistency, weaker than strong consistency. Good balance for social applications.

Used by: MongoDB (default since version 3.6), some configurations of Cassandra.

Read-Your-Own-Writes Consistency

After a user writes data, that same user always sees their own write. Other users may see stale data.

Read-Your-Own-Writes:

  Alex updates profile name to "Sam"
  Alex reads profile --> sees "Sam" (guaranteed)
  Jordan reads Alex's profile --> might see "Alex" (stale, temporarily)

This is implemented by routing the user’s reads to the node they wrote to, or by waiting for replication before returning.

Used by: Many web applications as a practical compromise.

PACELC Theorem

The CAP Theorem only describes what happens during a partition. But what about when the system is running normally (no partition)?

The PACELC Theorem extends CAP:

  • PAC: If there is a Partition, choose between Availability and Consistency (same as CAP).
  • ELC: Else (no partition), choose between Latency and Consistency.
PACELC Decision:

  Is there a network partition?
    YES --> Choose: Availability (A) or Consistency (C)?
    NO  --> Choose: Latency (L) or Consistency (C)?

Examples:
  Cassandra:  PA / EL  (availability during partition, low latency normally)
  MongoDB:    PC / EC  (consistency during partition, consistency normally)
  DynamoDB:   PA / EL  (availability during partition, low latency normally)
  ZooKeeper:  PC / EC  (consistency always)
  Spanner:    PC / EC  (consistency always, but uses TrueTime for low latency)

PACELC is more useful than CAP in practice because most of the time, there is no partition. The latency vs consistency trade-off matters every day, not just during rare partition events.

Quorum Reads and Writes

Quorum is a technique to balance consistency and availability in replicated systems. It uses a voting mechanism.

In a system with N replicas:

  • W = number of nodes that must confirm a write
  • R = number of nodes that must respond to a read

The rule for strong consistency: W + R > N

Quorum Example (N=3 replicas):

  Strong consistency: W=2, R=2 (2+2=4 > 3)
    Write: must be confirmed by at least 2 of 3 nodes
    Read:  must read from at least 2 of 3 nodes
    At least one node in every read has the latest data.

  Eventual consistency: W=1, R=1 (1+1=2 < 3)
    Write: confirmed by 1 node (fast!)
    Read:  reads from 1 node (fast!)
    That node might not have the latest data.

  High write availability: W=1, R=3 (1+3=4 > 3)
    Writes are fast (only 1 node confirms)
    Reads are slower (must check all 3 nodes)
    Still strongly consistent!

  High read availability: W=3, R=1 (3+1=4 > 3)
    Writes are slower (must confirm on all 3 nodes)
    Reads are fast (only 1 node)
    Still strongly consistent!

How Quorum Works

Write with W=2, N=3:

  Client writes "Sam"
    --> Node 1: writes "Sam" --> OK
    --> Node 2: writes "Sam" --> OK
    --> Node 3: (slow, not confirmed yet)

  Write returns success (2 out of 3 confirmed)

Read with R=2, N=3:

  Client reads:
    --> Node 1: returns "Sam" (latest)
    --> Node 2: returns "Sam" (latest)
    --> (Node 3 not queried, or returns "Alex" -- stale)

  Client gets "Sam" (the latest value from the majority)

Used by: Cassandra (tunable consistency), DynamoDB, Riak, and many distributed databases.

Vector Clocks and Conflict Resolution

When two nodes accept writes independently (during a partition or in a leader-leader setup), you get conflicting versions. How do you resolve them?

Vector Clocks

A vector clock is a mechanism to track the order of events across distributed nodes. Each node maintains a counter, and the vector clock is a list of these counters.

Vector Clock Example:

  Node A and Node B both have: item = "phone case", price = $10

  Node A updates price to $12:
    Vector clock: [A:1, B:0]

  Node B updates price to $15 (concurrent, during partition):
    Vector clock: [A:0, B:1]

  When the partition heals:
    [A:1, B:0] and [A:0, B:1] are CONCURRENT (neither happened before the other)
    This is a CONFLICT -- the system must resolve it.

  Resolution strategies:
    1. Last-writer-wins (LWW): use timestamps, pick the latest. Simple but may lose data.
    2. Application-level resolution: present both versions to the application (or user) to merge.
    3. CRDTs: conflict-free replicated data types that automatically merge without conflicts.

Last-Writer-Wins (LWW)

The simplest strategy. Attach a timestamp to each write. When there is a conflict, keep the value with the latest timestamp.

Problem: Timestamps across machines are not perfectly synchronized. Even with NTP, there can be millisecond-level drift. This means you might lose a valid write.

Used by: Cassandra (default), DynamoDB.

CRDTs (Conflict-Free Replicated Data Types)

CRDTs are data structures designed to be merged automatically without conflicts. Examples:

  • G-Counter: A grow-only counter. Each node has its own counter. The total is the sum of all counters. No conflicts possible.
  • OR-Set: An observed-remove set. Elements can be added and removed without conflicts.

Used by: Redis (CRDTs for active-active geo-replication), Riak, some features in DynamoDB.

Real-World Examples

Let us look at how real companies make CAP trade-offs.

Amazon — Shopping Cart (AP)

Amazon’s shopping cart is a classic AP system. During a network partition, customers can still add items to their cart. If the cart state diverges between nodes, Amazon merges the carts when the partition heals. The rule is: never lose an “add to cart” event. It is better to have a duplicate item in the cart (the customer can remove it) than to lose an item.

Google Spanner — Global Database (CP)

Google Spanner is a globally distributed SQL database that provides strong consistency. It uses GPS and atomic clocks (called TrueTime) to synchronize clocks across data centers with microsecond accuracy. This allows it to provide strong consistency with relatively low latency — but it is still higher latency than an AP system.

Netflix — Viewing History (AP)

Netflix uses Cassandra (AP) for viewing history and recommendations. If you watch a show during a partition, the viewing record might not immediately appear on all nodes. But it will eventually. A few seconds of delay in viewing history is fine — what matters is that the streaming service is always available.

Banking — Transactions (CP)

Banks use CP systems for account balances and transactions. If there is a network issue, the ATM shows an error rather than dispensing cash based on a stale balance. This prevents overdrafts and fraud.

Interview Tips

When discussing CAP Theorem in a system design interview:

  1. Do not say “pick two out of three.” Instead, say “Since network partitions are inevitable, the real choice is between consistency and availability during a partition.”

  2. Always justify your choice. “I choose AP for the social media feed because stale data is acceptable, and availability is critical for user experience.”

  3. Mention PACELC. “Even without a partition, I need to choose between latency and consistency. For this use case, I prioritize low latency.”

  4. Use quorum when appropriate. “I will use Cassandra with W=2 and R=2 for a quorum of 3 nodes, giving me strong consistency when I need it.”

  5. Different parts of the system can make different choices. “The payment service is CP (strong consistency), but the product recommendation service is AP (eventual consistency).”

  6. Know the consistency level of popular databases:

    • PostgreSQL: Strong consistency (single node) / CP (with streaming replication)
    • MongoDB: CP by default (tunable)
    • Cassandra: AP by default (tunable with quorum)
    • DynamoDB: AP by default (optional strong consistency reads)
    • Redis: CP in single node, AP in cluster mode

What’s Next?

In the next article, System Design #7: Message Queues, you will learn:

  • What message queues are and why every large system uses them
  • Apache Kafka, RabbitMQ, and Amazon SQS
  • Producer-consumer pattern and publish-subscribe
  • Exactly-once, at-least-once, and at-most-once delivery
  • Dead letter queues and event-driven architecture

This is part 6 of the System Design Tutorial series. Follow along to learn system design from scratch.