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).

MediumSystem Design

38 practiced

Design a saga orchestration for an e-commerce order workflow that touches services: Orders, Payments, Inventory, Shipping. Specify the normal-step flow and compensating actions for failures. Discuss how you ensure idempotency, how you persist saga state, and how you detect and handle partial failures and retries.

Sample Answer

Requirements & constraints:- Atomic user-visible order success across Orders, Payments, Inventory, Shipping.- Services are independent microservices; communication via reliable messaging (e.g., Kafka) and HTTP for commands.- Low-latency for happy path; durable recovery for failures.

High-level orchestration (centralized Saga Orchestrator):Normal flow (steps):1. Orders: Create Order in "PENDING" state (orderId). Orchestrator emits "OrderCreated" event.2. Payments: Authorize payment (reserve funds). On success emit "PaymentAuthorized".3. Inventory: Reserve inventory (decrement available, create reservation). On success emit "InventoryReserved".4. Shipping: Create shipment (booking, get tracking). On success emit "ShipmentBooked".5. Orders: Mark Order "CONFIRMED" and capture payment (or capture earlier depending on business). Emit "OrderCompleted".

Compensating actions (if a step fails):- If Payments fails -> Orders: mark "PAYMENT_FAILED", no further steps.- If Inventory fails after PaymentAuthorized -> Payments: void/rollback authorization (or refund if captured); Orders: mark "FAILED_INVENTORY".- If Shipping fails after InventoryReserved -> Shipping retry; if unrecoverable -> Inventory: release reservation; Payments: refund/void; Orders: mark "FAILED_SHIPPING".- If final capture fails after shipment -> Payments: refund and Orders: mark "COMPENSATED" and notify customer.

Ensuring idempotency:- Each service implements idempotent command handlers keyed by a unique sagaId + step name + requestId. Persist processed requestIds to dedupe.- Use optimistic update with idempotency tokens for external payment gateways; include idempotency-key header.- Idempotent compensation: compensation handlers check state (e.g., only release reservation if reserved) and record compensation done.

Persisting saga state:- Orchestrator stores saga state in durable store (e.g., PostgreSQL or Cassandra) with schema: sagaId, orderId, currentStep, stepStatus map, retries, timestamps, outcome. Events logged for audit.- Use write-ahead log / outbox pattern so orchestrator state changes and outgoing commands are atomic.

Detecting and handling partial failures & retries:- Use at-least-once messaging; services ACK results back to orchestrator.- Retry policy: exponential backoff with jitter for transient errors; configurable max attempts per step.- Distinguish transient vs permanent failures via error codes (e.g., network timeout vs business rejection).- If a step times out, orchestrator marks step "IN_PROGRESS" and schedules retry; after max retries -> run compensations for prior successful steps in reverse order.- Use a dead-letter queue for messages that repeatedly fail; include human-in-the-loop alerts and automated compensation triggers.- Periodic reconciliation job: scan orders stuck in non-terminal states and reconcile by querying services (idempotent read endpoints) and resume or compensate as needed.

Observability & testing:- Emit structured events/metrics for each saga step, success/failure, retries.- Run chaos tests and failure-injection to verify compensations and idempotency.- Add end-to-end integration tests to cover common partial-failure scenarios.

Trade-offs:- Central orchestrator simplifies complex coordination and retry logic; choreography would decentralize but increase coupling on event design.- Persisting full saga state increases complexity but enables robust recovery and audits.

MediumSystem Design

29 practiced

Design a multi-region user profile service that must support 100M users, 50k profile updates per second globally, and 1M reads per second. Requirements: (1) users should see their own updates immediately (read-your-writes) within a region, (2) other users can see updates eventually (within 1 minute), (3) 99th-percentile read latency < 50ms per region. Sketch a high-level architecture, replication strategy, and how you would provide the read-your-writes guarantee without strong global coordination.

Sample Answer

Requirements clarification:- 100M users, 50k global writes/s, 1M reads/s, per-region 99p read <50ms- Strong local read-your-writes (session) for the writer; eventual (<1m) for others- Multi-region scale, no global synchronous coordination

