Non-deterministic lock wake-up order under READ COMMITTED causes different final states
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Bug Report
### 1. Minimal reproduce step (Required)
This issue can be reproduced on TiDB v8.5.6 under `READ COMMITTED` and `REPEATABLE READ` in pessimistic transaction mode.
```sql
DROP TABLE IF EXISTS t0;
CREATE TABLE t0(c0 BOOL ZEROFILL CHECK (c0) UNIQUE);
CREATE INDEX i0 ON t0(c0) KEY_BLOCK_SIZE 4494659513140841094;
INSERT IGNORE INTO t0(c0) VALUES (NULL) ON DUPLICATE KEY UPDATE c0='i';
CREATE INDEX i99 ON t0(c0 ASC);
INSERT IGNORE INTO t0 VALUES (1057912112) ON DUPLICATE KEY UPDATE c0=(('')OR(t0.c0));
INSERT INTO t0(c0) VALUES (0.7209893184562981) ON DUPLICATE KEY UPDATE c0=((-1728827189) IS TRUE);
```
Use three sessions. Set the transaction mode and isolation level in each session:
```sql
SET SESSION tidb_txn_mode = 'pessimistic';
SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED;
```
Transaction 1:
```sql
BEGIN;
[1-0] BEGIN;
[1-1] UPDATE t0 SET c0=((t0.c0)<<(t0.c0)) WHERE ((((false)OR(-1728827189))) IS NULL);
[1-2] SELECT t0.c0 FROM t0 WHERE NULL FOR UPDATE;
[1-3] DELETE FROM t0;
[1-4] SELECT t0.c0 FROM t0 FOR UPDATE;
[1-5] INSERT LOW_PRIORITY IGNORE INTO t0 VALUES (1.057912112E9), ('');
[1-6] COMMIT;
```
Transaction 2:
```sql
[2-0] BEGIN;
[2-1] DELETE FROM t0 LIMIT 30949414;
[2-2] INSERT IGNORE INTO t0 VALUES ('a'), (true) ON DUPLICATE KEY UPDATE c0=DEFAULT(t0.c0);
[2-3] SELECT t0.c0 FROM t0 WHERE FALSE FOR UPDATE;
[2-4] DELETE FROM t0 WHERE t0.c0;
[2-5] COMMIT;
```
Transaction 3:
```sql
[3-0] BEGIN;
[3-1] UPDATE t0 SET c0=true WHERE t0.c0;
[3-2] DELETE FROM t0 LIMIT 50822292;
[3-3] UPDATE t0 SET c0=-365631123;
[3-4] INSERT INTO t0 VALUES (1) ON DUPLICATE KEY UPDATE c0=0;
[3-5] COMMIT;
```
Execute the statements in the following order:
```sql
[1-0] BEGIN;
[1-1] UPDATE t0 SET c0=((t0.c0)<<(t0.c0)) WHERE ((((false)OR(-1728827189))) IS NULL);
[3-0] BEGIN;
[1-2] SELECT t0.c0 FROM t0 WHERE NULL FOR UPDATE;
[1-3] DELETE FROM t0;
[1-4] SELECT t0.c0 FROM t0 FOR UPDATE;
[3-1] UPDATE t0 SET c0=true WHERE t0.c0;
-- [3-1] is blocked by Transaction 1.
[2-0] BEGIN;
[1-5] INSERT LOW_PRIORITY IGNORE INTO t0 VALUES (1.057912112E9), ('');
[2-1] DELETE FROM t0 LIMIT 30949414;
-- [2-1] is also blocked by Transaction 1.
[1-6] COMMIT;
[3-1] UPDATE t0 SET c0=true WHERE t0.c0;
-- [3-1] is resumed and [2-1] is still blocked
[3-2] DELETE FROM t0 LIMIT 50822292;
[3-3] UPDATE t0 SET c0=-365631123;
[3-4] INSERT INTO t0 VALUES (1) ON DUPLICATE KEY UPDATE c0=0;
[3-5] COMMIT;
[2-1] DELETE FROM t0 LIMIT 30949414;
-- [2-1] is resumed
[2-2] INSERT IGNORE INTO t0 VALUES ('a'), (true) ON DUPLICATE KEY UPDATE c0=DEFAULT(t0.c0);
[2-3] SELECT t0.c0 FROM t0 WHERE FALSE FOR UPDATE;
[2-4] DELETE FROM t0 WHERE t0.c0;
[2-5] COMMIT;
```
### 2. What did you expect to see? (Required)
I expected the lock wake-up order to be deterministic for the same test case, same isolation level, same initial data, and same execution schedule.
In this case, `[3-1]` is blocked by Transaction 1 first, and `[2-1]` is also blocked by Transaction 1 later. When Transaction 1 commits, both Transaction 2 and Transaction 3 are waiting for locks held by Transaction 1. Therefore, I think `[3-1]` should be unblocked first, and then after Transaction 3 commits, `[2-1]` should be unblocked.
For the same isolation level and the same schedule, I expected TiDB to wake up the blocked transactions in a consistent order. Therefore, the final database state should also be deterministic.
I also expected the wake-up behavior under `READ COMMITTED` and `REPEATABLE READ` to be consistent for this kind of pessimistic locking case.
### 3. What did you see instead (Required)
Under `READ COMMITTED`, the wake-up order is non-deterministic.
In most executions, after `[1-6] COMMIT`, `[3-1]` is resumed first. Then Transaction 3 continues. After Transaction 3 commits, `[2-1]` is unblocked. The final table state should be:
```sql
SELECT * FROM t0;
+----+
| c0 |
+----+
| 0 |
+----+
```
However, with the same initial data, same SQL statements, same isolation level, and same execution schedule, sometimes `[2-1]` is resumed first after `[1-6] COMMIT`. Then Transaction 2 continues. After Transaction 2 commits, `[3-1]` is unblocked. The final table state becomes:
```sql
SELECT * FROM t0;
+----+
| c0 |
+----+
| 1 |
+----+
```
This result and situation that `[2-1]` is resumed first after `[1-6] COMMIT` is the same as what I observed under `REPEATABLE READ`.
So under `READ COMMITTED`, repeated executions of the same schedule may produce different wake-up orders:
```text
Case A:
[1-6] COMMIT
=> [3-1] resumes first
=> [2-1] resumes later
=> final state: c0 = 0
Case B:
[1-6] COMMIT
=> [2-1] resumes first
=> [3-1] resumes later
=> final state: c0 = 1
```
This looks suspicious because the same schedule and same isolation level can produce different final database states.
I think the wake-up order of blocked transactions should be consistent for the same workload. Otherwise, the final result of the same concurrent transaction schedule becomes non-deterministic.
### 4. What is your TiDB version? (Required)
```sql
mysql> select version();
+--------------------+
| version() |
+--------------------+
| 8.0.11-TiDB-v8.5.6 |
+--------------------+
```
Contributor guide
Assessment
This issue has not been assessed yet.