Concurrency control interview questions, with answers

The questions, with answers

1. 1.What goes wrong when transactions run concurrently without control?

   Four named anomalies, and interviewers want the names. Lost update: two transactions read the same balance, each adds to it, and the second write overwrites the first — one deposit vanishes. Dirty read: a transaction reads a value another transaction has written but not yet committed, and then that other transaction rolls back, so the read value never existed. Non-repeatable read: the same row read twice in one transaction returns different values because another transaction committed in between. Phantom read: the same query run twice returns different sets of rows because another transaction inserted or deleted rows matching it. Concurrency control is the set of mechanisms that prevent these while keeping as much parallelism as possible; each isolation level is a choice of which to prevent.

2. 2.What does serializability mean, and what is the difference between conflict and view serializability?

   A schedule — an interleaving of operations from several transactions — is serializable if its effect equals that of some serial schedule that runs the same transactions one after another. It is the correctness criterion: any serializable interleaving is as good as no interleaving at all. Two operations conflict if they belong to different transactions, touch the same item, and at least one is a write. A schedule is conflict-serializable if swapping non-conflicting adjacent operations can turn it into a serial schedule; the test draws a precedence graph with an edge from Ti to Tj for each conflict where Ti acted first, and the schedule is conflict-serializable exactly when the graph has no cycle. View serializability is a weaker, harder-to-test notion that also admits schedules with blind writes; real systems enforce conflict serializability because it can be checked efficiently.

3. 3.What are shared and exclusive locks, and which combinations are compatible?

   A shared (S) lock is taken to read an item; an exclusive (X) lock is taken to write it. Any number of transactions can hold S locks on the same item at once — readers do not disturb each other — but an X lock is incompatible with everything: if T1 holds S on X, T2 can take another S but must wait for X; if T1 holds X, T2 waits for either. That is the whole compatibility matrix, and it encodes the rule that readers may share while a writer needs the item to itself. Lock upgrade — holding S and asking for X — is where deadlocks often start, because two readers each waiting to upgrade block each other forever. Intention locks (IS, IX) extend the matrix to hierarchies, so a transaction can lock a whole table without checking every row lock beneath it.

4. 4.What is two-phase locking, and what does it guarantee?

   Under two-phase locking, every transaction has a growing phase, in which it acquires locks and releases none, followed by a shrinking phase, in which it releases locks and acquires none — the moment it releases its first lock, it may never lock again. That single rule guarantees conflict serializability: the order in which transactions reach their lock points is a serial order equivalent to the schedule. What it does not guarantee is freedom from deadlock, since two transactions can each hold a lock the other needs while both are still growing; nor does it prevent cascading rollbacks, because a transaction may release a lock, let another read its write, and then abort. Strict 2PL fixes the second problem by holding all exclusive locks until commit, and rigorous 2PL holds every lock until commit; nearly every lock-based database implements one of those two.

5. 5.How do you tell a deadlock from a long wait, and how do databases prevent or resolve one?

   A deadlock is a cycle of waiting: T1 holds X and waits for Y while T2 holds Y and waits for X, so neither can ever proceed — the difference from a long wait is that no amount of time resolves it. Databases handle it two ways. Detection: maintain a wait-for graph, look for cycles periodically or when a wait exceeds a threshold, and abort one transaction in the cycle — the victim, usually the youngest or the one with the least work done — which rolls back, releases its locks, and is retried. Prevention: decide by timestamp at the moment of waiting. Wait-die lets an older transaction wait for a younger one but aborts a younger transaction that wants a lock held by an older one; wound-wait lets the older transaction pre-empt (wound) the younger holder, and makes the younger wait for the older. Both avoid cycles because waiting only ever happens in one age direction.

6. 6.How does timestamp ordering control concurrency without locks?

   Each transaction gets a timestamp when it starts, and the system enforces that the schedule is equivalent to the serial order of those timestamps. Every data item remembers the timestamp of the last transaction that read it and the last that wrote it. A transaction that tries to read an item already written by a younger transaction, or write an item already read or written by a younger one, is aborted and restarted with a new timestamp, because letting it proceed would put a younger transaction's operation before an older one's. There is never any waiting, so there are no deadlocks — but there can be many restarts under contention, and a long transaction can starve. Thomas's write rule is the refinement that skips an obsolete write instead of aborting. It is the basis of optimistic schemes, where conflicts are checked at commit rather than at each operation.

7. 7.What is MVCC, and why does it let readers and writers avoid blocking each other?

   Multi-version concurrency control keeps several versions of each row, each stamped with the transaction that created it. A transaction reads the version that was current when its snapshot was taken and ignores everything committed later, so a reader never waits for a writer and a writer never waits for a reader — only writers of the same row conflict. PostgreSQL, Oracle, InnoDB in MySQL and SQL Server's snapshot isolation all work this way, which is why a long report does not block updates in modern databases. The costs: old versions must be cleaned up (PostgreSQL's VACUUM, InnoDB's undo purge), and a snapshot alone does not give full serializability — write skew is the anomaly it admits — so PostgreSQL adds serializable snapshot isolation on top when you ask for the SERIALIZABLE level.

8. 8.What is the difference between optimistic and pessimistic concurrency control in practice?

   Pessimistic control assumes conflicts are likely and locks before acting: SELECT ... FOR UPDATE takes a row lock so nobody else can change the row until you commit, and a competing transaction waits. Optimistic control assumes conflicts are rare and checks afterwards: read the row with its version number, do the work, and write back with WHERE version = the one you read; if zero rows update, someone else changed it and you retry. Pessimistic is right when contention is high or a retry is expensive — inventory decrements, seat bookings; optimistic is right when reads vastly outnumber writes and holding locks across user think-time would be absurd, which is most web applications. Say which workload you are designing for; the interviewer is listening for the trade-off, not for a winner.

   -- optimistic: the version column is the check
   UPDATE Orders
   SET status = 'shipped', version = version + 1
   WHERE order_id = 42 AND version = 7;   -- 0 rows updated means someone got there first: retry

How the diagnostic asks it

One question from the DBMS bank, exactly as a sitting would show it. The bank has 4 on concurrency control and 60 across DBMS.