CAP Theorem: Understanding Distributed System Trade-offs

You've mastered the theory of CAP—consistency, availability, and partition tolerance. You understand the formal definitions, the trade-offs, and the impossibility results. But sitting in a design review, someone asks: "Should we use Cassandra or PostgreSQL for this service?" Theory alone won't answer that question.

CAP in practice is about translating theoretical understanding into architectural decisions. It's about recognizing that real systems exist on a spectrum, not in neat categories. It's about understanding that the same system can behave as CP in one configuration and AP in another. And it's about knowing when CAP is the right framework and when other considerations dominate.

When designing a distributed system, use this framework to make CAP-informed decisions:

Step 1: Identify Your Data Categories

Not all data has the same requirements. Categorize your data:

Step 2: Define Your Failure Scenarios

For each category, ask: What happens during a partition?

• Accepting stale data: Is a 5-minute-old view acceptable?
• Returning errors: Can users tolerate "try again later"?
• Queue for later: Can operations be deferred and applied later?
• Conflicting writes: What if two users modify the same data?

Step 3: Choose Your Strategy Per Category

For data requiring consistency:

• Use CP storage (PostgreSQL with sync replication, etcd, CockroachDB)
• Accept that some operations will fail during partitions
• Design UX for graceful error handling
• Implement retry logic with exponential backoff

For data tolerating eventual consistency:

• Use AP storage (Cassandra, DynamoDB with eventual read)
• Implement conflict resolution (LWW, merge, CRDT)
• Consider read-your-writes guarantees for better UX
• Monitor replication lag and divergence

For data that needs both (the hard cases):

• Separate the data: some fields CP, some fields AP
• Use hybrid architecture: CP for writes, cached AP for reads
• Accept degraded functionality during partitions
• Design explicit modes: "offline mode" vs "online mode"

Step 4: Validate with Failure Testing

After implementation, validate your choices:

• Inject partitions and verify behavior matches design
• Measure actual availability and consistency during failures
• Test conflict resolution with realistic scenarios
• Update design based on production experiences

Understanding how production systems handle CAP provides practical insight. Let's examine several popular distributed databases and their CAP characteristics.

Deep Dive: MongoDB's Configurable Consistency

MongoDB beautifully illustrates how modern systems offer tunable consistency:

Write Concern: Controls durability/consistency of writes

• w: 1 - Acknowledged when primary receives (AP-ish)
• w: majority - Acknowledged when majority has it (CP-ish)
• w: 0 - Fire and forget (pure AP)

Read Concern: Controls consistency of reads

• local - Returns primary's data, may be rolled back (AP)
• majority - Returns data confirmed by majority (CP)
• linearizable - Reflects all acknowledged writes (strong CP)

Read Preference: Where to read from

• primary - Always read from primary (consistent but SPOF)
• secondary - Read from secondaries (available but potentially stale)
• nearest - Read from lowest-latency node (fastest but unpredictable consistency)

This flexibility lets you tune per-operation, using strong consistency for critical ops and relaxed consistency for others.

CP systems sacrifice availability during partitions to maintain consistency. Let's explore when and how to use them effectively.

When to Choose CP:

• Financial transactions: Double-spending, incorrect balances are unacceptable
• Inventory management: Overselling has real costs (expedited shipping, customer anger)
• Booking systems: Double-booking a hotel room, flight seat, or appointment
• Leader election: Having two leaders causes split-brain and data corruption
• Configuration data: Inconsistent config can crash entire systems
• Identity/authentication: Wrong permissions are security vulnerabilities

Implementing CP Effectively:

1. Use consensus-based systems (etcd, ZooKeeper, Consul)

• Built on Paxos or Raft, proven correct
• Automatic leader election and failover
• Quorum-based operations ensure consistency

2. PostgreSQL with synchronous replication

synchronous_commit = on
synchronous_standby_names = 'first 1 (standby1, standby2)'

Writes are acknowledged only after at least one standby confirms. Partition of primary from all standbys means writes block.

3. CockroachDB for distributed SQL

• Serializable isolation by default
• Raft-based replication
• Automatic resharding and rebalancing

Trade-offs of CP Systems:

Latency: Writes go through consensus, adding round-trips. Expect 10-100ms per write depending on deployment topology.

Availability during partitions: Minority partitions are completely unavailable. In a 5-node cluster, 2 failing nodes means the minority cannot serve requests.

Scalability challenges: Every write must be agreed upon, limiting write throughput. Many CP systems don't scale writes horizontally well.

Complexity: Consensus protocols are subtle. Many implementations have had bugs. Use well-tested systems.

Mitigation strategies:

• Use CP for metadata/coordination, not high-volume data
• Cache reads aggressively (with appropriate invalidation)
• Use async followers for read scaling (with caution about staleness)
• Geographic placement to minimize consensus latency

AP systems continue serving requests during partitions, accepting that replicas may temporarily diverge. Let's explore when and how to use them effectively.

When to Choose AP:

• Shopping carts: Better to accept items than lose the sale; merge later
• Social media feeds: Showing slightly stale content is fine; being unavailable isn't
• IoT data ingestion: Sensors must always be able to report; merge duplicates later
• Session stores: User sessions should always work; occasional stale data is acceptable
• CDN cached content: Slight staleness is fine; availability is paramount
• Metrics and logging: Losing a few datapoints is better than blocking the system

Implementing AP Effectively:

1. Choose the right conflict resolution strategy

2. Implement read-your-writes when possible

Even in AP systems, users expect to see their own changes. Strategies:

• Session stickiness: Route user to the node that received their writes
• Version tokens: Include version in response; wait until replica reaches that version
• Read from writer: For a short window after write, read from the node that accepted the write

