Concurrency control

Concurrency control is the set of mechanisms a database, or your application, uses so that transactions running at the same time produce the same result as if they had run one after another. There are only a few basic moves: make conflicting transactions wait (locking), let them run and check at commit (optimistic validation), keep old versions so readers never wait (MVCC), or fix the order up front (timestamps). Real systems combine them, and the right mix depends mostly on how often your transactions collide.

Picture it first: one register, three rules

A housing society keeps one parking register. Three volunteers allot slots to new residents, and dozens of residents look up who has which slot.

• The pen rule. Whoever holds the register’s only pen may write; everyone else queues. Nobody overwrites anybody, but on allotment day the queue is long. Worse, if Anil holds the key cupboard while waiting for the pen, and Bela holds the pen while waiting for the keys, both stand there forever.
• The photocopy rule. Each volunteer works on a photocopy stamped with the page’s version number. At submission the secretary compares stamps; if the page changed since your copy, your work is rejected and you start again. No queues, but on a busy day people redo the same work again and again.
• The yesterday’s-copy rule. Residents who only want to look get last night’s printout. Readers never wait and never see half-finished edits; the cost is keeping old printouts around.

Map it back: the register is a row or a table, the pen is a lock, the version stamp is optimistic validation, the stuck pair is a deadlock, and the printouts are multi-version snapshots. Every database picks some mix of these rules.

The goal: a schedule that looks serial

A schedule is the interleaved order in which the database actually runs the reads and writes of concurrent transactions. It is serializable if its effect equals some one-at-a-time order. Two operations conflict when they come from different transactions, touch the same item, and at least one is a write:

• write–read (wr): T2 reads what T1 wrote, so T1 must come first.
• read–write (rw): T2 overwrites what T1 read, so T1 must come first (it saw the old value).
• write–write (ww): T2 overwrites what T1 wrote.

Draw each transaction as a node and each conflict as an edge from the earlier operation’s transaction to the later one. If this conflict graph has no cycle, sorting it gives an equivalent serial order; a cycle means none exists. Here is the classic lost update: two ₹100 top-ups to a ₹500 wallet.

T1: read balance  -> 500
                              T2: read balance  -> 500
T1: write balance  = 600
                              T2: write balance  = 600   -- T1's top-up is gone

T1 read before T2 wrote (rw edge T1 → T2) and T2 read before T1 wrote (rw edge T2 → T1). That is a cycle, and indeed the result, ₹600, matches neither serial order (both give ₹700).

Every mechanism below exists to stop such cycles. They differ in when they act: locking blocks a conflicting operation before it runs, optimistic schemes check at commit, timestamp ordering fixes the order at the start, and SSI watches for the shape of a cycle as it forms. The isolation level you configure decides which cycles the database bothers to stop.

Two-phase locking

Locking is the pessimistic answer: assume conflicts will happen and make the second transaction wait. Each item has a shared (S) lock for reading and an exclusive (X) lock for writing.

Locks alone are not enough. If T1 unlocks balance and later locks another row, T2 can slip in between and a cycle can still form. Two-phase locking (2PL) adds one rule: once a transaction releases any lock, it may not acquire another. Its life splits into a growing phase (acquire only) and a shrinking phase (release only). The moment it holds the most locks is its lock point, and conflicting transactions end up serialized in lock-point order.

That early release is the weakness of basic 2PL: T2 may read a value that T1 later rolls back, forcing T2 to abort as well, a cascading abort. Real databases use strict 2PL and hold locks until commit or rollback, as PostgreSQL row locks and InnoDB record locks do.

Lock granularity and intention locks

Locking a 10-million-row table one row at a time would be absurd, and so would checking 10 million row locks before granting a table lock. Multiple-granularity locking lets a transaction lock a table or a row, and uses intention locks to keep the levels honest. InnoDB makes a transaction take an IS lock on the table before an S lock on a row, and an IX lock before an X lock on a row. Intention locks don’t conflict with each other, so thousands of row lockers coexist; they only block a full-table request such as LOCK TABLES … WRITE, which can now see at a glance that someone is working inside.

Phantoms: locking rows that don’t exist yet

Row locks protect rows that exist. A transaction that runs SELECT … WHERE quota = 'tatkal' also needs to stop others inserting a new matching row, a phantom. Theory calls for predicate locks on the condition itself; engines approximate them with index ranges. InnoDB’s next-key lock covers an index record plus the gap before it, so inserts into a scanned range wait. How that plays out per isolation level, and why gap locks surprise people, is covered in transaction isolation levels in practice.

