Choosing Consistency and Availability in Distributed System Interviews

Learning outcome

By the end of this lesson, you can explain consistency and availability as workload-specific design choices rather than slogans. You can identify invariants, define behavior during failures, distinguish normal operation from network partitions, and defend different choices for different operations in the same system.

Intuition

Start with what users must never observe. A consistency model is useful only when connected to a concrete invariant such as “a coupon cannot be redeemed more than once” or “a user can read their own profile update.” Availability is also more precise than “the service stays up”: ask which operations must accept requests, at what latency, and whether a provisional or stale response is acceptable.

CAP does not force a system to choose one permanent identity as “CP” or “AP.” During a network partition, a replicated operation cannot simultaneously guarantee linearizable behavior and guarantee a successful response from every non-failing node. Real systems make choices per operation, data item, region, and failure mode. Outside partitions, latency, consistency, durability, and cost still involve trade-offs, but CAP alone does not describe them.

Use this decision sequence:

1. State the user-visible operation and its invariants.
2. Define the required consistency: linearizability, serializable transactions, read-your-writes, monotonic reads, bounded staleness, or eventual convergence.
3. Define operational availability quantitatively: success rate, timeout budget, and permitted degraded responses. Keep these service-level goals separate from CAP availability.
4. Name failures: packet loss, region isolation, leader loss, replica lag, retries, and client timeouts.
5. Choose partition behavior: reject, wait, serve stale data, accept tentative writes, or route to an authority.
6. Explain reconciliation, recovery time, observability, and operational cost.

State the model before the choice

For the following traces, assume non-malicious replicas, durable committed state unless a loss is explicitly introduced, and messages that may be delayed, duplicated, reordered, or lost. A partition can isolate live replicas indefinitely; a timeout cannot establish whether a peer is slow, unreachable, or dead. Progress after healing requires working communication and enough healthy capacity. These are crash/recovery and communication failures, not a claim about Byzantine faults or simultaneous loss of every durable copy.

Keep four contracts distinct:

• Linearizability: each operation behaves as if it took effect at one point between its invocation and response, respecting the real-time order of non-overlapping operations. With no later write, a read started after a completed write cannot return the older value.
• Transaction isolation: serializability orders whole transactions as if they ran one at a time; by itself it does not require that order to match real time. Strict serializability adds that constraint. Linearizable individual reads and writes do not make a multi-step read-check-write atomic.
• Session and staleness guarantees: read-your-writes concerns one client's observed writes; monotonic reads prevent that session from moving backward. State whether the guarantee survives region switches. Bounded staleness needs a precise bound and a refusal/wait policy when the bound cannot be met. Eventual convergence needs retained updates, eventual delivery/repair, and compatible merge rules; it supplies no universal deadline.
• Availability: CAP availability requires every request received by a non-failing node to finish with the operation's required response, even under the allowed partition. It sets no fixed latency bound. A fast transport error, health-check success, or provisional receipt is not completion of the original read/write contract. Product uptime, a 250 ms deadline, and a 99.9% success target are separate operational measures.

The CAP paper and linearizability paper provide the formal definitions. In an interview, state the contract you are applying rather than treating every meaning of “consistent” or “available” as interchangeable.

Deep dive

Strong consistency is justified when concurrent decisions must observe one authoritative order. A consensus-backed leader or a correctly designed quorum protocol can support that contract, but the read path and failover rules matter too. Fencing tokens, uniqueness constraints, and idempotency records solve narrower problems: stale-owner rejection, uniqueness within an enforcement boundary, and retry deduplication. None alone supplies global linearizability. A fence works only when the protected resource rejects stale tokens; a lease needs stated timing assumptions and a safe expiry rule.

These mechanisms can increase latency and may reject or delay operations when a quorum is unavailable. “Use a quorum” is incomplete unless you explain quorum membership, overlapping reads and writes, leader leases, stale replicas, and what happens during reconfiguration. A healthy majority may keep some requests working while an isolated minority cannot complete them; that is useful operational availability, not availability at every non-failing node.

Eventual consistency is appropriate when temporary divergence is tolerable and updates have a safe merge rule. Availability then depends on accepting operations locally and reconciling later. You must still define conflict semantics: last-write-wins can lose valid updates, clocks can be skewed, and duplicate delivery is normal. Alternatives include operation-based updates, conflict-free replicated data types, or domain-specific resolution. Version vectors help detect causal relationships and concurrent versions; they do not choose the business winner. A CRDT still needs the delivery and merge assumptions of its particular design, and convergence alone does not preserve every business invariant.

Consistency can be asymmetric. A product page may serve stale descriptions while inventory reservation uses an authoritative conditional write. A social application may accept a post locally but require stronger consistency for privacy-policy changes. Session guarantees such as read-your-writes can provide a good user experience without making every read globally linearizable.

