Round two: “two requests, same wallet”

Two distinct problems wearing one coat, and separating them is the first move:

Requirements this round adds

Isolation is defined by the anomalies it forbids. The useful way to hold this in your head is as a ladder of things that stop being possible as you climb, at increasing cost.

Write skew, since it is the one people cannot name

Not hypothetical for a bank. Suppose a rule says a customer's combined balance across two wallets must stay at or above zero, and each wallet holds ₦500:

-- T1: withdraw 800 from wallet A          -- T2: withdraw 800 from wallet B
SELECT sum(bal) FROM wallets              SELECT sum(bal) FROM wallets
 WHERE customer = 'c1';  -- 1000      WHERE customer = 'c1';  -- 1000
-- 1000 >= 800, allowed                  -- 1000 >= 800, allowed
UPDATE wallets SET bal = bal - 800       UPDATE wallets SET bal = bal - 800
 WHERE id = 'A';                          WHERE id = 'B';
COMMIT;                                   COMMIT;

-- combined balance is now -600. Neither transaction did anything wrong
-- individually. They each read a state the other then invalidated.

Note that no row was written by both transactions, so row locks do not help and REPEATABLE READ does not catch it. The fixes are SERIALIZABLE, an explicit lock on something both transactions must touch (the customer row), or restructuring the invariant so it lives on a single row.

Isolation levels are the contract. MVCC is the mechanism. Being able to explain it is the difference between quoting documentation and understanding the system.

The core idea: an update never overwrites a row in place. It writes a new version of the row and marks the old one as expired. Readers then pick the version that was visible when their snapshot was taken, which is why readers never block writers and writers never block readers.

The three things stored on every row

What a snapshot actually is

Not a copy of the data. A snapshot is a small descriptor of which transactions to believe:

          snapshot = { xmin: oldest still-running txid,

                       xmax: next txid to be assigned,

                       xip_list: txids in flight right now }


          a row version is visible to me if:

            its xmin committed, and xmin is not in my xip_list, and xmin < my xmax

            and its xmax is unset, aborted, or still in flight per my list

This is why the isolation levels differ so cheaply. READ COMMITTED takes a new snapshot per statement. REPEATABLE READ takes one per transaction. Same machinery, different refresh point, which is a satisfying thing to be able to say out loud.

The costs MVCC brings, which you should name

Pessimistic control assumes conflict is likely and takes the lock before doing the work.

BEGIN;
  -- acquires an exclusive row lock, held until COMMIT or ROLLBACK.
  -- a second transaction reaching this line blocks here.
  SELECT * FROM accounts WHERE id = $1 FOR UPDATE;

  -- now safe: nobody else can modify this row while we compute
  -- ... application logic, limit checks, fee derivation ...

  INSERT INTO entries (...) VALUES (...);
COMMIT;  -- lock released here

What the lock manager is doing

The lock is not stored on the row itself in the way people imagine. Postgres records the locking transaction id in the tuple header, and maintains a shared in-memory structure of lock requests:

          1. T1 requests exclusive on row R → granted, xmax = T1 on the tuple

          2. T2 requests exclusive on row R → conflict detected

          3. T2 is put on R's wait queue and sleeps on a semaphore

          4. T1 commits → lock released → T2 woken

          5. T2 re-checks visibility and proceeds against the new version


          step 5 is the important one: T2 does not act on the stale value it

          would have read earlier, because it re-resolves the row afterwards
        

The variants, and when each is right

The cost, stated honestly

A held lock serialises every other writer to that row for its entire duration, and the duration is your transaction, not your statement. Two rules keep this survivable:

SET statement_timeout = '3s';        -- kill runaway statements
SET lock_timeout = '500ms';          -- do not queue behind a lock forever
SET idle_in_transaction_session_timeout = '10s';  -- reap abandoned txns

Optimistic control assumes conflict is rare, takes no lock, and detects interference at write time.

-- 1. read, including the version
SELECT id, balance, version FROM accounts WHERE id = $1;
--    → balance 1000, version 7

-- 2. compute freely in the application. No lock is held.

-- 3. write, asserting nothing changed underneath
UPDATE accounts
   SET balance = 400, version = 8
 WHERE id = $1 AND version = 7;

-- 0 rows affected ⇒ somebody moved first ⇒ re-read and retry

This is compare-and-swap, the same primitive as an atomic CPU instruction, expressed in SQL. The write succeeds only if the world matches what you assumed.

The retry loop, written correctly

async function withRetry<T>(op: () => Promise<T>, tries = 3): Promise<T> {
  for (let i = 0; i < tries; i++) {
    try { return await op(); }
    catch (e) {
      if (!isConflict(e) || i === tries - 1) throw e;
      // full jitter: avoids a retry stampede aligning on the same instant
      await sleep(Math.random() * 50 * 2 ** i);
    }
  }
  throw new Error('unreachable');
}

