Lock-based concurrency control — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 4: Transactions, concurrency, and recovery

Prerequisites: Lesson 19 and the preceding foundations.

Learning outcomes

• Explain two-phase locking, lock compatibility, granularity, and predicate protection.
• Construct and resolve a wait-for cycle while preserving transaction correctness.
• Connect hot-key lock occupancy to throughput and fairness rather than assuming more workers remove serialization.

Two correct transfers can deadlock

Transaction A transfers from account 17 to account 22. Transaction B transfers in the opposite direction. A locks 17, B locks 22, then each requests the other’s account. Neither can proceed. Both transactions would be correct in isolation; their acquisition order creates a cycle.

Lock-based concurrency control prevents incompatible operations from observing or changing protected state simultaneously. It can provide serializable behavior under an appropriate protocol, but requires conflict modes, granularity, waiting, deadlock handling, and integration with recovery. A lock is a mechanism, not a complete isolation guarantee by itself.

Shared and exclusive protection

A shared lock permits compatible readers. An exclusive lock permits a writer while excluding conflicting access. Real engines provide more modes for tables, rows, schema, and internal structures, but the simple compatibility matrix establishes the basic idea.

A lock manager tracks ownership and waiters. The protected object might be a row, key, range, table, or logical resource. The identity must remain meaningful across changes. Protecting a physical location that can be reused requires care; logical transaction locks and physical page latches serve different purposes.

Lock acquisition can also fail through deadlines or policy. A transaction that receives an error must release every acquired resource through a defined abort path. Leaving one forgotten lock held can block unrelated work indefinitely.

Two-phase locking

In two-phase locking, a transaction first acquires locks and later releases them without acquiring new ones after the release phase begins. Under the appropriate conflict model, this can enforce serializable schedules. The protocol’s assumptions include protecting all relevant conflicting accesses, not merely the writes easiest to identify.

Strict two-phase locking retains write locks until commit or abort so other transactions do not depend on uncommitted writes. A stronger convention can retain both read and write locks until completion. Terminology varies, so a design should state the actual retention rules rather than relying only on a label.

Holding locks longer simplifies some recovery and visibility relationships but increases contention. Releasing protection early without a valid protocol can allow an interleaving that violates serializability. The choice is a correctness decision before it is a tuning parameter.

Deadlock detection

A wait-for graph has one vertex per transaction and an edge from a waiter to the transaction blocking it. A cycle indicates a deadlock in the modeled waits. In the two-transfer example, A points to B and B points to A.

A holds account 17 -> waits for account 22 held by B
B holds account 22 -> waits for account 17 held by A

Detection can run when waits occur or periodically. The engine selects a victim, aborts it, releases its locks, and allows others to continue. Victim choice can consider work performed, priority, age, and retry behavior. Repeatedly aborting the same transaction can cause starvation.

Timeouts are a coarser alternative. A long wait might be legitimate rather than cyclic, so a timeout can abort useful work unnecessarily. Detection itself has overhead and must reason over changing state safely. The engine balances prompt resolution against metadata and scheduling cost.

Prevention and acquisition order

A global order on lock identities can prevent cycles if every transaction acquires its required locks in that order. Sorting two account identifiers before locking removes the simple transfer cycle. It may be difficult when a transaction discovers its full access set only after reading data.

Other prevention schemes use transaction ages to decide who waits and who aborts. The rules must be consistent enough to prevent cycles and include a retry policy that avoids starvation. A lock upgrade from shared to exclusive can create its own deadlock pattern if several readers all attempt to upgrade.

transfer(a, b, amount):
    begin transaction
    acquire exclusive locks on distinct account IDs in sorted order
    validate ownership, amount, and sufficient funds
    apply debit and credit
    commit under required durability rule

The pseudocode assumes the lock manager protects the records and the transaction layer handles rollback and uniqueness of the business operation. Ordering locks prevents one deadlock class; it does not supply authentication, persistence, or duplicate-request handling.

Predicate protection and phantoms

Locking only rows that already exist does not necessarily protect a query result against new matching rows. A transaction checking that no reservation overlaps a time interval can read zero rows. Another transaction can then insert a conflicting reservation unless the isolation mechanism protects the predicate or an equivalent range.

