System Design Data

CAP Theorem

Picture an Uber rider app and a driver app talking to databases in two regions when the cross-region link blips. One side still accepts a seat reservation; the other still shows the seat free. Which story should the product trust?

The is the rule for exactly that moment. When replicas (copies of the same data on different machines) cannot coordinate, a distributed store must either protect the latest correct value or keep answering and repair later. Real systems make that choice per operation, not once for the whole product.

When the network splits

The cross-region link drops, so replicas cannot agree on the latest value in time.

Ask the operation

Does this read or write truly need the absolute latest state to be safe?

Money and inventory paths wait, error, or require a quorum instead of forking.

Feeds and carts answer now on the reachable side, then merge the histories later.

What actually happens when replicas cannot talk

Consider two reachable replicas that cannot communicate. A client writes value 1 to the first and receives success, then another client reads the second. To preserve linearizability, that read must reflect the completed write or wait/refuse until it can establish the correct ordering. To remain available in the CAP model, the second replica must complete an allowed response despite not learning the new value. The network prevents the system from satisfying both guarantees for this execution.

The Uber story above is the whole theorem in miniature. CAP is not "pick two forever." Gilbert and Lynch (the researchers who formalized the theorem) show that the trade-off bites during a partition: a separates the replicas, and a request lands on one side that cannot safely coordinate with the other. Under that failure the system must either answer anyway, risking stale or conflicting data, or refuse and wait so that a single correct history survives.

CAP consistency refers to linearizability: completed operations behave as if they took effect one at a time in an order compatible with real time. Internal replicas may temporarily differ, but an operation cannot expose an observation that violates that history. This is distinct from ACID consistency, which concerns preserving declared data invariants and valid state transitions. Name the observable guarantee rather than saying all physical copies are identical at every instant.

