Interview questions

By Little's Law, the number of transactions in flight is L = λW (arrival rate × duration), so it grew tenfold. Conflicts happen between pairs of live transactions, and pairs grow as L² / 2, so expected conflicts grow about a hundredfold.

Read moreThe arithmetic that governs this mechanism

The bug lives in how operations from different transactions interleave. The final data can look perfectly normal while being wrong: two lost updates leave a plausible balance. A system is correct if every interleaving it allows is equivalent to some serial order.

Read moreWe judge a schedule, not a state

No. Taking a lock costs about 100 ns and a commit is one log write. The expensive part is conflict itself, which depends on the workload and on how many transactions overlap, not on the speed of the machine.

Read moreThe cost is combinatorial, not physical

Conflict formulas depend on the effective number of keys being touched, N. With Zipf-skewed access, N is two or three orders of magnitude smaller than the row count, and since conflict probability depends on it steeply, the estimate moves by four to six orders of magnitude. Measure the real abort rate rather than trusting a uniform estimate.

Read moreThe assumption nobody can check

No. Atomicity and durability come from logging, isolation comes from concurrency control, and consistency means the application's own invariants, which the database only helps enforce.

Read moreACID, dismantled

Consensus needs a majority of nodes; atomic commit needs every participant to agree. So availability is the product of all participants' availability, 0.999ⁿ, about 0.99 for n = 10, instead of the much higher availability of a majority.

Read moreConsensus needs a majority; atomic commit needs unanimity

A lock is held by a transaction for as long as the transaction needs, protects logical contents (rows, ranges), and is tracked and checked for deadlocks. A latch is held by a thread for nanoseconds, protects a physical structure such as a page, costs one compare-and-swap with no metadata, and avoids deadlock by always being taken in a fixed order.

Read moreLocks and latches

A phantom is a row that appears between two reads of the same predicate, such as a new order matching WHERE total > 100. A row lock cannot lock a row that does not exist yet. The fixes lock the predicate or the gap: next-key locks, predicate locks, or the read-tracking locks of serializable snapshot isolation.

Read moreWhere the two protocols meet badly: phantoms

Draw a graph with an edge between two transactions whenever they conflict (write–write, write–read or read–write on the same item), pointing from the earlier operation to the later. The schedule is conflict-serializable if the graph has no cycle, because an acyclic graph can be sorted into an equivalent serial order.

Read moreConflicts and the serialization graph

Basic two-phase locking lets a transaction release locks before it commits, so another transaction can read a value whose writer later aborts, then commit on the strength of it. Holding write locks until commit (strict) or all locks until commit (rigorous) prevents these cascading aborts.

Read moreWhy strict

They answer "is anything below this node locked?" in constant time. A transaction locking a row first marks the page and table with intention locks, so another transaction wanting the whole table can see the conflict without scanning every row lock. They are a conservative summary, like a zone map.

Read moreIntention locks

Both give transactions timestamps and let waiting happen in only one direction, so no cycle can form. In wait-die, a younger transaction that requests a lock held by an older one dies (restarts). In wound-wait, an older requester aborts (wounds) the younger holder. A restarted transaction keeps its original timestamp, so it eventually becomes the oldest and cannot starve.

Read morePrevention by timestamp

Detection needs a global graph of who waits for whom, which across machines is an expensive and always slightly stale snapshot. Prevention needs only local comparisons of timestamps.

Read moreWhy distributed systems prevent instead of detect

A timeout cannot tell a deadlock from a slow transaction, and lock waits have a heavy tail. Any value is too short for some legitimate work or too long for some real deadlock.

Read moreTimeout, the degenerate prevention scheme

Deadlock: idle threads and a cycle of waits. Livelock: high CPU and zero progress. Starvation: normal-looking totals, but one class of work is never served.

Read moreDeadlockLivelock: the herd of twoFIFO, priority and feedback

Multiversion concurrency control (MVCC) keeps old row versions until no snapshot can see them. The oldest live snapshot sets the retention window, so one long read pins every version written since it began, and vacuum cannot reclaim them.

Read moreSpace and the oldest-reader problem

PostgreSQL keeps old versions in the table itself, so writers pay with bloat. Oracle keeps them in a bounded undo area, so when it runs out the reader fails with "snapshot too old". InnoDB cannot purge its undo history past the oldest snapshot, so the history keeps growing and its writers pay too. Same mechanism; a different party gets the bill.

Read moreCost 1: space and the oldest reader

When the probability of conflict is below about 1–2%. For example, with 10 locks per transaction at 150 ns each (1.5 µs) against 100 µs of work, the two break even at about a 1.5% conflict rate: below it, the occasional wasted retry is cheaper than always taking locks.

Read moreThe constraint is economic

