CAP and PACELC Applied

TL;DR. During a network partition, you sacrifice either consistency (AP) or availability (CP). That choice is rare. The choice you face on every single request is PACELC’s else-clause: pay coordination latency for strong consistency (EC), or accept stale reads for speed (EL). Default to PA/EL for user-facing traffic (carts, feeds, sessions) and PC/EC for coordination state (money, locks, inventory). Most production systems mix both per-operation, not per-cluster.

Learning Objectives

• Compare CP and AP behaviour under partition with concrete read/write semantics.
• Identify the PACELC category (PC/EC, PA/EL, PC/EL) of a given database configuration.
• Justify per-operation consistency levels instead of whole-system CP/AP labels.
• Evaluate when harvest/yield degradation is preferable to a binary CP or AP choice.

The Core Trade-off

CAP and PACELC introduced the theorem. This page is the decision guide.

Gilbert and Lynch proved that during a network partition, a replicated register cannot provide both linearizability and availability¹. Partitions are not a design choice because real networks partition². The live question is: when the split happens, do you refuse requests on the minority side (CP) or serve potentially stale data on both sides (AP)?

But partitions contribute less than 10 percent of outages on Google’s private fabric³. The daily tension is PACELC’s else-clause: synchronous replication (stronger consistency, higher tail latency) versus asynchronous replication (lower latency, weaker consistency)⁴. Every write to a replicated store pays this tax continuously, not just when a switch fails.

flowchart TD
    Start[Request arrives] --> P{Network partitioned?}
    P -->|Yes| PC{Sacrifice availability or consistency?}
    P -->|No| EC{Sacrifice latency or consistency?}
    PC -->|CP| CP_OUT[Reject writes on minority side]
    PC -->|AP| AP_OUT[Accept writes on any replica]
    EC -->|EC| COORD[Quorum coordination before ack]
    EC -->|EL| FAST[Async replication, local ack]
    CP_OUT --> EX1["Spanner, CockroachDB, etcd"]
    COORD --> EX1
    AP_OUT --> EX2["Cassandra, DynamoDB, Riak"]
    FAST --> EX2

Side-by-Side Comparison

The table misleads on one dimension: “AP systems are always available” is false. Cassandra at QUORUM fails reads when quorum is unreachable. DynamoDB strongly-consistent reads fail during AZ isolation. The CP/AP label describes default behaviour, not a guarantee. Per-operation consistency levels move a single system across cells¹¹¹².

The dominant dimension in practice is not partition behaviour but normal-operation latency. Spanner’s TrueTime commit-wait adds roughly 7 ms to every write¹³. Cassandra at ONE typically acks in low single-digit milliseconds locally. For a feed service doing 500K writes/sec, that difference is the entire capacity plan.

When to Pick CP

• Money and inventory. Double-spend, overselling the last seat, duplicate charge. A refused request is cheaper than a wrong answer. Banking ledgers, payment processors, seat reservations.
• Distributed coordination. Leader election, distributed locks, unique ID allocation. Consensus Protocols covers why these require majority agreement.
• Compliance and audit. Regulatory systems where “the record at time T” must be authoritative. Healthcare records, financial reporting, legal document stores.
• Small metadata stores. etcd (2 GiB default backend quota, 8 GiB suggested maximum¹⁴), ZooKeeper, Consul. The data is small, the coordination cost is affordable, and a wrong answer cascades to the entire cluster.

When to Pick AP

• User-facing traffic that tolerates staleness. Shopping carts, social feeds, like counts, view counters. Being off by seconds is invisible; adding 80 ms per write is not.
• Multi-region with frequent or long partitions. Cross-region links fail for minutes. PA/EL systems (DynamoDB Global Tables, Cassandra multi-DC) keep serving both sides and reconcile later¹⁵¹⁶.
• Offline-first and IoT. Mobile apps and edge devices are always partitioned by definition. The network is the exception, not the norm.
• Write-heavy workloads at scale. Leaderless architectures accept writes on any node. No single-leader bottleneck, no cross-region coordination on the write path.

The Hybrid Path

Most production systems do not pick one cell. They mix per-operation:

• DynamoDB: eventually-consistent reads by default (PA/EL), opt-in ConsistentRead=true at 2x RCU cost (PC/EC for that read)⁹.
• Cassandra: 11 consistency levels per query. ONE is PA/EL. QUORUM with RF=3 is effectively PC/EC within a DC. SERIAL uses Paxos for linearizable CAS¹².
• The metadata/data split: coordination state (who owns what partition, cluster membership) in etcd or ZooKeeper (PC/EC). User data in Cassandra or DynamoDB (PA/EL). This is the industry norm⁴.

