Wait, What?
Two perfectly correct transactions can produce the wrong answer when they run at the same time.
Concurrency control exists because correctness is not only about what each transaction does in isolation. It is also about which interleavings the database permits. A professional database must allow useful overlap while preventing histories that violate the intended isolation and consistency guarantees.
This topic is ideal for algorithm learners because it connects discrete reasoning, state machines, dependency graphs, timestamps, locking, versions, validation and failure recovery to something visible: two users touching the same data at once.
Quick Answer
Learn concurrency control through the route transactions → interleavings → anomalies → schedules → serial equivalence → conflict graphs → locks → two-phase locking → deadlocks → timestamps → optimistic concurrency control → MVCC snapshots → isolation levels → serializable execution → retries → observability and workload trade-offs. A beginner should be able to trace two transactions and identify a lost update. A professional should be able to connect a production isolation guarantee to the mechanism enforcing it, reproduce anomalies, reason about aborts and blocking, and choose a strategy for a workload rather than by slogan.
1. Begin With a Two-Transaction Story
Transaction A reads an account balance. Transaction B reads the same balance. Both compute a new value and write it back. If the database permits an unsafe interleaving, one update can overwrite the other. No line of application code has to be individually wrong for the combined history to be wrong.
2. A Schedule Is the Interleaving
Write each read, write, commit and abort operation on a timeline. The same transactions can have many possible schedules. Concurrency control is fundamentally about deciding which schedules are allowed, delayed or aborted.
3. Serial Execution Is the Reference Model
If transactions run one at a time, their effects are easy to reason about. Serializability asks whether a concurrent schedule is equivalent, in the relevant sense, to some serial ordering. The database seeks the performance of overlap with the correctness of an acceptable serial outcome.
4. Learn the Anomalies Before the Mechanisms
- Lost update: one write silently replaces another transaction’s work.
- Dirty read: a transaction observes data another transaction has not committed.
- Non-repeatable read: a row changes between reads within one transaction.
- Phantom: a repeated predicate query returns a changed set of rows.
- Write skew: concurrent transactions observe a shared condition and update different rows in a way that violates a cross-row invariant.
5. Conflict Graphs Turn a Timeline Into a Proof Object
For conflict-serializability analysis, make one node per transaction and add a directed edge when conflicting operations impose an order. A cycle is evidence that the schedule cannot be conflict-serializable. This graph is small enough for hand work and powerful enough to connect history to proof.
6. Locks Make Conflicts Wait
Pessimistic approaches acquire permissions before conflicting access proceeds. Shared/exclusive ideas are the simplest starting point, but real systems expose richer lock modes and lock at multiple granularities.
PostgreSQL 18 documents table-, row- and advisory-lock behaviour and explicitly discusses deadlock detection. See PostgreSQL 18: Explicit Locking.
7. Two-Phase Locking Is About When Locks May Be Acquired and Released
In basic two-phase locking (2PL), a transaction has a growing phase in which it acquires locks and a shrinking phase after it begins releasing them. Strict variants retain important write locks until commit or abort, simplifying recovery and preventing dirty exposure.
8. 2PL Protects Serializability but Can Block
The strength of locking comes with waiting. If a transaction holds a lock that another needs, the second transaction may pause. Throughput and tail latency therefore depend on contention, transaction length and lock granularity.
9. Deadlock Is a Cycle of Waiting
If T1 holds A and waits for B while T2 holds B and waits for A, neither can progress. A wait-for graph turns this into another graph problem: nodes are transactions, and an edge means “is waiting for.” A cycle signals deadlock.
PostgreSQL detects deadlocks and aborts one participant; its documentation also recommends consistent lock ordering as a defence.
10. Deadlock Handling Is a Policy Choice
Systems can prevent particular patterns, detect cycles, use timeouts or choose victims according to cost. There is no universal winner because aggressive prevention may reduce concurrency while detection allows more overlap at the cost of abort work.
11. Timestamp Ordering Replaces Some Waiting With Order Rules
Timestamp-based protocols assign transactions logical ordering information and reject operations that would violate the required order. The learner should trace each rule against a concrete history rather than memorise a table of cases.
12. Optimistic Concurrency Control Delays the Fight
Optimistic concurrency control (OCC) lets transactions perform work under the assumption that conflicts are relatively rare, then validates before commit. When validation fails, work is discarded and retried. OCC can shine when conflicts are uncommon and transactions are short; it can waste substantial effort under heavy contention.
13. MVCC Keeps Multiple Logical Versions
Multi-Version Concurrency Control lets readers see a suitable snapshot instead of forcing every read to conflict with a concurrent write. The mental model is not “no locks anywhere”; it is “visibility is determined through versions and transaction rules, while other conflicts still require coordination.”
PostgreSQL 18 states that its multiversion model lets each statement see a database snapshot and allows ordinary reads not to block writes. See PostgreSQL 18: MVCC Introduction.
14. A Snapshot Is a Visibility Rule
When a transaction reads, the database decides which row versions are visible given transaction state and the isolation mode. This turns concurrency control into a question of which world is this statement allowed to see?
15. Isolation Levels Are User-Visible Contracts
PostgreSQL 18 exposes Read Committed, Repeatable Read and Serializable behaviours. Its default Read Committed takes a statement-level view of committed data; stronger modes constrain how the visible world can change across the transaction.
See PostgreSQL 18: SET TRANSACTION.
16. “Repeatable Read” Does Not Mean “Serializable”
A snapshot can remain stable while a multi-row invariant is still vulnerable to certain write-skew patterns, depending on the DBMS semantics. Learners should reproduce an anomaly under the real product they use instead of assuming textbook names map identically across systems.
17. Serializable Is a Behavioural Goal, Not One Single Algorithm
Different systems can deliver serializable execution using locking, predicate/range mechanisms, Serializable Snapshot Isolation, deterministic ordering or other strategies. The public guarantee and the internal enforcement mechanism are related but not identical concepts.
PostgreSQL’s Serializable mode may abort a transaction with a serialization failure when a concurrent pattern cannot be reconciled with a serial order. Applications must be prepared to retry.
18. Abort and Retry Are Part of the Algorithm
A concurrency-control scheme that preserves correctness by aborting transactions is incomplete at the application boundary unless retry behaviour is designed. Retries need bounded backoff, idempotent surrounding effects where necessary, observability and a clear failure policy.
19. Long Transactions Magnify Contention
Locks held longer block more work. Old snapshots can retain more historical versions. Validation windows become wider. Professional design often improves concurrency not through a cleverer algorithm but by reducing transaction scope.
20. Granularity Creates Another Trade-Off
A coarse table lock is cheap to manage but blocks unrelated rows. Fine-grained row or key-range locking permits more concurrency but increases metadata and coordination. Multi-granularity locking exists because real workloads need both structure and scale.
21. Index Access and Predicates Matter
Serializable correctness cannot always be reduced to rows already present. Predicate/range conflicts matter when the invariant is about a set such as “there must be at least one on-call doctor” or “no booking may overlap this interval.” This is where phantoms and predicate-style reasoning enter.
22. Build a Tiny Concurrency Laboratory
- Create two database sessions and execute the same transaction steps manually.
- Reproduce blocking with one row lock.
- Create a deadlock with reversed lock order in a disposable table.
- Run the same read sequence under Read Committed and Repeatable Read.
- Attempt a write-skew example under snapshot-style isolation.
- Run Serializable and observe which participant is forced to retry.
23. Measure the Right Quantities
Track commit throughput, abort rate, lock wait time, deadlock count, transaction latency percentiles, time spent in retry loops, version-cleanup pressure and the conflict hot spots by key or query class. Average latency alone hides contention storms.
24. Common Learning Failure States
- Believing transactions are correct because each one is correct alone.
- Memorising anomaly names without drawing a schedule.
- Treating all locks as exclusive locks.
- Believing MVCC means no locking.
- Assuming snapshot isolation is automatically serializable.
- Treating aborts as exceptional bugs rather than possible control flow.
- Retrying a transaction without considering external side effects.
- Holding transactions open while waiting for user input.
- Benchmarking with random keys and missing the hot-key workload.
- Choosing a concurrency scheme without stating the required isolation contract.
25. A Beginner-to-Professional Learning Ladder
- Level 1: interleave two transactions on paper.
- Level 2: identify lost updates and dirty reads.
- Level 3: build precedence and wait-for graphs.
- Level 4: trace shared/exclusive locks and 2PL.
- Level 5: reproduce and resolve a deadlock.
- Level 6: trace timestamp and optimistic validation rules.
- Level 7: reason about MVCC snapshots and isolation levels.
- Level 8: reproduce write skew and serialization failures.
- Level 9: instrument abort, wait and retry behaviour.
- Level 10: select and defend a concurrency strategy for a production workload.
26. Use Prediction Before Running Concurrent Code
Show a two-session schedule and ask learners to predict the final rows and which statement will block. Then run it in a disposable database, investigate the mismatch, modify the transaction order and finally design a safe version. This keeps concurrency visible rather than mystical.
27. Worked Examples Should Label the Hidden Decisions
Subgoal labels such as establish snapshot → request access → test conflict → wait/abort → validate → commit help novices see the procedure rather than drowning in SQL syntax. Programming-education research supports subgoal-labelled worked examples for reducing unnecessary cognitive load.
See Subgoal-labelled Worked Examples in Introductory Programming.
28. Connect to Existing eduKateSengkang Algorithm Work
Use Database Join Algorithms for query execution and Concurrent Algorithms for shared-memory concurrency concepts. This article owns the distinct database job of transaction histories, isolation and concurrency-control mechanisms.
29. Current Professional Context
Carnegie Mellon’s current Database Systems course continues to treat transaction processing and concurrency control as core DBMS implementation topics alongside recovery, storage and query processing. See CMU 15-445 Database Systems.
30. Professional Direction
Advanced study includes strict 2PL, intention locks, key-range locking, timestamp ordering, Thomas write rule, OCC validation designs, snapshot isolation, Serializable Snapshot Isolation, serial safety nets, deterministic concurrency control, distributed transactions, consensus interaction, distributed deadlock, TrueTime-style ordering, contention-aware admission control and formal history testing. The governing question is simple: which concurrent histories can commit, and what mechanism proves that those histories satisfy the contract?
31. Isolation Tests Need Invariants, Not Only Example Rows
A robust concurrency test defines an invariant such as “total balance remains constant,” “at least one doctor remains on call,” or “a seat is assigned at most once.” Workers then execute concurrent transactions repeatedly and the harness checks the invariant after every run. This is stronger than inspecting whether one expected row changed, because many anomalies only appear through relationships across rows or across time.
32. Conflict Rate Determines Whether Optimism Is Really Optimistic
OCC is attractive when most transactions validate successfully. Under a hot-key workload, however, repeated validation failure can turn CPU work into discarded work. Measure validation-failure rate by transaction class and key range. If a few hot records dominate, partitioning, queueing, commutative updates or explicit locking may outperform a globally optimistic design.
33. Production Retries Must Be Designed End to End
A database transaction can be retried safely only if surrounding actions are also controlled. Sending an email, charging an external payment API or publishing a message before commit can duplicate real-world effects on retry. Use transactional outbox patterns, idempotency keys or post-commit dispatch where appropriate. Concurrency control ends at the database boundary; correctness of the workflow does not.
34. A Professional Exercise: Build an Isolation Matrix
For each application operation, list the invariant, rows or ranges read, rows or ranges written, acceptable anomalies, chosen isolation level, explicit locks if any, retryable errors and expected contention. Then replay the operation under a lower isolation level to create a counterexample. The matrix forces an architectural decision to be justified by behaviour rather than by the label “stronger” or “faster.”
35. Final Learning Check
Without notes, draw a non-serial interleaving, build its precedence graph, explain why 2PL can deadlock, explain how MVCC changes reader/writer interaction, describe one OCC validation failure, and explain why Serializable applications still need retry logic. If those connections are not fluent, repeat the two-session laboratory before reading more internals.
eduKate Sengkang 