Locking waits: utilization is low and queues are long. Optimistic concurrency burns: CPUs sit at 100% while useful completed work falls towards zero, because nearly every transaction aborts and retries. Watch goodput, not throughput.

Read moreHow OCC fails

Two bits per transaction: whether it has an incoming and an outgoing read–write dependency. A transaction with both could be the pivot of a cycle, so one of them is aborted. The costs are aborts that were not strictly necessary and memory for tracking reads; how coarsely reads are tracked sets the false-abort rate.

Read moreThe two-bit testThe honest cost of SSI

If the working set is in memory, a transaction takes about 50 µs, so one core does 20,000 transactions per second, and with one at a time no concurrency control is needed at all. It breaks for transactions that span partitions, and when data no longer fits in memory.

Read moreSingle-threaded per partition

Instead of locking a balance, a transaction reserves a quantity from it. "Subtract 10" commutes with another "subtract 10", so two reservations need no ordering; only the invariant, such as the balance staying at or above zero, is checked against the reserved amounts.

Read moreCommutativity

Nothing beneath the database can write many things at once. So the database picks one event the lower layer does make atomic, a log record becoming durable or a pointer being swapped, and defines that event as the commit.

Read moreNothing below you can do many writes at once

Write-ahead (the information needed to undo a change is durable before the change reaches disk) buys atomicity. Force-at-commit (the log is flushed before the commit is acknowledged) buys durability.

Read moreACID, dismantled

Otherwise another transaction could read your value, commit and be acknowledged, and then your crash would erase the value it read. A reader's durability depends on the durability of everything it read.

Read moreThe order of the steps is forced

Committed, aborted, or unknown. The unknown case cannot be designed away, so the client needs an idempotency key that makes asking again safe.

Read moreThe in-doubt window

When the snapshot is taken: a fresh one for each statement (Read Committed), or one for the whole transaction (Repeatable Read).

Read moreBegin, commit and abort

Only for in-place updates with an undo log, where abort must reverse every change. With out-of-place writes published by swapping a pointer, abort is nearly free, simply never publishing, and commit is the contended step.

Read moreAbort is not the mirror image of commit

It holds a snapshot, which pins old versions and blocks vacuum; it may hold locks; and it pins log segments. One local mistake becomes a cost for the whole database.

Read moreAn open transaction is never free

Almost nothing on the write path, since it is just a position in the undo chain. But in PostgreSQL, a session with more than 64 subtransactions makes every backend consult a shared lookup structure (pg_subtrans), which slows reads across the whole system.

Read moreSavepoints and nested transactions

A conditional write: put if absent, or put if the version tag still matches. At 10–50 ms per round trip, that allows about tens of commits per second per table, against tens of thousands in a database.

Read moreCompare-and-swapThe number that governs everything downstream

The unit of conflict is a file, not a row, so two writers' chance of touching the same unit is about 1 instead of about 10⁻⁴. And a commit takes about 50 ms instead of 100 µs, and duration enters the conflict formula squared.

Read moreOptimistic commit on a metadata log

Retrying a read-modify-write with the values read the first time silently overwrites the conflicting change: a lost update. And something must be able to re-execute the logic, which an interactive session typing statements cannot.

Read moreWrite conflicts and retry semantics

It needs no transaction ID, no locks, no commit record and no log flush. But under snapshot isolation it can still complete a serialization cycle with two writers. PostgreSQL offers safe snapshots through READ ONLY DEFERRABLE, which waits for a snapshot that cannot take part in one.

Read moreRead-only transactions

It stores the decision in the data. Committing is one atomic write to a designated primary row. Any reader that finds a leftover lock follows it to the primary and rolls the transaction forward or back, so a client that dies mid-commit cannot block anyone.

Read morePercolator-style timestamps

The right to abort on its own. From that moment it must wait for the coordinator's decision, holding its locks, which is why a dead coordinator can leave it stuck.

Read moreTwo-phase commit

Not the two round trips themselves, but the longer time locks are held, which enters the conflict formula squared, plus an unbounded blocking window if the coordinator fails.

Read moreThe cost accounting, done honestly

It avoids blocking only if the network never partitions and failures are detected accurately. A partition lets the two sides reach different decisions.

Read moreThree-phase commit and Paxos commit

They run two-phase commit over replicated participants: each participant, and the coordinator, is itself a consensus group, so no single machine's failure can block the protocol. "Two-phase commit versus Raft" is a category error; they solve different problems and are used together.

Read moreThree-phase commit and Paxos commit

Mostly because some participants, such as payment gateways, have no prepare phase, so they cannot take part in two-phase commit. Long-running business processes are the secondary reason.

Read moreSagas

It makes the state change and the intent to publish an event one local atomic commit, so they can never disagree. It leaves duplicates: the event is published at least once, so consumers must handle repeats.

Read moreTransactional outbox