The Lock Manager

A lock request names a resource and a mode. Shared (S) is for reading under locking protocols: any number of transactions may hold S on the same resource. Exclusive (X) is for writing: one holder, nothing else granted. With row-level locking a third question arises — can a transaction that wants to lock the whole table (DDL, LOCK TABLE, a full-table write) cheaply discover that some other transaction holds locks on individual rows? Scanning the lock table for every row of the relation would be absurd.

Intention locks answer that. A transaction that is going to take S locks on rows first takes IS on the table; one that will take X on rows first takes IX. Intention locks are compatible with each other (many transactions may work on rows of one table) and conflict with table-level S or X, so a table-level request checks one entry. SIX — shared on the whole table, intending exclusive on some rows — is the classic fifth mode for "read everything, update a few". The matrix below is the entire grant policy; everything the lock manager decides is a lookup in it.

Structurally the lock manager is a hash table in shared memory — a Hash Table keyed by a resource tag: (relation 16403), (relation 16403, page 91, tuple 7), (transaction 1038), and so on. Each entry records the modes currently granted and by whom, and a queue of requests that could not be granted. A lookup is a hash of the tag, a bucket walk under a partition latch, and a matrix check of the requested mode against the union of granted modes. Grant appends the requester to the holders; wait appends it to the queue and puts the process to sleep on its own semaphore.

Release is where the wake-up logic lives. The releaser removes its entry, recomputes the granted-mode set, and walks the wait queue from the head. Each waiter whose mode is now compatible with the granted set *and* with the waiters ahead of it is granted and signalled; the walk stops at the first waiter that still conflicts, so requests are served in arrival order and a stream of shared requests cannot starve an exclusive one indefinitely. A waiter that wakes up re-checks nothing: the releaser granted it before signalling.

A blocked request does not spin. The lock manager records it in the queue, records what it waits for (the edge that Deadlock Detection: The Waits-For Graph will read), and the process sleeps on a semaphore until the releaser signals it. The wake-up therefore costs the releaser a queue walk and a signal per granted waiter, and the waiter one context switch. Under contention on one hot row this is a convoy: dozens of processes sleeping and waking in turn, each holding the row for a few microseconds, with the scheduler overhead dominating the useful work. Lock waits are visible as such — pg_stat_activity.wait_event_type = 'Lock' in PostgreSQL, data_lock_waits in MySQL — and a lock wait that lasts seconds is almost always a transaction holding a lock across something it should not be doing.

Timeouts hang off the same queue. lock_timeout arms a timer when the request is queued and removes it from the queue with an error if it fires; NOWAIT skips the queue entirely and errors on the first incompatible holder; SKIP LOCKED treats an incompatible row as if it did not match. All three are policies of the waiter, not of the table.

Every lock is an entry in a fixed-size shared-memory table. A transaction that updates ten million rows under row-level locking would need ten million entries — and in engines that store row locks in the table, that is where lock escalation comes from: past a threshold (SQL Server: about 5,000 locks on one object; DB2: a configured fraction of the lock list), the engine replaces the row locks with a single table lock. Memory is saved; every other transaction on the table now blocks. Escalation is the reason a batch job can freeze an application without any explicit LOCK TABLE in its code.

PostgreSQL does not escalate, because it does not store row locks in the table at all (next section). InnoDB does not escalate either; its bitmap-per-page representation keeps a million row locks affordable. Both can still run out of lock memory — PostgreSQL with "out of shared memory: increase max_locks_per_transaction" when a transaction touches thousands of *relations* (partitions are the usual cause), InnoDB when the lock heap exhausts the buffer pool.

PostgreSQL keeps relation-level locks in the shared hash described above, but a row lock is stored *in the row*. Locking a tuple — by UPDATE, DELETE or SELECT … FOR UPDATE — writes the locker's transaction id into the tuple's xmax field and sets infomask bits (HEAP_XMAX_LOCK_ONLY, HEAP_XMAX_EXCL_LOCK or HEAP_XMAX_KEYSHR_LOCK) that say "this xmax is a lock, not a deletion". The lock costs no shared memory, survives as long as the page does, and there is no limit on how many a transaction may hold. It also means locking a row dirties its page and produces a WAL record — a SELECT … FOR UPDATE over a million rows is a write of a million rows.

Conflict detection is then a read of the header: a second transaction finds xmax = 1038, checks whether 1038 is still running, and if so must wait. To wait it *does* use the lock table: it takes a heavyweight lock on the tuple tag (so that several waiters queue in order rather than all racing for the row when it frees) and then requests a shared lock on the *transaction id* 1038 — a lock every transaction holds exclusively on its own xid from start to end, released by COMMIT or ROLLBACK. That release is the wake-up. This is why pg_locks shows the waiter with locktype = transactionid, and why a row lock is released exactly at transaction end and never earlier. Shared row locks with many holders do not fit in one xmax; they are represented by a multixact id stored in xmax that points to a list of member xids kept in pg_multixact.

InnoDB locks live in the lock system, hashed by the page they refer to, and come in three shapes because InnoDB's REPEATABLE READ must stop phantoms in locking reads using locks alone. A record lock covers one index record. A gap lock covers the open interval *between* two index records — an insert into that interval waits, which is how a range scan prevents a row from appearing inside its range. A next-key lock is a record lock plus the gap before the record; a locking range scan (SELECT … WHERE id BETWEEN 10 AND 20 FOR UPDATE) takes next-key locks on every index record it visits and one more on the gap after the last, sealing the whole interval.

Gap locks are the source of the deadlocks and the lock waits that surprise people migrating from PostgreSQL: two transactions inserting different ids into the same gap conflict, and an UPDATE by a non-indexed column locks *every* record of the table it scanned, plus every gap. Under READ COMMITTED InnoDB drops gap locks for ordinary statements, which is the usual first remedy. Unique-key equality lookups take only a record lock, which is why point updates by primary key remain cheap.