Data Consistency and Distributed Transactions Questions
In depth focus on data consistency models and practical approaches to maintaining correctness across distributed components. Covers strong consistency models including linearizability and serializability, causal consistency, eventual consistency, and the implications of each for replication, latency, and user experience. Discusses CAP theorem implications for consistency choices, idempotency, exactly once and at least once semantics, concurrency control and isolation levels, handling race conditions and conflict resolution, and concrete patterns for coordinating updates across services such as two phase commit, three phase commit, and the saga pattern with compensating transactions. Also includes operational challenges like retries, timeouts, ordering, clocks and monotonic timestamps, trade offs between throughput and consistency, and when eventual consistency is acceptable versus when strong consistency is required for correctness (for example financial systems versus social feeds).
MediumTechnical
32 practiced
Describe a practical design to implement idempotency keys for multi-step workflows that cross service boundaries and message queues (e.g., client HTTP -> API gateway -> Kafka -> worker -> DB). Explain where keys are generated, persisted, checked, expired, and how to handle retries and failure scenarios.
Sample Answer
Requirements & goals:- Ensure operations across HTTP -> API GW -> Kafka -> workers -> DB are idempotent (at-least-once delivery from Kafka), minimize duplicate side-effects, bounded storage, support retries and eventual cleanup.Design overview (high level):- Client generates a UUIDv4 or ULID idempotency-key (idempotency-key header) per user-intent (not per transport attempt). Keys are opaque to services.- API Gateway validates format and TTL, then persists a lightweight idempotency record in a centralized Idempotency Service (or DB) before accepting the request.- Gateway publishes message to Kafka including the idempotency-key.- Workers consume messages and consult the same Idempotency Service to decide to process, return cached result, or mark in-progress.Where keys are generated:- Generated by client (recommended) to tie retries across network hops and clients. Optionally, if client cannot, API Gateway can generate a server-side key and return it to client for future retries.Where keys are persisted:- Central Idempotency Store (fast KV like Redis for short TTL + durable backing like Postgres/Cassandra for longer-term audit). Schema: key -> {status: PENDING|IN_PROGRESS|COMPLETED|FAILED, created_at, updated_at, result_reference (pointer to DB row or response), attempt_count, expiry_ts}.Where keys are checked:- API Gateway: check to reject immediate duplicate submissions (return cached response if COMPLETED).- Kafka producer: attach key to message; no duplicate suppression at broker level.- Worker: atomically transition status PENDING -> IN_PROGRESS (compare-and-set) before performing side-effects. If CAS fails, read status and behave accordingly (another worker processing).Atomicity & consistency:- Use CAS / optimistic locking or lightweight distributed transaction on Idempotency Store to guarantee single executor.- For critical DB writes, include idempotency-key as unique constraint on target DB table (e.g., unique(idempotency_key)) as secondary protection; write should be upsert guarded by key.Expiration & retention:- Short-term: keep PENDING/IN_PROGRESS for max_processing_time (e.g., 1 hour). COMPLETED: keep for business TTL (e.g., 7 days) to serve retries. Use TTL in KV + background job to move to archival DB if needed.Retries & failure handling:- Client retries with same key — API Gateway returns cached COMPLETED response or requeues when status is FAILED depending on policy.- Worker crash after CAS to IN_PROGRESS: lease concept — set in_progress_until; if expired, another worker can take over by CAS IN_PROGRESS->IN_PROGRESS with incremented attempt_count.- If worker succeeds: write side-effect (DB) and update idempotency record to COMPLETED atomically (write DB then update idempotency record; if DB supports transactional outbox, use it to ensure atomic visibility). Alternatively, perform DB write with unique idempotency_key then set COMPLETED referencing DB row id.- If worker fails permanently: set status FAILED and include error metadata; decide if client can retry manually.Observability & operations:- Emit metrics: duplicate_requests, CAS_conflicts, retries, expired_leases.- Expose admin endpoints to inspect/force-complete/fail keys.- Backpressure: API Gateway should throttle if idempotency store is saturated.Trade-offs:- Centralized store simplifies checks but is a single dependency; mitigate with sharding and caches.- Relying solely on DB unique constraints is robust but increases load on core DB and complicates semantics for multi-step workflows.This pattern provides deterministic, recoverable processing across service boundaries while bounding storage and offering pragmatic failure and retry semantics.
MediumSystem Design
31 practiced
Design a distributed transaction approach for a bank transfer within a region that touches two independent account services owned by different teams. Compare Two-Phase Commit (2PC) with a saga-based approach: outline implementation steps, operational complexity, failure modes, and make a recommendation as a Solutions Architect.
Sample Answer
Requirements (clarify): transfer money within a region touching two independent account services owned by different teams. Strong consistency desirable for user-facing balance; high availability and clear operator boundaries required. Regulatory auditability and idempotency also required.Two-Phase Commit (2PC)- Implementation steps: 1. Coordinator starts transaction, sends prepare to both account services. 2. Participants lock/update resource and respond PREPARED or ABORT. 3. If all PREPARED, coordinator sends COMMIT; otherwise sends ROLLBACK. 4. Participants finalize and release locks.- Operational complexity: centralized coordinator, distributed locks, need for persistent logs, blocking behavior if coordinator or participant fails; cross-team deployment coordination for protocol support.- Failure modes: coordinator crash leaving participants in PREPARED (blocking); network partition causes long-held locks and reduced availability; complex recovery needed; harder live schema or service upgrades.- Suitability: provides strong atomicity but brittle for cross-team independent services.Saga-based (orchestration) (compensating transactions)- Implementation steps: 1. Orchestrator issues debit to Account A (local transaction). 2. If success, orchestrator issues credit to Account B. 3. On any failure, orchestrator issues compensating action(s) (e.g., refund) to revert completed steps. 4. All steps are idempotent and logged for audit.- Operational complexity: simpler participant requirements (local transactions + compensating API), asynchronous flow, visibility into state machine; requires robust orchestrator, clear compensating logic owned by each team.- Failure modes: eventual consistency window where balances temporarily inconsistent; compensations may fail or partial effects remain (need retries, manual reconciliation); requires careful design for idempotency and side-effects (notifications, risk checks).- Suitability: more operationally resilient across independent teams; fits microservices and team autonomy.Recommendation (Solutions Architect)- For bank transfers requiring strict synchronous atomicity (e.g., regulatory intraday settlement) and where teams can adopt coordinated protocol and tolerate lower availability: 2PC, but only with strong operational SLAs, automated recovery, and timeouts to avoid indefinite blocking.- For typical customer transfers in-region where team autonomy, availability, and evolutionary deployments matter: prefer Saga orchestration. Implement: - Central orchestrator service with durable state machine and audit logs. - Idempotent, compensating APIs on each account service. - Visibility/alerts for stuck compensations and automated retry policy + reconciliation job. - SLA: aim for "eventual consistency within X seconds" and tie UX to transfer states (pending/settled).This balances operational risk and team independence while meeting business needs.
HardTechnical
34 practiced
Explain session guarantees (read-your-writes, monotonic reads, monotonic writes, write-follows-reads). Propose an implementation strategy for client SDKs to provide these guarantees in a multi-region replicated datastore, including how to persist metadata across devices and handle token expiry.
Sample Answer
Start with concise definitions, then propose a practical SDK design and handling for multi-region replicas.Session guarantees- Read-Your-Writes (RYW): after a client writes, subsequent reads by that client reflect that write (possibly after replication).- Monotonic Reads: a client never sees older versions after seeing a newer one.- Monotonic Writes: a client’s writes are applied in the order issued.- Write-Follows-Reads (WFR): if a write follows a read, the write is ordered after the read’s observed state.SDK implementation strategy (high level)1. Metadata model (compact and portable)- Per-client causal token: a vector-clock-like structure or a single hybrid logical clock (HLC) timestamp per region + client sequence number. Represent as {lastSeenHLC, lastWriteSeq, originRegion}.- Operation sequence numbers for monotonic-writes and RYW.- Optional per-key causal metadata for fine-grained guarantees.2. Client workflow- On write: SDK increments local writeSeq, attaches causal token (lastSeenHLC, writeSeq) to the request. If using HLC, set write HLC = max(localHLC, serverHLC)+1.- On read: SDK sends current causal token as “wait-for” hint. Server uses token to ensure returned view is at least that causal state (or delays/redirects to a replica that can satisfy it).- On response: server returns updated token (serverHLC, commitSeq). SDK updates persisted metadata.3. Monotonic reads/writes and WFR- Monotonic reads: store lastSeenHLC and refuse to return responses with HLC < lastSeenHLC; SDK requests stronger read from region or waits.- Monotonic writes: attach sequential writeSeq; server applies writes in writeSeq order per client (or enforces via causal dependencies).- WFR: ensure write carries dependencies from last read token so server orders after those reads.4. Persistence across devices- Tokens must be portable and securely persisted: - Short-term: encrypted local storage (keychain/keystore) for same-device. - Cross-device: use a user-authenticated secure sync (e.g., encrypted blob in user’s account / identity provider), with optional user confirmation for sync. - Provide explicit “export/import session” for offline transfer.- Protect tokens cryptographically (signed by server) to prevent tampering.5. Token expiry & refresh- Use bounded TTL for tokens to limit state size. Include expiry timestamp inside token and server signature.- On expiry, SDK attempts token refresh: call auth/refresh endpoint to obtain a new continuing token derived from server’s latest HLC. If refresh fails, either: - Fall back to weaker consistency (documented) and inform application, or - Block reads/writes until token renewed (configurable).- For long-lived offline clients, queue writes locally with local monotonic ordering; on reconnect, send as a batch with causal metadata; server validates and may require reconciliation.6. Server support requirements- Servers must honor causal tokens: either serve from replicas that have applied up to token’s HLC or wait/apply replication.- Provide signed tokens and a “minHLC” / “commit point” in responses.7. Trade-offs and practical notes- Latency vs guarantees: satisfying RYW/WFR across regions may increase read latency (redirects/waits). Allow SDK options: strict vs eventual.- Token size vs granularity: HLC + seq is compact; full vector clocks give stronger causality but larger tokens.- Security: always sign/encrypt tokens; treat tokens as sensitive auth-adjacent data.Example sequence (simplified)- Client A reads region us-east → gets HLC=100 → stores lastSeen=100.- Client A writes value with writeSeq=1 and attaches lastSeen=100 → server assigns commit HLC=110 and returns token (110).- Later reads send token 110 so any read returns state >=110 (RYW satisfied).This design gives the SDK a portable, compact causal token, clear persistence strategies, expiry handling with refresh or configurable degraded behavior, and server-side obligations to enforce guarantees—balancing latency, storage, and security trade-offs.
MediumTechnical
31 practiced
A client needs maximum throughput for analytics ingestion while requiring reasonably fresh user profile data for joins. Propose an architecture that balances throughput and consistency and describe how you would set client expectations and monitor freshness.
Sample Answer
Requirements & constraints:- Maximize ingestion throughput for analytics events (high write volume).- Joins need reasonably fresh user profile data (near real-time, but not strict linearizability).- Balance throughput vs consistency, give measurable SLAs.Proposed architecture (Kappa-style streaming + async profile propagation):1. Ingestion layer: partitioned durable log (Apache Kafka / Kinesis) to accept high-throughput events; producers write idempotently.2. Analytics sink: stream consumers write raw events into cost-optimized append store (S3 / data lake) and real-time analytics engine (Flink / Spark Streaming) for nearline pipelines.3. Profile store (source of truth): transactional OLTP DB (Cloud Spanner / PostgreSQL) for profile updates.4. CDC pipeline: use Debezium or cloud CDC to publish profile change events into Kafka topics.5. Enrichment / join strategies: - Real-time enrich at stream-processing time: stream job consumes event + latest profile-change stream to perform joins with small state stores (RocksDB / embedded KV) that keep recent profile snapshots. - Read-through cache for query-time joins: low-latency cache (Redis / DynamoDB DAX) populated asynchronously from CDC; stream jobs fallback to cache lookups.6. Materialized views: maintain pre-joined, time-bucketed aggregates in OLAP for analytics queries that tolerate small staleness.Why this balances throughput & consistency:- Writes remain append-only to maximize throughput; profile updates are replicated asynchronously, avoiding write amplification on hot ingestion paths.- CDC provides close-to-source ordering for profile changes so stream processors can apply updates incrementally—achieving low tail staleness without blocking ingestion.- Trade-off: reads see "eventual" freshness; most joins will be <X seconds stale depending on pipeline latency rather than synchronously consistent.Client expectations & SLAs:- Define Freshness SLI: e.g., 95th percentile profile freshness ≤ 60 seconds; 99th ≤ 2 minutes. Freshness = time between profile update commit and first analytics job/consumer observing that change.- Define ingestion throughput SLO: sustained X MB/s, peak Y MB/s for Z minutes.- Document eventual-consistency semantics and failure modes (CDC backfill, transient consumer lag).Monitoring & verification:- Instrument metrics: - CDC lag (source commit timestamp → last applied offset) - Kafka consumer lag per partition - Stream processing end-to-end latency (event ingestion → enriched output) - Cache update latency and hit-rate - Freshness probes: synthetic updates to profile store with detectable markers, then measure time until they appear in analytics outputs (end-to-end synthetic SLA tests)- Dashboards & alerts: - Alert if CDC lag > threshold, consumer lag increasing, or synthetic probe misses SLA. - Track percentiles (P50/P95/P99) and trending.- Observability: logs, traces on processing paths; expose per-tenant metrics if multi-tenant.Operational practices:- Backpressure & autoscaling for stream processors; partitioning strategy keyed by user_id to co-locate events and profile state.- Idempotent consumers and exactly-once (or at-least-once + dedupe) semantics where needed.- Graceful degradation: if real-time enrichment lags, flag events as "stale" and route queries to batch-enriched materialized views.Example numbers (for negotiation):- With tuned CDC + stream processing, typical freshness 5–30s; conservative SLA: 95% ≤ 60s.- If client requires sub-second strong consistency, propose hybrid: route critical updates to a synchronous lookup path at cost of throughput/latency.This design gives the client high ingestion throughput by decoupling writes from synchronous profile reads, while CDC + stream-state + caching keeps profile staleness low and measurable.
HardSystem Design
34 practiced
Design a collaborative real-time document editing service and choose a conflict-resolution strategy: Operational Transformation (OT) vs CRDT. Compare their consistency convergence, intention preservation, implementation complexity, metadata overhead, and support for offline editing at scale.
Sample Answer
Requirements & constraints:- Real-time collaborative editing (low-latency updates for many concurrent users)- Strong convergence (all replicas eventually same), preserve user intention when possible- Support offline edits and reconcilation, scale to millions of docs/users- Reasonable metadata overhead, operational complexity must be maintainable for clientsHigh-level architecture:- Clients (web/mobile) ↔ Sync gateway / WebSocket cluster ↔ Collaboration service (session manager, op/merge processor) ↔ Storage (append-only journal + snapshot store) ↔ Search/indices- Optional: CRDT/OT library embedded in client and server for local echo and conflict resolutionCompare OT vs CRDT1) Consistency & convergence- OT: Converges when same transform rules applied and transformation history is consistent; requires central or coordinated transformation to avoid divergence.- CRDT: Strong mathematical convergence (commutative, associative, idempotent ops); no central ordering needed—replicas converge autonomously.2) Intention preservation- OT: Good at preserving high-level intentions (cursor positions, formatting) because transforms can be intention-aware, but tricky under complex concurrent transforms.- CRDT: Focuses on state convergence; intention preservation (e.g., user cursor) requires additional layers and heuristics.3) Implementation complexity- OT: Complex server logic (transformation matrices, control of history, correctness proofs), subtle edge cases when scaling across sharded servers; clients simpler if server centralizes transforms.- CRDT: Simpler correctness model but higher engineering effort to design efficient CRDTs for rich text (tombstones, identifier schemes); easier to implement peer-to-peer/offline-first.4) Metadata overhead- OT: Lower per-operation metadata (position indexes, op id, context vectors), but needs global ordering and version vectors for causality—moderate.- CRDT: Higher per-element metadata (unique identifiers, tombstones, causal contexts). Some CRDTs cause growing tombstone or identifier sizes; requires compaction/garbage collection.5) Offline editing & scale- OT: Offline support possible but requires buffering and complex rebase logic when reconnecting; works best with server mediation.- CRDT: Excellent offline-first support—local ops merge deterministically; scales well in decentralized or multi-shard setups but needs strategies to control metadata growth.Trade-offs & recommendation for enterprise SaaS:- If your priority is offline-first, easy peer sync, and robust convergence at scale (and you can invest in GC/compaction): choose CRDT (e.g., RGA/WOOT variants or sequence CRDTs with bounded metadata like LogootSplit or Yjs/Yjs-like implementations).- If you require maximal intention-preservation for complex collaborative semantics (rich caret behavior), want smaller runtime metadata, and are comfortable centralizing coordination: choose OT (mature in Google Docs, more intuitive cursor handling) but plan for robust sharding and cross-session transform coordination.Operational notes:- Use hybrid approach: CRDT on client for local responsiveness and offline merges; server-side service can compact CRDT metadata, produce canonical snapshots, and apply additional intention-preserving layering (e.g., transform cursors/annotations).- Add background GC, snapshotting, and a compact journal to bound storage growth.- Provide conflict-visualization and deterministic tie-breakers for user-facing ambiguous cases.- Measure: ops/sec, avg latency, metadata growth per doc, reconcilation time after offline period.Final: For a scalable, offline-capable enterprise solution I’d favor a well-engineered CRDT (or Yjs/Automerge variant with GC and snapshotting) augmented server-side to restore some intention semantics. If the client must strictly match legacy Google-Docs behavior and you can centralize transforms, OT is acceptable but operationally heavier at scale.
Unlock Full Question Bank
Get access to hundreds of Data Consistency and Distributed Transactions interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.