The idea: a row lock is one bit in a per-page lock object
InnoDB does not keep one lock object per locked row. It keeps one lock object (lock_t) per transaction, per page and per lock mode, and inside it a bitmap with one bit for every record slot on that page. A record's slot number is its heap_no: 0 is the infimum, 1 the supremum, and user records get 2, 3, 4… in the order they were put on the page. "T1 holds an X lock on id 2" means: in T1's X lock_t for the page that holds id 2, the bit for id 2's heap_no is set. All these objects live in one global hash table, lock_sys->rec_hash, keyed on the page id (space_id, page_no).
The canvas shows table t (id INT PRIMARY KEY, v INT) in tablespace 7. Its clustered index has two leaf pages: (7, 4) with ids 1–4 and (7, 5) with ids 5–8, each at heap_no 2–5. Under each record is its hidden DB_TRX_ID. Below the pages is rec_hash with four cells; page (7, 4) hashes to cell 2 and page (7, 5) to cell 0. Both sessions run under READ COMMITTED, so a locking read locks only the rows it returns, with no gap locks. Pick a session and a statement and press Execute, or run a demo.
One lock_t, many rows
SELECT * FROM t WHERE id IN (1,2,3) FOR UPDATE locks three rows of page (7, 4). The first row has no lock object yet, so InnoDB creates a lock_t with mode X,REC_NOT_GAP and sets bit 2. For ids 2 and 3, lock_rec_add_to_queue finds the same transaction's lock of the same mode on the same page (lock_rec_find_similar_on_page) and only sets bits 3 and 4. Id 6 is on another page, so it needs a second lock_t, in cell 0 (Demo: one lock_t, one bit per row).
That is what INFORMATION_SCHEMA.INNODB_TRX shows:
| Column | Counts | After the demo's two SELECTs |
|---|---|---|
trx_lock_structs | lock objects: record lock_ts plus table locks | 3 (IX on t, (7,4), (7,5)) |
trx_rows_locked | bits set in the record locks | 4 (ids 1, 2, 3, 6) |
trx_lock_memory_bytes | memory of those objects | a few hundred bytes |
A bitmap is allocated with n_bits = the page's heap size + 64 spare bits, so later inserts on the page still fit. 100,000 locked rows spread over 300 pages cost about 300 lock objects, not 100,000. This is why InnoDB has no lock escalation: locking many rows is cheap.
A new mode, a new lock_t
One lock_t has one mode. When T1 already holds X locks on page (7, 4) and runs SELECT … WHERE id = 4 FOR SHARE, the S request can't be a bit in the X object, so InnoDB creates a second lock_t for T1 on the same page, in mode S,REC_NOT_GAP. T2's FOR SHARE on id 4 is compatible (S with S) but belongs to another transaction, so it is a third object in the same chain (Demo: a new mode needs a new lock_t). A request that is already covered, such as an S or X request for a row whose bit is set in your own X lock, adds nothing (lock_rec_has_expl).
A wait is a lock_t with LOCK_WAIT
To check a request, InnoDB hashes the page, walks the cell's chain and, for every other transaction's lock on that page, tests the bit of the row. X conflicts with everything, S only with X. Waiting requests count too, so a newcomer can't jump the queue. When T2 runs UPDATE t SET v = v + 1 WHERE id = 2 while T1 holds bit 3, T2's request still becomes a lock_t: mode X,REC_NOT_GAP with the LOCK_WAIT flag, appended at the end of the chain. T2's thread sleeps; trx_state is LOCK WAIT and performance_schema.data_locks shows the lock with LOCK_STATUS = WAITING. After innodb_lock_wait_timeout (50 s) it would give up with error 1205.
On COMMIT, lock_release unlinks every lock object of T1 from rec_hash. Then lock_grant looks at each waiting lock on the page: if no lock ahead of it in the queue still conflicts, it clears LOCK_WAIT and wakes the thread. The granted object stays a separate lock_t; it is not merged into another one (Demo: a lock wait in the queue).
Implicit locks: an INSERT stores no lock_t
Most inserted rows are never wanted by anyone else before their transaction ends, so InnoDB doesn't create a lock object for them. The new row's DB_TRX_ID holds the inserting transaction's id, and while that transaction is active, the row counts as locked: an implicit lock. When T1 inserts id 9 into heap_no 6 of page (7, 5), its trx_rows_locked doesn't change. When T2 then runs SELECT … WHERE id = 9 FOR UPDATE, it finds no bit, reads the row's DB_TRX_ID, sees that trx 1301 is still active, and first creates an explicit X lock_t for T1 (lock_rec_convert_impl_to_expl). Only then does it queue its own waiting lock behind it (Demo: INSERT keeps an implicit lock). Rows changed by an UPDATE carry the writer's trx id too, but the UPDATE already took an explicit lock while searching.
Deadlocks
Each new wait starts a deadlock check (innodb_deadlock_detect = ON): follow "who does this waiter wait for" until it ends or comes back to the start. With T1 holding ids 1–3 and T2 holding id 6, T1's request for id 6 waits; T2's UPDATE … id = 2 would wait for T1, which waits for T2. InnoDB rolls back the transaction with the lower weight (rows changed plus lock objects), which gets ERROR 1213 (40001): Deadlock found when trying to get lock. Its lock objects leave the hash, and the other transaction's waiting lock is granted (Demo: waits on two pages, a deadlock). On a tie, the page rolls back the transaction whose request closed the cycle.
Who protects rec_hash
The hash and the queues are shared by every thread, so they need a latch. Up to MySQL 8.0.20 one global lock_sys->mutex guarded all of it, which became a bottleneck on many cores. Since 8.0.21 lock_sys is sharded: a thread that touches one page's queue takes a shared global latch plus the latch of that page's shard; only rare operations that touch many queues, such as deadlock resolution, take the global latch exclusively. The number of rec_hash cells grows with the buffer pool (about five per buffer pool page), so chains are short and pages that share a cell are rare.
See also InnoDB Record, Gap and Next-Key Locks for which locks each statement takes (the same bitmap also holds gap and next-key locks, as different modes), Inside an InnoDB Index Page for heap_no and the record list, Two-Phase Locking and Deadlock Detection for the general lock table and wait-for graph, and the PostgreSQL lock manager, which stores row locks in the row's xmax instead of in memory.
What the page leaves out
Gap, next-key and insert-intention locks (the same lock_t with other mode flags; see the gap locks page); the duplicate-key check of an INSERT, which on a row inserted by an active transaction converts its implicit lock and waits with an S lock (here a duplicate fails at once); secondary-index records, whose implicit locks are found through the page's PAGE_MAX_TRX_ID and the clustered record; lock inheritance when a record is purged or a page splits or merges (bits move to other heap_nos or pages); the separate hash tables for predicate and spatial locks; table lock objects in detail; lock wait timeouts; the real weight and victim rules; and the real hash function and table size. Only two sessions and two pages are modelled.
See where this page fits on the MySQL / InnoDB Internals mind map.