Advanced Distributed Systems #CAP #PACELC #consistency #system-design

CAP & PACELC

5 exercises — master CAP and PACELC trade-off vocabulary: CP vs AP systems, PACELC latency/consistency trade-off, Spanner external consistency, tunable consistency, and applying CAP analysis to payment system design.

0 / 5 completed

CAP & PACELC quick reference

CAP theorem — during partition, choose C (consistency: error rather than stale) or A (availability: respond even if stale). P is mandatory.
CP examples — etcd, ZooKeeper, RDBMS sync replicas, HBase, CockroachDB.
AP examples — Cassandra, DynamoDB (eventual), CouchDB, Riak.
PACELC — extends CAP: if Partition → A/C; Else (healthy) → Latency/Consistency trade-off.
PA/EL — available under partition, low latency when healthy (Cassandra, DynamoDB eventual).
PC/EC — consistent under partition, higher latency when healthy (Spanner, etcd).
Tunable consistency — per-operation consistency levels (Cassandra: ONE/QUORUM/ALL; DynamoDB: ConsistentRead).
Spanner — CP, external consistency via TrueTime; not a CAP refutation — sacrifices availability under partition.

1 / 5

A system design interviewer asks: "Explain the CAP theorem. Can a distributed system ever provide all three guarantees?"

CAP theorem (Brewer, 2000; formally proven by Gilbert & Lynch, 2002): pick C or A when P occurs — you cannot have all three during a partition.

The three properties:
• Consistency (C) — every read receives the most recent write or an error. (Note: CAP uses a specific definition — equivalent to linearizability, not just "no corruption")
• Availability (A) — every request to a non-failing node receives a non-error response (though it may be stale)
• Partition tolerance (P) — the system continues operating even when messages are lost or delayed between nodes

Why P is mandatory:
Any distributed system operating over a network will experience partitions. Network cables break, switches fail, BGP re-routes, clouds have outages. Choosing "not P" means your system stops when the first partition occurs — not viable for production systems.

The practical trade-off therefore is: during a partition, choose C or A:

Choice	Behaviour during partition	Examples
CP	Return error or wait rather than return stale data	etcd, ZooKeeper, Consul, HBase
AP	Return potentially stale data rather than error	Cassandra, CouchDB, Riak, DynamoDB (eventually consistent)

Important nuance:
• CAP says nothing about how often to sacrifice C or A — just that under partition you must choose
• Modern systems (Spanner, CockroachDB) are "effectively CA when the network is healthy" and CP when partitioned — the partition case matters
• CAP's "Availability" has a specific formal definition (every non-failing node responds) — differs from "99.99% uptime SLA"

Key vocabulary:
• CAP theorem — a distributed system can guarantee at most two of: Consistency, Availability, Partition-tolerance; during a partition, must choose C or A
• CP system — chooses consistency over availability during partition; returns errors rather than stale data
• AP system — chooses availability over consistency during partition; returns possibly-stale data rather than errors
• Linearizability — the consistency semantics CAP uses; every read sees the latest committed write

2 / 5

A senior engineer says: "CAP theorem is a useful concept but it's too blunt for real system design. I prefer using the PACELC model when making database tradeoff discussions."

What does PACELC add that CAP doesn't address?

PACELC framework (Abadi, 2012): If P (partition), choose A or C. Else (no partition), choose L (latency) or C (consistency).

PACELC notation:
$$ ext{System} = ext{P} ightarrow ext{A/C} ext{ + E} ightarrow ext{L/C}$$
A system is described by both halves: e.g., PA/EL (availability during partition, low latency otherwise) or PC/EC (consistency during partition, consistency otherwise).

Why the EL/EC trade-off matters:
• In a system without partitions, strong consistency still requires reads to confirm with the leader (or quorum) before responding
• That confirmation requires network round-trips → increased read latency
• Eventual consistency allows reads from any local replica → lower latency, but potentially stale
• 99.9% of operations happen in the "no partition" case — this trade-off dominates real performance