The jitter matters more than the backoff. Without it, every conflicted transaction retries at the same moment and you have rebuilt the contention you were escaping.

Head to head

The answer that earns credit is not "we use optimistic locking". It is a mapping from operation to mechanism, justified by expected contention.

A transfer touches two accounts, so a transfer can deadlock with another transfer going the other way. This is not exotic; it is the default outcome of unordered locking.

How the database resolves it

Postgres does not prevent deadlocks; it detects them. After a lock wait exceeds deadlock_timeout (1 second by default), it builds the wait-for graph of which transaction waits on which, searches for a cycle, and if it finds one aborts the transaction that triggered the check with error 40P01.

          wait-for graph:  T1 → T2  (T1 waits for a lock T2 holds)

                          T2 → T1  (T2 waits for a lock T1 holds)


cycle found → abort one victim → the other proceeds


          detection costs a graph walk after a 1 second stall.

          so a deadlock is not just an error, it is a second of latency
          first

The fix: a total order on lock acquisition

If every transaction acquires locks in the same order, a cycle is impossible. Any deterministic order works as long as everybody uses it, and account id sorts naturally:

// Never lock in "from, to" order. Lock in sorted order, always.
const [first, second] = [fromId, toId].sort();

await tx.query(
  `SELECT id FROM accounts WHERE id = ANY($1) ORDER BY id FOR UPDATE`,
  [[first, second]]
);
// both directions of a transfer now queue rather than cycle

The ORDER BY inside the locking statement matters. Without it the engine may acquire in whatever order it scans, which defeats the point.

Now the second half of the interviewer's question: the client timed out and retried. The request may have succeeded, failed, or still be in flight. The client cannot tell, and the server must make the ambiguity harmless.

The mechanism

The client generates a key per intent and reuses it on every retry of that intent. The server enforces uniqueness at the database level:

CREATE TABLE idempotency (
  key          TEXT PRIMARY KEY,
  fingerprint  TEXT NOT NULL,     -- SHA-256 of the canonical body
  state        TEXT NOT NULL,     -- in_flight | done | failed
  response     JSONB,                -- the original response, replayed verbatim
  journal_id   UUID,
  created_at   TIMESTAMPTZ NOT NULL DEFAULT now(),
  expires_at   TIMESTAMPTZ NOT NULL
);

Why a fingerprint as well as a key

The key alone is not enough. A buggy or malicious client could reuse one key for two different transfers, and returning the first response for the second request would silently drop a payment. So the server hashes the canonical request body and compares:

function fingerprint(body: TransferRequest): string {
  // canonical: sorted keys, no whitespace, amounts as exact strings.
  // the hash must not change because a client reordered its JSON.
  const canon = JSON.stringify({
    from: body.from, to: body.to,
    amount: body.amount.toString(), currency: body.currency
  });
  return sha256(canon);
}

Where the key lives, and why ours needs no second table

A separate table means two writes that must agree, which is the dual-write problem in miniature. Our round-one schema avoided it by putting the key directly on the journal row under a UNIQUE constraint, so the duplicate check and the money movement are the same atomic commit:

BEGIN;
  -- a duplicate raises unique_violation right here, before any entry exists.
  INSERT INTO journal (id, kind, idempotency_key) VALUES ($jid, 'transfer', $key);
  INSERT INTO entries ...  -- debit
  INSERT INTO entries ...  -- credit
COMMIT;

-- on unique_violation: look up the original journal row by key and
-- return its result. The retry is now indistinguishable from the original.

Keep the richer idempotency table for operations that are not a single ledger posting, such as the external payouts in Part 6, where the response must be replayed and the state machine has more than one terminal state.

A claim worth being able to defend, because it comes up in every distributed systems conversation and most people repeat the marketing.

Exactly-once delivery is impossible over an unreliable network. The sender cannot distinguish "the message was lost" from "the message arrived and the acknowledgement was lost". It must therefore either resend, risking a duplicate, or not resend, risking a loss. There is no third option, and no protocol removes it. This is the Two Generals problem.

at-most-once  = send, never retry  → may lose

at-least-once = send, retry until acked  → may duplicate

exactly-once  = not achievable in delivery


          but: at-least-once delivery + idempotent processing

               = exactly-once effect

That last line is the whole answer. You stop trying to make delivery exact and make processing tolerant of repetition. The duplicate still arrives; it just does not do anything the second time.

What "exactly-once" means when a vendor says it

The three places our design makes repetition harmless

The design has not grown a single new box this round. It grew guarantees, which is worth pointing out explicitly, because it shows that not every round should add infrastructure.

The invariants now enforced, and by what

-- make the append-only rule a database guarantee, not a code review habit
REVOKE UPDATE, DELETE ON entries FROM ledger_app;
-- corrections are new, opposite entries. history is never rewritten.

And the interviewer takes the invitation, because ten million transactions a day is exactly where one primary stops being enough.