InnoDB Locking Internals: Next-Key Locks, Gap Locks & Real-World Deadlock Cases

Correcting Three Fundamental Misconceptions

Before diving into lock types, the article corrects three common misunderstandings that lead to wrong lock analysis:

Locks are placed on index records, not "data rows". InnoDB organizes data as a clustered index (B+ tree); the only locatable position is "which index record". If an UPDATE lacks an index, a full table scan locks every visited record — effectively locking the table despite using row locks.

SELECT does not always avoid locks. Plain SELECT uses snapshot reads (MVCC) and acquires no locks. However, FOR UPDATE or FOR SHARE turns it into a current read that follows the full locking process. UPDATE and DELETE also start as current reads to evaluate conditions on the latest version.

Locks and MVCC are not parallel schemes; they divide labor. MVCC ensures consistent reads without blocking; locks enforce mutual exclusion between writes and between writes and current reads. Almost all lock waits occur among current reads.

Lock Granularity, Modes, and Seven Lock Types

Locks are described by three dimensions: granularity (table vs row), mode (shared S vs exclusive X), and type (what structure is locked). InnoDB has only table and row granularity — no page locks.

Table-Level Locks

Intention Shared (IS), Intention Exclusive (IX), Shared (S), Exclusive (X), Auto-Increment (AUTO-INC). Low overhead, high conflict probability.

Row-Level Locks (only valid inside a transaction)

Record Lock : locks a single index record. LOCK_MODE: X,REC_NOT_GAP Gap Lock : locks the open interval between two records, preventing inserts. LOCK_MODE: X,GAP Next-Key Lock : record lock + preceding gap lock, interval (prev, current]. Default unit under REPEATABLE READ. LOCK_MODE: X Insert Intention Lock : special gap lock taken before INSERT, indicating intent to insert.

LOCK_MODE: X,INSERT_INTENTION

Two Counter-Intuitive Gap Lock Properties

Gap locks do not conflict with each other — multiple transactions can hold a gap lock on the same interval.

Gap locks conflict only with insert intention locks (i.e., they only block INSERT).

These two properties create the classic deadlock: two transactions each hold a gap lock on the same interval (no conflict), then both attempt to insert (need insert intention lock), each blocked by the other's gap lock.

Why Next-Key Lock Is Left-Open, Right-Closed

For records 5, 10, 15 the next-key locks are (-∞,5], (5,10], (10,15]. Right-closed ensures the record itself is locked; left-open avoids overlapping with the previous interval, partitioning the entire index space into non-overlapping, fully covering intervals so any insert must fall into one and be blocked.

Auto-Increment Lock & MDL

innodb_autoinc_lock_mode

controls three modes (0: traditional table lock, 1: consecutive — default in 5.7, 2: interleaved — default in 8.0). Mode 2 uses lightweight mutexes, allows gaps in auto-increment values, requires ROW binlog. MDL (Metadata Lock) is a Server-layer lock protecting table structure; a long transaction holding MDL read lock can cause a DDL to wait for write lock, and all subsequent queries queue behind the DDL — a common cause of full-table stalls.

Locking Rules: Five Principles and Eight Derivations

All derivations use the same table and data:

CREATE TABLE t (id int NOT NULL, c int DEFAULT NULL, d int DEFAULT NULL, PRIMARY KEY (id), KEY c (c)) ENGINE=InnoDB; INSERT INTO t VALUES (0,0,0),(5,5,5),(10,10,10),(15,15,15),(20,20,20),(25,25,25);

Isolation level: REPEATABLE READ. id is unique; c is non-unique (critical for differences); d has no index.

Five Core Rules

Basic locking unit is next-key lock (prev, current].

Only objects actually visited during the search are locked.

Optimization 1: Unique index equality hit → next-key lock degrades to record lock.

Optimization 2: Unique index equality miss (scan stops at first non-matching value) → next-key lock degrades to gap lock.

Bug: Unique index range query continues to first non-matching value and locks it (should not).

Eight Derivations (RR)

Unique index equality hit : SELECT * FROM t WHERE id=5 FOR UPDATE → record lock on id=5 only.

Unique index equality miss : WHERE id=7 → gap lock (5,10); id=10 not locked. Practical note: querying a non-existent ID with FOR UPDATE locks a whole gap, blocking inserts.

Unique index range : WHERE id>=10 AND id<11 → record lock id=10 + next-key lock (10,15]. Bug example: WHERE id>10 AND id<=15 locks (10,15] and (15,20] (extra lock on id=20). Workaround: add LIMIT 1.

Non-unique index equality : WHERE c=5 → c-index (0,5] + (5,10) + primary key record lock on id=5 (three locks). Covering index ( SELECT id FROM t WHERE c=5 FOR SHARE) eliminates primary key lock.