PACELC system classification:

Database	During partition	No partition	PACELC
DynamoDB (eventual)	Available	Low latency	PA/EL
Cassandra (default)	Available	Low latency	PA/EL
RDBMS (sync replication)	Consistent	Higher latency	PC/EC
Spanner / CockroachDB	Consistent	Higher latency	PC/EC
MongoDB (majority read)	Consistent	Higher latency	PC/EC

Tunable consistency (Cassandra example):
Cassandra allows per-query tuning: ONE, QUORUM, ALL for both reads and writes. At ONE, it's PA/EL; at ALL, it approaches PC/EC. This lets developers choose the trade-off per operation based on criticality.

Key vocabulary:
• PACELC — framework extending CAP: during Partition choose A/C; Else choose latency/consistency trade-off
• PA/EL — available during partition, low-latency when healthy; AP systems like Cassandra, DynamoDB (eventual)
• PC/EC — consistent during partition, higher-latency when healthy; CP systems like Spanner, etcd
• Tunable consistency — per-operation choice of consistency level; allows different trade-offs for different workloads in the same system

3 / 5

A team is debating database choice. They say: "For our financial ledger we need strong consistency. For our product catalogue we're fine with eventual consistency. Can we use the same database for both, or do we need different databases?"

Tunable consistency databases offer a practical middle ground — but the right choice depends on the consistency requirements, operational complexity tolerance, and latency budgets.

Cassandra tunable consistency example:

-- Financial transaction (strong consistency required)
INSERT INTO transactions (...) USING CONSISTENCY QUORUM;
SELECT balance FROM accounts WHERE id=? USING CONSISTENCY QUORUM;
-- N=3 replicas; W+R = QUORUM+QUORUM = 2+2 = 4 > 3 → overlapping quorums

-- Product catalogue (eventual consistency acceptable)
SELECT * FROM products WHERE category=? USING CONSISTENCY ONE;
-- Any replica can respond; may be slightly stale; maximum throughput

DynamoDB tunable consistency:
• Default (eventually consistent): GetItem without ConsistentRead=true → returns from a replica in ~ms, may be 1-2 seconds stale
• Strongly consistent: GetItem with ConsistentRead=true → always contacts the leader; up to 2x cost

When to use two separate databases:
• Operational complexity of tunable consistency and its testing requirements exceeds the benefit
• The financial ledger needs full ACID transaction semantics (multi-row atomicity, not just single-item consistency)
• Different teams own different services; each team picks the appropriate store for their data
• The catalogue needs full-text search (Elasticsearch) — a different capability requirement entirely

Practical recommendation for the scenario:
• Financial ledger: PostgreSQL or CockroachDB (full ACID, synchronous replication, serializable isolation)
• Product catalogue: DynamoDB or Cassandra (high read throughput, global replication, eventual consistency fine for read-heavy catalogue data)
• Accept two datastores: the consistency guarantees and performance profiles are fundamentally different

Key vocabulary:
• Tunable consistency — the ability to choose the consistency level per operation; lets different queries trade consistency for latency
• readConcern / writeConcern — MongoDB's per-operation consistency level parameters
• ConsistentRead — DynamoDB parameter forcing the read to go to the leader replica for linearizable consistency
• W+R>N quorum overlap — when write quorum + read quorum exceeds replica count, at least one replica seen by both; guarantees seeing the latest write

4 / 5

An architect argues: "The CAP theorem is outdated and misleading. Modern systems like Google Spanner achieve 'external consistency' — which is stronger than linearizability — while remaining available globally. Does that refute CAP?"

Spanner is a remarkable engineering achievement — but it is firmly CP and does not refute CAP. It trades availability (blocking during clock uncertainty) for consistency.

