CAP, Consistency and Reliability

7 pages · ~5 min✓ Reviewed

System DesignPage 1

CAP and PACELC Mental Model

1. CAP: CP vs AP

Under a partition, pick Consistency (reads see the latest write) or Availability (every live node answers)
Partitions are unavoidable, so the real choice is CP vs AP
Partition heals: AP sides reconcile

	CP	AP
Examples	etcd, ZooKeeper, HBase	Cassandra, DynamoDB default, Riak
Minority side	Rejects requests or errors	Keeps serving
Both sides	Only majority is correct	Diverge, then reconcile
Trade	Correct, may refuse	Always answers, may be stale

2. PACELC

Healthy systems still trade speed for freshness
Fresher reads cost cross-node coordination

3. Mistakes

'Pick 2 of 3' is wrong
CA is not a real option for a distributed system
CAP says nothing about behavior with no partition

Remember

CP = correct but may refuse. AP = always answers but may be stale.

System DesignPage 2

Strong vs Eventual Consistency

1. Strong vs eventual

	Strong (linearizable)	Eventual
After a write returns	every later read sees it	reads can be stale
Replicas	coordinate across nodes	converge if writes stop
Cost	higher latency	low latency

2. Middle models

Read-your-writes: you always see your own update
Monotonic reads: never jump back to older data
Causal: a reply never appears before its post
A sane user view without full linearizability

3. Convergence tools

Last-write-wins: clock-dependent, can lose writes
Vector clocks: detect concurrent writes
CRDTs: merge automatically, no lost updates
Read repair: fix a stale replica during a read
Anti-entropy: background replica comparison and sync

4. Mistakes

Strong	Eventual
Balances	Feeds
Inventory	Likes
Uniqueness checks	Counters

Money and uniqueness

Eventual consistency for balances, inventory or uniqueness checks causes overspending and duplicates.

System DesignPage 3

Quorums: R, W and N

1. The Three Numbers

N = replica count
W = acks needed for a write
R = replicas consulted for a read
Strong read rule: R + W > N, so the read set overlaps the latest write set

2. Tuning with N=3

Setting	Reads	Writes	Failures
`W=2, R=2`	balanced	balanced	tolerates 1
`W=3, R=1`	fast	slowest, strongest durability	writes fail if any replica is down
`W=1, R=3`	slow	fast	reads need all 3

3. Majority Quorum

Majority = floor(N/2)+1
A cluster of 2f+1 nodes survives f failures
Use odd sizes: an even node adds cost, not tolerance

Nodes	Majority	Tolerates
3	2	1
5	3	2
6	4	still 2

4. Common Mistake

R+W>N alone is not linearizable

It breaks with sloppy quorums, hinted handoff or clock-based last-write-wins conflict resolution.

System DesignPage 4

Rate Limiting Algorithms

1. Purpose

Cap requests per client per time window
Protects a service from overload and abuse
Reject with HTTP 429 plus a Retry-After header

2. The Algorithms

Refillsteady rate
Bucketup to capacity
Requestspends 1 token
Empty?reject with 429

Algorithm	Bursts	Trade-off
Token bucket	up to bucket size	most common choice
Leaky bucket	none	queue drains at fixed rate, smooth output
Fixed window	2x at boundary	simplest counter
Sliding window log	exact	memory heavy
Sliding window counter	approximate	cheap

3. Shared Counters

Keep counters in a shared store like Redis
Use atomic INCR or a Lua script
Key by user, API key or IP

bash

INCR rl:user42:12345
EXPIRE rl:user42:12345 60

one key per client per window

Per-instance counters

Each app instance counts alone, so the real limit grows with the instance count. Always use a shared store.

System DesignPage 5

Circuit Breakers and Retries with Backoff

1. Circuit Breaker States

Closedcalls pass, failures counted
Openthreshold hit: fail fast, no calls
Half-Openafter timeout: few probes

Probe succeeds → Closed; probe fails → back to Open
Trip on failure-rate threshold over a rolling window
Tune: open duration, probe count
Fail fast with a fallback or cached response

2. Retry with Backoff

Wait base * 2^attempt: 100ms, 200ms, 400ms ... cap 10s
Always set a max attempt count
Full jitter = random(0, backoff): no synchronized retry waves

python

delay = min(cap, base * 2 ** attempt)
time.sleep(random.uniform(0, delay))

full jitter

3. Common Mistakes

Retrying non-idempotent calls without an idempotency key
Retrying 4xx errors
Stacking retries at every layer

Retry storm

3 layers x 3 tries = 27 calls on one failing request. Retry at one layer only.

System DesignPage 6

Availability Nines Cheat Sheet

1. Downtime per Nines

Availability	Per year	Per month
99%	3.65 days	-
99.9%	8.76 hours	≈ 43.8 min
99.99%	52.6 min	≈ 4.4 min
99.999%	5.26 min	-

2. Combining and Targets

Layout	Formula	Example
Serial	a1 × a2	two 99.9% → ≈ 99.8%
Parallel	1 - (1-a)^n	two 99.9% → 99.9999%

Each extra nine costs 10x more effort
SLO = internal target, error budget = 100% - SLO
SLA = contractual promise, looser than the SLO

3. Chapter Cheat Sheet

CP = correct but may refuse; AP = always answers, may be stale
R+W>N gives strong reads
Token bucket for bursts
Breaker: Closed → Open → Half-Open
Backoff = base*2^n plus jitter

Serial chains lose, parallel replicas gain

Every dependency in a chain multiplies availability down; redundancy lifts it.

System DesignPage 7

Check yourself

N=5, W=2, R=3. A write is acked by replicas A and B. Can a read still return the old value?

Yes: R+W = 5, which is not > 5.
The read can hit C, D, E, and none of them saw the write.
Fix: W=3, or R=4.

Three layers each try a call 3 times and the backend is down. How many calls hit the backend per user request?

27 (3 x 3 x 3), a retry storm.
Retry at one layer only, with backoff and jitter.

A breaker is Open and its timeout expires. The next probe fails. What state is it in now?

Open again.
Half-Open lets a few probes through: success closes it, any failure reopens it.