Non-unique index range : WHERE c>=10 AND c<11 → c-index (5,10] + (10,15) + primary key record lock id=10.

No index : UPDATE t SET d=100 WHERE d=5 → full scan, every primary key record gets next-key lock → effectively locks entire table.

LIMIT reduces locks : WHERE c=10 LIMIT 2 stops after second match, skipping the next gap lock.

RC vs RR : RC adds no gap locks except for foreign-key/uniqueness checks. RR uses next-key locks, larger lock scope, prevents phantom reads but higher deadlock probability. Downgrading to RC requires ROW binlog and application must not rely on repeatable reads.

Core Flow: Full Locking Path of an UPDATE

Call stack:

mysql_update() → ha_update_row() → ha_innobase::update_row() → row_update_for_mysql() → row_search_mvcc()

(locate + lock) → lock_clust_rec() → lock_rec_lock() → btr_cur_update_in_place(). Key insight: locking happens during the search phase, not the modify phase — the B+ tree cursor locks each visited record as it scans.

Five Stages

Semantic preparation (Server layer: parse, optimize, pick index).

Locate and lock ( row_search_mvcc scans with cursor, calls lock function per record).

Conflict detection ( lock_rec_lock checks existing locks via compatibility matrix).

Wait or deadlock detection (enter wait queue; if innodb_deadlock_detect=ON, run detection).

Execute modification, write undo; locks held until commit/rollback.

Lock Request Life Cycle

lock_rec_lock()

fast path: if page has no locks, create lock directly. lock_rec_lock_slow() slow path: check compatibility. lock_rec_has_to_wait() confirm wait needed (exclude same transaction).

Create lock_t, insert into wait queue. lock_deadlock_check_and_resolve() DFS for cycle; if found, rollback victim (lowest weight).

Sleep until wakeup or innodb_lock_wait_timeout (default 50s).

Fast path explains why cold pages have near-zero lock overhead; hot pages become slower as contention grows.

Lock Order = Scan Order = Deadlock Root Cause

If two transactions scan the same records in different orders, deadlock is structurally possible. Example: Tx A updates id=1 then id=2; Tx B updates id=2 then id=1 → cycle. Fix: enforce consistent order (e.g., ORDER BY id in batch updates).

INSERT Locking: Implicit to Explicit

INSERT uses implicit lock via hidden column DB_TRX_ID; no lock structure created until another transaction tries to read/modify the row and finds the inserter still active — then lock_rec_convert_impl_to_expl builds an explicit lock. Saves memory/CPU for bulk inserts but makes insert deadlocks harder to predict.

Secondary Index Update Locks Two Places

Update via secondary index locks the secondary index record + primary key record (clustered index). Updating the indexed column itself adds a gap lock on the new value's insertion point. Prefer primary key lookups to halve lock count.

Core Source Code: Five Mainlines in lock0lock.cc

Directory: storage/innobase/lock/. Read order: lock0lock.h (structures) → lock_rec_lock → deadlock detection.

lock_t Structure: Bitmap per Page

struct lock_t { trx_t* trx; lock_t* trx_locks; dict_index_t* index; lock_t* hash; ulint type_mode; page_no_t page_no; ulong n_bits; byte* bitmap; };

One lock_t covers multiple rows on the same page; bitmap bits correspond to heap_no (record sequence in page). Merges locks on same page → memory and list operations reduced by an order of magnitude. Consequence: large transactions keep lock count manageable but cover many rows, killing concurrency.

Mainline 1: lock_rec_lock Fast Path

if (!lock_rec_get_first_on_page(block)) { lock_rec_create(...); return DB_SUCCESS; } return lock_rec_lock_slow(...);

First locker on a page takes fast path; subsequent lockers go through full conflict check.

Mainline 2: Conflict Detection — Two Checks

lock_rec_other_has_conflicting

iterates existing locks on the record; for each other:

Mode compatibility: S+S compatible; all other combos conflict.

Gap overlap: GAP-type locks can coexist with non-GAP locks (one locks gap, one locks record).

Same-transaction locks never conflict (upgrade/merge via bitmap).

Mainline 3: Deadlock Detection — Graph DFS

lock_deadlock_check_and_resolve()

builds wait-for graph: transactions = nodes, wait edges = directed edges. From the newly waiting transaction, DFS follows wait_lock to holder; if path returns to start, cycle found. Victim = lowest weight (weight ≈ modified rows + held locks). Large transactions often survive; small ones become victims repeatedly.

Deadlock detection and lock wait timeout are independent: detection (default ON) rolls back in milliseconds; timeout (default 50s) is fallback when detection is off.

Mainline 4: Insert Gap Check

lock_rec_insert_check_and_lock()