Range, next-key, predicate, or serializable validation mechanisms address this in different designs. The engine must connect logical conditions to the access path used to evaluate them. An unindexed broad predicate can require broad protection, reducing concurrency. Index design can therefore affect both query speed and the granularity of serializable conflict handling.

A uniqueness constraint is a special protected predicate: no other accepted row may have the same identity. A safe implementation accounts for in-progress conflicting insertions rather than only currently committed matches. Application code that independently checks absence and inserts later without protection leaves a race.

Granularity and escalation

Fine-grained locks allow independent rows to proceed but require more metadata and lock-manager operations. Coarse-grained locks reduce metadata while blocking more work. Intention locks can express that lower-level objects are protected and allow safe coordination across a hierarchy.

Lock escalation replaces many fine-grained locks with broader protection under defined conditions. It can reduce memory pressure but introduce a sudden concurrency change. An operation that was interacting with a few rows may now block an entire table’s writers. Exact behavior is implementation-specific and should be observed rather than assumed.

The metadata itself can become contended. A global lock table with one internal mutex can serialize logically independent transactions. Sharded lock metadata and careful memory management can improve concurrency while preserving consistent ownership and deadlock information. Lesson 23 treats these internal synchronization issues.

Duration dominates hot paths

For a fully contended record held for an illustrative 4 milliseconds, the ideal serialized completion ceiling is 1/0.004 = 250/s before additional costs. Adding more clients creates more waiters, not more independent access to that record. If localizing the operation reduces the protected interval to 100 microseconds, the corresponding ideal interval ceiling becomes 10,000/s.

This is a conditional cost analysis, not a product comparison. Some operations can be restructured to shorten protection; others intrinsically depend on more work. Waiting for network calls, user interaction, or unrelated computation while holding locks can greatly increase both average and tail duration.

Fairness matters at high contention. New arrivals should not indefinitely bypass an old waiter unless the policy deliberately permits it. A priority system must account for priority inversion, where high-priority work waits on a low-priority holder. Aborting or throttling traffic can preserve progress better than letting an unlimited queue build.

Derive the lock compatibility rules

Suppose two transactions only read account 17. Shared locks can coexist because neither changes the value. A writer requesting an exclusive lock must wait for both readers, and a reader arriving after an exclusive lock cannot safely read the writer’s tentative state without another visibility mechanism. These rules produce a small compatibility matrix, but an implementation also needs queue policy and ownership tracking.

“Usually compatible” leaves room for fairness. If an exclusive waiter has already queued, admitting an endless stream of later readers can starve it. A fair queue can delay new compatible readers so the older writer eventually obtains ownership. This changes latency distribution without changing the basic correctness matrix.

A lock request belongs to a transaction, not necessarily to a particular thread. The transaction may suspend and resume on another worker. The lock table therefore records transaction identity, mode, granted owners, waiters, and cancellation state. Thread-local mutex ownership alone cannot represent a transaction that survives across asynchronous waits.

Locks also need stable resource identities. A physical row pointer can become invalid if the row moves. Logical key locks, row identifiers with controlled lifetimes, or engine-specific mappings preserve what is protected. Deleting and recreating a row under the same key raises an additional question: does a waiting request protect the logical key, one record incarnation, or an index range? Correct answers depend on the isolation contract.

Two-phase locking produces a serialization argument

During the growing phase, a transaction acquires locks and does not release them. During the shrinking phase, it releases locks and acquires no new ones. If all relevant conflicting accesses follow this discipline, the resulting schedule is conflict serializable. A transaction’s lock point—the moment it has acquired its final lock—helps construct the equivalent serial order.

Strict two-phase locking usually holds exclusive locks until commit or abort. That prevents another transaction from reading a value that might later need undo. Rigorous variants hold shared locks to the end as well. Terminology differs across descriptions, so a lesson or implementation should state actual release rules rather than rely on a name alone.

Releasing an exclusive lock before a durable or otherwise final outcome can introduce cascading dependencies. Transaction B might read A’s change and commit; A then aborts. Recovery cannot simply undo A without invalidating B. Strict release rules avoid this class of problem at the cost of longer ownership intervals. Durability and lock release must agree on which outcomes can still be reversed.

An abort path must remove granted locks and pending requests. It must also wake appropriate waiters after rollback has restored a valid visible state. Releasing first and undoing later can allow another transaction to observe intermediate rollback. Conversely, failing to remove a queued request can make an aborted transaction block others indefinitely.

