distributed-systems-cap-theorem

CAP theorem fundamentals, consistency vs availability trade-offs, and practical implications for distributed system design

CAP Theorem

Scope: CAP theorem, consistency-availability trade-offs, partition tolerance, system design implications Lines: ~290 Last Updated: 2025-10-27 Format Version: 1.0 (Atomic)

When to Use This Skill

Activate this skill when:

Core Concepts

The CAP Theorem

Statement: In a distributed system, you can only guarantee two of three properties:

C = Consistency
    All nodes see the same data at the same time

A = Availability
    Every request receives a response (success or failure)

P = Partition Tolerance
    System continues despite network partitions

Reality: Network partitions will happen, so you must choose between:

Why CAP?

Proof sketch:

Given:
- Network partition splits nodes into two groups
- Client writes to one side
- Client reads from other side

If Consistent (C):
  → Must wait for partition to heal
  → System unavailable (violates A)

If Available (A):
  → Return potentially stale data
  → Not consistent (violates C)

Cannot have both C and A during partition (P)

Consistency vs Availability

CP Systems (Consistency + Partition Tolerance)

Behavior during partition: Reject requests to maintain consistency

Examples:

When to choose:

Example:

# CP system: Returns error if can't guarantee consistency
try:
    balance = bank_db.get_balance(account_id)
    if balance >= amount:
        bank_db.withdraw(account_id, amount)  # Blocks during partition
except ConsistencyError:
    return "Service temporarily unavailable"  # Better than wrong data

AP Systems (Availability + Partition Tolerance)

Behavior during partition: Always respond, may return stale data

Examples:

When to choose:

Example:

# AP system: Always returns data, may be stale
user_profile = cache.get(user_id)  # Returns even if stale
if user_profile is None:
    user_profile = eventual_consistency_db.get(user_id)  # Best effort

Real-World Considerations

PACELC Extension

CAP is incomplete: Only describes behavior during partitions

PACELC adds:

If Partition (P):
    Choose between Availability (A) and Consistency (C)
Else (E):
    Choose between Latency (L) and Consistency (C)

Full framework:
- PA/EL: Prioritize availability and low latency (Cassandra)
- PA/EC: Prioritize availability, then consistency (DynamoDB)
- PC/EL: Prioritize consistency, then low latency (MongoDB)
- PC/EC: Prioritize consistency (traditional RDBMS)

Consistency Spectrum

Not binary:

Strong Consistency (CP)
├─ Linearizability
├─ Sequential Consistency
└─ Causal Consistency

Eventual Consistency (AP)
├─ Read Your Writes
├─ Monotonic Reads
└─ Eventual

System Examples

Example 1: Social Media Feed (AP)

class SocialMediaFeed:
    """AP system: Always available, eventually consistent"""

    def post_update(self, user_id, content):
        # Write to multiple regions asynchronously
        for region in self.regions:
            region.write_async(user_id, content)  # Don't wait
        return {"status": "posted"}  # Immediate response

    def get_feed(self, user_id):
        # Read from nearest region
        region = self.get_nearest_region()
        posts = region.read(user_id)  # May be slightly stale
        return posts  # Always returns something

Trade-off: User might not see their post immediately on different device (eventual consistency), but system is always available.

Example 2: Bank Account (CP)

class BankAccount:
    """CP system: Strongly consistent, may be unavailable"""

    def transfer(self, from_account, to_account, amount):
        # Distributed transaction with 2PC
        transaction = self.begin_transaction()
        try:
            # Both operations must succeed or both fail
            transaction.debit(from_account, amount)
            transaction.credit(to_account, amount)
            transaction.commit()  # Blocks until confirmed on all nodes
            return {"status": "success"}
        except PartitionError:
            transaction.rollback()
            raise ServiceUnavailableError("Cannot guarantee consistency")

    def get_balance(self, account_id):
        # Read from majority quorum
        return self.read_with_quorum(account_id)  # Blocks if partition

Trade-off: System may become unavailable during network issues, but data is always correct.

Example 3: Hybrid Approach

class HybridSystem:
    """Different consistency for different data"""

    def write_user_profile(self, user_id, profile):
        # AP: Profile updates can be eventually consistent
        self.ap_store.write_async(user_id, profile)
        return {"status": "updated"}

    def charge_payment(self, user_id, amount):
        # CP: Payments must be strongly consistent
        try:
            result = self.cp_store.transaction(user_id, amount)
            return {"status": "charged"}
        except PartitionError:
            return {"status": "unavailable", "retry": True}

Database Classification

CP Databases

MongoDB (w=majority):
- Consistent reads from primary
- Blocks during partition
- Use for: Transactions, inventory

Etcd/Consul:
- Raft consensus
- Strong consistency
- Use for: Configuration, service discovery

HBase:
- Single master, consistent regions
- May be unavailable during failures
- Use for: Time-series, analytics requiring consistency

AP Databases

Cassandra:
- Tunable consistency (default AP)
- Eventually consistent
- Use for: Time-series, logging, IoT

DynamoDB:
- Eventually consistent reads (default)
- Strongly consistent reads (optional, higher latency)
- Use for: User profiles, session data

Riak:
- Eventual consistency
- High availability
- Use for: Content storage, caching

Tunable Consistency

Cassandra Example

from cassandra.cluster import Cluster
from cassandra.query import SimpleStatement
from cassandra import ConsistencyLevel

cluster = Cluster(['node1', 'node2', 'node3'])
session = cluster.connect('my_keyspace')

# AP: Eventually consistent (fast)
statement = SimpleStatement(
    "SELECT * FROM users WHERE user_id = %s",
    consistency_level=ConsistencyLevel.ONE  # Read from any single node
)

# CP: Strongly consistent (slower)
statement = SimpleStatement(
    "SELECT * FROM users WHERE user_id = %s",
    consistency_level=ConsistencyLevel.QUORUM  # Read from majority
)

# Per-query choice based on use case

Decision Framework

Choose CP When:

✅ Correctness is critical (financial, inventory)
✅ Can tolerate downtime
✅ Data conflicts must be prevented
✅ Transactions required
✅ Regulated industry (banking, healthcare)

Choose AP When:

✅ Availability is critical (user-facing)
✅ Can tolerate stale reads
✅ Conflicts can be resolved later
✅ High write throughput needed
✅ Global distribution required

Common Misconceptions

Misconception 1: "CAP means pick 2 of 3"

Wrong: Network partitions happen, so it's really "CP or AP"

Correct: Choose consistency or availability during partitions

Misconception 2: "NoSQL = AP, SQL = CP"

Wrong: Many NoSQL databases offer tunable consistency

Examples:

Misconception 3: "AP means no consistency"

Wrong: AP means eventual consistency, not no consistency

Clarification: Updates propagate to all nodes, just not immediately

Testing CAP Properties

Partition Simulation

import subprocess
import time

def simulate_partition(node_ips):
    """Block network traffic between nodes"""
    for ip in node_ips:
        subprocess.run([
            'iptables', '-A', 'INPUT', '-s', ip, '-j', 'DROP'
        ])

def test_ap_system():
    """Test that system remains available during partition"""
    simulate_partition(['192.168.1.2'])

    # Should still respond (maybe stale)
    response = api.get('/data')
    assert response.status_code == 200  # Available

def test_cp_system():
    """Test that system maintains consistency during partition"""
    simulate_partition(['192.168.1.2'])

    # Should refuse to serve potentially inconsistent data
    response = api.get('/data')
    assert response.status_code in [503, 500]  # Unavailable but consistent

Related Skills

Last Updated: 2025-10-27