CAP Theorem and Consistency Models Questions

Understand the CAP theorem and how Consistency, Availability, and Partition Tolerance interact in distributed systems. Know different consistency models including strong consistency such as linearizability, eventual consistency, causal consistency, and session consistency, and how to apply them to different use cases. Be familiar with consensus protocols and distributed coordination primitives such as Raft and Paxos, quorum reads and writes, two phase commit and when to use them. Understand trade offs between consistency and availability under network partitions, patterns for hybrid approaches where different data uses different guarantees, and the product and developer experience implications such as latency, stale reads, and API contract clarity.

MediumTechnical

22 practiced

Explain the trade-offs between two-phase commit (2PC) and distributed consensus (e.g., Raft-based transactions) for achieving atomic multi-shard transactions. Discuss blocking behavior, coordinator or leader failures, performance implications, and scenarios where one approach is clearly preferable to the other.

Sample Answer

Two-phase commit (2PC) and consensus-based (Raft-style) multi-shard transactions both aim for atomicity across participants but trade off availability, latency, and complexity differently.

Short definitions:- 2PC: a coordinator asks all participants to prepare, then issues commit/abort. Simpler to implement on top of independent storage engines.- Raft-based transactions: participants replicate a transaction (or intent) through a replicated state machine/consensus group (often per-shard) so a leader/consensus decision drives commit.

Blocking behavior:- 2PC can block: if the coordinator crashes after participants have prepared, participants may hold locks or prepared state until coordinator recovery—leading to availability loss and potential stalled progress.- Raft-based: non-blocking under leader changes (assuming majority available). Consensus ensures progress if a majority of replicas are up; no single external coordinator needs to be contacted after replication.

Coordinator/leader failures:- 2PC: single coordinator is a single point of decision; recovery protocols exist but are complex and require human/automatic resolution; participants must wait.- Raft: leaders can change; a new leader can drive the commit if logs are replicated. Failure handling is built-in (leader election), so availability is higher at the cost of more moving parts.

Performance implications:- 2PC: lower steady-state replication overhead—participants only write local prepare/commit—and fewer cross-shard consensus messages; but can incur long-held locks and tail latency if coordinator or network is slow.- Raft-based: extra replication (write to majority) increases write latency and I/O, and cross-shard coordination often means multi-consensus rounds; however, it avoids blocking and improves safety during failures.

When to prefer which:- 2PC is preferable when shards are independent durable stores, performance/throughput is critical, failures are rare or you can tolerate temporary blocking, and implementation simplicity matters.- Raft/consensus-based transactions are preferable when high availability under failures, linearizability, predictable recovery, and automated failover are required—e.g., geo-distributed databases, systems needing strong consistency without manual recovery.

Hybrid note: many systems use optimizations—presumed commit/abort, participant-side leases, or combining 2PC with Paxos/Raft for coordinator state—to reduce blocking or latency. Choice depends on failure model, latency budget, and operational complexity trade-offs.

MediumTechnical

30 practiced

A follower in your leader-follower replicated store occasionally lags behind the leader, causing stale reads when clients are routed to it. Describe four strategies to reduce stale reads (e.g., read-from-leader, version checks, client-side staleness tolerance, read-repair) while minimizing impact on read throughput and tail latency. For each, describe trade-offs and best-use scenarios.

Sample Answer

Framework: goal = reduce stale reads served by lagging followers while preserving overall read throughput and low tail latency. Below are four practical strategies, each with trade-offs and best-use scenarios.

1) Read-from-leader (or leader-preferring reads)- What: Route either all strong-consistency reads or reads with a freshness requirement to the leader.- Trade-offs: Strong consistency, no stale reads; increases leader CPU/network load and can raise leader tail latency under high read pressure.- Best use: Hot keys or operations that cannot tolerate staleness (billing, account balance). Use selective routing (only critical keys) and autoscale leaders or rate-limit to contain impact.

2) Version checks / conditional read validation- What: Serve from follower but return a lightweight version/timestamp; client optionally validates version with leader or requests a stale->fresh upgrade if version too old.- Trade-offs: Low average latency (most reads cheap); occasional extra round-trip for upgraded reads increases tail latency. Requires storing monotonic version metadata.- Best use: Read-heavy workloads where most reads tolerate small staleness but some must be validated (e.g., UIs showing mostly-read-only data with occasional writes).

