Concurrency control research and isolation correctness

Why it matters

Concurrency control is where database theory meets systems performance. Protocols are proved correct on paper, evaluated on specific hardware and workloads, and implementations still ship with isolation bugs. A research interview will test whether you can lay out the design space, read an evaluation critically and say what evidence would change your mind.

Core ideas

Families and their failure modes.

• Two-phase locking detects conflicts when a lock is requested; contention causes waiting and deadlocks, handled by detection or by prevention policies (no-wait, wait-die, wound-wait).
• Optimistic concurrency control (OCC) executes without locks, records read and write sets and validates at commit; contention causes late aborts that waste the whole transaction's work.
• Timestamp ordering assigns timestamps up front and rejects operations that arrive too late; it needs a scalable timestamp source.
• MVCC keeps versions so readers use snapshots; writers still need a protocol (MV2PL, MVOCC, MVTO), and the system pays for version storage and garbage collection.

MVCC design space. Wu et al. separate four dimensions: the concurrency protocol; version storage (append-only chains ordered oldest-to-newest or newest-to-oldest, a separate time-travel table, or deltas); garbage collection (per tuple or per transaction); and index management (indexes pointing at physical versions or at logical row IDs). Each choice moves cost between reads, updates and cleanup; their evaluation found version storage to be among the most important choices for multi-core scaling, against the usual focus on protocols.

Scaling to many cores. Yu et al. ran seven protocols in one engine on a simulated thousand-core machine and none scaled: lock thrashing and centralized deadlock detection limited the 2PL variants, timestamp allocation limited the timestamp-based schemes, and high contention raised abort rates; even the default memory allocator was an early limit that they removed with a custom per-thread allocator. The lesson for evaluation is that centralized components (timestamp counters, lock tables, allocators) can dominate, so measured performance reflects the implementation as much as the protocol.

Correctness. Serializability is defined over histories. Adya's formalism expresses isolation levels as forbidden cycles in a graph of write-write, write-read and read-write dependencies, avoiding the ambiguity of ANSI phenomena. Snapshot isolation forbids some cycles but allows those with two consecutive read-write antidependencies; SSI aborts a transaction when it sees that structure, which can abort transactions that would have been serializable. A correctness proof covers the protocol under stated assumptions, not the code. Black-box testing fills part of the gap: two-session scripts such as Hermitage, or checkers such as Jepsen's Elle, record client-observed histories and search for anomalies. Testing can find bugs but never prove their absence.

What drives results. Contention (skew and hot rows), transaction length, read/write ratio, and whether transactions are interactive or run as stored procedures change the ranking of protocols. Rules of thumb such as "OCC wins at low contention, waiting-based locking degrades more gracefully at high contention, MVCC helps long readers" are hypotheses to check against a specific setup, not results.

Common misconceptions

• "Optimistic is always faster than pessimistic." Under high contention OCC wastes work on aborts; the crossover depends on workload and implementation.
• "MVCC is a concurrency-control protocol." It is a storage and visibility scheme; a protocol for writers sits on top.
• "A correctness proof means the system is correct." Proofs cover the protocol under assumptions; implementations and configurations still produce anomalies.
• "Throughput results transfer between systems." They depend on hardware, workload parameters and implementation details such as latches and memory allocators.
• "SSI aborts only non-serializable transactions." It is conservative and produces false positives.

How to approach it

Rebuild the families as a table: detection point, abort cause, main overhead, best and worst workloads. Read the CMU 15-721 MVCC notes and Wu et al. with the focus on experimental variables, then Yu et al. for scalability attribution and the PostgreSQL SSI paper for the engineering side of correctness. Implement or extend BusTub's MVCC project and write tests that try to provoke write skew. For interviews, prepare a five-minute answer to "how would you evaluate a new concurrency-control protocol?" naming workloads, baselines, metrics and correctness checks.