Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Transactions and recoverable execution
Page 13 of 20

Concurrency Control

Compare the protocols that turn concurrent reads and writes into an admissible history.

Lesson briefTransactions and recoverable execution · 8 h · 4 outcomes

Required knowledge

  • Transaction histories, conflict serializability, and application invariants
  • Directed graphs, timestamps, and basic set reasoning
  • SQL update predicates and the difference between a row and a predicate

Learning outcomes

  • Trace strict two-phase locking, including lock compatibility, waits-for edges, and deadlock resolution.
  • Compare locking, timestamp ordering, optimistic validation, and MVCC by their validation point and failure mode.
  • Choose a concurrency-control boundary for a row, range, or aggregate invariant and predict its contention cost.
  • Design a retry path that does not duplicate non-transactional side effects.

Assessment target

Given an unseen schedule, lock table, or read/write-set trace, identify the protocol's decision point, prove or refute the intended serial order, and propose a bounded retry or deadlock repair.

Scope boundary

  • Lock-free index algorithms, full serializable-snapshot-isolation proofs, and vendor lock-manager tuning are outside scope.
  • Distributed concurrency protocols and consensus are treated in distributed-data work rather than as local lock-manager variants.

Two customers buy the last unit at the same instant. Each transaction reads available = 1, computes 1 - 1 = 0, and writes 0. Both commits succeed, the stock never becomes negative, and two units are sold from one. No individual statement is wrong; the interleaving is.

StepT1T2Last written available (not necessarily committed)
1read 11
2read 11
3write 00
4write 00
5commitcommit0

The lost update is the motivating problem. Isolation names an allowed history; concurrency control is the mechanism that admits or rejects individual operations on the path to that history. A stock row can be protected with a lock, a version check, a timestamp rule, or serializable dependency tracking. Those mechanisms fail differently, so a system design must choose an error it can handle rather than merely demand “no races.”

This schedule also shows why the repair must match the invariant. A conditional update SET available = available - 1 WHERE available >= 1 prevents the negative count without an explicit read, while a plain read-then-write needs a lock or version check that spans both steps. The protocol is chosen from the invariant, not from a preference for one lock mode.

Why two commits are not enough

0 / 4 answered

Both transactions in the lost-update schedule commit successfully without error. Evaluate which assertions regarding this concurrent execution are correct:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
The concurrent execution sold two units from one in stock, producing a history that is not equivalent to any serial ordering.
2
This lost update is purely a transient performance degradation caused by row lock contention rather than an integrity failure.
3
Automatic retries on application commit errors would have naturally prevented this lost update anomaly without code changes.
4
Local transaction commit success under weak isolation does not guarantee preservation of global business invariants.

Strict two-phase locking blocks unsafe orderings

Requested lockExisting sharedExisting exclusive
sharedcompatiblewait
exclusivewaitwait
Code
participant "T1" as T1
participant "lock manager" as L
participant "T2" as T2
T1 -> L : X(A) granted
T2 -> L : S(A) waits
T1 -> L : write A; COMMIT; release A
L -> T2 : S(A) granted
note right of L
T2 cannot read T1's
uncommitted value.
end note
T1lock managerT2T1T1lock managerlock managerT2T2X(A) grantedS(A) waitswrite A; COMMIT;release AS(A) grantedT2 cannot read T1'suncommitted value.

Strictness is a recovery aid as well as a serializability tool: no committed transaction has observed a value that must later be undone. It can still reduce concurrency when a long transaction holds a hot row. A carefully bounded critical transaction is often more important than choosing an exotic lock mode.

Application — lock the fact, not the screen

A reservation flow reads inventory, calls a remote payment service for 10 seconds, then decrements inventory. Should it hold an exclusive database lock during the call?

HintExpand

A database lock protects a local invariant; remote latency makes the protected interval unbounded.

Worked solutionExpand