Worked trace: quorum overlap is not the whole protocol

Assume a fixed replica set A, B, C; writes acknowledge after two replicas store a tagged value; reads query two replicas and return the largest tag seen. Tags are totally ordered, replicas retain their largest tag, and reads perform no write-back or other coordination. The following is a deliberately incomplete algorithm, not a consensus implementation.

1. A completed write of tag 1, value “blue” is stored on A and B. C still has tag 0, value “white.”
2. A new writer stores tag 2, value “green” on B only, then stalls before reaching its two-replica acknowledgment threshold.
3. Read X queries B and C and returns “green” from tag 2. X completes.
4. After X completes, read Y queries A and C and returns “blue” from tag 1. No other writes occur.

Answer: all read sets have size two, all acknowledged write sets have size two, and any such sets intersect. Nevertheless, the read history is not linearizable. Returning “green” can expose the pending write, but once X has returned it, Y cannot move backward to “blue.” Quorum arithmetic does not specify how partially propagated writes, concurrent operations, read repair/write-back, or leadership are handled. Use a protocol with a correctness argument for the requested contract, not just R + W > N. This trace assumes fixed membership; changing replica sets needs its own safe transition protocol.

Worked scenario 1: limited inventory checkout

Invariant: confirmed reservations must not exceed stock. During a region partition, allowing every region to confirm against the same remaining units risks overselling. A defensible design routes reservations to a consensus-backed owner for each stock item or pre-allocates bounded inventory tokens to regions. Without authority or an available token, checkout returns a retryable failure or “pending” result rather than false confirmation.

Catalog browsing remains available from local replicas and may be slightly stale. Reservation requests use a scoped idempotency key and a payload fingerprint. The authoritative atomic decision records the reservation and its replayable result together; a matching retry returns that result, while reuse for a different payload is rejected. Keep that record for the stated retry window. A key in a separate best-effort cache does not by itself prevent double consumption. Recovery includes reconciling pending attempts, expiring abandoned holds, and monitoring quorum health, token exhaustion, and reservation latency. The trade-off is reduced write availability for a strict business invariant, not reduced availability for the entire storefront.

Inventory trace and answer key

Assume one sellable unit, one owner backed by replicas A/B/C, majority commitment, and an atomic reserve-if-positive operation that also records the request key. The protocol prevents an isolated old leader from committing and makes confirmed state survive an allowed single-replica failure.

1. Request K reaches A. A and B commit reservation R for K, leaving zero units.
2. The response is lost. The client times out. A then becomes isolated from B/C.
3. The client retries K through B/C after safe leadership recovery.
4. A different request J also tries to reserve the last unit.

Answer: K's retry returns R and does not decrement again. J receives sold out. The isolated A must not confirm new reservations without authority; a timeout for K did not mean failure. If B/C cannot yet establish safe leadership or recover the committed record, they must wait or return an uncertain/retryable outcome instead of inventing a fresh reservation. Define status lookup, retention, and the terminal states of holds before implementing retries.

Why an atomic operation matters: even with linearizable reads and writes, K and J could both read stock = 1 before either writes stock = 0. Confirming both would violate the invariant. Reserve-if-positive must make the check and change indivisible, for example with an appropriate conditional operation or transaction.

Token alternative: with five units, allocate three exclusive tokens to East and two to West before a partition. Each region may confirm at most its own token count using atomic local consumption. East may sell out while West still has capacity. Do not reissue West's tokens just because West timed out; old tokens must be provably unusable before reassignment. Safe reclamation and hold expiry cannot race a still-valid owner into selling the same unit twice.

Worked scenario 2: social timeline and privacy

Timeline reads prioritize low latency and can use cached, eventually consistent fan-out results. A newly published post may appear late or temporarily out of order. Posting can acknowledge after durable local acceptance, with background replication and idempotent fan-out. That acknowledgment survives only the failures covered by the local durability contract; loss of the entire region before replication may lose the post. If acknowledgment must survive region loss, require an appropriate remote durability boundary before confirming it.

Privacy changes require different treatment. Define the guarantee precisely: a protected read invoked after the block acknowledgment must not newly authorize the blocked reader. A simple design orders policy changes and authorization decisions through the same authoritative, linearizable service and fails closed when that authority is unreachable. A stored policy-version number alone cannot prove that a cache is current during a partition. Reusing positive cached decisions needs an explicit validity/revocation protocol, including any lease and clock assumptions, and the block cannot be acknowledged before that protocol's promised boundary is met.

Trace: West holds cached allow decision at policy version 40, then loses contact with the authority. East commits block version 41 and returns confirmation. A new protected read reaches West afterward. Answer: West must deny or fail closed unless it has authorization valid under the stated revocation protocol. “My cache still says 40” is not evidence that 41 does not exist. Serving the post and deleting it during later repair cannot undo the disclosure.