What Spanner's TrueTime does:
• GPS + atomic clocks in every Google data centre provide bounded clock uncertainty: True time = [earliest, latest] interval of width typically 1-6ms
• Before committing a transaction, Spanner waits (commit wait) until the transaction's timestamp is definitely in the past for all clocks — absorbs the uncertainty interval
• This ensures that any transaction reading after the commit wait will see the committed value — achieves external consistency (= strict serializability)

Why Spanner is still CP, not "CA":
• Under network partition: Spanner's Paxos groups require quorum; minority partition stops serving
• Under high clock uncertainty: commit waits are longer; latency increases but availability is preserved for writes
• Under data centre failure: Paxos group may not form quorum across DCs → writes block
• Spanner's "five 9s" availability is achieved by engineering (multi-DC Paxos, fast recovery) not by avoiding CAP trade-offs

The key insight from Spanner:
CAP's "Availability" means every non-failing node responds. Spanner is not "always available" in the CAP formal sense — it can block writes when partitioned or when clock synchronisation issues occur. What Spanner shows is that with extraordinary infrastructure, you can push the C-vs-A trade-off to extreme edge cases while appearing "both" in normal operation. That's not refuting CAP; it's making partitions so rare and recovery so fast that the trade-off is almost invisible in practice.

Key vocabulary:
• External consistency (Spanner) — if transaction T1 commits before T2 starts, then T2's timestamp is larger than T1's; equivalent to strict serializability
• TrueTime — Google's clock infrastructure providing bounded uncertainty intervals using GPS + atomic clocks
• Commit wait — Spanner's mechanism: delay commit acknowledgement until clock uncertainty interval passes, ensuring external consistency
• Clock uncertainty — the window of time within which a distributed system cannot determine exact event ordering due to clock skew

5 / 5

In a system design interview: "You're designing a global payment processing system. Walk me through your CAP/PACELC trade-off analysis and justify your database choice."

The right CAP/PACELC decision always depends on the cost of each trade-off. For payments, the cost of an availability outage (user retries) is lower than the cost of a consistency violation (double charge, incorrect balance).

Payment system CAP analysis:

Scenario	CP result	AP result	Impact
Network partition during checkout	Returns error to user	Proceeds with stale data	CP: user retries; AP: potential double charge
Leader election during write	Write blocks until new leader	Both replicas accept writes	CP: 200-500ms delay; AP: split-brain
Replica lag on balance read	Reads from leader only	May read stale balance	CP: higher latency; AP: incorrect balance shown

PACELC for payments (Else/Normal case):
• EC (Else: Consistency) chosen: read from leader, accept latency
• Typical consequence: 5-20ms additional read latency vs replica read
• Worth it for: regulatory compliance (PCI-DSS requires accurate balance representation), fraud prevention (stale balance enables overdraft attacks), customer trust

Why CRDTs don't work for payment balances:
• A balance is NOT a CRDT-friendly data structure: debit(-50) + concurrent debit(-50) from balance 60 = allow both? No — one must fail
• CRDTs require commutative, associative merge semantics with no domain constraints. "Balance must remain ≥ 0" is a constraint that CRDTs cannot enforce across concurrent writes without coordination

Recommended databases for payments:
• PostgreSQL with synchronous streaming replication — proven, ACID, synchronous replica acknowledgement
• CockroachDB — distributed SQL, serializable isolation, geo-distributed with automatic failover
• Google Spanner — external consistency, global, managed
• Avoid: Cassandra (AP), DynamoDB eventual consistency reads, Redis without strong persistence

Key vocabulary:
• CAP trade-off analysis — systematic evaluation of consistency vs availability per failure scenario, weighted by business impact
• PACELC trade-off — extending the analysis to latency vs consistency in healthy-system operation
• PCI-DSS — Payment Card Industry Data Security Standard; regulatory framework requiring accurate transaction records
• Overdraft attack — exploiting stale balance reads to authorize transactions the account cannot cover