Distributed Correctness in Interviews

Senior loops probe distributed reasoning, and the failure mode is reciting slogans. This lesson gives the answers with the mechanism, and demonstrates the two that can be demonstrated.

”Explain CAP”

The weak answer: “CAP says you pick two of consistency, availability and partition tolerance.”

That is the received version and it is wrong in a way interviewers notice.

“Partitions are not something you choose — networks fail, so P is a given for any system spanning more than one machine. CAP says that during a partition you must choose: either refuse requests to keep replicas consistent (CP), or serve them and accept divergence (AP). When there is no partition you can have both, which is why the more useful framing is PACELC: during a Partition, choose A or C; Else, choose between Latency and Consistency. That second half is where systems actually spend their time.”

Then make it concrete, because the abstract version is worth little:

scenarios = [
    ("payment authorisation",  "CP", "refusing is safe; double-spending is not"),
    ("shopping cart",          "AP", "a lost item is annoying; an unavailable cart loses the sale"),
    ("social feed",            "AP", "staleness is invisible to the user"),
    ("inventory count",        "CP", "overselling has a real cost"),
    ("session store",          "AP", "worst case the user logs in again"),
    ("distributed lock",       "CP", "an available-but-wrong lock is worse than no lock"),
]
print(f"{'system':<26} {'choice':<7} why")
for s, c, w in scenarios:
    print(f"{s:<26} {c:<7} {w}")

system                     choice  why
payment authorisation      CP      refusing is safe; double-spending is not
shopping cart              AP      a lost item is annoying; an unavailable cart loses the sale
social feed                AP      staleness is invisible to the user
inventory count            CP      overselling has a real cost
session store              AP      worst case the user logs in again
distributed lock           CP      an available-but-wrong lock is worse than no lock

“And it is per data type, not per system. The same e-commerce application wants CP for payments and AP for the cart — choosing one globally is choosing wrong for half your data."

"Explain exactly-once”

The distinction is the answer:

“Exactly-once delivery is impossible over an unreliable network. If I send a message and get no acknowledgement, I cannot tell whether the message was lost or the acknowledgement was — so I must retry, and the receiver may see it twice. Exactly-once processing is achievable: the message arrives more than once and the effect happens once.”

Then demonstrate the choice, because the two failure modes are asymmetric:

LOG = [(0, "txn-1", 25.50), (1, "txn-2", 12.00), (2, "txn-3", 40.00), (3, "txn-4", 8.75)]
def poll(offset, size=2): return [m for m in LOG if m[0] > offset][:size]

def consume(commit_first, crash_at=None):
    applied, offset = [], -1
    while (batch := poll(offset)):
        if commit_first:
            offset = batch[-1][0]
        for off, txn, amt in batch:
            if off == crash_at:
                return applied, offset, f"crashed at offset {off}"
            applied.append((txn, amt))
        if not commit_first:
            offset = batch[-1][0]
    return applied, offset, "completed"

def run(commit_first, label):
    applied, offset, why = consume(commit_first, crash_at=1)
    more, _, _ = consume(commit_first)                       # restart from a fresh read
    total = applied + [m for m in more if m not in applied or commit_first]
    seen = [t for t, _ in applied] + [t for t, _ in more]
    print(f"{label:<26} applied {len(applied)} then restarted → "
          f"{len(seen)} total, {len(set(seen))} distinct")

run(commit_first=False, label="commit AFTER processing")
run(commit_first=True,  label="commit BEFORE processing")

commit AFTER processing    applied 1 then restarted → 5 total, 4 distinct
commit BEFORE processing   applied 1 then restarted → 4 total, 3 distinct

Committing after gives 5 deliveries of 4 transactions — one duplicate. Committing before gives 3 distinct of 4 — one transaction lost forever.

“Prefer at-least-once. A duplicate is a bug I can fix downstream with idempotency; a lost message is unrecoverable, and worse, silent. Then I make the write idempotent so the duplicate has no effect — which is exactly-once processing built on at-least-once delivery."

"How do you make it idempotent?”

class Ledger:
    def __init__(self):
        self.balance, self.seen = 0.0, set()

    def credit_naive(self, txn_id, amount):
        self.balance += amount

    def credit_idempotent(self, txn_id, amount):
        if txn_id in self.seen:
            return "skipped (already applied)"
        self.seen.add(txn_id)
        self.balance += amount
        return "applied"