No. Holding the lock causes a slow external system to serialize unrelated reservations and can create deadlocks. First record an idempotent payment intent or outbox state, perform the remote call outside the inventory-critical transaction, then execute a short conditional reservation transaction. The repair is an explicit state machine, not a longer lock.

For one inventory row, the critical statement can be:

UPDATE inventory
SET available = available - :quantity
WHERE sku = :sku AND available >= :quantity;

The caller must inspect the affected-row count. 1 commits the reservation; 0 means the attempt lost the race or the request is no longer satisfiable and must not be treated as success. A serialization/deadlock error may be retried with the same idempotency key, bounded attempts, and backoff; a committed success must be returned from the idempotency record rather than applied twice. The predicate is necessary but not, by itself, evidence that an aggregate invariant spanning several stock rows is protected.

Deadlock is a graph, not “a slow query”

Code
rectangle "T1\nholds X(order 7)\nwaits X(stock 9)" as T1
rectangle "T2\nholds X(stock 9)\nwaits X(order 7)" as T2
T1 --> T2 : waits for stock 9
T2 --> T1 : waits for order 7
note bottom of T2
Cycle: select a victim,
abort it, release its locks,
then retry safely.
end note
T1holds X(order 7)waits X(stock 9)T2holds X(stock 9)waits X(order 7)Cycle: select a victim,abort it, release its locks,then retry safely.waits for stock 9waits for order 7

Detection periodically finds cycles and aborts a victim. Prevention imposes an ordering, such as always locking inventory before orders. Timeouts are simpler but can abort work that would have completed and may miss an operational root cause. Victim selection weighs age, work done, locks held, and rollback cost; it must never assume the transaction’s external side effects can be undone by database rollback.

Prediction — break the cycle

T1 holds warehouse/5 and waits for sku/9; T2 holds sku/9 and waits for warehouse/5. Give one prevention and one detection response.

Worked solutionExpand

Prevention: define and enforce a global lock order, for example (warehouse_id, sku) sorted lexicographically, so both transactions request warehouse 5 before sku 9. Detection: record T1 → T2 and T2 → T1, abort a chosen victim, roll back its database work, then retry only if its operation uses an idempotency key or has no exposed external effect. Retrying without that boundary can duplicate messages or charges.

Protocols move the conflict check to different times

Worked example. A flash-sale counter has frequent writes to one row; an analytics dashboard reads millions of rows and rarely writes. One protocol need not optimize both workloads.

ProtocolWhen it rejects/confirms conflictStrengthCost / failure mode
strict 2PLlock requestclear exclusion and recoverable writeswaits and deadlocks
timestamp orderingoperation violates timestamp orderno deadlocksrestarts under hot contention
optimistic controlcommit-time read/write-set validationreaders run freely when conflicts are rareexpensive wasted work on conflict
MVCCversion visibility plus write/serializability validationreaders often avoid writer blockingold-version retention; write skew unless stronger validation

Timestamp ordering and optimistic control do not make conflicts disappear: they shift them into aborts. MVCC makes a snapshot readable, not necessarily serializable. A high-contention counter may prefer a single conditional update or a sharded/aggregated representation over a broad transaction that repeatedly aborts.

Worked example — snapshot isolation permits write skew. Two doctors are on call, and the invariant is “at least one doctor remains on call.” T1 reads the on-call set {Alice,Bob}\{\text{Alice},\text{Bob}\} and removes Alice; T2 concurrently reads the same set and removes Bob. Under snapshot isolation each transaction reads a consistent snapshot and writes a different row, so neither write conflicts with the other. Both commit, and the invariant is false. The conflict is on the predicate “the on-call set has size at least two,” not on a single row. Repairs include serializable isolation with predicate or summary-row protection, a constraint enforced by a coordinated operation, or a design that makes the aggregate a versioned object. Retrying one transaction after commit is insufficient because neither transaction observed a write conflict.

Granularity must match the invariant