High-level architecture:- Clients -> Regional API Gateway -> Regional Profile Service (stateless) -> Regional Read Cache (Redis/Memcached) + Regional Primary DB (sharded key-value store, e.g., Cockroach/Scylla/partitioned Dynamo-style)- Cross-region async replication bus: per-region Kafka cluster or CDC stream + cross-region Kafka replication (MirrorMaker/cluster linking)- Global metadata service for user home-region mapping (small, strongly consistent, highly-available)

Partitioning & ownership:- Partition by user_id (consistent hashing). Assign a “home” region (usually user’s primary/nearest region) that is the canonical write leader for that user.- Writes from anywhere are routed to the user’s home-region service (gateway proxies or client SDK knows home region via metadata). To avoid extra RTT, allow local-write-forwarding to home-region asynchronously for mobile clients if needed.

Replication strategy:- Home-region stores the authoritative version, emits change events (CDC) to local Kafka, which replicate asynchronously to other regions within 1 minute SLA.- Replicas in other regions apply updates eventually. Use versioned writes (logical timestamp: (home-region-id, monotonic counter) or Lamport) for last-writer-wins and conflict-free merges for multi-field profiles.

Providing read-your-writes without global coordination:- Within the home region: reads after a successful write go to local primary DB or read cache warmed synchronously (write-through) — immediate visibility guaranteed.- If client is in a different region than home: - Client SDK / API Gateway carries a session token with the last-write version (version id). - On reads in non-home region: - Check local cache; if cached version >= session version return it. - If not, either: - Proxy a read to the home-region (fast path, used rarely) OR - Forward the write log entry (or metadata) when the write completed so the remote region can serve the updated value from a local per-session write cache (in-memory or Redis) for that client until replication finishes.- Practical approach: client writes are acknowledged by home-region with the new version id. Client includes version in subsequent reads; regional gateway ensures read-your-writes by consulting a small per-session cache or fetching from home-region if needed. This avoids global strong coordination.

Latency & scaling to meet SLO:- Read 99p <50ms: serve from regional Redis cache; keep profile objects compact; use local sharded caches co-located with API servers.- Scale reads by partitioning across many cache nodes; read replicas per DB shard for cold misses.- Writes 50k/s: scale home-region write capacity by sharding users; use async replication to smooth cross-region load.- Replication latency tuned (batching, high-throughput links) to keep propagation <1 minute.

Failure & consistency considerations:- Home-region failover: elect new home for affected user partitions (metadata service + automated failover). During failover, read-your-writes for in-flight sessions may fall back to proxying to the surviving replica or to clients buffering writes until home returns.- Conflict resolution: since all authoritative writes go to home-region, conflicts are rare. If multi-master allowed temporarily, use vector clocks or CRDTs for safe merge.- Monitoring: track replication lag, 99p read latency, cache hit rates, and per-user write queue lengths.

Why this meets requirements:- Read-your-writes locally: writes acknowledged and stored in home region + local caches or session cache ensure immediate visibility for that user without global sync.- Eventual consistency for others: async replication ensures updates propagate within 1 minute.- Low read latency per region: served from local caches or replicas; only rare reads need cross-region proxy.

HardTechnical

36 practiced

Implement (or outline in Java-style pseudocode) a simplified two-phase commit coordinator that persists its state to disk, sends PREPARE to participants, collects votes, and either COMMITs or ABORTs. Include crash-recovery behavior: on restart the coordinator must consult the log and continue to completion. Describe how you avoid duplicate messages and ensure idempotent operations at participants.

Sample Answer

Approach: coordinator persists a per-transaction log to disk (append-only) recording state transitions. It sends PREPARE (vote-request) to participants, waits for votes (with retry/timeouts), decides COMMIT only if all vote YES, persists decision, then sends GLOBAL-COMMIT or GLOBAL-ABORT. On restart the coordinator replays the log to resume: if decision already written, resend final decision until acknowledgements; if in PREPARE phase, resend PREPARE and wait for remaining votes. Use unique transactionId and per-message phase tag to avoid duplicates. Participants make operations idempotent by persisting last seen txId + decision and acknowledging requests.

Java-style pseudocode:

java

enum State { INIT, PREPARED, COMMIT, ABORT }
class Log {
  void append(String entry) { /* fsync append */ }
  List<String> readAll() { /* replay on startup */ }
}

