Distributed Systems Fundamentals Questions
Core theory that underpins any multi-node system: the CAP and PACELC theorems, consistency models (strong, causal, eventual), partitioning, replication, and the fundamental tradeoffs between latency, availability, and consistency. Covers how network partitions, clock skew, and partial failure change the reasoning compared to single-node systems. This is the vocabulary layer every distributed design question builds on.
Explain the saga pattern for coordinating a transaction across multiple services without a distributed commit protocol: choreography versus orchestration, and how compensating actions undo partial work. Walk through a concrete order-fulfillment sequence (reserve inventory, charge payment, schedule shipment) and what happens when the shipment step fails.
Sample Answer
Direct Answer
A saga coordinates a business transaction that spans multiple services by breaking it into a sequence of local transactions. Each service commits its own step immediately with no cross-service lock held, and if a later step fails, the saga undoes the steps that already succeeded by running a compensating action for each one, in reverse order. This trades strict, all-or-nothing atomicity for eventual, recoverable consistency and loose coupling between services.
Choreography vs. Orchestration
- Orchestration: a central coordinator issues each step as a command to the relevant service and decides, based on that service's response, what to do next, including which compensations to trigger if something fails. The whole workflow lives in one place, which makes it easier to see, test, and reason about end to end.
- Choreography: there is no central coordinator; each service publishes an event when it finishes its local step, and whichever service is subscribed to that event reacts by doing its own step and publishing its own event in turn. This avoids coupling every service to a central coordinator's command contract, but it scatters the workflow logic across services, so understanding or changing the whole sequence means tracing through several services' event subscriptions instead of reading one place.
| Aspect | Orchestration | Choreography |
|---|---|---|
| Control | Central coordinator issues commands and tracks saga state | Distributed: each service reacts to events it's subscribed to |
| Visibility | Whole workflow visible in one place | Scattered across each service's event handlers |
| Coupling | Services coupled to the coordinator's command contract | Services coupled to the event schema and topic |
| Adding a new step | Change the coordinator | Every service that needs to react to the new step's event has to change |
Worked Trace: Order Fulfillment When Shipment Fails (Orchestration Style)
Order O123, three steps: reserve inventory, charge payment, schedule shipment.
- Orchestrator sends ReserveInventory(O123, sku=42, qty=1) to Inventory. Inventory reserves the unit and replies Reserved.
- Orchestrator sends ChargePayment(O123, $50) to Payment. Payment captures the charge and replies Charged.
- Orchestrator sends ScheduleShipment(O123) to Shipping. Shipping tries to allocate a carrier slot and replies Failed: no carrier capacity.
- The orchestrator now runs compensations in reverse order. It sends RefundPayment(O123, $50) to Payment, undoing step 2. Payment replies Refunded.
- It sends ReleaseReservation(O123, sku=42, qty=1) to Inventory, undoing step 1. Inventory replies Released.
- The orchestrator marks order O123 as Failed and notifies the customer.
The same sequence in choreography looks like this instead: Inventory reserves and emits InventoryReserved(O123). Payment, subscribed to that event, charges and emits PaymentCharged(O123). Shipping, subscribed to PaymentCharged, tries to schedule and, on failure, emits ShipmentFailed(O123). Both Payment and Inventory are subscribed to ShipmentFailed: Payment independently issues its own refund and emits PaymentRefunded(O123), and Inventory independently releases its reservation and emits ReservationReleased(O123). No single component ever holds the full picture of the workflow; each service only knows what to do when it sees an event it's subscribed to.
Trade-offs and Pitfalls
- Every forward step and every compensating action has to tolerate being retried, since at-least-once delivery means ChargePayment could be delivered twice; this is a system-property requirement on the saga's steps, a separate concern from how an external API exposes idempotency to its own callers.
- The saga's state, meaning which steps have completed and which compensations are pending, needs to be durably persisted, whether by a central orchestrator or by each participant in a choreography, so that a crash and restart can resume the saga correctly instead of leaving it stuck partway.
- Not every action has a true inverse. Compensating a shipment step after the package has physically left the warehouse can't undo the physical fact, only correct the system's record and possibly trigger a real-world return process; a senior design puts the hardest-to-compensate steps as late as possible in the sequence.
- Choose a saga when the steps naturally live in separate services or databases and each one can be given a real, working compensating action. Reach for a real distributed transaction only when an intermediate, partially-applied state genuinely cannot be tolerated and you can afford a synchronous locking protocol across every participant, which a saga specifically avoids.
Explain what a CRDT (Conflict-free Replicated Data Type) is and why state-based and operation-based CRDTs let replicas converge to the same value without any coordination between them. Walk through two concrete examples: a grow-only counter (G-Counter) and an observed-remove set, and describe what property of the underlying merge operation makes convergence guaranteed.
Sample Answer
A CRDT (Conflict-free Replicated Data Type) is a data structure whose update and merge operations are mathematically guaranteed to make every replica converge to the same value, with no locking, coordination, or central authority, as long as every update eventually reaches every replica. State-based CRDTs ship the whole replica state and merge it with a commutative, associative, idempotent join function; operation-based CRDTs ship individual operations that must themselves be commutative and be delivered with causal ordering. A grow-only counter (G-Counter) and an observed-remove set (OR-Set) are the two simplest concrete examples of this guarantee in action.
Why convergence is guaranteed
Convergence works because the merge operation is commutative (order doesn't matter), associative (grouping doesn't matter), and idempotent (merging a state with itself changes nothing), so applying merges in any order, any number of times, produces the same final state. Formally, this kind of merge is called a join, and a replica's state is modeled as an element of a join-semilattice: a partially ordered set where the join always computes the least upper bound of two states. That is the actual property behind convergence without coordination: it is not that conflicts never happen, it is that the merge function is defined so a conflict has exactly one well-defined resolution no matter how or when it gets computed.
G-Counter (grow-only counter)
- State: a vector with one non-negative integer slot per replica, c[i].
- Local update: a replica only ever increments its own slot.
- Merge: element-wise maximum across the two vectors.
c′[i]=max(c1[i],c2[i])
- Read: sum across all slots.
total=∑ic[i]
- Because each slot only ever grows for its own replica, taking the max per slot can never lose an increment either side already recorded.
OR-Set (observed-remove set)
- State: a set of (element, unique tag) pairs, split into an add-set and a remove-set of tags.
- Add(e): mint a fresh tag, insert (e, tag) into the add-set.
- Remove(e): copy every tag currently observed for e into the remove-set; it removes only tags this replica has actually seen, never tags added elsewhere that haven't arrived yet.
- Merge: union the add-sets, union the remove-sets.
- An element counts as present if it has at least one tag in the add-set that is not in the remove-set.
Naming the comparators explicitly
| Strategy | How a conflict is resolved | What it guarantees | Where it fails |
|---|---|---|---|
| Last-write-wins (LWW) | Keep the value with the later timestamp, discard the other | Deterministic if clocks are totally ordered | Silently discards a concurrent write; a clock-skewed node can win even though its update happened earlier in real time |
| Vector clocks | Compare vectors to detect that two writes are concurrent | Tells you a conflict exists | Detection only. It does not resolve the conflict; an application or a person still has to pick a winner |
| CRDTs (this answer) | The merge function is commutative, associative, and idempotent by construction | Automatic, coordination-free convergence | Only works for data types whose semantics fit that mold; does not generalize to arbitrary business logic |
| Application-specific merge | Domain code decides, for example union two shopping carts, or keep the higher of two account balances | Correctness tailored to the domain | Bespoke code per data type; nothing about it is automatic or reusable |
Worked example: G-Counter convergence
Three replicas A, B, C start at (0,0,0):
- Replica A processes 2 local increments: its state becomes (2,0,0).
- Replica B processes 3 local increments, concurrently, before hearing from A: (0,3,0).
- Replica C stays idle: (0,0,0).
A and B exchange state and merge (element-wise max): merge((2,0,0),(0,3,0)) = (2,3,0). Read = 2+3+0 = 5. C later merges with that result: merge((0,0,0),(2,3,0)) = (2,3,0). Read = 5. Whichever order the three replicas merge in, the final vector is (2,3,0) and the read is 5, exactly matching the 2+3=5 real increments actually performed. No increment is lost and none is double-counted.
Worked example: OR-Set add and remove race
Replicas R1 and R2 have already converged on a set containing 'milk' with tag t1. The two replicas are then partitioned from each other:
- R1's user removes 'milk': remove-set gains {t1}, the only tag R1 has ever observed for 'milk'.
- R2's user, unaware of the removal, re-adds 'milk': add-set gains a brand-new tag {t2}, so the add-set is now {t1, t2}.
On merge: add-set = {t1, t2} (union), remove-set = {t1} (union). 'milk' is present because t2 is in the add-set and not in the remove-set. This is the correct outcome: R2's re-add introduced a tag the remover never saw, so it survives, exactly the observed-remove semantics the name describes.
Trade-offs & pitfalls
- Storage and bandwidth: every element needs extra metadata (a vector slot per replica for counters, a unique tag per add for sets), and removed elements don't disappear until a garbage-collection pass establishes causal stability across replicas.
- The edge case that catches teams out: CRDTs don't compose across non-commutative operations. A G-Counter or OR-Set is safe because the operations that define it (increment, tagged add and remove) are commutative by construction. But if you build an append-only log CRDT and then bolt on an application-level 'delete the last 3 entries' operation defined by position, that composition is not well-defined under concurrency: 'last 3' means something different on each replica depending on how many entries have been concurrently appended there at the time the delete runs, so two replicas can end up deleting different entries even though each individually applied a correct-looking CRDT merge. The fix is the principle OR-Set already uses: target deletions by a stable element identifier, never by position or count.
- When to avoid: anywhere a global invariant spans multiple keys (uniqueness, a balance that must never go negative), or the business logic genuinely isn't commutative. CRDTs solve convergence, not arbitrary correctness.
Design an approach that gives a user read-your-writes (session consistency) for their own profile updates in a system that replicates writes asynchronously across regions. Cover how you'd track what the client has already seen (session tokens, sticky routing, or version vectors), and how you'd handle token expiry, a failed request whose outcome is unknown, and a client that migrates to a new region mid-session.
Sample Answer
Direct answer
Give the client a small piece of state recording what it has already seen, not what time it wrote at, and require every subsequent read to prove it reflects at least that much. Read-your-writes (RYW), the guarantee that once a client observes or performs a write, every later read in that same session reflects it or something newer, can be built with sticky routing, a session token carrying a single write position, or a version vector, and only the version vector survives a client moving to a different region mid-session.
Mechanism 1: sticky routing
Pin the entire session to the region the write went to. Simple to build, but availability degrades if that region becomes unreachable, and it fails outright the moment the client is routed to a different region.
Mechanism 2: session token with a scalar position
After a write, the client receives a token carrying (origin_region, write_position), a per-region monotonically increasing sequence number or log offset. On a later read, the serving replica compares its own applied position for that origin region against the token; if it has caught up, it answers locally, otherwise it waits, proxies to the origin, or serves from a short-lived read-after-write cache holding the write's payload directly. This works as long as the client only ever wrote in one region during the session.
Mechanism 3: version vectors
Instead of one scalar number, the token carries a vector of positions, one per region that could plausibly have accepted a write during the session: for example VV = {A: 5, B: 3}, meaning "I have seen everything through position 5 from region A and position 3 from region B." Any replica in any region can check RYW correctness against the whole vector, which is exactly what's needed once the client is no longer talking to the region it originally wrote in.
Worked example: a write in region A, then a migration to region B
sequenceDiagram
participant Client
participant A as Region A
participant B as Region B
Client->>A: write profile
A-->>Client: ack, VV={A:5,B:0}
Client->>A: read profile
A-->>Client: local answer (A already at 5)
Note over Client: migrates to Region B
Client->>B: read profile, token VV={A:5,B:0}
Note over B: B's replicated-from-A cursor = 3, behind 5
B-->>Client: wait or proxy to A
Note over B: cursor catches up to 5
B-->>Client: local answer, VV={A:5,B:new}
- Client, in a session against Region A, writes a profile update. Region A's local write-sequence advances to position 5. The client's version vector becomes
VV = {A: 5, B: 0}: it has seen its own write at A's position 5, and has a floor of 0 for anything from B, since it hasn't observed anything from there yet. - Client reads its profile again, still talking to Region A: A's own applied position for itself is already at least 5 (it just accepted the write locally), so it answers directly.
VVis unchanged. - The client's connection migrates to Region B mid-session. It presents its token
VV = {A: 5, B: 0}to Region B. - Region B checks whether its own cursor for replication-from-A has reached position 5. Suppose B's cursor currently sits at
A: 3, meaning it has only applied A's writes through position 3; the write at position 5 hasn't propagated across the inter-region link yet. - Since B's cursor (3) is behind what the token requires (5), Region B cannot honor read-your-writes from its current local state. It has three honest options: wait or briefly poll until its A-cursor reaches 5, proxy this one read to Region A directly, or check a short-lived read-after-write cache keyed by the write's own id if one exists. It must not simply answer from its current, stale-relative-to-the-token state.
- Once B's cursor from A reaches position 5, whether by waiting or because the async pipeline naturally caught up, B answers locally and updates the client's token going forward to
VV = {A: 5, B: <B's own current position>}.
Token expiry
Bound the token's validity window, for example expiring it after a period of client inactivity. On expiry, the client should not try to remember its "seen" state indefinitely; it should treat expiry as the session ending and fall back to whatever the default consistency level is for a fresh session. Indefinitely-lived tokens would force every replica to retain unbounded replication-position history purely to be able to compare against old tokens.
A failed request with an unknown outcome
If a write request times out with no clear success or failure response, the client does not yet know whether to advance its version vector. The safe rule is to only advance the "seen" vector once the client has positive confirmation, an acknowledgment carrying the write's assigned position; on an unknown-outcome timeout, the client must not assume the write happened. If the client then retries the write, that retry needs its own idempotency handling so a write that actually did succeed the first time doesn't get double-applied, which is a separate mechanism from RYW tracking itself: the version vector is only ever updated from a confirmed position, never a guessed one.
Trade-offs & pitfalls
| Mechanism | Survives region migration | State carried | Availability if origin region is down |
|---|---|---|---|
| Sticky routing | No | None beyond a routing decision | Session breaks entirely |
| Scalar session token | No, if the client writes in more than one region | One (region, position) pair | Read can proxy to origin, but that's the failure point |
| Version vector | Yes | One position per region touched this session | Any region that has caught up can serve the read |
Version vectors scale with the number of regions that could plausibly appear in a single session; fine at a handful of regions, unwieldy with dozens of independent write origins, in which case grouping by a coarser unit (a datacenter cluster rather than a single node) keeps the vector small. A common bug is comparing only the single most recent write's position once a client has actually written in more than one region during a session, which silently drops read-your-writes for the earlier region's write. Storing session state server-side instead of in a client-held token shifts the scaling concern from token size to session-storage capacity, which is a real trade to name rather than a free win.
A less technical stakeholder asks you: 'what is eventual consistency, and how will it affect what users actually see?' Give a plain-language explanation and list three concrete UX impacts or edge cases (for example: duplicate-looking actions, a change that briefly appears to disappear or revert) that a product team should plan for.
Sample Answer
Direct Answer
Eventual consistency means that if a piece of data stops changing, every copy of it, spread across different machines, will eventually show the same value, but there's no promise about how quickly that happens. Right after something changes, different copies can briefly disagree, so different people, or even the same person on different devices, can see different things for a short window.
Three Concrete Things Users Will Notice
1. A change that looks like it disappeared or reverted. You update something, say your profile bio, and it saves fine, but a moment later, on a different device or after a refresh, you briefly see the old version again. This happens because that device happened to read from a copy of the data that hadn't caught up yet, not because your change was lost. The same effect shows up in less obviously social products too: right after a recommendation or personalization model is updated, some requests can still be served by a copy of the system using the old values for a short window, so two people who do the exact same thing a minute apart can get visibly different recommendations, purely because of which copy answered them.
2. Actions that look duplicated. If a user doesn't get quick feedback that their action went through (a like, a form submission), they often retry it. If the retry and the original attempt both eventually land, the user can end up seeing what looks like two of the same action. This isn't really an eventual-consistency artifact on its own; it becomes a real duplicate unless the system also deduplicates the underlying writes, not just the on-screen display.
3. Optimistic updates that hide the delay, until they don't. Many products make the delay invisible to the person taking the action by updating their own screen immediately, before the write has actually finished spreading to other copies. For example, when you post a comment, it appears in your own feed the instant you hit submit, even though the write is still propagating to the copies that other users' feeds are reading from. This makes the product feel instant for the person who acted, but it means other people may not see that comment for a moment, and if the underlying write ultimately fails, the app has to quietly roll back the comment it optimistically showed you.
A Concrete Trace
Say a comment-posting service has two copies of the feed data, one near user A and one near user B. User A posts "Great point!". Step 1: A's client shows the comment in A's own feed immediately, the optimistic update, while the actual write is sent to A's nearby copy. Step 2: User B, served by their own nearby copy, refreshes their feed before the write has replicated over to B's copy; B does not see the comment yet. Step 3: once the write has replicated to B's copy, B's next refresh does show the comment. Nothing was lost; B was simply reading from a copy that hadn't caught up at step 2.
Trade-offs and What to Plan For
- Eventual consistency is a deliberate trade for availability and responsiveness, not a bug, but it is the wrong choice for data where a stale answer is actively harmful, such as an account balance, the last unit of inventory, or a security permission change. Those flows are usually worth paying for stronger consistency even if it's slower.
- A common and cheap mitigation for the "did my own change disappear" complaint is guaranteeing read-your-writes (RYW): making sure the person who just made a change always sees their own latest write, typically by routing their own subsequent reads back to the copy that has it, even while other users' view of that same data is still catching up.
- A common wrong turn is treating optimistic UI as if it solves eventual consistency; it only hides the delay from the person who acted. It doesn't change how long the write actually takes to reach everyone else, and it adds its own failure case, rolling back a shown-then-failed action, that the product needs to handle gracefully.
Design a CRDT suitable for a real-time collaborative text editor where multiple users can type and delete concurrently without a central lock. Describe the data structure, how concurrent operations from different users merge deterministically, and the practical cost (metadata growth, garbage collection of tombstones) of the approach.
Sample Answer
A text editor where users type and delete concurrently without a lock needs a sequence CRDT (a Conflict-free Replicated Data Type: a data structure whose merge operation is commutative, associative, and idempotent, so concurrent replicas always converge to the same state without coordination). Each character gets a globally unique, immutable identifier, deletions mark a tombstone instead of physically removing the character, and a deterministic tie-break rule orders characters that were inserted concurrently at the same position. The design pays for this with permanent per-character metadata and a garbage-collection problem for tombstones.
Data structure
- Represent the document as an ordered sequence of atoms:
{ id: (site, counter), char, prev_id, tombstone }. idis globally unique because it pairs a site identifier (one per editing client) with that site's own monotonically increasing counter.prev_idrecords which atom this one was inserted immediately after, at the moment of insertion. That is what preserves each user's actual intent (insert right after the character I was looking at), even if other edits land nearby before this one is delivered.
Concurrent insert resolution
- Insert(id, prev_id, char) is broadcast to every replica.
- When two inserts share the same prev_id, both intended the same insertion point, that shared prev_id is exactly what concurrency looks like here. A deterministic comparator orders competing children of the same prev_id by site identifier (higher-precedence site placed first), so every replica, regardless of arrival order, produces the same final sequence.
Deletion and tombstones
- Delete(id) sets tombstone=true on that atom. The atom stays in the structure, because its ordering role must persist: a later, concurrently-arriving insert may still reference it as prev_id and needs it to resolve correctly.
- A tombstoned atom cannot be physically removed until every replica has definitely applied it.
Garbage collection of tombstones
- Replicas exchange a version vector (one counter per site, the highest counter from that site each replica has durably applied) during anti-entropy (a periodic background exchange where replicas compare state and reconcile any differences, rather than waiting for a live update to arrive).
- The element-wise minimum across all replicas' version vectors is the causal stability frontier: any tombstone at or below that frontier has been seen everywhere and can be physically purged.
- Cost: computing and propagating that frontier needs periodic all-to-all or gossip-based exchange, and a replica that stays offline indefinitely blocks compaction for everyone unless it is explicitly evicted from the version-vector set.
Worked example: two concurrent inserts at the same position
Both replicas have already converged on a one-character document containing 'X', a single atom with id (A,1). Two users, on different replicas, both position their cursor right after 'X' at the same time:
- Site A's user types 'p': op1 = Insert(id=(A,2), prev=(A,1), char='p')
- Site B's user types 'q': op2 = Insert(id=(B,1), prev=(A,1), char='q')
Both operations reference prev=(A,1): that shared reference is the concurrency. The merge rule for atoms competing for the same prev is order competing children by site identifier, descending, so a child from site B is placed before a child from site A when both point at the same prev.
- At replica A: op1 applies locally first, giving 'Xp'. When op2 arrives, it is spliced into the children of (A,1) and re-sorted by the rule above, giving order [op2, op1], so the document becomes 'Xqp'.
- At replica B: op2 applies locally first, giving 'Xq'. When op1 arrives, the same re-sort rule applies, again giving [op2, op1], so the document becomes 'Xqp'.
Both replicas land on 'Xqp' even though they applied the two operations in opposite order. That is what merging deterministically means in practice: the comparator, not arrival order, decides the final sequence.
graph LR
X["X (id A,1)"] --> Q["q (id B,1)"]
Q --> P["p (id A,2)"]
Now say 'q' is later deleted by its author. Atom (B,1) is not removed, only flagged tombstone=true, so the document reads 'Xp', but the underlying structure still holds three atoms, two live and one tombstone, until compaction runs.
Trade-offs & pitfalls
- Metadata growth: every character carries an id pair, a prev pointer, and (once deleted) a tombstone bit; on a long-lived, heavily-edited document the tombstone count can exceed the live character count, so uncompacted storage is proportional to live plus deleted atoms rather than just live ones.
- The same observed-remove technique (adding creates a fresh tag, removing targets only the tags actually observed) applies directly to a shared wishlist service: adding an item is an add-tag, removing it is a remove-tag scoped to the tags a client has actually seen, and the tombstone-compaction and consistent-read story are identical to the text editor's, just at item granularity instead of character granularity.
- Formatting spans (bold, italic) and structural moves (relocate a paragraph) do not compose as cleanly as single-character insert and delete; a naive extension can lose the same intention-preservation guarantee, which is why production collaborative-editing CRDTs spend real engineering effort specifically on this.
- Common wrong turn: implementing deletion by removing the atom outright instead of tombstoning it. That breaks any concurrent insert whose prev_id pointed at the now-missing atom, since there is nothing left to splice after.
Unlock Full Question Bank
Get access to all 9 Distributed Systems Fundamentals interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.