checks the record before the insert position ( next_rec) for GAP/NEXT_KEY locks. If none, only insert intention lock is taken; if present, insert intention lock waits. Two insert intention locks on same gap are compatible — deadlock arises only when a gap lock blocks them.

8.0 Observability

performance_schema.data_locks

+ data_lock_waits: real-time, per-lock, with wait relationships.

5.7: information_schema.INNODB_LOCKS/WAITS (limited).

Universal: SHOW ENGINE INNODB STATUS TRANSACTIONS section — only complete deadlock snapshot.

Note: data_locks shows only current held/waiting locks; implicit locks have no structure and won't appear. Check INNODB_TRX for transaction state instead.

Learning Path: Four Stages & Sixteen Interview Questions

Four Stages

Use tools (1-2 weeks) : query data_locks, data_lock_waits, INNODB_TRX; read LOCK_MODE suffixes. Graduate: identify blocker in 5 minutes.

Predict locks (2-4 weeks) : manually run the eight derivations, draw intervals, compare with data_locks. Graduate: given schema + SQL, predict 80% of lock ranges without executing.

Analyze deadlocks (1-2 months) : parse LATEST DETECTED DEADLOCK, locate conflicting index/interval from HOLDING/WAITING. Graduate: explain which two locks formed the cycle and propose fix.

Redesign (ongoing) : move from SQL fixes to design changes — batch ordering, shorter transactions, optimistic locking, RC downgrade. Graduate: design zero-deadlock bulk write scheme under load test.

Ten-Step Source Code Reading Order

lock0lock.h

lock_t

lock_rec_lock

lock_rec_lock_slow

lock_rec_other_has_conflicting

lock_rec_has_to_wait

lock_rec_create

lock_deadlock_check_and_resolve

lock_rec_insert_check_and_lock

lock_clust_rec_read_check_and_lock

trx_commit

(lock release)

Minimal Lab: Three Sessions

-- Session 1 BEGIN; UPDATE t SET d=1 WHERE id=5; -- Session 2 BEGIN; UPDATE t SET d=2 WHERE id=5; -- blocks -- Session 3 SELECT ENGINE_TRANSACTION_ID, OBJECT_NAME, INDEX_NAME, LOCK_TYPE, LOCK_MODE, LOCK_STATUS, LOCK_DATA FROM performance_schema.data_locks; SELECT * FROM performance_schema.data_lock_waits;

Vary conditions (equality, range, missing value, non-indexed column) and observe LOCK_DATA changes.

Sixteen High-Frequency Interview Questions (with answers)

InnoDB lock categories? → Table/row; row: record/gap/next-key/insert-intention; table: IS/IX/S/X/AUTO-INC; plus MDL.

Why gap locks? → Prevent phantom reads; RR requires repeatable range results.

Do gap locks conflict? → No; only conflict with insert intention locks — root cause of insert deadlocks.

Why next-key lock left-open right-closed? → Right-closed locks record; left-open avoids overlap, partitions index space.

When does row lock become table lock? → No index on condition → full scan locks every row.

RC vs RR locking difference? → RC: mostly record locks; RR: next-key locks, larger scope, prevents phantoms, more conflicts.

Insert intention lock vs intention lock? → Former: row-level, special gap lock meaning "I will insert"; latter: table-level, only records "I locked rows".

What is implicit lock? → Insert uses DB_TRX_ID instead of lock struct; explicit lock built on demand when another transaction accesses the row.

How does deadlock arise? → Circular wait from inconsistent lock order (scan order).

How does InnoDB detect deadlock? → Wait-for graph DFS from new waiter; on cycle, rollback lowest-weight transaction.

How to avoid deadlock? → Fixed lock order (sort/primary key), smaller transactions, hit indexes, shorter hold time, RC or optimistic locking.

Deadlock vs lock wait timeout? → Deadlock: cycle detected, immediate rollback (ms); timeout: no cycle, wait until innodb_lock_wait_timeout (50s).

Does covering index affect locking? → Yes; no lookup → no primary key lock, lock count halved.

How many locks for UPDATE via secondary index? → Two: secondary index record + primary key record; if updating indexed column, add gap lock on new value position.

What is MDL? Why avalanche? → Server-layer metadata lock; long transaction holds read lock, DDL waits for write lock, all subsequent queries queue behind DDL → full stall.

Why are large transactions dangerous? → Long lock hold, undo bloat, high rollback cost, replication lag, wide lock coverage; often survive deadlocks, shifting risk to small transactions.

Deadlock Troubleshooting: Three Real Cases

Reading Deadlock Log: Three Sections

SHOW ENGINE INNODB STATUS

shows latest deadlock only. Key: cross-reference HOLDS and WAITING between the two transactions.

Four-Step Reading Method

Identify what each transaction is doing ( inserting / updating).

Check if Tx1's WAITING matches Tx2's HOLDS (same location → cycle closed).