Walk through a wait-for graph

Use three transactions and three resources. T1 holds A and waits for B. T2 holds B and waits for C. T3 holds C and waits for A. The wait-for graph contains edges T1 to T2, T2 to T3, and T3 to T1. No participant can resolve the cycle by ordinary progress.

T1 --needs B--> T2
 ^              |
 |              | needs C
 needs A        v
 +------------- T3

The graph represents blocking dependencies, not data-flow edges or serialization edges. Confusing those graphs leads to incorrect reasoning: an MVCC dependency cycle can cause a serialization anomaly without a lock deadlock, and a deadlock can occur even though aborting one transaction would leave a perfectly serializable result.

A detector examines a consistent-enough snapshot of wait relationships, identifies cycles, and chooses a victim. Victim cost can include work done, modified pages, rollback effort, age, and previous abort count. Always aborting the youngest is simple but can starve a steady stream of short new transactions under some workloads. A fairness policy may increase priority after repeated aborts.

The detector and grant path must synchronize. If a waiter completes while detection is running, a stale graph should not corrupt lock state. Aborting a transaction that no longer participates may waste work but can be safer than acting on an invalid pointer. Production lock managers need defined lifetimes and careful synchronization around graph inspection.

Ordering prevents some cycles, not every form of waiting

For transfers, sorting account identifiers before acquiring exclusive locks eliminates the opposite-order cycle. Every transaction takes the smaller key first. A cycle requiring strictly increasing keys to return to the starting key cannot occur. The proof depends on all relevant transactions following the same total order.

Real operations may discover additional records during execution. An application cannot claim ordered acquisition if it locks account 90, reads a relationship, then decides to lock account 12. It can gather keys first, validate them after locking, or restart when it discovers an earlier key. Each option has costs and must preserve correctness if the discovery data changes.

Lock upgrades are another source of deadlock. T1 and T2 both hold shared locks on one row; each then asks for exclusive ownership. Neither can upgrade while the other reader remains. Acquiring the necessary write lock initially, using a designated update mode, or resolving the cycle through abort can address this. A compatibility matrix with only shared and exclusive modes does not automatically solve upgrading.

Timestamp-based prevention policies choose which transaction waits and which aborts based on a stable age order. Their purpose is to forbid cycles in waiting, not to remove contention. They can shift cost from detector work to retries. An aborted transaction should generally retain the relevant age identity across retries if the policy depends on age to avoid starvation.

Predicate protection extends beyond rows that exist

Suppose a transaction checks that no active reservation overlaps the interval from 14:00 to 15:00 and then inserts a reservation. Locking only returned rows protects nothing when the result is empty. Two transactions can both find no match and insert conflicting reservations. Protecting an absence requires a predicate or a conservative range that represents potential matching inserts.

An ordered index can support gap or next-key style protection, depending on the engine. A lookup may lock the relevant interval between neighboring keys so another insertion into that interval conflicts. A coarse table lock can also be correct but reduces concurrency. Predicate dependency tracking is another approach: it records relevant reads and detects dangerous concurrent writes rather than blocking every possibility.

The chosen index affects protection granularity. An index ordered by tenant and start time can narrow the range for one tenant. Without it, a conservative scan may cover much more of the table. Query planning can therefore affect concurrency even when two plans return identical rows. An engine’s serializable implementation must remain correct for every chosen plan.

A uniqueness constraint is a specialized and efficient form of protecting an absence: no other row may occupy a particular key. It can replace an application-level “check then insert” race when the business rule genuinely is unique-key equality. It cannot express every interval or aggregate invariant. Selecting the right declarative constraint can remove custom locking while strengthening enforcement.

Intention modes and hierarchy

A hierarchical lock manager can protect tables, pages, and rows. Before locking a row, a transaction takes an intention mode on its ancestors. That announces that finer-grained locks exist below, allowing a table-level request to test compatibility without inspecting every row individually. Intention locks do not themselves imply exclusive ownership of the whole table.

Fine-grained locking increases concurrency but consumes memory and CPU per lock. If one transaction locks millions of rows, its bookkeeping can become large. Escalation replaces many fine locks with a coarser lock when permitted. This can reduce lock-table pressure while unexpectedly blocking unrelated rows. Some engines choose other policies instead, so escalation should not be assumed universally.