Deadlocks: detect, prevent or time out

Waiting creates a new failure: T1 holds row A and waits for B, while T2 holds B and waits for A, as when two transfers lock the same two accounts in opposite order. The database tracks a wait-for graph, where an edge T1 → T2 means T1 is waiting for a lock T2 holds. A deadlock is a cycle in that graph.

Detection lets cycles form, then breaks them.

• PostgreSQL waits deadlock_timeout (default 1 s) before running its relatively expensive check, betting that most waits end on their own. The victim gets an error; the docs warn that which transaction is chosen is hard to predict.
• InnoDB checks as soon as a transaction starts waiting and tries to roll back the smallest one, measured in rows changed. A wait-for list longer than 200 transactions is simply treated as a deadlock. With very many threads waiting on one row, detection itself becomes the bottleneck, so innodb_deadlock_detect can be turned off, leaving innodb_lock_wait_timeout (50 s by default) to break deadlocks.

Prevention makes cycles impossible.

• Lock ordering. Always lock rows in one global order, such as ascending account ID. It is the cheapest fix and the first one PostgreSQL’s docs recommend.
• Wait-die and wound-wait. Each transaction gets a timestamp when it starts. In wait-die, an older requester waits for a younger holder, and a younger requester aborts (“dies”). In wound-wait, an older requester aborts the younger holder (“wounds” it), and a younger requester waits. Only younger transactions ever abort, and a restarted one keeps its original timestamp, so it eventually becomes the oldest and finishes. Spanner uses wound-wait.
• Timeouts. lock_timeout in PostgreSQL caps any wait. It is crude, but it also catches a lock held by a stuck application, which no graph can fix.

Optimistic concurrency control

Kung and Robinson’s 1981 paper, “On Optimistic Methods for Concurrency Control”, starts from a simple observation: if transactions rarely touch the same data, locking makes every transaction pay for a conflict that seldom happens. With n equally likely items and two transactions running at the same rate, locking is really needed only about once every n transactions. So they split each transaction into three phases:

1. Read. Run freely. Reads go to the shared database; writes go to a private workspace that nobody else sees.
2. Validate. At commit, check whether anything you read was changed by a transaction that committed in the meantime.
3. Write. If validation passes, publish the private writes. If not, throw the workspace away and start again.

There are two ways to validate. Backward validation, the paper’s approach, compares your read set with the write sets of transactions that committed during your read phase; on any overlap, you abort. Forward validation compares your write set with the read sets of transactions still running, which lets the validator choose which side to abort. Either way OCC cannot deadlock, because nobody waits.

Optimism in everyday systems

You rarely run textbook OCC, but you use its core idea constantly: write only if the version you read is unchanged.

-- Read:  SELECT stock, version FROM products WHERE id = 42;   -> stock 8, version 17
UPDATE products
SET    stock = 7, version = version + 1
WHERE  id = 42 AND version = 17;
-- 1 row updated: you won.  0 rows: someone committed first; re-read and retry.

• Version columns, as above. ORMs call this optimistic locking; see optimistic vs pessimistic locking.
• ETags over HTTP. A GET returns an ETag; the client sends it back in If-Match with its PUT, and the server answers 412 Precondition Failed if someone else saved first.
• Conditional writes. A DynamoDB UpdateItem with a condition expression such as version = :expected either applies atomically or fails with a conditional-check error.
• Redis WATCH. If any watched key changes before EXEC, the whole MULTI block is discarded; Redis 8.4 also added a one-command compare-and-set (SET with IFEQ).

All of them turn a silent lost update into a visible failure that your code must handle, usually by re-reading and retrying.

Timestamp ordering

A second lock-free family fixes the serial order up front: every transaction gets a timestamp, and the outcome must match running them in timestamp order. Each item remembers the newest timestamp that read it (rts) and wrote it (wts).

• A read with ts(T) < wts(x) arrives too late, because a younger transaction already overwrote x: abort T.
• A write with ts(T) < rts(x) arrives too late, because a younger transaction already read the old value: abort T.
• A write with ts(T) < wts(x) that passes the read check can simply be skipped. This is the Thomas write rule: a younger write has already superseded it, and nobody read in between.