class Coordinator {
  String txId;
  State state;
  Log log;
  List<Participant> participants;
  Map<String,String> votes = new HashMap<>(); // participantId -> "YES"/"NO"

  Coordinator(String txId, List<Participant> parts, Log log) {
    this.txId = txId; this.participants = parts; this.log = log;
    recover();
  }

  void recover() {
    for(String e: log.readAll()){
      // entries: "TXID:PHASE:DETAIL" e.g. "t1:VOTE:nodeA:YES", "t1:DECIDE:COMMIT"
      apply(e);
    }
    if(state == State.COMMIT || state == State.ABORT){
      // ensure final decision sent
      sendFinalDecisionUntilAcks();
    } else if(state == State.PREPARED || state == State.INIT){
      // resend PREPARE to missing participants and await votes
      sendPrepareAndCollect();
    }
  }

  void start() {
    log.append(txId + ":START");
    sendPrepareAndCollect();
  }

  void sendPrepareAndCollect(){
    log.append(txId + ":PHASE:PREPARE_SENT");
    for(Participant p: participants) sendPrepare(p);
    waitForVotesWithRetries();
    if(allYes()) {
      log.append(txId + ":DECIDE:COMMIT");
      state = State.COMMIT;
      sendFinalDecision("COMMIT");
    } else {
      log.append(txId + ":DECIDE:ABORT");
      state = State.ABORT;
      sendFinalDecision("ABORT");
    }
  }

  void receiveVote(String participantId, String vote){
    // idempotent: ignore duplicate votes beyond first recorded
    if(!votes.containsKey(participantId)){
      votes.put(participantId, vote);
      log.append(txId + ":VOTE:" + participantId + ":" + vote);
    }
  }

  void sendFinalDecision(String decision){
    for(Participant p: participants) {
      sendToParticipant(p, "GLOBAL_" + decision, txId);
    }
    // wait for ACKs or keep retrying; coordinator can garbage collect after all ACKs
  }
}

Participant behavior (idempotence & duplicate suppression):- Persist lastSeenTxId -> state/decision and whether prepared.- On PREPARE(txId): if txId seen and prepared -> reply YES; if seen and decided -> reply stored decision; else run local prepare (write "PREPARED" durable), reply YES/NO.- On GLOBAL_COMMIT/ABORT(txId): if already decided same -> ACK; if different or unseen, apply or roll back idempotently, persist decision, ACK.

Crash-recovery reasoning:- Coordinator durable log ensures decision is never lost. After crash, replay determines exact point and continues without violating atomicity.- Participants persist their prepare/decision so repeating PREPARE or GLOBAL_DECISION is safe (idempotent).- Duplicate messages avoided by including txId and phase and having participants ignore repeated identical requests (or reply with cached response).- Liveness: coordinator retries and uses timeouts; in two-phase commit blocking can occur if coordinator permanently fails — this design requires an external leader election or coordinator recovery policy for production.

Durability/performance notes:- Log entries must fsync before critical transitions (e.g., before sending GLOBAL_DECIDE).- To reduce duplicate work, participants store and respond with cached ACKs.- For scale, use participant batching or asynchronous ACKs and garbage collect logs after durable commit confirmed by all.

MediumTechnical

34 practiced

Describe hybrid logical clocks (HLC) and how they combine physical time with logical counters to produce monotonic timestamps resilient to small clock skew. Explain how HLC can be used to provide causal ordering and why it's preferable over pure physical clocks in some distributed systems.

Sample Answer

Hybrid Logical Clocks (HLC) combine wall-clock timestamps with a small logical counter to produce monotonically increasing, low-latency timestamps that tolerate small clock skew. Each HLC timestamp is a pair (physical, logical). On local event:- read now = physical_clock()- if now > physical: set physical = now, logical = 0- else: physical stays same, logical += 1On receiving a remote HLC (p_r, l_r):- now = physical_clock()- physical = max(now, p_r, local.physical)- if physical == local.physical == p_r: logical = max(local.logical, l_r) + 1- else if physical == local.physical: logical = local.logical + 1- else if physical == p_r: logical = l_r + 1- else logical = 0

Example (python-like):

python