Partitioned lock tables can reduce internal latch contention for unrelated keys. Hot logical resources still concentrate requests in their corresponding entry. Optimizing hash-table access will not make one exclusively owned record process incompatible operations simultaneously. There are two separate bottlenecks: logical contention over data and physical contention within the lock manager.

A lock manager can also become a denial-of-service surface. A transaction opening many locks or waiting indefinitely consumes resources. Transaction timeouts, idle-in-transaction limits, per-session budgets, and admission control protect the service. Timeout selection must allow legitimate long work or provide a separate workload class rather than randomly abort every large operation.

Model the hot-key queue

Assume an illustrative hot record is exclusively held for four milliseconds per successful transaction. Its ideal service rate is 250 per second. At 200 arriving operations per second, utilization of that serialized resource is 0.8. In a simplified M/M/1 model, mean total residence time is 1 / (250 - 200), or twenty milliseconds. The four-millisecond service component is only part of the observed delay.

The exponential assumptions are deliberately restrictive. A deterministic four-millisecond service distribution has different waiting behavior, and real traffic can be bursty or correlated. The example still demonstrates why queueing rises sharply before maximum throughput is reached. A p99 target can fail while average CPU utilization across the machine looks low because the hot lock, not total CPU, is saturated.

If moving validation into the database shortens the interval from four milliseconds to one millisecond, the ideal service rate becomes one thousand per second. At the same two hundred arrivals per second, utilization falls to 0.2. This mechanism explains why eliminating transaction-held network waits can improve tail latency more than its direct millisecond saving suggests. It does not require parallel execution of incompatible updates.

Long-tail hold times can be especially harmful. A normally short transaction that pauses for one second while holding the hot lock blocks many later requests. Avoid external network calls, unbounded computation, or user think time inside the protected interval. Moving work before acquisition is safe only if its assumptions are revalidated after ownership is obtained.

Application-level correctness and implementation evidence

PostgreSQL’s explicit-locking documentation provides concrete lock modes and deadlock behavior; its transaction-isolation documentation explains relevant visibility semantics. Those product details should be distinguished from the abstract two-phase-locking model here. An engine can combine MVCC reads with lock-based writes and still need deadlock handling.

For a marketplace purchase, the smallest correct solution may be a conditional update that decreases stock only when stock remains sufficient, followed by checking whether a row changed. The database still uses its concurrency machinery internally. Avoiding manual lock statements does not mean the action has no serialization boundary; it means the platform expresses it within one atomic operation.

The engineer’s responsibility is to identify the invariant, protect every access that can break it, and keep that protection as short as correctness allows. Counting locks or praising lock-free code is less useful than tracing the exact interval, queue, and release behavior under contention. That reasoning carries into MVCC, where waiting may be reduced but dependency cycles and version retention introduce other costs.

Locate the lock point on a timeline

T1: acquire shared A -> acquire exclusive B -> LOCK POINT -> commit -> release B,A
T2:                 request B [..............wait................] -> acquire B

The lock point is the final acquisition in the illustrated growing phase. No new locks are acquired after releases begin. Holding the exclusive lock until the terminal transaction outcome prevents T2 from acting on tentative B. The diagram uses a deliberately conservative release policy; an actual engine’s MVCC reads and lock modes can differ.

If T1 performs an external request between acquiring B and commit, every incompatible B operation inherits that unpredictable delay. Moving the external request earlier shortens ownership only if T1 rechecks all relevant assumptions afterward. Moving it later may require an outbox or another side-effect protocol. The lock timeline therefore connects application structure with engine concurrency: the protected interval includes everything the application makes the engine wait for, not merely the machine instructions that update B.

Case connection and design conclusion

PostgreSQL documents explicit locking modes and transaction-isolation behavior. It uses a broader architecture than the simplified two-phase-locking model developed here, so an application should follow its documented guarantees rather than infer its exact internals from this teaching example.

A complete lock design identifies protected objects, modes, retention, predicate coverage, waiting policy, deadlock handling, and abort cleanup. Lesson 21 contrasts this with multiversion visibility, where readers can often observe an older consistent version instead of waiting for a writer, while write conflicts and invariant protection remain necessary.

Sources and further reading

• PostgreSQL 18 explicit locking
• PostgreSQL 18 transaction isolation

Course index · Lesson plan