Pure timestamp ordering aborts transactions that a short wait would have saved, so few engines use it alone. Its ideas live on in MVCC engines that order transactions by timestamp, such as CockroachDB below.

MVCC and snapshot isolation

Multi-version concurrency control keeps several versions of each row, so a reader can see a consistent snapshot without waiting: reads never block writes and writes never block reads. Writers still block writers, so MVCC is almost always paired with row locks for updates. Engines store versions differently (details in MVCC):

• PostgreSQL writes each update as a new tuple in the table, stamped with the creating transaction (xmin) and the deleting one (xmax); dead tuples wait for vacuum.
• InnoDB updates the row in place and keeps the previous version in the undo log; a reader that needs an older version follows the row’s roll pointer and rebuilds it.
• Oracle also updates in place and rebuilds read-consistent data from undo.

Snapshot isolation (SI) is what you get when every transaction reads one snapshot taken at its start. Its rule for write–write conflicts is first updater wins: if T2 tries to change a row that a concurrent T1 has already changed and committed, T2 is aborted. PostgreSQL’s Repeatable Read is SI and reports could not serialize access due to concurrent update, which stops lost updates for free.

SI is not serializable, though. Two transactions can read overlapping data, then write different rows, so no write–write conflict ever fires. This is write skew. Say Meera and Kabir supervise a warehouse at night, and at least one must stay on shift. Each one’s transaction counts “2 on shift”, signs off only its own row, and commits. Now nobody is on shift. The two rw edges form a cycle, and SI never looked at rw edges. Oracle’s SERIALIZABLE level is actually SI, and PostgreSQL’s was too until version 9.1.

Serializable snapshot isolation

For years the choice was serializable 2PL (correct, but readers block writers) or SI (fast, but write skew). In 2008 Cahill, Röhm and Fekete proposed serializable snapshot isolation (SSI): run on SI, track rw conflicts at runtime, and abort when they line up dangerously. PostgreSQL 9.1 shipped it as Serializable, and Ports and Grittner described the implementation at VLDB 2012.

The theory is compact. Every SI anomaly’s conflict graph contains two consecutive rw edges, T1 → T2 → T3, where T3 is the first in the cycle to commit (T1 and T3 can be the same transaction, as in write skew). SSI doesn’t search for whole cycles, which is expensive. It watches for this dangerous structure and aborts a transaction as soon as one appears.

To see rw edges, a serializable transaction takes SIRead locks on what it reads; they appear in pg_locks with mode SIReadLock. They never block anyone. When a write lands on data another transaction holds an SIRead lock on, the database records an rw edge. Those locks must outlive the reader’s commit, until every overlapping transaction has finished.

The costs are bookkeeping and false positives. Not every dangerous structure closes into a cycle, and PostgreSQL coarsens SIRead locks from rows to pages to whole tables when its lock memory runs short. A sequential scan always takes a table-level SIRead lock, so a missing index raises your abort rate. Ports and Grittner measured a cost of under 7% versus plain SI on their benchmarks, and much better throughput than 2PL on read-heavy work. Your side of the deal: retry every transaction that fails with SQLSTATE 40001, mark read-only transactions READ ONLY, and keep transactions short.

Distributed concurrency control

When a transaction spans machines, locks live on each shard’s leader and commit needs two-phase commit across them.

Spanner uses strict 2PL for read-write transactions. Reads take locks at each Paxos group’s leader, wound-wait prevents deadlocks, writes are buffered at the client until commit, and two-phase commit runs across groups. The coordinator picks a commit timestamp no earlier than TrueTime’s now().latest, then performs commit wait: it reveals the commit only once TrueTime guarantees that timestamp has passed. The 2012 paper reports clock uncertainty ε varying from about 1 to 7 ms, around 4 ms most of the time, and an expected commit wait of at least 2ε, so roughly 8 ms. In return, commit timestamps respect real-time order, so read-only transactions and snapshot reads take no locks and can be served by any replica that is current enough.

CockroachDB uses MVCC with hybrid-logical-clock timestamps and runs at Serializable by default. A write lays down a write intent: a provisional MVCC value that doubles as an exclusive lock and points to the transaction’s transaction record (PENDING, STAGING, COMMITTED or ABORTED), which anyone meeting the intent checks to decide whether to wait, push or clean up. A timestamp cache remembers the latest read of each key, so a later write with an older timestamp is pushed to a newer one. A pushed transaction must refresh its reads, re-checking that nothing it read changed in between; if something did, the client gets a retry error. Deadlocks between intents are broken by aborting one transaction at random.

