Eventual consistency and conflict resolution Questions
Design systems that don't require global consensus but achieve eventual consistency. Understand replication strategies for eventual consistency: multi-master replication, read repair, anti-entropy repair. Handle conflicts: last-write-wins, vector clocks, application-level conflict resolution (e.g., CRDTs). At Staff level, discuss: When is eventual consistency acceptable? How do you handle the window where different replicas see different data? What's the user experience during inconsistency?
MediumTechnical
72 practiced
Design a strategy to provide 'read-your-writes' (session consistency) for a global service when sticky sessions cannot be guaranteed. Describe both client-side token approaches and server-side techniques, trade-offs in latency, and how to prevent token replay or misuse.
Sample Answer
Goal: guarantee read-your-writes (RYW) across a geo-distributed system where client requests may hit any replica and sticky sessions are not available.Client-side token approaches- Write-token (causal token): after a successful write, client receives a lightweight token encoding a logical timestamp / version vector entry (e.g., write-id = {region:seq} or hybrid logical clock).- Client attaches token on subsequent reads (Authorization or custom header). Any replica that serves the read must ensure it has applied at least that version before responding; if not, it either (a) forward the read to a replica that has the version, (b) wait/apply replication, or (c) return 202 + retry-after.- Token types: single scalar (HLC/timestamp) for monotonic writes, or per-object version vector for multi-key causal consistency. Trade-offs: scalar tokens are compact but weaker for concurrent multi-region writes; vectors provide stronger causality at higher size/complexity.Server-side techniques- Versioned storage: store per-item versions and track global/region advance (HLC, Lamport, or vector clocks).- Read-path enforcement: - Catch-up: if replica's local applied-version < token.version, either block until caught-up, or proxy to an up-to-date replica. - Read repair/fetch-from-primary: fetch latest committed state before answering.- Metadata propagation: lightweight per-region watermarks (maxAppliedHLC) to quickly test satisfiability of token without per-object checks.- Fast-path: if token <= watermark, serve immediately; else mitigate.Latency vs consistency trade-offs- Low-latency: proxying to nearest replica and returning stale reads yields lower latency but breaks RYW.- Stronger RYW: waiting for replication/catching-up increases read latency proportional to cross-region replication delay.- Hybrid: return cached/stale result with a background catch-up and a warning code — good for UX when eventual consistency acceptable.- Choosing HLC vs vectors: HLC reduces header size and comparison cost => lower latency checks; vectors give finer causal guarantees but larger headers and slower comparisons.Preventing token replay and misuse- Bind tokens to client/session: include client id and signature (HMAC) and short expiry. Token = {write_version, client_id, expiry, nonce, signature}.- Nonce or monotonic counters: server rejects reused nonces or tokens older than client's last-seen version to avoid replay.- Signature/KID: servers validate signature with shared keys or rotate keys via KMS; use TLS+auth to prevent leakage.- Scope tokens: per-object or per-tenant scoping prevents cross-tenant replay.- Rate-limiting / anomaly detection: detect unusual reuse patterns, reject or re-authenticate.Operational notes- Instrument metrics: token-staleness, proxy-hits, wait-times to tune thresholds.- Client SDK: hide complexity—retry logic, backoff, token management.- Security: enforce TLS, short token TTL, rotate signing keys, log verification failures.Recommendation- For most global services, use HLC-based signed tokens with per-region watermarks and proxy/catch-up server behavior. This balance gives compact tokens, simple comparators, reasonable RYW guarantees, and predictable latency trade-offs; fall back to per-object vectors only for heavy causal-multi-key workloads.
MediumSystem Design
68 practiced
Design an anti-entropy process for a distributed key-value store containing 10 million keys across hundreds of nodes. Cover: scheduling (how often, stagger), prioritization (hot keys first), bandwidth control, verification (checksums), and how to resume after node crashes. Explain your choices and expected operational costs.
Sample Answer
Requirements & goals:- Ensure eventual consistency across ~10M keys on hundreds of nodes with minimal production impact: low added latency, bounded bandwidth, prioritize high-value ("hot") keys, reliable verification and resumable work after crashes.High-level approach:- Use anti-entropy via Merkle-tree based sync per shard + opportunistic incremental sync for hot keys. Each node hosts shard-level merkle roots and maintains per-key version vector or timestamp.Scheduling:- Two-tier schedule: 1) Continuous light-weight background: every shard compute Merkle root every 5–15min (staggered across nodes by hash(shard) % window to avoid spikes). 2) Full reconciliation sweep: low-priority full scans across all shards nightly/weekend, distributed by consistent-hash ring segments to different windows.Prioritization:- Track key access frequency and write-rate via local counters + sampled telemetry. Maintain a hot-key queue; hot keys trigger immediate point-to-point anti-entropy (push/pull), cold keys batched by shard.Bandwidth control:- Rate-limit sync traffic per node (configurable e.g., 50–200 Mbps) and per-peer backoff. Use adaptive window: lower throughput during peak production (detected via CPU/latency signals). Compact diffs (rsync-like deltas) and compress payloads.Verification:- Use Merkle trees for shard-level divergence detection; then per-key checksum (e.g., CRC64 or SHA1) before apply. For writes, use version/timestamp to decide final state; for conflicting versions, bubble to conflict-resolution policy (last-write-wins or CRDTs).Resume & fault tolerance:- Anti-entropy tasks are idempotent and checkpointed: maintain per-peer reconciliation cursor (Merkle subtree ranges, last-processed key ranges). On crash, node reads cursor and resumes; use write-ahead-log for local changes so reconciliation can re-check recent windows. Retries with exponential backoff and tombstone retention window to avoid resurrection of deleted keys.Operational costs & trade-offs:- CPU: Merkle tree computation ~O(n_keys_per_shard) but incremental updates limit cost. Memory: store small trees + cursors. Network: typical steady-state proportional to divergence; budget ~1–5% of aggregate dataset per day for full reconciliation; tune by schedule and bandwidth caps. Complexity: Merkle + per-key checksums reliable but more complex than full-table scouring; CRDTs add development cost but simplify conflict resolution.Why these choices:- Merkle trees minimize transferred data by isolating differing ranges; hot-key direct sync reduces user-visible inconsistency; staging, rate-limits and staggered scheduling avoid thundering herd; checkpointing ensures fast resume after crashes with bounded read amplification.
HardTechnical
59 practiced
Design a comprehensive test plan to verify correctness of a CRDT-based collaborative editor at scale. Include unit testing strategies, property-based/fuzz testing, model-based tests for convergence, distributed integration tests, and performance/stress tests. Explain how to detect subtle merge bugs and regressions.
Sample Answer
Requirements clarification:- Target CRDT types (sequence CRDT e.g., RGA/WOOT/LSEQ or OT-like), expected offline/partial connectivity, targeted client count (tens of thousands), latency/SLA, durability and storage model.Test-plan overview:1. Unit tests (deterministic)- Isolate core CRDT ops: insert, delete, tombstone compact, identifier allocation, merge/compose functions.- Table-driven cases for edge identifiers, concurrent deletes/inserts, reordering. Mock clock/ID generators to force collision scenarios.- Invariants asserted: id uniqueness, monotonic causal metadata, commutativity of pairwise merge.2. Property-based & fuzz testing- Use Hypothesis/QuickCheck to generate random op sequences, concurrent streams, network reorders and drops.- Properties: convergence (all replicas equal after applying same multiset of ops), preservation of intention (where spec applies), invariant preservation (no lost ops).- Fuzz mutated metadata (timestamps, site IDs) to find parser/merge edgecases.3. Model-based / formal convergence tests- Build a reference model: simple abstract state machine (ops as events) and a verifier that applies CRDT spec (commutative semilattice) to check strong eventual consistency.- Use model checking (TLA+/PlusCal or Alloy) for small-scale exhaustive states to find corner-case merges (concurrent tombstones vs reinserts).- Generate counterexamples and translate into regression unit tests.4. Distributed integration tests- Multi-process testbed (Docker/Kubernetes) simulating N replicas, network partitions, message duplication, delays, reorder, and crashes.- Scenarios: long offline edits then sync, client reboots, forwarded ops, partial delivery.- Assert eventual convergence and causal-delivery semantics within SLA windows.5. Performance & stress tests- Load generators simulating thousands of clients, mixed read/write workloads, varying op sizes.- Measure op latency, merge time, memory growth (tombstone accumulation), snapshot/compaction throughput.- Run endurance tests to detect memory leaks and compaction regressions.Detecting subtle merge bugs & regressions- Golden divergence detection: run randomized distributed runs, capture final state hashes per replica; on mismatch, run delta-debugging to minimize ops to reproducible failing sequence.- Causal/timing-sensitive bugs: inject controlled clock skews and duplicate IDs; compare against reference model to identify where invariant breaks.- CI integration: every bug-finding sequence becomes a deterministic replay test stored as a regression case with seeded RNG and network trace.- Telemetry & assertions in prod: hash-window checkpoints, operational counters for tombstone count, merge-conflict rate; auto-alert on divergence anomalies to trigger replay tests.Tooling & process- Use Hypothesis + TLA+/model checker + chaos test harness (Jepsen-like) + Kubernetes infrastructure.- Automate generation of minimized repros into unit tests; run nightly large-scale distributed fuzz; gate PRs with fast unit/property checks.- Prioritize test coverage for merge/compaction codepaths and metadata handling (ID allocation, serialization).This layered strategy ensures correctness across code units, probabilistic edge cases, formal convergence guarantees, realistic distributed behavior, and performance at scale while enabling fast regression detection and reproducible debugging.
MediumTechnical
73 practiced
Recommend UX patterns and client-side behaviors to surface data staleness and reduce confusion when eventual consistency causes divergent results. Provide examples specifically for a social feed and a collaborative document editor, including how to notify users and allow recovery.
Sample Answer
Start with principles: make staleness visible, explain cause briefly, minimize disruption, and provide clear recovery paths. Patterns and client behaviors:Global and contextual indicators- Global banner: “You’re viewing cached data — reconnecting…” with retry button. Use low-contrast red/orange for urgency.- Per-item staleness badges/timestamps: “Updated 3m ago • might be stale” on feed posts or document sections.Social feed (eventual consistency scenarios)- Optimistic UI for user actions (like/post/comment) with transient state and spinner; show “Saved locally — syncing” and a small error icon if server later rejects.- Reconciliation toast: “New posts available — refresh” + “Merge” to insert new items above while preserving your scroll position.- Inline conflict hint: if an edited comment changed on server, show both versions collapsed with “View server version / Keep mine / Merge”.Collaborative document editor- Real-time sync using OT/CRDT; when divergence detected, show unobtrusive “Working offline / Changes queued” indicator.- Visual diff pane for conflicting ranges with “Accept remote / Keep local / Open manual merge.” Allow automatic three-way merge for non-overlapping edits.- Version history + undo/redo across sync boundaries; provide “restore last-synced” and ability to export current local copy.Notifications & recovery UX- Non-blocking toasts for automatic reconciliations; blocking modal only for unrecoverable conflicts.- Provide one-click actions: Retry, Refresh, Merge, Restore.- Audit trail: show why divergence happened (latency, partition) and timestamp of last successful sync.Implementation notes & trade-offs- Balance frequency of staleness checks vs. battery/network cost: use exponential backoff and push notifications for updates.- Prefer CRDTs/OT for low-latency editors; fallback to server-side conflict resolution for feeds.- Log telemetry for incidence of conflicts to tune UX.These patterns surface staleness, reduce surprise, and give users clear, low-cost recovery options while remaining feasible at scale.
HardSystem Design
112 practiced
Propose a hybrid architecture that uses a consensus system (Paxos/Raft) for metadata and CRDTs for application state in a collaboration platform. Draw the data flow: where metadata is stored and why, how CRDT state is exchanged, how failure scenarios are handled, and operational considerations.
Sample Answer
Requirements:- Strong consistency for metadata (permissions, document ownership, version pointers, user presence)- Low-latency, highly-available collaborative editing (concurrent edits, offline support)- Automatic conflict resolution for document state- Operational observability and easy recoveryHigh-level architecture:- Metadata service: Raft quorum cluster (3+ nodes) providing linearizable reads/writes via leader; stores metadata in a replicated durable store (WAL + RocksDB / SQLite).- CRDT engines: Deployed at clients and edge/relay servers; each document state represented by a CRDT (e.g., RGA/WOOT for sequences, OR-Set for objects).- Relay/Sync layer: Stateless gateways that forward CRDT ops, persist op logs for catch-up, and subscribe to metadata changes.- Long-term storage: Periodic snapshots of CRDT state stored in object store; metadata has canonical pointers to latest snapshot and oplog index.Data flow (ASCII):Client <--> Relay/Edge <---> CRDT Peers (Gossip / PubSub) | v Metadata Raft Cluster (writes/reads) | v Durable metadata DB / Snapshot pointersWhere metadata is stored and why:- Use Raft for metadata to provide strong consistency for access control, document canonical versions, and collaborative session coordination. Metadata stored in replicated WAL-backed KV store for durability and quick leader reads.How CRDT state is exchanged:- Clients apply local ops immediately and send op-ids to relay via WebSocket/HTTP. Relays broadcast ops via pub/sub (NATS, Kafka, or CRDT-aware gossip). Each op is commutative/ID’ed so replicas converge. Relays keep an append-only oplog per document for new joiners/offline clients to catch up; occasional compaction creates snapshots and updates metadata pointers via Raft.Failure scenarios:- Raft leader failure: new leader election (<500ms typical) — metadata writes unavailable during election; reads served by followers with linearizability via leader read-index or lease.- Relay down: clients failover to other relays; relays are stateless so no metadata loss.- Client offline: client buffers CRDT ops locally; upon reconnect, sends ops; CRDT merge is deterministic.- Oplog/snapshot inconsistency: use checksums in metadata; if checksum mismatch, fetch latest snapshot + apply oplog from object store.- Split-brain: prevented by Raft quorum; CRDTs tolerate partitions and converge once connectivity restored.Operational considerations:- Monitoring: Raft metrics (leader, commit index, election latency), relay throughput, oplog backlog, CRDT op rate, snapshot durations.- Scaling: shard documents by id across multiple Raft clusters and relay clusters; use consistent hashing for routing.- Backups: periodic metadata backups and snapshot retention policy; store snapshots in immutable object store with versioning.- Security: sign CRDT ops, enforce access via metadata ACLs validated by relay, encrypt in transit/storage.- Upgrades: migrate CRDT formats with versioned ops and transformation functions; perform rolling leader migrations.- SLOs: specify metadata write latency and CRDT op TTL; use rate limiting to protect Raft during bursts.Trade-offs:- Strong metadata consistency simplifies ACLs and coordination but adds brief unavailability during elections.- CRDTs give offline and low-latency UX but require careful op-size management and compaction.- Hybrid design balances correctness and user experience for collaboration at scale.
Unlock Full Question Bank
Get access to hundreds of Eventual consistency and conflict resolution interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.