This guarantee does not recall bytes already delivered. Reads authorized before the block may overlap it; downloads, streams, signed URLs, and external caches need separately stated revocation semantics. If the requirement is that no further bytes leave any server after confirmation, the design must account for those in-flight deliveries before making that stronger promise. Recovery removes previously materialized timeline entries, refreshes policies, and audits any exposure. This hybrid answer shows that availability decisions follow the consequence of staleness, not the broad product category.

Failure modes

Common weak answers include:

• “Choose CP for money and AP for social media.” This labels domains without identifying operations or invariants.
• “CAP means pick any two.” Partition tolerance is not usually optional across an unreliable network, and the consistency-versus-availability tension becomes unavoidable specifically during a partition.
• “Eventual consistency means no consistency.” Eventual convergence is a guarantee under stated assumptions, but it does not define conflict resolution or user session behavior.
• “Quorums guarantee consistency.” Poorly configured quorums, stale leases, non-overlapping replica sets, or unsafe membership changes can violate that claim.
• “Return success and reconcile later.” Compensation may be impossible for leaked private data, duplicate external payments, or legally binding confirmation.
• Ignoring ambiguous outcomes. A client timeout does not prove that a write failed; retries need idempotency and status lookup.
• Ignoring recovery. A design must explain backlog draining, conflict repair, cache invalidation, and how operators know convergence has completed.

Interview drill

When given a distributed design prompt, say: “I will choose guarantees per operation. First I want to identify irreversible outcomes and stale-read consequences.” Then ask about regional topology, latency targets, acceptable staleness, outage expectations, data ownership, and whether degraded or pending responses count as available.

For each critical operation, present a compact decision record: invariant, consistency level, normal path, partition path, client-visible response, retry semantics, reconciliation, and metrics. Compare at least one alternative. For example, centralized inventory offers simpler correctness but higher cross-region latency; regional token allocation lowers latency and preserves a global bound but adds allocation, stranded-capacity, and rebalancing complexity.

A senior answer also discusses operational cost: consensus maintenance, hot partitions, capacity needed during failover, clock assumptions, disaster recovery, repair tooling, and testing with delayed, duplicated, reordered, or dropped messages.

Practice questions with answer keys

1. A dashboard shows 100% HTTP responses and p99 = 80 ms during a partition, but writes receive “retry later.” Has it demonstrated CAP availability for the write operation? No. It measured responses and latency. The specified writes were not completed; reporting those errors honestly can preserve safety but cannot prove CAP availability.
2. A user saves a profile in East, moves to West, and sees the old profile. Which claim is definitely broken if read-your-writes was promised across regions? That session guarantee. To enforce it, carry a suitable session position/version and wait, route, or refuse when West cannot satisfy it. Do not silently serve an older value. Other clients may still see stale data under that contract.
3. Two regions independently add distinct items to a cart and later exchange updates. Does last-write-wins on the whole cart necessarily preserve both additions? No. One whole-cart version may replace the other. A suitable per-item operation/merge model may preserve additions, but remove-versus-add conflicts and duplicate operations need explicit rules. Eventual convergence alone does not choose them.
4. A blocked region reconnects and its queue becomes empty. Is recovery proved complete? No. A queue could have lost updates or fed a failed consumer. Check applied positions or equivalent reconciliation evidence, unresolved conflicts, authoritative invariants, retry outcomes, and refreshed privacy decisions. Also check that resumed capacity does not overwhelm dependencies.
5. A majority is reachable. Does that alone promise a fixed recovery deadline? No. Safe leader selection, persisted state, routing, processing capacity, and the protocol's progress assumptions still matter. State the operational recovery target and measure it; do not turn a safety property into a latency guarantee.

For an interview answer, score each scenario against five checks: clear operation/invariant, explicit failure assumptions, justified normal and partition behavior, retry/recovery treatment, and one credible alternative with its cost. A named product or “CP/AP” label earns no substitute credit for those explanations.

Revision checklist

• Did I define user-visible invariants before naming a consistency model?
• Did I separate normal latency trade-offs from partition behavior?
• Did I distinguish CAP availability from uptime, latency, and degraded-response SLOs?
• Did I state the fault model and the scope of each consistency and durability promise?
• Did I specify availability for individual operations and response types?
• Did I explain what stale reads, duplicate writes, and client timeouts do?
• Did I choose safe retry and idempotency semantics?
• Did I describe conflict resolution or justify rejecting writes?
• Did I justify the full quorum, authority, and membership protocol rather than only quorum sizes?
• Did I cover recovery, convergence, observability, and manual repair?
• Did I distinguish confirmation from tentative acceptance?
• Did I compare an alternative and its latency and operational costs?
• Did I avoid treating the whole system as permanently “CP” or “AP”?