CAP theorem is a statement about what a replicated data store can promise when the network between its nodes breaks. It is one of the most quoted and most misquoted results in system design: interviewers use it to find out whether you can reason about behaviour under failure, or only recite "pick two of three". The useful skill is not labelling a database "CP" or "AP"; it is being able to say, for each piece of state in your system, what a client is allowed to observe while replicas disagree, and what the cost of preventing that would be. For a Backend or AI engineer this matters more than it first appears, because an AI platform is really a bundle of very different stores (a model registry, a feature store, a vector index, chat history, a billing ledger) and each one needs a different point on the consistency ladder. This page focuses on those AI-system needs; the general theory and the quorum mechanics are in CAP Theorem (DBMS) and Distributed Databases (DBMS), and I deliberately do not repeat them here.
The CAP theorem says that when you spread one dataset across several machines, and the network connecting those machines can fail, you cannot always have both "everyone sees the same, most up-to-date data" (consistency) and "the system keeps answering requests" (availability) at the very same moment. When a connection between machines drops, the system has to choose: pause some requests until it is sure the data is correct, or keep answering and risk giving out slightly outdated information.
A consistency model is a rulebook that says exactly how "out of date" information is allowed to be before it reaches you. Some systems promise you will never see anything but the freshest possible value; others only promise that things will even out eventually, a few seconds or minutes later. Picking a model is really picking how much staleness a particular piece of information can tolerate before it causes a real problem.
Picture a chain of coffee shops that all share one central "today's specials" board, updated by phone calls between stores. If the phone lines go down between two shops, each shop has to decide: stop selling anything special until the lines are back up (consistency), or keep selling based on the last specials they heard about, even if it's slightly out of date compared to the other shop (availability). Consistency models are just the store's policy for how stale that specials list is allowed to get before a customer notices something's wrong.
C Consistency = linearizability. Every operation appears to take effect at a single instant between
its start and its end, and all clients agree on one real-time order. Once a write has
returned, every later read, from any client, sees that write or a newer one.
A Availability = every request that reaches a non-failed node receives a non-error response.
(The formal definition sets no latency bound: a reply after 10 minutes still counts.)
P Partition tolerance = the system keeps its promises even if the network drops or delays arbitrary messages
between nodes.
Do not confuse: ACID "Consistency" = a transaction moves the data between states that satisfy its constraints.
CAP "Consistency" = all replicas behave like one copy (a property of replication, not of constraints).The folk version, "you can only have two of the three", is misleading because partition tolerance is not optional. The moment data lives on more than one machine, the network can drop, delay or reorder messages, and you do not get to decline that. So the real statement is narrower: if a partition happens, a system must give up either linearizable consistency or availability for the requests it cannot safely serve. A "CA" system is not a third design option; it is a single-node system, or one that simply stops working correctly when a partition occurs.
Two details are worth having ready. First, CAP's "C" is exactly linearizability, the strongest single-object model. Many designs that people call "consistent" (snapshot isolation, read committed on a primary, a cache that is usually fresh) are not CAP-consistent in that sense, so arguments that use the word loosely go nowhere. Second, CAP's "A" is both stricter and weaker than the "high availability" of a dashboard: stricter because every non-failed node must answer, weaker because it puts no bound on how slowly. A system that hangs for 30 seconds satisfies the theorem's A but is not available to your users, which is one reason critics such as Martin Kleppmann argue CAP is a blunt tool and that latency-oriented models are more useful in practice.
Three replicas, majority = 2. A network partition isolates C from {A, B}.
client X client Y
| |
+----+----+ X X X +-----+-----+
| A | B | partition | C |
+---------+ +-----------+
majority side minority side
CP behaviour AP behaviour
majority side {A,B}: keeps serving both sides keep serving
minority side {C}: refuses reads/writes X writes price=11 on {A,B}; Y writes price=99 on {C}
(returns errors / times out) Y can still read - but it may read stale data
after heal: C catches up, no conflict after heal: two histories exist -> must reconcile
(last-write-wins can silently lose one of the writes;
version vectors / CRDTs / app-level merge are the alternatives)The diagram is the whole theorem in practice. A CP system protects the single-copy illusion by making the side that cannot prove it has the latest data (usually a minority that cannot form a quorum) unavailable. An AP system keeps every node answering and pays with stale reads and, if it accepts writes on both sides, divergent histories that must be merged later. Neither is "better"; the question is which failure you prefer for that data. Note also what is not in the picture: when there is no partition, a well-built system can be both consistent and available, and the trade-off does not force anything. Most of the time your cluster is healthy, which is why the next section matters more day to day.
The real world is less binary than the labels. The same product often exposes both behaviours per operation: DynamoDB lets a read ask for strong consistency instead of the default eventual read, Cassandra lets each query choose a consistency level, and MongoDB read and write concerns move it along the same axis (check the current documentation for exact defaults, which differ by version and driver). "Is X CP or AP?" is therefore usually the wrong question; "which consistency level do I request for this operation, and what does it cost?" is the right one.
PACELC: if Partition -> choose Availability or Consistency
Else (normal) -> choose Latency or Consistency
Why the "Else" branch exists (ILLUSTRATIVE physics, not a benchmark):
light in fibre travels roughly 200,000 km/s = about 5 ms per 1,000 km, one way
two regions 6,000 km apart: one-way >= ~30 ms, round trip >= ~60 ms (real routes are longer)
write path extra latency on the critical path
---------------------------------------------------------------------------------------------
ack after local commit, replicate async ~0 (but a replica can be stale, a failover can lose writes)
ack after a same-region quorum about one intra-region round trip (typically low ms)
ack after a cross-region quorum at least one inter-region round trip (tens of ms and up)
Commonly cited classifications (defaults and config vary - treat as a mnemonic, not a spec):
Dynamo / Cassandra-style, default tuning PA/EL available under partition, low latency normally
Spanner, etcd, ZooKeeper (writes) PC/EC consistency first, pays coordination latency
MongoDB, DynamoDB, Cosmos DB tunable per operation or per accountPACELC (Daniel Abadi) adds the observation that consistency costs something even when nothing is broken: to make a read reflect the latest write, replicas must either coordinate on every operation or route reads to one authoritative place, and both add latency. That is a far more frequent cost than partitions, so it is often what actually drives a design. For an inference platform this shows up in every request path: if a feature lookup, a prompt-config fetch and a rate-limit check each demand a cross-region linearizable read, you have spent your latency budget before the model runs. That is why these lookups are typically served from local, eventually consistent copies with a bounded staleness contract, and only the rare decision that must be exact (a ledger write, a "promote this model" switch) pays for coordination.
stronger, more coordination, less available under partition, higher latency
|
| linearizable one real-time order. A read that starts after a write completes sees it.
| (single-leader with reads from the leader and a fenced failover; Raft-based stores like etcd
| by default; Spanner. Note: ZooKeeper reads can be stale unless you sync first.)
| sequential one total order that every client agrees on and that respects each client's own order,
| but is not tied to wall-clock time (a client may lag behind reality, never reorder).
| causal if A could have influenced B (B read A, or same session), everyone sees A before B.
| Concurrent, unrelated writes may appear in different orders on different replicas.
| session guarantees, each cheap enough to add on top of "eventual":
| read-your-writes I always see my own earlier writes
| monotonic reads I never see an older state after seeing a newer one
| monotonic writes my writes are applied in the order I issued them
| writes-follow-reads a write is ordered after the reads it was based on
| eventual if writes stop, replicas converge. No promise about what you read before that.
v
weaker, cheaper, faster, available under partitionThe ladder is useful because the middle rungs are cheap and solve most user-visible bugs. Full linearizability needs a single ordering authority (a leader or a consensus group, see Consensus & Coordination), so it costs latency and availability. Eventual consistency costs nothing but pushes weirdness to the user: a message they just sent disappears on refresh, or a value flips back to an older one. Session guarantees fix exactly that weirdness without global coordination: pin a session to one replica for monotonic reads, or carry a "last seen version" token so any replica that is behind your last write refuses or redirects you for read-your-writes. Causal consistency is the strongest model that generally remains available under partition, which is why it is attractive for conversational state where a reply must never be shown before the question it answers.
One trap: a quorum configuration with R + W > N sounds like it gives linearizability, but by itself it generally does not. Sloppy quorums, concurrent writes resolved by last-write-wins with skewed clocks, and the timing of read repair can all still return stale or reordered results. Say "quorum reads and writes overlap, which makes stale reads less likely, but linearizability needs more than overlap" and point to the mechanics in Distributed Databases.
Component Needs What breaks if it is wrong
-----------------------------------------------------------------------------------------------------------------------
Model registry "production" pointer linearizable compare-and-swap (CP) two operators promote different versions;
rollback races with a promote
Serving node's local model/config eventual, staleness bounded by a TTL nodes disagree on version for a while (mixed
cache + a version stamp in every response fleet); acceptable if you can see it
Online feature store (Redis/Dynamo eventual, with a freshness SLO model scores with a stale feature; small
style key-value) (e.g. "p99 age below N seconds") accuracy loss, not an outage
Offline / training feature tables point-in-time (as-of) correctness label leakage; NOT a CAP issue, a temporal one
Vector index: inserts eventual (searchable after a refresh) a brand-new document is missing from answers
Vector index: deletes / ACL revokes bounded staleness, ideally filter-at- a deleted or forbidden chunk is still
read against an authoritative source retrieved into the prompt: a security bug
Chat / session state read-your-writes + monotonic reads; user's last message vanishes on refresh;
per-conversation ordering (causal) reply appears before the question
Billing / token-usage ledger linearizable or serializable writes over- or under-charging, double credits
Rate-limit counters approximate is usually fine slightly loose limit, no financial harm
Idempotency-key store linearizable insert-if-absent duplicate side effects on retryRead the table by asking one question per component: "what is the harm of a stale read here, and how long can it last?" A stale feature is a slightly worse prediction; a stale model pointer is a confusing rollout; a stale vector-index delete is a data-leak. The last one is easy to miss. Deletions and permission changes are the writes where staleness turns from a quality problem into a compliance problem, so retrieval systems generally apply access filters against an authoritative store at query time (or keep the deletion lag small and measured) rather than trusting that the index has caught up. The same reasoning is why feature stores split into an online eventually consistent store and an offline store whose correctness is about time travel, not replica agreement, and why vector databases advertise "near real-time" indexing rather than read-after-write.
Two small simulations, standard library only. The first is a replicated register with asynchronous followers (one slow, one fast) and three client read policies. It shows that reading random replicas breaks both read-your-writes and monotonic reads, that pinning a session to one replica fixes monotonic reads but not read-your-writes when that replica lags, and that a version token gives read-your-writes by falling back to the leader only when the pinned replica is behind. Replication lag is a fixed number of ticks to keep the run deterministic; real lag varies.
import random
class Replica:
def __init__(self, name):
self.name, self.version, self.value = name, 0, None
class Cluster:
"""1 leader + 2 async followers; a write reaches each follower after a fixed lag (in ticks)."""
def __init__(self, lags):
self.leader = Replica("leader")
self.followers = [Replica("f1"), Replica("f2")]
self.lags, self.pending, self.tick = lags, [], 0
def write(self, value):
self.leader.version += 1
self.leader.value = value
for f, lag in zip(self.followers, self.lags):
self.pending.append((self.tick + lag, f, self.leader.version, value))
return self.leader.version # version token returned to the client
def advance(self):
self.tick += 1
for item in [p for p in self.pending if p[0] <= self.tick]:
_, f, ver, val = item
if ver > f.version: f.version, f.value = ver, val
self.pending.remove(item)
def run(policy, seed=3):
rnd = random.Random(seed)
c = Cluster(lags=[3, 1]) # f1 is the slow follower, f2 the fast one
token, pinned, out = 0, c.followers[0], [] # token = newest version this client knows about
for step in range(1, 7):
token = max(token, c.write(f"v{step}"))
c.advance() # one tick, then the client reads
if policy == "random replica":
r = rnd.choice([c.leader] + c.followers)
elif policy == "pinned to f1":
r = pinned
else: # pinned to f1, but never accept a copy older than my token
r = pinned if pinned.version >= token else c.leader
out.append((step, r.name, r.version))
return out
for policy in ["random replica", "pinned to f1", "pinned to f1 + token"]:
out = run(policy)
ryw = sum(1 for s, n, v in out if v < s) # read older than my own latest write
mono = sum(1 for a, b in zip(out, out[1:]) if b[2] < a[2]) # version went backwards between reads
print(f"{policy:22} read-your-writes violations={ryw} monotonic-read violations={mono}")
print(" " + " ".join(f"w{s}->{n}:v{v}" for s, n, v in out))
# Real output from python3:
# random replica read-your-writes violations=1 monotonic-read violations=1
# w1->leader:v1 w2->f2:v2 w3->f2:v3 w4->leader:v4 w5->f1:v3 w6->f2:v6
# pinned to f1 read-your-writes violations=6 monotonic-read violations=0
# w1->f1:v0 w2->f1:v0 w3->f1:v1 w4->f1:v2 w5->f1:v3 w6->f1:v4
# pinned to f1 + token read-your-writes violations=0 monotonic-read violations=0
# w1->leader:v1 w2->leader:v2 w3->leader:v3 w4->leader:v4 w5->leader:v5 w6->leader:v6The second simulates a three-node store during a partition. In CP mode a client that can reach only one node is refused; in AP mode it is served, but the "healed" state shows what naive reconciliation costs: both sides wrote version 2, and the toy repair keeps one of them, silently dropping the other write (price=99). That dropped write is the hidden price of AP without a real merge strategy.
class Node:
def __init__(self, name): self.name, self.ver, self.val = name, 0, "init"
class Store:
"""3 nodes. mode 'CP': operate only with a majority (2 of 3). mode 'AP': serve from whatever node you can reach."""
def __init__(self, mode):
self.mode = mode
self.nodes = {n: Node(n) for n in "ABC"}
self.cut = set() # nodes cut off from the client's side
def reachable(self, side): # nodes on the client's side of the partition
return [n for n in self.nodes if (n in self.cut) == (side == "minority")]
def write(self, side, val):
nodes = self.reachable(side)
if self.mode == "CP" and len(nodes) < 2:
return "REJECTED (no majority)"
top = max(self.nodes[n].ver for n in nodes) + 1
for n in nodes: self.nodes[n].ver, self.nodes[n].val = top, val
return f"ok v{top} on {nodes}"
def read(self, side):
nodes = self.reachable(side)
if self.mode == "CP" and len(nodes) < 2:
return "REJECTED (no majority)"
best = max((self.nodes[n] for n in nodes), key=lambda x: x.ver)
return f"{best.val} (v{best.ver})"
def heal(self):
self.cut = set()
best = max(self.nodes.values(), key=lambda x: x.ver) # naive last-highest-version-wins repair
for n in self.nodes.values(): n.ver, n.val = best.ver, best.val
for mode in ["CP", "AP"]:
s = Store(mode)
print(f"=== {mode} store, 3 nodes, majority = 2")
print(" before partition write :", s.write("majority", "price=10"))
s.cut = {"C"} # node C is partitioned away from A and B
print(" partition: minority client (sees only C)")
print(" read :", s.read("minority"))
print(" write price=99 :", s.write("minority", "price=99"))
print(" partition: majority client (sees A,B)")
print(" write price=11 :", s.write("majority", "price=11"))
print(" read :", s.read("majority"))
print(" minority client reads again:", s.read("minority"))
s.heal()
print(" after heal, all nodes:", {n: (x.val, x.ver) for n, x in s.nodes.items()})
# Real output from python3:
# === CP store, 3 nodes, majority = 2
# before partition write : ok v1 on ['A', 'B', 'C']
# partition: minority client (sees only C)
# read : REJECTED (no majority)
# write price=99 : REJECTED (no majority)
# partition: majority client (sees A,B)
# write price=11 : ok v2 on ['A', 'B']
# read : price=11 (v2)
# minority client reads again: REJECTED (no majority)
# after heal, all nodes: {'A': ('price=11', 2), 'B': ('price=11', 2), 'C': ('price=11', 2)}
# === AP store, 3 nodes, majority = 2
# before partition write : ok v1 on ['A', 'B', 'C']
# partition: minority client (sees only C)
# read : price=10 (v1)
# write price=99 : ok v2 on ['C']
# partition: majority client (sees A,B)
# write price=11 : ok v2 on ['A', 'B']
# read : price=11 (v2)
# minority client reads again: price=99 (v2)
# after heal, all nodes: {'A': ('price=11', 2), 'B': ('price=11', 2), 'C': ('price=11', 2)}Both programs are teaching models: no real network, no clocks, no failure detection. In a real system, the equivalent knobs are named things such as a strongly consistent read flag, a quorum level, a leader-only read, or a "wait until replica LSN is at least X" check; see the vendor documentation for what your version actually offers.
Q: Explain CAP theorem in one minute without saying "pick two".
A: In a replicated system, if the network partitions, a node that cannot reach the others must either answer from possibly outdated state (staying available, giving up linearizable consistency) or refuse (staying consistent, giving up availability for that request). Since partitions cannot be ruled out, that is the only choice; when the network is healthy, the theorem forces nothing. The follow-on cost is latency, which PACELC captures: even without a partition, stronger consistency needs more coordination.
Q: Is the "C" in CAP the same as the "C" in ACID?
A: No. ACID consistency means a transaction leaves the data satisfying its declared invariants, such as constraints and foreign keys, which is largely the application's job. CAP consistency means linearizability: all replicas behave as one copy and reads never return something older than a completed write. Mixing them up is a common red flag in interviews.
Q: For a RAG system, which parts would you make strongly consistent and which eventual?
A: Strong for the small control-plane state where a wrong answer is expensive: the model or index "current version" pointer, the usage and billing ledger, and idempotency keys. Eventual for the high-volume data plane: vector-index inserts, cached embeddings, feature values, prompt-config caches, with a stated staleness bound. I would treat deletes and permission revocations specially, filtering against an authoritative store at query time, because a stale index there leaks data instead of merely lowering quality.
Q: A user says the chatbot "forgot" the message they just sent when the page refreshed. What happened and how do you fix it?
A: Almost certainly a read-your-writes violation: the write went to the primary and the refresh was served by an asynchronous replica that had not applied it yet. Fixes in increasing strength: read the conversation from the primary for a short window after a write, return the write's version (or log position) to the client and only accept replicas at or beyond it, or pin a conversation to one partition with a single writer. The cost is extra load on the primary or a small latency bump when a replica is behind.
Q: How would you promote a new model version to production safely across many serving nodes?
A: Store the "production version" pointer in a linearizable store and change it with a compare-and-swap on the previous version, so two concurrent promotions cannot both succeed. Serving nodes then pick it up by polling or watching with a short TTL, which is deliberately eventually consistent, so for a short window the fleet serves a mix of versions. To make that safe, the version has to be stamped on every response and metric, the old artifact must remain available until all nodes have moved, and the rollout should be treated as a canary rather than an instant switch.
Q: Why is an eventually consistent vector index usually acceptable?
A: Retrieval already returns approximate results, and a document missing for a second or two after ingestion is almost always tolerable, whereas requiring read-after-write would push every insert through coordination and hurt ingest throughput. It stops being acceptable when the write is a deletion or a permission change, or when a workflow requires "upload then ask about it immediately", which then needs an explicit wait-for-refresh or a fallback path that reads the fresh document directly.
Q: What does PACELC add over CAP?
A: CAP only speaks about behaviour during a partition. PACELC adds the normal-operation trade-off: latency versus consistency. Synchronously replicating across regions adds at least one inter-region round trip (tens of milliseconds) to every write, so many systems accept asynchronous replication and stale reads to keep p99 low. The catch is that the label is a rough mnemonic, since most stores are configurable per operation.
Follow-up: Does a quorum with R + W > N give you linearizability?
A: Not by itself. The overlap guarantees that a read quorum intersects the latest write quorum, but concurrent writes, last-write-wins with clock skew, sloppy quorums during failures, and a write that has reached some replicas but not yet a full write quorum can all let a client observe stale or non-monotonic values. Getting linearizable behaviour needs extra mechanisms such as read repair before returning, consensus for the write order, or leader-based reads with fencing, and each adds latency.
Follow-up: Two regions, one user in each, both editing the same conversation title. What do you do?
A: It depends on the cost of losing an edit. If it is low, accept both writes locally (AP) and merge with last-write-wins or a per-field CRDT, telling the user that the last edit wins. If it must be exact, route all writes for that conversation to a single home region (a single-writer partition), giving up write availability for users far from it when that region is unreachable. Either way, pick it deliberately per data type.
Follow-up: Your feature store is "eventually consistent". How do you know if that is hurting the model?
A: Measure it instead of arguing about it: record the age of each feature value at serving time and alert on a freshness SLO, log the feature values used with each prediction, and compare online values to offline recomputation on a sample. If stale features correlate with worse predictions for a feature class (for example a fast-moving "items viewed in the last 5 minutes"), give that class a shorter propagation path or compute it at request time, and leave slow-moving features on the cheap path.
In a design review, a CAP-aware answer walks the state inventory and assigns each item a consistency requirement and a staleness budget, rather than declaring one global choice. Take an assistant product and assume (illustratively) 5 million conversations a day with about 10 turns each: that is 50 million message writes a day, roughly 600 per second on average and perhaps 3,000 per second at a 5x peak, which one well-provisioned primary database with asynchronous read replicas can handle. That primary-plus-replicas layout then gives eventual reads by default, so the design adds read-your-writes for the conversation being viewed (read the primary, or use a version token, for a few seconds after a write), keeps the model-version pointer and quota ledger in a small strongly consistent store such as a Raft-backed key-value store or a relational primary, and lets the feature cache and vector index run with a freshness SLO of, say, seconds for features and a minute for inserts, with deletes checked against the authoritative store at query time. Cross-region adds the physics penalty: at least about a 60 ms round trip for 6,000 km, so a synchronous cross-region commit is a deliberate spend, usually reserved for the ledger, while reads and caches stay region-local. Interviewers listen for two things: how stale is acceptable (seconds, minutes) and what the fallback is when the strongly consistent component is unreachable (fail closed for billing, serve stale for features, degrade rather than error for retrieval). See also Caching Strategies and Idempotency & Exactly-Once Semantics for how retries interact with these choices.
Choosing stronger consistency buys simpler reasoning for developers and users (no vanishing messages, no double-charging, no conflicting promotions) and costs latency, throughput and availability during failures, because more nodes must agree before an operation completes and a minority partition stops serving. Choosing weaker consistency buys low latency, scale and availability and costs correctness work pushed into the application: reconciliation, idempotency, staleness monitoring and user-facing caveats. The wrong choice in the strong direction is forcing linearizability on high-volume data that tolerates staleness (embedding caches, feature lookups), which burns latency budget and reduces resilience for no benefit. The wrong choice in the weak direction is leaving ledgers, permissions, deletions or leader-election state eventually consistent, where a stale read is a financial or security incident rather than a slightly worse answer. The practical compromise is the ladder itself: default to eventual, add session guarantees where users can notice, reserve linearizable operations for a small, well-guarded core, and keep measuring how stale "eventual" really is in production.