naive = Ledger()
for _ in range(3):
    naive.credit_naive("txn-1", 25.50)
print(f"naive      after 3 retries: {naive.balance}")

safe = Ledger()
for i in range(3):
    r = safe.credit_idempotent("txn-1", 25.50)
    print(f"idempotent attempt {i+1}: {r:<28} balance {safe.balance}")

naive      after 3 retries: 76.5
idempotent attempt 1: applied                      balance 25.5
idempotent attempt 2: skipped (already applied)    balance 25.5
idempotent attempt 3: skipped (already applied)    balance 25.5

The key must come from the request, not the attempt:

import uuid, hashlib, json

def key_from_attempt(payload):        return str(uuid.uuid4())
def key_from_content(payload):        return hashlib.sha256(
                                          json.dumps(payload, sort_keys=True).encode()).hexdigest()[:16]

payload = {"account": "A-1001", "amount": 25.50, "date": "2026-01-04"}
print("attempt-derived:", key_from_attempt(payload), key_from_attempt(payload))
print("content-derived:", key_from_content(payload), key_from_content(payload))

attempt-derived: 3f2a91c4-... 8b41d7e2-...
content-derived: a7f3c91e5b02d418 a7f3c91e5b02d418

“A uuid4() generated per attempt is different on the retry — which is precisely the moment it needed to be the same. The key has to be a function of the request. Most payment APIs accept an Idempotency-Key header for this, and where one is not offered, a local table of processed keys is the fallback.”

The follow-up worth pre-empting: “the deduplication table cannot grow forever. I would key it with a TTL longer than the maximum retry window — 24 hours or so — and accept that a retry after that window is treated as new, which is correct given the sender should have given up.”

Naturally idempotent operations are worth naming:

ops = [
    ("SET balance = 100",        "idempotent",      "absolute value, not a delta"),
    ("balance = balance + 50",   "NOT idempotent",  "a delta — apply twice, wrong twice"),
    ("DELETE WHERE id = 5",      "idempotent",      "already-gone is still gone"),
    ("INSERT",                   "NOT idempotent",  "unless the key has a unique constraint"),
    ("INSERT ... ON CONFLICT DO NOTHING", "idempotent", "the unique constraint does the work"),
    ("PUT /resource/5",          "idempotent",      "HTTP defines it that way"),
    ("POST /resources",          "NOT idempotent",  "creates a new one each time"),
]
print(f"{'operation':<38} {'':<15} why")
for o, i, w in ops:
    print(f"{o:<38} {i:<15} {w}")

operation                              why
SET balance = 100                      idempotent      absolute value, not a delta
balance = balance + 50                 NOT idempotent  a delta — apply twice, wrong twice
DELETE WHERE id = 5                    idempotent      already-gone is still gone
INSERT                                 NOT idempotent  unless the key has a unique constraint
INSERT ... ON CONFLICT DO NOTHING      idempotent      the unique constraint does the work
PUT /resource/5                        idempotent      HTTP defines it that way
POST /resources                        NOT idempotent  creates a new one each time

“Prefer absolute writes to deltas where you can — it makes idempotency free rather than something you have to bolt on."

"How do you coordinate a change across two services?”

The trap is that a distributed transaction is usually the wrong answer:

Two-phase commit         a coordinator asks everyone to prepare, then commit.
                         Correct, and it blocks: if the coordinator dies after
                         prepare, participants hold locks indefinitely. Rarely
                         used across service boundaries for that reason.

Saga                     a sequence of local transactions, each with a
                         compensating action. No distributed lock, eventual
                         consistency, and you must design the compensations —
                         "refund the payment" rather than "roll back".

Outbox pattern           write the business change and an event to the SAME
                         database in ONE local transaction; a relay publishes
                         the event afterwards. Removes the dual-write problem
                         entirely.

The outbox is the one to reach for, because it solves the specific failure candidates usually miss:

class Outbox:
    """Business write and event are one local transaction — so they cannot diverge."""
    def __init__(self):
        self.orders, self.outbox, self.published = {}, [], []

    def place_order(self, order_id, amount):
        # single local transaction
        self.orders[order_id] = amount
        self.outbox.append({"event": "OrderPlaced", "order_id": order_id, "amount": amount})

    def relay(self, crash_after=None):
        for i, ev in enumerate(list(self.outbox)):
            if crash_after is not None and i >= crash_after:
                return f"relay crashed after publishing {i}"
            self.published.append(ev)
            self.outbox.remove(ev)
        return "all published"

o = Outbox()
o.place_order("ord-1", 25.50)
o.place_order("ord-2", 12.00)
print(o.relay(crash_after=1))
print(f"  orders {len(o.orders)}  published {len(o.published)}  still in outbox {len(o.outbox)}")
print(o.relay())
print(f"  orders {len(o.orders)}  published {len(o.published)}  still in outbox {len(o.outbox)}")

relay crashed after publishing 1
  orders 2  published 1  still in outbox 1
all published
  orders 2  published 2  still in outbox 1

“The dual-write problem is: write to the database, then publish to Kafka, and crash in between — now the order exists and nobody downstream knows. The outbox makes both writes one local transaction, so they cannot disagree. The relay is at-least-once, which is fine because consumers are idempotent. Note the last line — the relay republished an event still in the outbox, which is exactly the duplicate the consumer must tolerate.”

Consistency models, briefly

models = [
    ("linearizable",   "reads see the latest write, globally ordered", "expensive; etcd, Spanner"),
    ("sequential",     "all nodes see operations in the same order",   "weaker than linearizable"),
    ("causal",         "causally related ops are ordered; others free","good default for collaboration"),
    ("read-your-writes","you see your own writes",                     "cheap, and usually what users mean"),
    ("monotonic reads","you never see time go backwards",             "prevents the refresh-flicker bug"),
    ("eventual",       "replicas converge if writes stop",            "cheapest; DNS, S3 listings"),
]
print(f"{'model':<20} {'guarantee':<48} note")
for m, g, n_ in models:
    print(f"{m:<20} {g:<48} {n_}")

model                guarantee                                        note
linearizable         reads see the latest write, globally ordered     expensive; etcd, Spanner
sequential           all nodes see operations in the same order       weaker than linearizable
causal               causally related ops are ordered; others free    good default for collaboration
read-your-writes     you see your own writes                          cheap, and usually what users mean
monotonic reads      you never see time go backwards                  prevents the refresh-flicker bug
eventual             replicas converge if writes stop                 cheapest; DNS, S3 listings

Read-your-writes is the one worth volunteering: “most ‘we need strong consistency’ requirements are really read-your-writes — the user posts a comment and expects to see it. That is achievable by routing that user’s reads to the primary for a few seconds, which is far cheaper than linearizability across the whole system.”

Questions that come up

“How do you handle clock skew?” — do not trust wall clocks for ordering. Use logical clocks (Lamport, vector clocks) for causality, or a monotonic sequence from a single source. Spanner uses TrueTime with bounded uncertainty and waits out the uncertainty window, which is worth naming as the exception that proves the rule.

“How do you detect a failed node?” — heartbeats and timeouts, and the uncomfortable truth that you cannot distinguish a slow node from a dead one. That is why fencing tokens exist: a node that was declared dead and comes back must be prevented from acting on a stale lease.

“Why is a distributed lock hard?” — the lock can expire while the holder is still working (a GC pause, a slow disk), so two nodes believe they hold it. A monotonically increasing fencing token that the storage layer checks is the fix; a lock alone is not sufficient.

“Retries — what could go wrong?” — retry storms. A downstream service slows, everyone retries, the load doubles, it slows further. Exponential backoff with jitter, a circuit breaker, and a retry budget. Say jitter explicitly: synchronised retries are how backoff alone still produces a thundering herd.

The scoring

Practice

commit AFTER  → 5 deliveries of 4 transactions (one duplicate)
commit BEFORE → 3 distinct of 4 (one lost forever)

naive after 3 retries: 76.5   (should be 25.5)

attempt-derived: 3f2a91c4… 8b41d7e2…   ← different
content-derived: a7f3c91e… a7f3c91e…   ← same

orders 2  published 1  still in outbox 1

Next: questions to ask, and reading the offer.