means that during a partition every non-failing node still returns a non-error response, with no guarantee that it contains the most recent write. A shopping cart that always accepts items and merges later, a social feed that shows slightly stale posts rather than an error, and DNS (the internet's name lookup service) answering from cache all behave this way. It is not an uptime SLA (service level agreement) figure such as 99.99%: a cluster can meet its uptime target while still refusing writes under partition.

means the system keeps operating when messages between nodes are lost or delayed. In any multi-node system partitions happen: switch failures, cable cuts, cloud availability-zone (AZ, an isolated datacenter inside a region) outages, and cross-datacenter link failures that occur monthly at scale. So P is assumed rather than picked, and the real choice appears under partition, usually differing from one operation to the next.

Two more terms carry the rest of the page. A is the majority of replicas that must agree before a read or write counts, and is the promise that replicas converge once writes stop. adds the half CAP leaves out: even with a healthy network, stronger consistency costs coordination latency. The next section turns the three letters into a per-operation decision.

How to choose CP vs AP

With the vocabulary settled, three questions decide which side of the split an operation should favour.

1. What breaks if the answer is stale? Overselling seats or double-charging is a problem. A slightly old like count is usually an problem.

2. What happens on conflict? AP paths need a merge rule, last-write-wins (the newest timestamp silently overwrites the rest), or a compensation step. CP paths need retries, errors, or waiting for a .

3. Is the network healthy right now? If it is, the partition question never arises, yet strong reads still cost latency; the section below names that steady-state trade.

Simple rule of thumb

Decide per operation, not per product. Put anything whose stale answer costs money or trust on a CP-shaped path, and let everything else stay AP-friendly with a repair step.

In simple terms: when replicas disagree, either pause for truth or answer fast and clean up, and pick based on the cost of being wrong.

Correctness invariant

What must never become false

The rule of thumb has a hard edge. Under a network partition, a money or inventory operation that claims CP must not silently accept conflicting writes on both sides of the split; it waits, errors, or requires quorum. An AP path may answer, but then a named merge or repair policy must own the divergence.

The partition decision in a picture

The same three questions, drawn as a flow: follow one request from the moment the link drops to the outcome users see.

Network partition separates replicas

Request hits one side

Must this operation see latest state?

Yes: money, inventory, lock

Prefer CP: wait, error, or require quorum

Higher latency or temporary unavailability

No: feed, cart, count

Prefer AP: accept locally

Reconcile later with merge, repair, or conflict policy

Stale reads or divergent writes are product-visible trade-offs

Numbers to know: nines vs partition behavior

CAP availability is a formal property that every request to a non-failing node eventually completes with a valid response; it is not a percentage uptime target or a bounded latency promise. Operational availability usually counts successful requests within a time window and often a deadline. A system can have excellent annual availability while deliberately rejecting some operations during a partition to preserve consistency.

The flow above says "wait" or "answer"; these rows attach numbers to each outcome and separate CAP from the uptime figures interviewers often mix in.

Claim	Math / scenario	What it does not mean
99.99% uptime	~52 min downtime / year budgeted	Not CAP A: nodes may still refuse writes under partition
CP inventory, 3-node quorum	Majority lost → writes pause; ~1 AZ cut can make that shard unavailable	"Unavailable" here is correctness-preserving, not "bad SRE" (site reliability engineering)
AP cart, two regions split 30 min	Both sides accept adds; merge may need conflict UI for ~0.1–1% of carts	Not free consistency. You bought answers with repair cost
Cross-region strong read	+50–150 ms coordination vs local replica read	PACELC latency tax even when the network is healthy

Failure timeline: seat hold across a partition

Here is the hero's Uber scenario step by step, showing how the AP cart row above becomes an oversold seat and how a path with a avoids it.

T0  Rider app (Region A) and driver app (Region B) share seat inventory replicas
T1  Cross-region link partitions; both sides still accept local writes
T2  A holds seat S1; B shows S1 free and also holds S1 (AP-shaped path)
T3  Partition heals; two held owners for one seat: oversell / trust failure
T4  CP path instead: B cannot get quorum → error/wait; only one hold survives
Outcome  Partition-time C vs A choice decides whether money/inventory can fork

Notice that both regions were "up" (their uptime SLA looked fine) while CAP consistency was already broken; that is the first row of the table in action.

CP vs AP in practice

The timeline used an abstract "inventory store"; real databases sit on a spectrum, and each exposes the choice through different knobs.

Consistency + partition tolerance

Under split-brain risk (two sides each believing they hold the truth), a store prefers errors or waiting over serving contradictory writes. Money, inventory, and single-primary designs usually land here, and most rely on a or an elected leader.

System	How quorum / leader shows up	How to say it
Global SQL (Structured Query Language)	Consensus groups (a majority of nodes agrees on each write) + bounded clock uncertainty; strong reads cost latency.	"Globally ordered commits, still unavailable if a quorum partition loses majority."
Coordination store	Consensus; writes need majority; reads often linearizable via leader.	"Coordination store: correctness beats answering during a minority partition."
Single-writer region store	Single writer per region; strong row consistency.	"Region unavailable ⇒ that shard stops, not AP on the hot path."
Single-primary document store	Single-primary replica set; elections pause writes briefly.	"Primary loss ⇒ brief write unavailability rather than dual writers."

Availability + partition tolerance

The mirror image: an store keeps accepting traffic during partitions and reconciles divergent histories afterward. Carts, feeds, and DNS-like lookups fit, and each row below names the tuning that trades staleness for speed.

System	What stays available	Trade-off / tuning
Leaderless wide-column store	Replica writes without a single global leader for every key.	Tunable `R`/`W`/`N` (replicas that must answer a read, a write, and the total copies): local quorum vs one-replica reads shifts latency vs staleness.
Managed key-value table	Partition accepts reads/writes inside its scope; regional tables stay up.	Default reads eventually consistent; strongly consistent reads add coordination and usually higher latency than default reads.
Multi-master document store	Multi-master friendly replication with revision metadata.	Conflicts surface to apps or merge functions, not hidden silent CP.
DNS	Always returns something cacheable.	TTL (time to live, the cache expiry) + propagation delay = textbook eventual consistency.

PACELC: beyond CAP

The practice tables above describe partition time only. (if Partition, Availability or Consistency; Else, Latency or Consistency) covers the rest of the year: even when the network is fine, you trade latency against consistency on the steady-state path.

Read the letters as two pairs: the first pair is the CAP choice under partition, the second is the everyday choice when healthy.

PA / EL: availability under partition, low latency when healthy; typical of wide-column AP stores.
PC / EC: consistency in both regimes, as in globally consistent SQL and NewSQL (distributed SQL) designs.
PA / EC: mixed defaults, such as strong primary reads with replica lag exposed elsewhere.

Database	CAP sketch	PACELC bucket	Default behavior & knobs
Wide-column AP store	AP	PA / EL	Fast paths via one-replica reads; tighten to local quorum when money-grade reads matter.
Managed key-value table	AP	PA / EL	Eventually consistent reads by default; request a stronger read when you need linearizable-style reads for that call.
Global SQL	CP	PC / EC	Strong default; stale reads only when you explicitly choose cheaper snapshots / bounded staleness (reads allowed to lag by a fixed limit).
Single-primary document store	CP	PA / EC	Writes route to primary; secondaries can serve stale reads unless you request majority-style read concern / primary read preference.
Consensus SQL	CP	PC / EC	Serializable default in-region (transactions behave as if run one at a time); follower reads (served by a non-leader replica) and stale snapshots expose latency/consistency sliders.

PACELC letters describe tendencies: vendor defaults plus your chosen isolation / consistency APIs decide what interviewers should hear.

Tunable consistency and consistency models

A replica-count setting changes how many acknowledgments or responses an operation waits for; it does not alone define the full consistency model. Membership changes, version ordering, concurrent writes, and read repair also matter. A majority-based consensus group can let its majority partition continue while its minority refuses operations, preserving one history. Calling the entire product “CP” or “AP” hides these per-operation and per-failure details.

PACELC says consistency costs latency even on a healthy network. This section shows the dials that let you pay that cost only on the operations that need it, and the named guarantees each dial position buys.

Quick mental model

Stronger means more replicas must coordinate, so reads and writes slow down and fail more readily.
Weaker counts fewer votes, so reads are faster and more forgiving of unreachable nodes.
You then design around stale or reordered views with UI hints, retries, and idempotency (operations safe to repeat).
Real apps mix strict paths (payments, inventory) with relaxed paths (feeds, counts) rather than one setting forever.

Where the knobs live (by database)

Each database family exposes the dial differently, so name one concrete knob per system below, not just "it is tunable."

Leaderless store (you choose R, W, N)

N = how many replicas hold the row. R / W = how many must respond before a read or write returns. Bigger R or W → stricter; smaller → quicker but easier to read slightly behind writes.

Setting	Beginner-friendly meaning
LOCAL_ONE	Ask one replica in your datacenter: fastest; most risk of lag vs other copies.
LOCAL_QUORUM	Majority inside the datacenter: balanced default for many transactional-style reads.
QUORUM / ALL	Broader agreement across replicas: stronger; slower and fails more easily if regions or nodes are down.

Managed key-value table (mostly read settings)

You do not tune R/W/N manually. You pick how each read behaves and optionally use transactions when several items must move together.

Default readEventually consistent: cheap and fast; right after a write, another reader might still see the old value briefly.
ConsistentRead(strong for that read)The database checks enough replicas so this read reflects successful writes; use when you must read your own update immediately, at higher latency or capacity cost.
TransactionsCondition checks and multi-item updates so related rows stay consistent (e.g. debit + credit).

Document and SQL primaries

One machine usually accepts writes (the primary). "Consistency" for reads often means which copy you read and whether the database waits for replication before answering.

Read from primaryFreshest data; all read load hits the writer: fine until the primary is hot.
Read from secondariesSpreads load; data can lag seconds behind: good for dashboards, bad for "did my payment land?"
readConcern majorityMajority-style reads return data acknowledged by most replicas: a middle ground between primary-only and totally stale secondaries.

Consistency models, from strictest to most relaxed

These guarantees are not all points on one speed dial. Linearizability orders individual operations consistently with real time. Serializability makes committed transactions equivalent to some serial execution, without necessarily preserving real-time order. Read-your-writes and monotonic reads concern a session’s observations; causal consistency preserves cause-and-effect dependencies. Name the guarantee the user flow needs rather than assuming one vague “strong” setting covers them all.

The knobs above set a position; these are the named promises each position buys. Think of it as a ladder you climb down for speed: top steps enforce global ordering; lower steps only promise "good enough" behavior for many apps. Production systems often use different rungs for different APIs.

Top: stronger guarantees, usually higher cost·Bottom: weaker guarantees, usually easier to scale fast

Linearizability

Strongest

Behaves like a single machine: every read/write lines up with real time, no weird overlaps.

Formal version: each operation appears instantaneous: globally ordered like one correct sequential machine.

Used where correctness dominates (distributed locks, some financial paths). Hard globally because clocks and consensus add coordination.

Example: account balance must never “jump backward” in a way real banks could not explain.

Sequential consistency

Strong global order

Everyone agrees on one story for how operations happened, in order, but not pinned to wall-clock instants like linearizability.

All processes see the same total order, and each client’s operations appear in the order they issued them.

Still strong for reasoning about bugs; slightly weaker than linearizability because timing vs real-world clocks is less strict.

Example: a shared log where order matters more than “exactly when” each byte arrived.

Causal consistency

Happens-before

If your edit replies to someone else’s message, nobody sees your reply before that message. Unrelated stuff can still reorder.

If operation B causally depends on A, every observer orders A before B; concurrent ops may commute.

Sweet spot for social feeds and collaborative docs: cheaper than linearizable everywhere while preserving human-visible cause and effect.

Example: comments stay under the correct post even if like counts are a bit fuzzy.

Read-your-writes

Session

After you save something, your next refresh shows it, even if friends still see the old version for a moment.

After you write X, your subsequent reads in that session observe X (other sessions may lag).

Often sticky sessions or routing you back to the replica that took your write, which fixes “I posted but it vanished.”

Example: profile bio update visible to you immediately; CDN edge might update seconds later.

Monotonic reads

No time travel

Once you have seen a newer version, your session will not bounce back to an older one.

If you have observed version v, later reads in the session never return a version older than v.

Stops confusing UX (“refresh made my inbox smaller”). Others may still be ahead or behind you.

Example: infinite scroll never shows rows that disappeared compared to what you already loaded.

Eventual consistency

Weakest

If writes stop, all copies eventually match, but reads can be arbitrarily stale until then.

Replicas converge when idle; no guaranteed freshness bound unless you add timestamps or SLAs.

Common for caches, edge/CDN, and default eventually consistent reads; monitor replication lag and handle conflicts explicitly.

Example: video view counts or follower totals where being off by a little is acceptable.

Real-world per-operation CAP

An available cart merge still needs a defined meaning. If one device removes an item while another adds it during a partition, the system must choose a documented merge rule and show the reconciled result. “Repair later” cannot recover business information that the data model never recorded. For a scarce resource such as the last seat, conflicting confirmations may be unacceptable, so the booking path needs coordination even if browsing remains available.

With the knobs and models in hand, here is what per-operation choice looks like inside two familiar products, followed by the partition scenarios that come up most in interviews.

Banking-style paths

Operation	Bias	Why
Balance / auth'd debit	CP	Stale balance risks real money loss.
Transfer ledger commit	CP	Serializable (as if one at a time) / linearizable expectations across accounts.
Monthly PDF statement list	AP-friendly	Seconds of lag acceptable for read-mostly history.

Social / feed-style paths

Surface	Bias	Why
Public like counter	AP	Approximate counts are fine; absorb spikes.
Home timeline	AP + RYW (read-your-writes)	Small staleness OK; author should see their own post.
DM thread	Stronger	Ordering / delivery guarantees: often causal+ (causal order with converging replicas) or per-thread linearizable reads.

Scenario	Stale/conflict cost	Likely choice	Repair or routing
Inventory decrement during partition	Oversell loses trust or money	CP for decrement	Require quorum or primary path; show temporary error if needed
Feed read during partition	User may miss latest posts briefly	AP-friendly	Serve local replica, merge when connectivity returns
Cart update from two devices	Duplicate or missing item	AP with conflict policy	Merge item sets, reject impossible quantities, show correction
Permission change while replicas lag	Security decision uses old access	CP or primary route	Route authorization reads to fresh source until lag clears

Global SQL and bounded clocks

The banking table above wants globally ordered commits; global SQL systems are the family that delivers them, and interviewers like to ask whether they somehow escape CAP.

Some global SQL systems target external consistency (a globally meaningful commit order) using synchronized clocks plus consensus groups (a majority-agreement protocol) per shard. The rows below show where the clock enters.

Clock interval API	Interval `[earliest, latest]` instead of one timestamp: typically sub-millisecond class uncertainty in healthy regions (marketing numbers drift; concept matters).
Commit wait	Wait out clock uncertainty before acknowledging commits so global observers agree on order.
Reads	Cheap stale reads vs explicitly stronger reads: latency moves with the guarantee you purchase per query.
Partitions	Lose a consensus majority ⇒ writes pause for that group: classic CP trade-off.

<7ms

often-cited uncertainty bound

99.999%

example SLA class

Global

multi-region deployments

Money-grade

strict workload class

Try it: simulate a partition under CP vs AP

Gilbert and Lynch CAP is about behavior during a network partition, not a permanent label on a database logo. Toggle the split, pick a policy, then write and read from different nodes.

Leader

reachable

v42

Follower A

reachable

v42

Follower B

reachable

v42

Partition active: No
Policy: CP
Values disagree: No

Healthy network: all nodes agree on v42. Start a partition to see whether writes wait or diverge.

CP waits or errors. Money-grade inventory often belongs here, paired with retries and idempotent operation ids.

AP keeps answering. Feeds and like counters accept temporary divergence and repair later with merge rules clients understand.

Choosing and explaining CAP nuance

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

CAP is about behavior during a network partition (Gilbert & Lynch), not a permanent pick-two label.

Partition tolerance is assumed once the system spans nodes; the real question is whether this operation answers or waits under partition.

Use PACELC to mention that healthy networks still trade latency against consistency.

When it belongs

The interviewer asks whether a database is CP or AP.

The design has multi-region writes, leader failover, caches, read replicas, or leaderless storage.

Different operations have different correctness value, such as inventory versus like counters.

How it fails

Treating CAP consistency as the same thing as ACID consistency.

Calling a system available because it has good uptime, while CAP availability means non-failing nodes answer during partition.

Ignoring conflict resolution for AP paths or retry behavior for CP paths.

Trade-offs to weigh

CP preserves a single correct history by waiting or erroring; AP preserves responses by accepting possible divergence.

Stronger reads usually add coordination latency even when the network is healthy.

Per-operation decisions let money paths be strict while feeds, counters, and notifications stay relaxed.

Common misunderstandings

Do not say “pick any two”; partitions are the condition that forces the choice.

Do not label the whole product CP or AP if individual APIs differ.

Do not promise strong consistency everywhere without explaining latency, quorum, and failure behavior.

How to explain the consistency trade-off

The interview block above lists what to say; this card gives you the order to say it in, starting with the questions that surface the right and paths.

Ask first

Which operations lose money or user trust if they act on a stale answer?
How many seconds of stale reads can the product tolerate before users notice?
Is the deployment single-region, multi-AZ, or active-active multi-region, since distance makes partitions likelier?
On conflict, does the system reject, merge, compensate, or let the last write win?

Answer shape

Name the critical CP path and the relaxed AP path separately, with one example each.
Mention so the interviewer hears that healthy networks still trade latency for consistency.
Mention the concrete knob: primary reads, quorum reads, strong read mode, or majority read concern.
State what you will monitor: replication lag, conflict count, stale-read complaints, quorum failures.

Strong answer: "Checkout inventory needs quorum or primary reads; likes and recommendations can be eventually consistent with repair, because availability matters more than exact freshness."

CAP answer template: (1) identify the operation, (2) state the failure (a partition), (3) choose wait/error vs accept/repair, (4) name monitoring and repair. Consistency budget: stale window in seconds, max lost writes, conflict policy, user trust impact.

Wrap-up

You have seen the definitions, the decision, the numbers, and the knobs. Here is the one-paragraph version to remember, then exercises to test it and the primary sources behind it.

What to remember

is about partition behavior, so and carry their CAP meanings, not the ACID or uptime ones. Pick or per operation, name the conflict or retry story, and use when the network is healthy too. Start AP where stale answers are fine; add CP surgically where money, inventory, or trust demands it.

Exercises

Partition-time label. A teammate says "our database is CP." Rewrite the claim as two sentences: one for inventory decrement under partition, one for like-count under partition. Name what each path does on conflict.
Nines vs CAP A. Product wants 99.99% uptime and linearizable inventory across two regions. Explain why those goals pull in opposite directions during a majority loss (see Numbers to know above), and what users should see (error vs oversell).
PACELC healthy-network knob. No partition, but strong cross-region reads add ~80ms at p99 (the latency the slowest 1% of requests see). Which APIs stay strong, which accept local quorum or stale reads, and what lag metric do you page on?

Topic-specific references

Gilbert & Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" : the formal C/A trade-off under partition that the whole page rests on.
Brewer, "CAP Twelve Years Later" : per-operation nuance and how real systems mix CP and AP paths.
Abadi, PACELC : latency vs consistency when the network is healthy.

Practice and further reading

Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.

Focus for this lesson: Apply CAP only during a network partition and distinguish availability, linearizability, serializability, latency, and normal-operation trade-offs.

Explain the decision

What choice does CAP force during a partition?

Read the reasoning

For operations that cannot communicate, either reject/delay some requests to preserve a single-copy view or answer from isolated state and risk inconsistency.

Apply it to a production scenario

During a partition, a catalog remains writable but checkout inventory does not. Is that inconsistent design?

Read one approach

No; CAP choices are per operation/invariant. Catalog edits may merge later while overselling inventory may be unacceptable.

Work through the numbers

A five-node quorum uses R=3 and W=3. How many node failures can still serve both reads and writes?

Read the worked calculation

Two failures leave three nodes, enough for both; topology and latency still matter, and overlap alone does not prove linearizability.

Reason through a failure

What invariant should a CP lock service preserve?

Read the recovery reasoning

It must never grant two valid owners for the same lock epoch, even if that means rejecting requests without quorum.

Sources and further study

Continue with ACID Properties.