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.
HardTechnical
31 practiced
Design a developer SDK for a distributed key-value store that surfaces consistency guarantees (strong, causal, eventual). The SDK should provide primitives to request guarantees, helpers for migrations, testing utilities to simulate partitions, and instrumentation hooks. Describe key API shapes and developer ergonomics.
Sample Answer
Requirements and approach:- Provide explicit per-operation consistency selection (strong, causal, eventual).- Make safe defaults (causal) and easy opt-in/out.- Offer migration helpers to transition keys/namespaces between consistency modes.- Testing utilities to simulate partitions, latency, clock skew.- Instrumentation hooks (metrics, traces, events) for SLO/alerting.API shapes (pseudo-Go / Python friendly):Client construction (safe defaults + policy override)Per-operation primitivesConsistency policy object (reusable)Migration helpers- dry-run analyze: scans keyspace and reports cross-consistency access patterns.- staged-migrate(namespace, from, to, options) with progress, reversible checkpoints.- automatic tombstone/repair thresholds for moving to stronger guarantees.Testing utilities / chaos primitives- Local test harness that can inject: - Partition(nodeIDs...), heal() - Delay(node, ms) - ClockSkew(node, ms)- Deterministic record-and-replay to reproduce failures in CI.Example:Instrumentation hooks- Built-in metrics: operation_latency{consistency}, staleness_distribution, conflict_rate, migrate_progress- Tracing spans: sdk.start_span("kv.get", attrs={"consistency":"causal"})- Event callbacks: onInconsistencyDetected(callback), onFailover(callback)- Expose context propagation for distributed SLOs (trace IDs, request origin)Developer ergonomics & SRE considerations- Defaults lean to safer consistency (causal) to avoid surprising stale reads.- Clear errors: return structured error types (StaleRead, Unavailable, Retryable).- Non-blocking migrations with progress APIs and rollback tokens.- SDK integrates with Prometheus/OpenTelemetry, emits semantic metrics and traces for SLO dashboards.- Documentation: migration playbooks, cost/perf trade-offs (latency vs. freshness), sample configs for common deployments.- CI integration: provide test fixtures to run chaos tests as part of pipeline, with assertions on SLOs.Trade-offs- Strong consistency increases latency and availability risks; SDK surfaces cost so teams can choose per-use-case.- Simulating partitions in CI adds flakiness unless harness supports deterministic modes — provide both random-chaos and deterministic-replay.This design balances developer ergonomics, SRE needs for observability and safe migration, and realistic testing of distributed failure modes.
go
// Go-like
cfg := sdk.Config{DefaultConsistency: sdk.Causal, Tracing: true, MetricsNamespace:"kvsvc"}
client := sdk.NewClient(cfg)python
# Python-like
val = client.get("user:123", consistency="strong", timeout_ms=2000)
client.put("user:123", value, consistency="causal")
txn = client.txn(consistency="strong") # multi-key atomic under chosen guaranteego
pol := sdk.ConsistencyPolicy{Mode: sdk.Eventual, MaxStalenessSec:30}
client.getWithPolicy(key, pol)python
harness.partition(["replica-2","replica-3"])
harness.delay("replica-1", 200)MediumSystem Design
28 practiced
Design the replication and consistency approach for a globally-accessible shopping cart so users rarely lose items and have a pleasant UX. Discuss per-user data locality, conflict resolution, eventual vs strong guarantees, and how to handle offline clients and merges.
Sample Answer
Requirements:- Per-user cart globally available with low read/write latency- Minimize lost items and confusing UX (duplication, stale views)- Support offline clients and merges- High availability and partition toleranceHigh-level approach:- Geo-partition by user: each user’s cart has a home region (based on signup or recent activity). Primary write target = home region; reads served from nearest replica with fast cache invalidation.- Store: a distributed, multi-master-capable DB with CRDT support (or use append-only event store + materialized view). Use per-cart CRDT (Observed-Remove Set or LWW-Element-Set with client timestamps + causal metadata).Replication & consistency:- Async geo-replication of cart state to other regions for reads; background convergence via CRDT merge ensures eventual consistency.- For low-latency strong-ish guarantees on writes from non-home region: route writes to home region (fast proxy + smart routing) when network latency acceptable; otherwise accept local write with per-operation causal metadata and replicate.- Use causal ordering (vector clocks or Lamport + session IDs) to preserve user intent for sequential operations.Conflict resolution:- Use CRDT semantics so merges are deterministic and user-friendly: adds are preserved, removals require causal knowledge (OR-Set avoids resurrecting removed items). For quantity updates, use last-writer-wins with monotonic client-increment operations or per-item counters (PN-Counters).Offline clients & merges:- Client maintains an operation log (ops: add, remove, update quantity) with monotonically increasing local sequence + device ID.- On reconnect, client sends ops; server applies with causal checks and merges into CRDT; server returns resolved cart and conflict metadata for client UI.- UI displays merge hints: e.g., “We merged items added while offline” and lets user resolve ambiguous quantity conflicts.Operational considerations (SRE):- SLOs: 99.9% write availability, p95 read latency < 50ms region-local.- Monitoring: ingest metrics for replication lag, divergence rate (conflicting ops/sec), merge frequency, and client error rates. Alert on replication lag > threshold and CRDT convergence delays.- Backups & audit: keep append-only write log for replay and debugging.- Capacity & scaling: shard by user-id, replicate partitions across regions; autoscale proxy/router to avoid hotspots.- Safety nets: tombstone expiry policy for removed items; mechanism to convert to strong consistency (synchronous write to home) for critical flows (checkout) to guarantee correctness.Trade-offs:- Eventual+CRDTs maximize availability and UX (rare lost items) but can show short-term divergence; mitigated by routing writes to home region and clear UI merge messaging.- Strong global consistency would increase latency and reduce availability—restrict to checkout where correctness is critical.
MediumTechnical
24 practiced
Describe Raft leader failover behavior: what happens to in-flight writes, how logs are reconciled, and which safety guarantees are preserved. As an SRE, what operational knobs and metrics do you tune to reduce failover-induced unavailability?
Sample Answer
Raft leader failover behavior — what happens and whyOverview:- When a leader fails, followers detect missing heartbeats and start a timed election. One follower becomes candidate, solicits votes, and a new leader is elected after a majority grants votes. Raft preserves strong consistency (linearizability) by requiring a leader to have the latest committed log entries before serving new writes.In-flight writes:- Writes acknowledged to the client (committed) remain durable — followers that had replicated the entry and a majority persisted it. Partially replicated or uncommitted in-flight entries (not stored on a majority) are not guaranteed: the new leader will overwrite or discard them during log replication and reconciliation. Clients may see retried or failed requests.Log reconciliation and safety:- Raft’s log matching and leader’s AppendEntries enforce that a new leader only accepts entries that match a majority prefix. If a candidate lacks some committed entries, election restrictions (leader election restriction: candidates must have up-to-date logs via term/vote rules) prevent data loss. Conflicting uncommitted entries get truncated on followers to match the leader’s log; committed entries are never lost once a majority had them.Preserved guarantees:- Safety (no two different committed entries at same log index) — preserved.- Linearizability for committed operations — preserved.- Liveness depends on timeliness and stable leader election (can be affected by network partitions).SRE operational knobs and metrics to reduce failover-induced unavailabilityKnobs:- Election timeout tuning: increase timeouts to reduce needless elections in high-latency environments; set randomized ranges to avoid split votes.- Heartbeat interval: shorter heartbeats detect failures faster but increase overhead; balance per workload.- Leader stickiness: prefer leader transfer rather than abrupt elections during planned maintenance.- Snapshotting/compaction frequency: reduce log size to speed recovery and replication.- Quorum placement: colocate quorum nodes or use topology-aware placement to minimize cross-region latency.- Throttle or backpressure client writes during unstable periods; tune retry/backoff on clients.Metrics and alerts:- Election rate (elections/sec) and election latency- Leader change frequency and duration of leaderless windows- Commit latency (median/p99) and tail latencies- Replication lag per follower (bytes/entries behind)- Log growth and snapshot frequency- RPC failure rates/timeouts and network RTT distribution- Disk I/O and persist latencyOperational practices:- Use canary and staged maintenance with leader transfer- Auto-promote healthy nodes with up-to-date logs- Maintain runbooks: for stuck elections, check clock drift, network partitions, disk stalls- Simulate failures (chaos testing) to validate timeouts and SLOsSummary:- Committed writes survive; uncommitted in-flight ones may be lost and retried. Raft’s election and log-matching preserve safety. As an SRE, tune timeouts, heartbeats, quorum topology, snapshotting, and monitor elections/replication/commit latencies to minimize failover-induced unavailability.
EasyTechnical
23 practiced
Explain quorum reads and writes in the context of N replicas. State the R + W > N rule, why it provides read-after-write safety, and describe a scenario where picking R and W poorly can cause unacceptable latency or unavailability.
Sample Answer
Quorum reads/writes: with N replicas, a write must be acknowledged by W replicas, and a read returns results from R replicas (or waits for R responses). The R + W > N rule ensures every read and write sets have at least one overlapping replica.Why R + W > N gives read-after-write safety:- If a client writes and receives W acknowledgements, at least W replicas hold the latest value.- A subsequent read that waits for R responses must contact R replicas. Because R + W > N, the read set intersects the write set at ≥1 replica, so at least one responder has the latest value. By using versioning/timestamps and choosing the newest value among responders, the read sees the just-written value (read-after-write consistency).Operational implications / bad choices:- Example poor choice: N=5, W=1, R=1 (R+W=2 ≤ N). Writes succeed with a single replica; reads may contact a different replica and get stale data → no read-after-write safety.- Latency/unavailability trade-off: choosing W=N and R=1 gives strong durability but write latency equals slowest replica and writes fail if any replica is down (reduced availability). Conversely W=1, R=N makes reads slow and susceptible to long tail latency.- SRE consideration: pick R and W to meet SLOs (latency and availability) and consistency needs. Common compromise: N=3, W=2, R=2 (R+W=4>3) gives good balance: tolerant to one failure, moderate latency.
HardSystem Design
29 practiced
Design caching and invalidation strategies for a high-throughput service that needs low-latency reads for most keys but strong consistency for a small fraction. Discuss choices: write-through caches, invalidation pub/sub, short TTLs, or client-side validation, and analyze their failure modes and operational costs.
Sample Answer
Requirements & constraints:- High-throughput, low-latency reads for most keys.- Strong consistency (linearizability/near-zero staleness) for a small fraction of keys.- SRE concerns: availability, operational complexity, observability, recovery/runbooks.Recommended hybrid design (practical SRE-focused):1. Default: cache-aside (read-through on miss) with long TTLs and background refresh for hot keys.2. Strong-consistency path: write-through + synchronous invalidation for the small subset of critical keys (or bypass cache entirely).3. Global invalidation/coordination: reliable pub/sub for invalidation messages + versioned keys (or ETags) for client-side validation.4. Safety nets: short TTL or background validation for medium-critical keys and client-side "If-None-Match"/ETag checks for recently-updated reads.Components and flow:- Primary datastore (source of truth) with durability.- Distributed cache (e.g., Redis cluster) for low-latency reads.- Invalidation pub/sub (Kafka/Redis Streams) to broadcast writes/invalidations.- API servers implement: - For non-critical keys: cache-aside read; write updates DB then publish invalidation asynchronously. - For critical keys: write-through (write DB and cache in same transaction or use a two-phase commit pattern), or always read from DB.- Use versioned cache keys: key:vN so consumers can detect stale cache and reject if version mismatch.Analysis of approachesWrite-through caches- Pros: Stronger consistency for writes because cache updated atomically with write; fewer invalidations.- Cons: Higher write latency; harder to scale writes; operational cost because write path includes cache. Failure modes: cache unavailability can block writes if synchronous—use fallback to DB with compensating operations. Requires careful retries and idempotency.Invalidation pub/sub- Pros: Scales well; low read latency remains. Keeps cache small and fresh.- Cons: Requires at-least-once delivery handling (idempotency). Failure modes: - Lost messages => stale cache (use periodic TTL or reconciliation). - Out-of-order messages => older invalidation could overwrite newer values (use versions). - Broker outage => invalidations queue up => staleness spike.- Ops cost: run/monitor message broker, metric invalidation lag, ensure retention and consumer lag monitoring.Short TTLs- Pros: Simplicity; bounds staleness window.- Cons: Higher DB load; increased cache churn; potential for cache stampede. Failure modes: TTL too short => RPS spike to DB; TTL too long => unacceptable staleness for critical reads.- Ops: tune TTL per key class; circuit breakers and rate-limiters to protect DB.Client-side validation (ETag/If-None-Match)- Pros: Low overhead for reads when cache indicates possible staleness; supports conditional fetch.- Cons: Extra round-trip for validation in some flows; complexity in clients. Works best when data sizes are small or when cache can serve stale data while validation occurs (stale-while-revalidate).- Failure modes: clients not honoring validation => stale reads; more complexity in SDKs.Failure modes and mitigations (SRE focus)- Lost invalidation messages: use persisted broker with consumer offsets + replay; add periodic reconciliation job comparing small-key set checksums.- Ordering/race: include monotonically-increasing version or write timestamp; on processing, apply only if newer.- Cache or broker outage: degrade gracefully — route critical reads to DB; use bulkhead/resilience patterns, circuit breakers on caches; autoscale caches.- Cache stampede/thundering herd: use request coalescing (single-flight), randomized jittered TTLs, and pre-warming hot keys.- Increased DB load (due to TTLs or cache misses): protect DB via read replicas, rate limiting, and fallback caches.- Data corruption / partial writes: write-ahead logs and idempotent writes; health checks to detect divergence.Operational costs & observability- Metrics: cache hit ratio, invalidation latency, broker consumer lag, DB QPS, read tail latency, percent of reads served by DB for critical keys.- Instrumentation: trace write → invalidation → cache update to measure propagation time; alert on invalidation lag and cache hit ratio drops.- Runbooks: degrade-to-DB plan for cache/broker failures; automated failover for brokers and caches; scripts for replaying invalidations; reconciler to detect and fix divergence.- Capacity/cost: write-through increases cache IO and DB write latency; pub/sub adds broker cost; shorter TTLs increase DB cost.Trade-offs / guidance- Use write-through (or bypass cache) only for the small set that requires strong consistency to avoid write-path latency explosion.- Use pub/sub invalidation + versioned keys for most keys: low latency reads and scalable invalidation.- Enforce idempotency and versions to handle at-least-once delivery and ordering.- Combine short TTLs or periodic reconciliation as a safety net for lost invalidations.- Invest in observability (invalidations lag, divergence checks) and automated mitigations (replay, circuit breakers).Example operational policy (concise)- Class A (critical, ~1% keys): strong consistency — write-through or DB-read-only; monitor 99.9th latency, alert on any cache involvement.- Class B (important): cache-aside + pub/sub invalidation + short TTL (30s) + versioning.- Class C (bulk): cache-aside with longer TTLs + background refresh.This hybrid balances low-latency reads for most traffic while ensuring strong consistency where needed, limits operational blast radius, and provides observable safety nets and runbooks to recover from broker/cache failures.
Unlock Full Question Bank
Get access to hundreds of CAP Theorem and Consistency Models interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.