3) Client-side staleness tolerance (bounded staleness / read-your-writes window)- What: Expose a bounded-staleness SLA (e.g., max T seconds or N versions). Clients accept follower reads if follower’s lag <= bound; otherwise they fallback to leader.- Trade-offs: Keeps throughput and low latency for tolerant clients; requires exposing lag metrics and client logic. Choosing bounds trades freshness vs availability.- Best use: Social feeds, analytics dashboards where slight staleness is acceptable and performance prioritized.

4) Read-repair (proactive or lazy)- What: On detection of stale read (via version mismatch or anti-entropy), either synchronously repair before responding or asynchronously repair after serving (background fixes).- Trade-offs: Synchronous repair prevents stale response but adds latency to that request; asynchronous repair preserves latency but may continue serving stale reads until repaired. Repairs consume bandwidth/IO.- Best use: Use async repair for high-throughput systems to gradually converge; use synchronous repair only when correctness demands it for that operation.

Practical mix: combine strategies—route critical reads to leader, use bounded-staleness for most clients, apply lightweight version checks for sensitive actions, and run continuous async read-repair/anti-entropy to reduce future lag. Monitor follower lag, tail latency, and leader saturation to tune thresholds.

HardSystem Design

21 practiced

Explain how you would implement multi-region leader election to provide linearizable writes globally. Discuss deployment topologies (single active leader vs leader-per-region with forwarding), the latency and availability implications, and how network partitions affect progress and correctness.

Sample Answer

Requirements and constraints:- Global linearizable writes (single global total order).- Reasonable write latency for global clients, high availability when possible.- Tolerate region failures and network partitions without violating linearizability.

High-level options:1) Single active leader (global leader elected via consensus across region quorums)- Architecture: one leader node in a region; all writes go to that leader which runs Raft/Paxos to replicate to majority of voting replicas across regions.- Latency: writes require leader + majority RTTs. Global clients far from leader incur high latency (cross-region RTT).- Availability: if quorum remains, progress continues; if leader’s region partitioned but quorum reachable, leader can continue. If quorum lost, no progress (linearizability preserved).- Correctness: strong — consensus ensures a single ordered log; prevents split-brain.

2) Leader-per-region with forwarding (local leaders accept client, forward to global sequencer or run hierarchical consensus)- Architecture: each region has a local leader; either (a) forward writes to global sequencer/leader, or (b) run a two-level consensus (regional Raft + global ordering using a Global Log Service).- Latency: local writes routed to local leader are low-latency for read-only, but writes requiring global order pay extra hop: local → global leader → replicate → ack. Optimizations: batching, lease-based fast-paths for commutative ops.- Availability: better locality for client contact; but global progress still needs global quorum. If forwarding to an unavailable global leader, regions can buffer but cannot make globally linearizable commits.- Correctness: must carefully manage ordering when forwarding; use global sequence numbers or single-source log to maintain linearizability.

Partition behavior and trade-offs:- Network partition that prevents a majority of voting replicas from forming blocks progress in consensus-based designs — this preserves safety (no two leaders commit conflicting entries) at the cost of availability (CAP).- Lease-based leaders (time-bounded) can improve availability/latency: a leader holds a lease to serve writes locally without contacting global quorum. Risk: lease expiry + partition can lead to concurrent leaders — must ensure leases are obtained only via quorum or use clock-synchronized monotonic leases (TrueTime-like) to preserve safety.- Optimistic fast-paths (e.g., EPaxos-style commutativity) let geographically distributed nodes commit without global coordination for non-conflicting operations; for conflicting writes they fall back to global coordination.

Practical recommendations:- Use single global leader if strict linearizability and simplicity are primary; accept higher median latency for global clients.- Use leader-per-region with forwarding + global sequencer when reducing client-perceived latency is important; implement robust retry/backpressure and ensure forwarded ordering uses a single logical sequence (global log).- Always implement failure detection, quorum reconfiguration, and monitoring. Expose SLAs: in partitions expect degraded availability; never sacrifice linearizability for availability without explicit relaxations (e.g., eventual consistency for some operations).- Consider hybrid: local reads/commutative writes fast-path, conflicting/ordering-critical writes go through global consensus.