Note lock_mode and index: GAP vs REC_NOT_GAP, PRIMARY vs secondary. WE ROLL BACK TRANSACTION (N) tells victim; assess business impact.

Case 1: Concurrent Insert of Same Value (Classic)

Pattern: SELECT ... FOR UPDATE on non-existent ID, then INSERT.

-- Tx A          -- Tx B BEGIN;            BEGIN; SELECT * FROM t   SELECT * FROM t WHERE id=11       WHERE id=11 FOR UPDATE;       FOR UPDATE; -- both get gap lock (10,15) -- no conflict INSERT INTO t     INSERT INTO t VALUES(11,...);   VALUES(11,...); -- each waits for other's gap lock → deadlock

Mechanism: (1) id=11 missing → equality miss → gap lock (10,15). (2) Gap locks don't conflict → both succeed. (3) Insert needs insert intention lock → blocked by other's gap lock. (4) Cycle.

Fix : FOR UPDATE is useless here — it locks a non-existent record. Use INSERT ... ON DUPLICATE KEY UPDATE (unique index guarantees atomicity), or catch duplicate key error (1062) and retry read, or serialize with distributed lock (overkill).

Case 2: Two Update Paths, Reverse Lock Order

Table: PRIMARY(id), UNIQUE KEY uk_no(biz_no).

Tx A: UPDATE t SET status=1 WHERE biz_no='X'; -- locks uk_no record, then primary id=100 Tx B: UPDATE t SET status=2 WHERE id=100;   -- locks primary id=100, then may lock uk_no gap for new value

If B modifies biz_no or checks uniqueness, it locks uk_no gap where new value would go; A already holds uk_no record. A waits for B's primary, B waits for A's secondary → cycle.

Fix : Unify all write paths to locate by primary key first (query biz_no → get id → update by id). Fallback: optimistic locking UPDATE ... WHERE id=? AND version=? — no long lock hold, no deadlock.

Case 3: Batch Update Missing Explicit Sort

Tx A: UPDATE t SET c=1 WHERE id IN (1,2,3); Tx B: UPDATE t SET c=2 WHERE id IN (3,2,1); -- both use primary key but optimizer may choose different scan orders (range scan vs individual lookups) → order mismatch → deadlock

Fix : Add ORDER BY id to batch statements; split large batches (e.g., 500 rows) to limit blast radius.

Four On-Site Diagnostic Queries

-- 1. Who waits for whom SELECT * FROM performance_schema.data_lock_waits; -- 2. Lock details SELECT * FROM performance_schema.data_locks; -- 3. Long transactions (culprits) SELECT trx_id, trx_state, trx_started, TIMESTAMPDIFF(SECOND, trx_started, NOW()) AS secs, trx_rows_locked, trx_rows_modified FROM information_schema.INNODB_TRX ORDER BY secs DESC; -- 4. Deadlock scene SHOW ENGINE INNODB STATUS;

trx_rows_locked

is underused — directly shows how many rows a transaction locked; values in hundreds of thousands indicate missing index or massive batch.

Four-Layer Remediation

Stop bleeding (minutes) : kill longest holder / most blocked; temporarily lower innodb_lock_wait_timeout for fast failure.

Short-term (today) : add missing indexes; replace FOR UPDATE with unique constraints or optimistic locking; eliminate "select-then-insert".

Medium-term (release) : enforce batch ordering + batching; shorten transactions (move RPC out); unify write paths via primary key.

Long-term (architecture) : split hot tables, read-write separation, serialize via queues where needed, consider RC if business allows.

Must-have : application-level retry for deadlock (error 1213) and lock wait timeout (1205) — InnoDB already rolled back the transaction; retry usually succeeds.

One-Page Cheat Sheet

Essence : Locks on index records, not "rows". Division : MVCC handles read consistency; locks handle write exclusion. Granularity : Table IS/IX/S/X/AUTO-INC; Row: record/gap/next-key/insert-intention. Principle 1 : Default unit = next-key lock (prev, cur] . Principle 2 : Only visited objects get locked. Optimization 1 : Unique index equality hit → record lock. Optimization 2 : Unique index equality miss → gap lock. Bug : Unique index range query over-locks first non-matching value. Gap lock ① : No conflict with each other. Gap lock ② : Conflict only with insert. Deadlock root : Inconsistent lock order. Detection : DFS finds cycle, rolls back lowest weight. Timeout : innodb_lock_wait_timeout default 50s. Diagnose : data_lock_waits → who waits for whom. Cure : Ordering / indexes / small transactions / optimistic locking / RC / retry.

Final takeaway: Index determines lock scope, order determines deadlock, transaction length determines blast radius. If you remember one action: before writing UPDATE, run EXPLAIN to see which index it uses and how many rows it scans — that's more valuable than memorizing seven lock names.