def update_on_receive(local, remote, now):
    p = max(now, remote.p, local.p)
    if p == local.p == remote.p:
        l = max(local.l, remote.l) + 1
    elif p == local.p:
        l = local.l + 1
    elif p == remote.p:
        l = remote.l + 1
    else:
        l = 0
    return (p, l)

Why this helps:- Monotonicity: timestamps never go backward even if clocks skew slightly.- Causality: if event A causally precedes B (message sent/received), B’s HLC will be greater than A’s HLC, so HLC captures happens-before without full vector clocks.- Efficiency: requires constant-size metadata (two integers) vs O(N) vectors, and leverages physical time for compactness and real-time reasoning.

Prefer HLC over pure physical clocks because physical clocks can drift and break monotonicity (causing anomalies like time moving backward after synchronization). HLC is preferable when you need causal ordering with low overhead and low added latency, while maintaining timestamps that are roughly real-time. Edge cases: large skew beyond tolerance may force dependence on logical counter growth — systems should bound accepted skew or fall back to stronger synchronization if needed.

HardSystem Design

27 practiced

Compare CRDTs and Operational Transformation (OT) approaches for building a collaborative rich-text editor. Discuss convergence guarantees, metadata growth, undo/redo complexity, latency of local edits, and design implications for presence/awareness features.

Sample Answer

Requirements clarification:- Real-time collaborative rich-text editor with concurrent edits, offline/online, per-user undo/redo, low local latency, and presence (cursors, selections, user colors). Persistence and moderate scale (thousands of documents, dozens of concurrent users).

High-level comparison (CRDT vs OT) across requested dimensions:

Convergence guarantees- CRDT: Strong mathematical convergence — replicas that apply all operations (in any order) deterministically reach same state (commutative ops). Good for peer-to-peer/offline-first.- OT: Convergence achieved via transformation functions and a stable intent model; requires well-designed transform functions and agreement on operation order (often server-mediated). More delicate when operations are complex (rich-text formatting).

Metadata growth- CRDT: Typically retains per-character identifiers (timestamps, replica IDs), tombstones for deletions; metadata grows linearly with edits and can bloat without compaction/garbage collection. Complex CRDTs for rich text need more metadata.- OT: Operations are deltas; metadata overhead is smaller and transient (operation logs, versions). Storage of history is optional; compaction easier.

Undo/redo complexity- CRDT: Global undo is hard — need causal/intent tracking and possibly tombstone-aware inverse ops; per-user local undo is feasible but requires mapping from visible positions to identifiers. Implementations often maintain operation causality trees.- OT: Undo/redo maps naturally to operation history with transform-aware inverse operations; per-user undo integrated with operational history and server sequence numbers.

Latency of local edits- CRDT: Local edits are immediately applied (local-first) with no server round-trip; great perceived latency.- OT: OT can be local-first (optimistic) too, but requires buffering and transform on acknowledgment—more complexity; naive OT can cause more rebase glitches.

Design implications for presence/awareness- CRDT: Presence maps to identifiers (cursor points to an element id) — robust across concurrent edits. But mapping requires keeping identifiers alive (tombstones) or translating when elements are garbage-collected.- OT: Presence typically attaches to positions (indices) and relies on transforms to shift positions on concurrent edits; simpler index transforms but needs careful handling for rich formatting boundaries.

Trade-offs and recommendation- Choose CRDT if offline-first, peer-to-peer, or minimal server coordination is key and you can invest in metadata GC and sophisticated undo semantics.- Choose OT if you want smaller metadata, easier undo/redo semantics, and are comfortable operating a server to serialize/transform ops; often simpler for enterprise client-server deployments.- Hybrid approach: use CRDT for fast local state + a server-side compaction/garbage-collection service, or use OT with CRDT-like identifiers for robust presence.

Implementation notes- For rich-text, prefer element-based models (spans with attributes) rather than per-character CRDT to limit metadata.- Implement background GC and periodic compaction; store operation snapshots to bound log growth.- Design presence as first-class (cursor objects with resilience to transforms/identifier remapping) and test edge cases (formatting boundaries, multi-selection).

Unlock Full Question Bank

Get access to hundreds of Data Consistency and Distributed Transactions interview questions and detailed answers.

Join thousands of developers preparing for their dream job.