InvariantSuitable shared boundaryCommon false repair
one seat never sold twiceone inventory/seat row plus conditional updateread value in application, then unconditional write
no duplicate usernameunique constraintrely on an application mutex
at least one doctor on callserializable predicate protection or summary rowlock only the doctor being changed
total monthly credit ≤ limittenant-month summary row or serializable validationlock each newly inserted invoice

Transfer — predict contention before implementing

A service records one million page views per minute and must display an approximate dashboard every minute; it also records money transfers requiring exact balances. Which path may tolerate commutative or delayed aggregation, and which cannot?

HintExpand

Separate the semantic requirement from the shared data shape.

Worked solutionExpand

Page-view counters can be sharded, buffered, or eventually aggregated when a bounded delay/error is acceptable. Money transfers require an exact invariant at commit and need a transaction/constraint boundary that prevents overdraft. Applying exact locking to every page view wastes concurrency; applying approximate aggregation to balances changes the financial contract.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 4.2.1: Strict 2PL Deadlock Precedence Cycle Detection

Verificationapplication

Consider two transactions under strict two-phase locking: T1T_1 holds an exclusive lock on row AA and requests an exclusive lock on row BB T2T_2 holds an exclusive lock on row BB and requests an exclusive lock on row AA Construct the wait-for graph, verify why this state is a deadlock, and describe how the engine resolves it.

HintExpand

Draw directed edges from the waiting transaction to the lock-holding transaction.

Worked solutionExpand

The wait-for graph contains directed edges: T1→T2T_1 \to T_2 (since T1T_1 waits for BB held by T2T_2 and T2→T1T_2 \to T_1 (since T2T_2 waits for AA held by T1T_1 The resulting cycle T1→T2→T1T_1 \to T_2 \to T_1 represents a circular wait where neither transaction can progress. The engine’s deadlock detector identifies the cycle and aborts one transaction (the victim), rolling back its operations and releasing its locks so the other can proceed.

Exercise 4.2.2: Row-Level Lock Inadequacy for Predicate Constraints

Descriptionrecall

Explain why executing SELECT * FROM Doctor WHERE on_call = true FOR UPDATE; in PostgreSQL fails to protect against phantom inserts that violate predicate-level business invariants.

HintExpand

Row locks attach only to currently existing tuples returned by the query.

Worked solutionExpand

SELECT ... FOR UPDATE acquires row-level locks strictly on existing physical tuples matching the predicate at query execution time. It cannot lock nonexistent rows. A concurrent transaction can insert a brand new Doctor record that satisfies the predicate, committing without waiting on existing row locks. Preventing phantom violations requires true predicate locks (SSI), table-level locking, or explicit locks on a parent anchor row.

Exercise 4.2.3: Atomic Conditional Write for Inventory Reservation

Constructionapplication

Write an atomic SQL update statement that decrements inventory item 42 by 1 while strictly guaranteeing that available stock never drops below zero, without requiring an explicit application-side lock or prior select.

HintExpand

Include the non-negative invariant directly in the WHERE clause and inspect row count.

Worked solutionExpand
UPDATE inventory
SET available = available - 1
WHERE item_id = 42
  AND available >= 1;

If the statement affects 1 row, the reservation succeeded atomically within single-statement execution. If it affects 0 rows, stock was exhausted, and the application safely rejects the purchase without race conditions.

Exercise 4.2.4: Workload-Aware Concurrency Control: Exact vs. Commutative Aggregation

Generalisationtransfer

A social platform handles 100,000 post like increments per second and 500 bank balance transfers per second. Contrast how concurrency control should be architected for the like counter versus the bank balance.

HintExpand

Determine whether operation order matters and whether intermediate states violate invariant constraints.

Worked solutionExpand

Like increments are commutative +1+1 can be applied in any order) and tolerate eventual consistency: they should be sharded into NN counter slots per post or buffered in an in-memory queue and flushed in batches, avoiding single-row lock serialization. In contrast, bank balance transfers are non-commutative with zero error tolerance: an account must never overdraw, requiring strict serializable isolation or row-level FOR UPDATE serialization on account balances at commit time.

References & Further Reading