A third approach is deterministic ordering, as in Calvin (Thomson et al., SIGMOD 2012): agree on a global order of transactions before running them, and every replica executes that order to the same result with no commit vote. The catch is that each transaction must know its read and write sets in advance. Leaderless stores take yet another route: Cassandra’s lightweight transactions run Paxos per partition for compare-and-set (see quorums and leaderless replication).

Concurrency control in your application

The same moves appear one layer up, and picking the right one often matters more than the isolation level.

1. Make it one atomic statement. UPDATE inventory SET stock = stock - 1 WHERE sku = 'K-42' AND stock > 0 reads and writes under one row lock, leaving no window for a lost update. Check the affected-row count.
2. Lock what you read. When a decision needs several reads, SELECT … FOR UPDATE them first. Keep the transaction short and lock in a fixed order.
3. Version-check long edits. An admin editing a product page for two minutes cannot hold a lock that long; use a version column or ETag.
4. Let a constraint referee. A unique index on (show_id, seat_no), or on an idempotency key, turns a race into a clean duplicate-key error.
5. Advisory locks. pg_advisory_xact_lock(merchant_id) serializes work that isn’t a row, such as one settlement run per merchant. The database doesn’t enforce them; every caller must cooperate.
6. Distributed locks across services need a lease plus a fencing token, a number that grows with every grant so storage can reject a stale holder. See distributed locking and design a distributed lock.

Choosing by contention

Contention, the chance that two concurrent transactions touch the same data, decides which family wins.

With optimism, if each attempt conflicts with probability p, a transaction needs on average 1 / (1 − p) attempts. At p = 0.1 that is 1.1 attempts; at p = 0.5, 2; at p = 0.9, 10 attempts, and every failed attempt adds load that makes the next conflict likelier. With locking, a conflict costs waiting instead of wasted work, but a hot row serializes everyone who touches it. If each transaction holds that row’s lock for 5 ms (a read, some application logic, a write, the commit), the row can absorb at most 1,000 / 5 = 200 transactions per second, no matter how many servers you add.

So: with low contention (catalogue edits, profile updates) use version checks or SSI; with moderate contention and short transactions (wallet transfers) use row locks in a consistent order, or SSI with a retry loop; and for one hot row (a flash-sale stock counter, the last seats for a final) change the shape of the problem. Patterns for hot rows, each with its price:

• Shrink the critical section. A single conditional UPDATE holds the lock for well under a millisecond instead of 5 ms, lifting the ceiling several-fold. You give up multi-step logic inside the lock.
• Shard the counter. Split 10,000 units across 10 rows of 1,000 and decrement a random one; each row sees a tenth of the traffic. Reading the total now means summing 10 rows, and the last units need care.
• Queue through a single owner. Route every purchase for the item to one partition of a log and let one consumer decrement in memory and write in batches. No locks and a natural order, at the cost of asynchronous confirmation.
• Reserve with a TTL. Grab a short hold now, confirm payment later, and release expired holds. See contention and double booking and design a flash sale.

Failure modes in production

• Deadlock storms. Almost always a lock-order bug: two code paths update the same tables in opposite orders. Turn on log_lock_waits, read the victim’s statements, and sort keys before locking.
• Lock convoys. A popular row’s holder does something slow, every other transaction queues behind it, and throughput falls to one transaction per hold time. Shorten the hold before you add servers.
• Retry storms. Serialization failures retried instantly and in lockstep collide again and again. Cap attempts and add jittered backoff; see retry storm and timeouts, retries and backoff.
• Long transactions. A transaction left open for an hour holds locks, stops vacuum or undo purge from reclaiming old versions, and keeps SIRead locks alive, raising everyone’s abort rate. Set idle_in_transaction_session_timeout and statement timeouts.
• Silent coarsening. Short of predicate-lock memory, PostgreSQL promotes row SIRead locks to page or table locks and serialization failures jump; raise max_pred_locks_per_transaction.

Cheat sheet

How to say it in the interview