flowchart LR
    subgraph PC_EC["PC/EC layer"]
        ETCD["etcd / ZooKeeper"]
    end
    subgraph PA_EL["PA/EL layer"]
        CASS["Cassandra / DynamoDB"]
    end
    APP["Application"] -->|"metadata, locks, config"| ETCD
    APP -->|"user data, sessions, feeds"| CASS
    ETCD -.->|"partition map"| CASS

Harvest/yield offers a third path. Fox and Brewer proposed that instead of binary CP or AP, a system can degrade harvest (return results from 90% of shards) to preserve yield (still respond within SLA)¹⁷. Google web search does exactly this: a shard failure reduces result quality, not availability.

Real-World Examples

Google Spanner (PC/EC). Availability target exceeds five 9s³. Spanner is technically CP: during partition, minority-side writes fail. But Google engineered the network (private fiber, redundant paths) and clock hardware (GPS + atomic) to make partitions rare enough that users treat Spanner as always-available. TrueTime’s commit-wait window is typically under 7 ms¹³. The lesson: if you can afford to make partitions rare, CP’s availability cost becomes negligible.

Redis Sentinel (the cautionary tale). Kingsbury’s 2013 Jepsen test partitioned a Redis Sentinel cluster for 42 seconds. Result: 1,126 of 1,998 acknowledged writes lost, a 56% loss rate¹⁸. The failure mode: async data-path replication plus quorum-based failover produced split-brain. The old primary kept acking writes that were discarded when Sentinel promoted a new primary on heal. This is what happens when you want “available and consistent” and engineer neither.

flowchart LR
    subgraph Minority["Minority side"]
        N1["Redis primary (old)"]
    end
    subgraph Majority["Majority side"]
        N5["Redis primary (new)"]
        S3["Sentinel"]
        S4["Sentinel"]
    end
    C1["Clients"] -->|"writes ack'd, LOST on heal"| N1
    C2["Clients"] -->|"writes ack'd, kept"| N5
    S3 -.->|"promotes"| N5

Cassandra at QUORUM. Jepsen found 28% acknowledged-write loss with QUORUM reads and writes on a partitioned cluster due to LWW conflict resolution (exacerbated by millisecond-resolution timestamp generation)⁷. The fix is not “use ALL”; it is understanding that LWW conflict resolution silently discards data even with overlapping quorums.

Common Mistakes

Decision Checklist

• How often does your network actually partition? (Measure. Single-region AZ failures are the usual pain.)
• During partition, is “temporarily refusing writes” acceptable UX, or an outage-triggering incident?
• In normal operation, are you paying coordination latency for consistency you do not need?
• If two replicas accept conflicting writes, what resolves the conflict: CRDT, LWW, or a human?
• Are you mixing CP and AP per-operation? (Most real systems do. Name which data is which.)
• Have you tested partition behaviour, or only assumed it from the vendor’s marketing?

Key Takeaways

• CAP is a partition-time choice (C or A). PACELC adds the daily choice (L or C). The daily choice dominates.
• No system is “CP” or “AP” as a whole. Per-operation consistency levels are the production reality¹¹.
• PA/EL is the default for user-facing traffic. PC/EC is the default for coordination state. Mix both.
• Async replication plus automatic failover equals silent data loss during partition. Redis Sentinel lost 56% of writes in 42 seconds¹⁸.
• If you cannot state what a read returns during partition for every operation, you have not designed your system.

Further Reading

• Brewer, “CAP Twelve Years Later” - The author’s own correction of the “2 of 3” myth; the definitive framing of CAP as a per-operation choice.
• Abadi, “Consistency Tradeoffs in Modern Distributed Database System Design” - The PACELC paper; explains why latency matters more than partition behaviour day-to-day.
• Kleppmann, “Please stop calling databases CP or AP” - The critique that explains why single-letter labels hide layered reality.
• Jepsen analyses - What databases actually do versus marketing claims; start with Redis and Cassandra.
• Fox and Brewer, “Harvest, Yield, and Scalable Tolerant Systems” - Conceptual precursor to tunable consistency; reframes CAP’s binary into a design knob.
• Brewer, “Inside Cloud Spanner and the CAP Theorem” - The “effectively CA” argument and its engineering limits.

Flashcards

References