Understand deadlock by gap locking in InnoDB_weixin

When we develop a web application, sometimes we want to implement a DB-related logic like SELECT and INSERT if the row is not found. However, this may cause deadlock in InnoDB under a specific condition.

This article explains what is a Gap lock, and how it causes deadlock.

A quick introduction to Gap locking

A gap lock is a lock on a gap between index records, or a lock on the gap before the first or after the last index record.

MySQL :: MySQL 8.0 Reference Manual :: 15.7.1 InnoDB Locking

In addition to foreign-key constraint checking and duplicate key checking, gap locking is enabled for searches and an index scan if the transaction isolation level is above Repeatable Read.

This locking mechanism helps to prevent other transactions from inserting into the gap while the transaction reads the range. As a result, InnoDB can prevent Phantom-Read anomaly even if InnoDB transaction isolation level is Repeatable Read.

(For more details about ANSI SQL Isolation Levels, see this awesome blog post).

A Critique of ANSI SQL Isolation Levels — Berenson et al. 1995

Gap locking prevents Phantom-Read anomalies. However, if you develop an application that concurrently INSERTs a bunch of data without knowing this locking mechanism, numerous deadlocks may occur.

A problematic case causes deadlocking

Assume that you are developing an application that executes the following SQL in a single transaction concurrently (and you cannot use INSERT ... ON DUPLICATE KEY UPDATE for some reasons).

SELECT * FROM `blog` WHERE id = ... FOR UPDATE;

-- the following query will be executed only when  
-- the row was not found in the first query.

INSERT INTO `blog` (id, title, content) VALUES (...);

where the database schema is something like this.

CREATE TABLE `blog` (
    `id` BIGINT UNSIGNED NOT NULL,
    `title` VARCHAR(512) NOT NULL,
    `content` TEXT NOT NULL,
    PRIMARY KEY (id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

(We use SELECT ... FOR UPDATE for this example, but any locking read queries can be applied to this case like UPDATE and DELETE).

Why those queries cause deadlock

As long as you successfully find a row in the first query, it’s no problem. However, if the first search query couldn’t find any rows, the problem will happen because

if the locking read statement uses a unique index with a unique search condition, InnoDB locks only the index record found.
However, if no records found by the statement, InnoDB acquire the (shared) gap lock that covers the key described by search condition.

As a result, a deadlock will happen in the following case (assume that the records whose id is 3 and 6 exist).

Transaction1: SELECT * FROM blog WHERE id = 4 FOR UPDATE; , and locks the gap between id=3 and id=6 (because it failed to find the record).
Transaction2: SELECT * FROM blog WHERE id = 5 FOR UPDATE; , and locks the gap between id=3 and id=6 (it won’t be blocked because these gap locks are shared lock).
Transaction1: INSERT INTO blog (id, ...) VALUES (4, ...); , this statement will wait because Transaction2 has already locked the gap between id=3 and id=6.
Transaction2: INSERT INTO blog (id, ...) VALUES (5, ...); , this statement will wait because Transaction1 has already locked the gap between id=3 and id=6.
Deadlock occurred!

For more details about lock mechanisms in InnoDB, see the documentation.

MySQL :: MySQL 8.0 Reference Manual :: 15.7.3 Locks Set by Different SQL Statements in InnoDB

How to "fix" deadlock

The straightforward way is just retrying the failed transaction. This is the most reliable way, but sometimes this retrying cost cannot be ignored especially for the application that requires high processing performance.

One way of resolving this problem is executing the following SQL in a single transaction instead of SELECT ... FOR UPDATE then INSERT.

INSERT INTO blog (...) VALUES (...) ON DUPLICATE KEY UPDATE id = id;  
SELECT * FROM blog WHERE id = ... FOR UPDATE;

The first query tries to INSERT a record and does nothing if the entry is duplicated. This query doesn’t acquire a gap lock that blocks locking read query in another transaction as far as the unique key isn’t duplicated.

(Technically, INSERT query does get a gap lock called Insert Intention Locks).

Therefore, this transaction can execute the same logic as “SELECT and INSERT if the row is not found” with no deadlocking.

Note that, unfortunately, this technique cannot be always appliable. For example, if there are foreign-key constraints on the unique key.