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
23 practiced
Describe an approach to implement 'read-repair' proactively (background reconciliation) in a distributed store without impacting foreground read latency. How would you schedule repairs, prioritize hot keys, and ensure repairs converge safely?
Sample Answer
Framework / approach:- Treat proactive read-repair as a background anti-entropy service that reconciles divergent replicas without blocking foreground reads. Use a prioritized scheduler, safe reconciliation protocol, and rate controls so foreground latency is unaffected.Design summary:1. Metadata + detection- Maintain lightweight per-key/version metadata (last-write timestamp, vector clock or monotonic version, tombstone flag). Track divergence signals from reads (soft errors) and periodic sampling via Merkle trees for large ranges.2. Scheduling & prioritization- Two-tier queue: hot-key fast queue and cold-key batch queue.- Hot-key detection: real-time counters (approximate, e.g., Count-Min Sketch) and recent read QPS. Hot keys get higher priority but also stricter rate caps to avoid impacting clients.- Use weighted token-bucket rate limiter per node and global concurrency limits. Schedule repairs during spare CPU/I/O windows; opportunistically on read path only if budgeted and non-blocking.3. Repair algorithm & safe convergence- Fetch versions from quorum (or use hinted handoff if a replica is down). Reconcile using deterministic conflict resolution (last-write-wins with vector-clock merge or application-level merge). Write reconciled state back to minority replicas via idempotent upserts with causal metadata.- Use version checks (compare version before write) and conditional writes to avoid overwriting newer concurrent updates.- For deletes/tombstones, retain TTL to ensure safe propagation before compaction.4. Efficiency & scale- Use Merkle trees for large-range anti-entropy to avoid full scans.- Batch repairs for nearby keys, deduplicate concurrent repair tasks via in-memory de-dup map.- Exponential backoff for repeated failures, escalate to operator alerts if a replica is persistently unreachable.5. Observability & safety- Emit metrics: repair latency, bytes repaired, repairs/sec, contention errors. Throttle when tail latency or CPU crosses thresholds.- Run repairs under admission control so foreground read path gets priority; measure read P99 and dynamically reduce repair throughput when P99 rises.Example flow (hot key):- Read hot-key triggers divergence metric increment.- Scheduler enqueues repair to hot queue with priority weight.- Token-bucket allows a small repair write; fetch quorum versions, deterministically merge, conditional write to lagging replicas, mark key reconciled.- If concurrent update occurred, abort and requeue after backoff.Outcomes and trade-offs:- Proactive repairs reduce long-term staleness and background anti-entropy cost. Trade-offs: must carefully tune rate limits and prioritization to avoid hurting foreground latency. Deterministic merges and conditional writes ensure convergence and safety.
MediumTechnical
30 practiced
Explain idempotency in distributed write paths. Provide at least three strategies for ensuring idempotent writes from mobile clients in the presence of retries and partitions, and discuss how each interacts with consistency guarantees.
Sample Answer
Idempotency means that applying the same write multiple times has the same effect as applying it once — crucial for mobile clients that retry over flaky networks to avoid duplicates or data corruption.Three strategies for mobile clients:1) Client-generated idempotency keys- Approach: Client generates a UUID or deterministic key (e.g., hash of payload + timestamp) and sends it with each write. Server stores seen keys and ignores duplicates (or returns previous result).- Example: Payment or event ingestion: POST /events {idempotency-key: abc, body: {...}}- Consistency interaction: Enables at-most-once semantics from client perspective even if transport retries. Requires server-side de-dup table (stateful) which must be durable and replicated; with eventual replication you may see duplicates across partitions until de-dup state converges—so stronger consistency (linearizable de-dup store) yields better global guarantees at cost of latency.2) Make operations naturally idempotent (design PUT semantics or create-or-replace)- Approach: Design the API so writes are “set to value” instead of “increment” (e.g., PUT resource with full state or use deterministic upserts keyed by client-generated id).- Example: Uploading latest sensor snapshot: PUT /device/123/state {value: X}- Consistency interaction: Works well with eventual consistency because repeated writes converge to same state. If ordering matters, you may need versioning (last-write-wins) or timestamps; under weak clocks this can cause lost updates unless you combine with causal metadata.3) Server-side deduplication via write-ahead logs / sequencers- Approach: Client obtains a short-lived sequence token or monotonic sequence from a sequencer (or the server stamps a monotonic sequence) and server uses that ordering to apply idempotent merges or ignore repeats.- Example: Mobile batch uploader requests upload-token, then sends records labeled with sequence numbers.- Consistency interaction: If the sequencer is a single source of truth (strong consistency), you get ordered, exactly-once semantics. If token issuance is partitioned or lost, you need retries for token acquisition; distributed sequencers add complexity but can be scaled with consensus (Paxos/Raft) to preserve strong guarantees.Trade-offs and practical notes:- Storage overhead: de-dup tables and sequencers require retention policies (TTL) to bound storage.- Fault tolerance: Client keys + server de-dup easier to implement than globally consistent sequencers, but give weaker global guarantees under partitions.- Hybrid approach: Combine idempotency keys with causal versioning (vector clocks or last-writer-id) to mitigate lost updates and preserve convergence under eventual consistency.In practice for data pipelines, prefer client idempotency keys for ingestion (easy, scales), design idempotent operations for immutable event logs, and reserve sequencers/consensus when strict ordering and exactly-once semantics are required.
MediumTechnical
39 practiced
Design a monitoring dashboard and SLOs to detect consistency regressions for a replicated key-value store. Specify at least five metrics or alerts that would help catch issues like stale reads, write loss, or split-brain early.
Sample Answer
High-level approach- Combine real user-observed SLOs (what clients see) with internal replication/health metrics and synthetic canary checks. Use active probes (canary writes + read-after-write) and passive telemetry (replication lag, quorum errors, divergence metrics). Alert on deviations that statistically indicate stale reads, write loss, or split-brain.SLOs (examples)- Read-after-write SLO: 99.9% of read-after-write checks must return the latest value within 500 ms.- Successful-write durability SLO: 99.95% of client writes acknowledged as durable (replicated to quorum) within 5 s.- Replication convergence SLO: 99.9% of partitions must have follower lag < 2 s.- Consistency-incident budget: no more than 1 consistency incident per 30 days (an incident = a verified stale-read or lost write affecting >1% of requests).Dashboard layout- Top row: SLO compliance widgets (Read-after-write %, write durability %, replication convergence %)- Middle row: Synthetic checks and error trends (canary results, checksum diffs)- Bottom row: Node/cluster health (quorum status, leader count by partition, partition split-brain indicators)Key metrics/alerts (5+ with rationale)1) Read-after-write probe failure rate (canary keys)- Metric: % of canary reads that return old value within X ms after write.- Alert: >0.1% failures sustained for 5 min OR absolute count > 10 in 1 min.- Detects stale reads or replication delay from client perspective.2) Replication lag (per follower, per partition)- Metric: tail (p95/p99) of log-index/LSN lag in seconds.- Alert: any partition p99 lag > 5s OR > 1% partitions with lag > 2s.- Early sign of delayed replication causing stale reads or potential write loss if leader fails.3) Quorum/acknowledgement failures & write commit discrepancies- Metric: rate of writes that get NACKs or timeout vs acknowledged by quorum.- Alert: sustained increase >3x baseline or >0.01% of writes time out in 1 min.- Catches partial write replication and possible write loss.4) Divergence / checksum mismatch across replicas- Metric: periodic per-partition checksum/hash comparison between leader and a random follower; number of mismatched partitions.- Alert: any non-zero mismatches or >0.1% partitions mismatched.- Detects split-brain or bit-rot leading to inconsistent state.5) Leader count anomalies / split-brain indicator- Metric: number of leaders per partition (should be 1) and nodes claiming leadership.- Alert: any partition with >1 leader OR rapid leader flapping (>5 leadership changes in 1 min).- Direct detector of split-brain and instability that can cause lost writes.6) Tombstone / persisted-op divergence and repair backlog- Metric: backlog of unapplied replication ops, count of tombstone mismatches, unresolved repair jobs.- Alert: backlog growth > threshold or unapplied ops older than X hours.- Detects long-term divergence and repair failures.7) Client-observed consistency errors & anomalies- Metric: client error types (stale-read detected by client checks, version conflicts, unexpected nulls).- Alert: spike >2x baseline or absolute >0.05% of requests.- Ties internal health to user impact.Implementation notes / instrumentation- Use synthetic canary writes with monotonic version or unique IDs per write to detect staleness deterministically.- Compute rolling baselines and use both absolute thresholds and relative anomaly detection to avoid alert fatigue.- Correlate alerts with topology events (network partitions, GC pauses, leader elections) in dashboard for triage.- Automate periodic background consistency scans with sampled keys and provide per-partition root-cause links.Why this set- Covers client-visible correctness (canary, client errors), replication mechanics (lag, ack), and systemic failures (split-brain, divergence). Alerts are tuned to catch early deviations while providing actionable signals for on-call responders.
MediumTechnical
28 practiced
Implement a simple vector clock comparison function in Python. Given two vector clocks represented as dicts, return -1 if clock A happened-before B, 1 if A happened-after B, 0 if concurrent, and 2 if equal. Assume keys are node ids and missing entries imply zero.
Sample Answer
To compare two vector clocks, iterate over the union of node keys, compare A[k] vs B[k] (treat missing as 0), and track whether A is strictly less for any key and whether A is strictly greater for any key. Results:- if all equal → 2- if A strictly <= B for all keys and at least one < → -1 (A happened-before B)- if A strictly >= B for all keys and at least one > → 1 (A happened-after B)- otherwise → 0 (concurrent)Key points:- Linear in number of distinct node ids: O(n) time, O(n) space to build the union (n = |keys|).- Handles missing keys as zero.Edge cases:- Empty dicts → equal (2).- Partial overlap of keys handled correctly.Alternative: return richer enum or pair of booleans if callers need more detail.
python
def compare_vector_clocks(A: dict, B: dict) -> int:
"""
Compare two vector clocks A and B.
Returns:
-1 if A happened-before B
1 if A happened-after B
0 if concurrent
2 if equal
Missing keys imply zero.
"""
keys = set(A) | set(B)
a_less = False
a_greater = False
for k in keys:
av = A.get(k, 0)
bv = B.get(k, 0)
if av < bv:
a_less = True
elif av > bv:
a_greater = True
# early exit: if we already saw both directions, they're concurrent
if a_less and a_greater:
return 0
if not a_less and not a_greater:
return 2
if a_less and not a_greater:
return -1
if a_greater and not a_less:
return 1
return 0 # fallback (shouldn't reach)MediumTechnical
24 practiced
Explain how vector clocks can be used for conflict detection and why they do not always provide a deterministic conflict resolution. Discuss how you would integrate vector clocks with application-level merge logic.
Sample Answer
Vector clocks are a compact logical-timestamp mechanism for tracking causality across distributed writers. Each replica (writer/node) keeps a vector of counters indexed by replica ID. On a local write the node increments its counter and attaches the vector clock to the object. To detect conflicts, compare two clocks: A <= B (every entry in A ≤ corresponding entry in B) means A causally precedes B (no conflict); if neither A ≤ B nor B ≤ A they are concurrent — a detected conflict.Why they don’t deterministically resolve conflicts:- Vector clocks only encode causality, not intent or semantics. When two updates are concurrent they’re “incomparable” but there’s no automatic rule about which value is “correct.”- Concurrent updates may be complex (e.g., two independent edits to different fields of a JSON doc), and picking one deterministically (like last-writer-wins by coarse timestamp) can lose information or violate business semantics.- Size and dynamic membership: with many writers clocks grow and may be pruned, which can lose causal detail and cause ambiguous comparisons.Integrating vector clocks with application-level merge logic (practical approach):1. Store: Persist the object together with its vector clock and a small history or tombstone metadata per record in your data store or event log.2. Conflict detection: On ingest/replication, compare incoming and stored vector clocks. If descendant, accept; if concurrent, mark as conflict and route to merge logic.3. Merge strategies (choose per domain): - Composable field-level merges: for structured data, merge non-overlapping fields automatically; for overlapping fields apply domain rules (max, sum, concatenation, pick latest by business timestamp). - CRDTs where possible: if data type can be modeled as a CRDT (PN-counter, G-set, OR-set), they provide deterministic merges. - Application merge functions: implement deterministic, idempotent merge functions that take both versions + clocks and return merged state + updated vector clock (typically element-wise max). - Manual or human-in-the-loop for ambiguous/high-value records: surface to owners with diff + metadata.4. Practical considerations: - Use replica IDs tied to logical writers (not ephemeral pods), and compact vectors (garbage collect stopped writers). - Persist metadata and makes merge functions idempotent for retries. - Instrument metrics on conflict rate to tune upstream partitioning or update patterns.Example (conceptual): two JSON updates A and B concurrent → merge function:- merged.fields = union of fields; for conflicting fields call businessResolve(fieldName, A.value, B.value, clocks)- merged.clock = elementwiseMax(A.clock, B.clock) + optionally increment local IDThis keeps causality info, avoids silent data loss, and lets domain rules produce deterministic, meaningful results when pure logical timestamps cannot.
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.