“Concurrency control is how a database makes concurrent transactions behave as if they ran one at a time. There are four basic moves. Strict two-phase locking makes conflicting transactions wait, so it needs deadlock detection or a fixed lock order. Optimistic control lets them run and validates at commit, so the loser retries. MVCC keeps old versions so readers never block writers; on its own that gives snapshot isolation, which still allows write skew, and SSI closes that gap by aborting on two consecutive read-write conflicts. Timestamp ordering fixes the order up front, which is how distributed SQL databases like CockroachDB work. In this design the seat rows are the hot spot, so I’d use one conditional UPDATE per seat backed by a unique constraint, keep transactions short, and retry serialization failures with jittered backoff.”

Optimistic or pessimistic locking for seat booking? It depends on contention per seat. For an ordinary show, two buyers rarely want the same seat in the same second, so a conditional update or version check is cheapest. For a final’s first minute, thousands chase the same rows; optimism turns into a retry storm and locking into a convoy, so hold seats with a short TTL reservation and admit buyers through a queue.

Why doesn’t MVCC alone stop write skew? Snapshot isolation only checks write–write conflicts. In write skew each transaction writes a different row, so neither conflicts; the real conflict is read–write, which SI never tracks. Fix it with Serializable (SSI), with SELECT … FOR UPDATE on the rows you read, or by materializing the conflict into one row.

How does the database find a deadlock, and how do you avoid one? It looks for a cycle in the wait-for graph: PostgreSQL after deadlock_timeout (1 s by default), InnoDB as soon as a transaction waits. It aborts a victim, which must retry. Avoid deadlocks by locking rows in a consistent order and keeping transactions short.

What does SSI cost compared with snapshot isolation? Bookkeeping for SIRead locks, under 7% in Ports and Grittner’s benchmarks, plus aborts, some of them false positives. Every client needs a retry loop for SQLSTATE 40001, and sequential scans and long transactions raise the abort rate.

Where to go next

• MVCC: how row versions are stored, made visible and cleaned up.
• Optimistic vs pessimistic locking: the two application-level styles side by side.
• Serializable isolation: what the strongest isolation level promises.
• Transaction isolation levels in practice: engine defaults, gap locks, SKIP LOCKED and retry loops.
• Distributed transactions: 2PC vs sagas: committing across services and shards.
• Distributed locking: leases, fencing tokens and their limits.
• Contention and double booking: hot-row patterns for tickets, seats and stock.

References and further reading

1. PostgreSQL documentation: Explicit Lockingpostgresql.orgRow-level lock modes, how deadlocks are detected and resolved, the advice to lock in a consistent order, and advisory locks.
2. PostgreSQL documentation: Lock Management settingspostgresql.orgdeadlock_timeout (default 1 s) and why the deadlock check is deferred; predicate-lock memory limits.
3. PostgreSQL documentation: Transaction Isolationpostgresql.orgFirst-updater-wins under Repeatable Read, how Serializable uses SSI and SIReadLock, SQLSTATE 40001, and tuning to reduce false positives.
4. Serializable Snapshot Isolation in PostgreSQL (Ports and Grittner, VLDB 2012)drkp.netDangerous structures of rw-antidependencies, SIREAD locks, false positives, and the measured cost versus snapshot isolation and 2PL.
5. On Optimistic Methods for Concurrency Control (Kung and Robinson, ACM TODS 1981)eecs.harvard.eduThe read, validation and write phases, the validation conditions, and the argument for when optimism beats locking.
6. Concurrency Control and Recovery in Database Systems (Bernstein, Hadzilacos and Goodman)microsoft.comTwo-phase locking, wait-die and wound-wait deadlock prevention, timestamp ordering and the Thomas write rule (chapters 3 and 4).
7. MySQL 8.4 Reference Manual: InnoDB Lockingdev.mysql.comShared and exclusive locks, IS and IX intention locks, record, gap and next-key locks.
8. MySQL 8.4 Reference Manual: InnoDB Deadlock Detectiondev.mysql.comImmediate detection, choosing the smallest transaction as victim, the 200-transaction wait-for limit, and innodb_deadlock_detect.
9. Spanner: Google’s Globally-Distributed Database (Corbett et al., OSDI 2012)research.googleTwo-phase locking with wound-wait for read-write transactions, commit wait and TrueTime uncertainty, and lock-free snapshot reads.
10. CockroachDB documentation: Transaction Layercockroachlabs.comWrite intents, transaction records, the timestamp cache, read refreshing and how deadlocks between intents are broken.