3. Monitor and alert on divergence

AP systems should track:

• Replication lag across replicas
• Conflict rate and resolution outcomes
• Retry rates on inter-node replication
• Time since last successful sync per replica pair

Alert when divergence exceeds thresholds—a replica that's hours behind may have a problem.

Modern distributed systems increasingly offer tunable consistency, allowing per-operation or per-table consistency settings. This is powerful but introduces complexity.

How Tunable Consistency Works:

Most tunable systems use quorum-based logic:

• N: Total number of replicas
• W: Write quorum (nodes that must acknowledge a write)
• R: Read quorum (nodes that must respond to a read)

Guarantee: If W + R > N, at least one node in the read quorum was in the write quorum, ensuring you read the latest write.

Examples configurations for N=3:

Practical Application: Per-Operation Tuning

Develop conventions for your application:

Critical operations: Use strong consistency

// User signup - must not duplicate
await cassandra.execute(
  'INSERT INTO users ...', 
  values,
  { consistency: types.consistencies.quorum }
);

Read-heavy analytics: Use eventual consistency

// Dashboard view - okay if slightly stale
await cassandra.execute(
  'SELECT * FROM page_views ...',
  values,
  { consistency: types.consistencies.one }
);

The Danger of Tunable Consistency:

Tunable consistency adds cognitive load and error opportunity:

• Developers must remember which operations need which consistency
• Mixing consistency levels can lead to subtle bugs
• Testing all combinations is difficult
• Production behavior depends on per-call settings, not just configuration

Best practice: Establish a small set of allowed patterns (e.g., "critical writes" and "casual reads") and use framework-level enforcement. Don't let every developer set consistency ad-hoc.

CAP is foundational, but it's not the only framework for distributed system trade-offs. Understanding related concepts provides a more complete picture.

PACELC: Extending CAP

The PACELC theorem extends CAP to describe behavior when there is NO partition:

Ppartition → Availability/Consistency Else (no partition) → Latency/Consistency

Translation:

• During partitions: Choose between Availability and Consistency (CAP)
• During normal operation: Choose between Latency and Consistency

This captures an important reality: even without partitions, synchronous replication (strong consistency) increases latency. Some systems sacrifice consistency for lower latency even when they could achieve consistency.

Examples in PACELC terms:

ACID vs BASE

Database consistency is often discussed in terms of ACID (traditional) vs BASE (NoSQL):

ACID:

• Atomicity: Transactions complete fully or not at all
• Consistency: Transactions maintain database invariants
• Isolation: Concurrent transactions don't interfere
• Durability: Committed data survives failures

BASE:

• Basically Available: System responds, even if degraded
• Soft state: State may change without input (due to eventual consistency)
• Eventual consistency: System becomes consistent over time

BASE systems trade ACID guarantees for availability and partition tolerance. They're not "worse"—they're optimized for different use cases.

Consistency Models Hierarchy:

Beyond CAP's binary consistency, there's a rich hierarchy:

1. Linearizability (strongest) - Real-time order, CAP's "C"
2. Sequential consistency - Some total order, not real-time
3. Causal consistency - Causally related events ordered
4. Read-your-writes - You see your own writes
5. Monotonic reads - You never see data go backward
6. Eventual consistency (weakest) - Eventually converges

Let's examine architectural patterns that apply CAP thinking to real systems.

Pattern 1: Polyglot Persistence

Use different databases for different data based on CAP requirements:

┌─────────────────────────────────────────────────────────────┐
│                    MICROSERVICES SYSTEM                     │
├─────────────────────────────────────────────────────────────┤
│  Order Service     → PostgreSQL (CP)                        │
│  (Financial data needs strong consistency)                  │
│                                                             │
│  Session Service   → Redis Cluster (AP)                     │
│  (Sessions need availability, can tolerate staleness)       │
│                                                             │
│  Product Catalog   → Elasticsearch (AP)                     │
│  (Search needs availability, eventual updates are fine)     │
│                                                             │
│  User Preferences  → DynamoDB (AP)                          │
│  (Preferences can be eventually consistent)                 │
│                                                             │
│  Configuration     → etcd (CP)                              │
│  (Config must be consistent across all services)            │
└─────────────────────────────────────────────────────────────┘

Pattern 2: CQRS with Event Sourcing

Command Query Responsibility Segregation separates reads from writes, allowing different consistency for each:

• Command side (writes): Strong consistency, ensure correct state transitions
• Query side (reads): Eventually consistent projections, optimized for read patterns
• Event store: Append-only, source of truth, CP characteristics
• Read models: Derived from events, can be rebuilt, AP characteristics

Pattern 3: Cache-Aside with TTL

In this pattern, the cache (AP) provides low-latency reads while the database (CP) remains the source of truth:

1. Read: Check cache first. On miss, read from DB, populate cache with TTL.
2. Write: Write to DB. Invalidate cache entry (or let TTL expire).

Trade-off: Reads may return stale data up to TTL duration. Acceptable for many use cases (product pages, user profiles, analytics dashboards).

Pattern 4: Write-Ahead Log with Async Replication

Local writes are durable to a WAL, then asynchronously replicated:

1. Client writes to local node
2. Write persisted to local WAL (durable)
3. Success returned to client
4. Background process replicates to other nodes

Trade-off: If the local node fails before replication, data is lost from other nodes' perspective. But writes are fast and available.

We've bridged theory and practice, exploring how CAP principles translate into real architectural decisions. Let's consolidate the essential insights.

What's Next:

With CAP in Practice covered, we'll close this module with Choosing Between CP and AP—a focused decision guide for making the final call. You'll get concrete criteria, decision trees, and case studies to solidify your ability to make CAP-informed architectural choices.