Example technologies/patterns: Raft/Paxos for safety, Global sequence service (like Spanner or CockroachDB’s timestamp/lease model), TrueTime or hybrid logical clocks for lease safety, and EPaxos/CRDTs for lower-latency commutative ops.

EasyTechnical

21 practiced

Describe the two-phase commit (2PC) protocol: coordinator and participants, prepare and commit phases. Explain a common failure case where 2PC can block and why that blocking matters. Provide one mitigation strategy (e.g., timeouts, participant recovery) and discuss when you would prefer sagas over distributed transactions.

HardTechnical

28 practiced

Write a short advisory (for engineering teams) on how to reason about CAP in a multi-tenant SaaS product that must guarantee consistency for configuration changes (critical) but can tolerate eventual consistency for analytics and usage metrics. Propose a partition-time strategy, feature-level consistency mapping, and a migration plan for changing consistency levels without service interruption.

Sample Answer

Context & goal: For a multi-tenant SaaS where configuration changes must be strongly consistent (no risk of conflicting or lost config) but analytics/usage metrics can be eventually consistent, apply CAP by choosing per-feature consistency and partitioning to keep availability and performance high while preserving correctness for critical paths.

Partition-time strategy- Partition by tenant (tenant-id) as primary shard key. This isolates blast radius and keeps config reads/writes localized.- Use synchronous, single-leader writes for config within a tenant shard (CP behavior): leader node serializes config changes and replicates to followers; write acknowledged only after durable commit to leader (and optionally one follower) to guarantee consistency.- For non-critical data (analytics/metrics), use AP behavior: write to local replicas or an append-only stream (Kafka) and replicate asynchronously for high availability.

Feature-level consistency mapping- Configuration (feature flags, billing thresholds, security settings): Strong consistency. Enforce linearizability within tenant shard; use leader-based consensus (Raft/Paxos) or a single primary DB per shard.- Access control and authentication metadata used in auth path: Strong or read-with-lease to avoid stale denies.- Analytics, usage metrics, dashboards, aggregates: Eventual. Accept delayed visibility; use event streams, micro-batches, and materialized views rebuilt asynchronously.- Derived counters that influence billing/limits: Strongly consistent or use hybrid (write-ahead ledger + async counters reconciled nightly).

Migration plan (changing consistency without interruption)1. Feature flag the consistency model per-tenant. Implement config gate so you can flip consistency behavior per tenant gradually.2. Shadow mode: Start by duplicating writes — write to both old (current) and new (target) systems. For config, write synchronously to leader and also stream to new consensus cluster without switching reads.3. Read verification: For a pilot set of tenants, read from both systems and compare responses; log divergences for inspection.4. Gradual cutover: Move a small percentage of tenants to read from the new model while still writing to both. Monitor correctness, latency, error rates, and operational metrics.5. Full switchover: When consistent across pilot tenants, switch writes to the new system and disable dual-write. Keep rollback hooks to revert feature flag.6. Reconciliation & cleanup: Run consistency scanners to reconcile any diffs and purge the legacy path once stable.

Operational safeguards- Use strong schema for config changes with versioning and idempotent operations.- Maintain audit logs and causal metadata (vector clocks/monotonic sequence numbers) for reconciliation.- SLOs: Define read/write latency and staleness SLAs per feature; alert on breaches.- Test: Chaos-test replication, leader failover, split-brain, and migration rollback.

Trade-offs- Leader-based strong consistency increases write latency and requires failover handling; mitigated by per-tenant partitioning and leader collocation.- Eventual consistency improves throughput for analytics but requires careful reconciliation when analytics drive billing or limits.

This plan preserves correctness for critical config while maximizing availability and scalability for non-critical data, and gives a safe, observable path to change consistency models without service interruption.

Unlock Full Question Bank

Get access to hundreds of CAP Theorem and Consistency Models interview questions and detailed answers.

Join thousands of developers preparing for their dream job.