The invisible deadlock: two UPDATEs on one table can still form a cycle

Fictional setting, verified lab evidence. Fortex in this narrative is fictional; Tom and Ben are characters illustrating engineering reasoning. All metrics, deadlock graphs, and assertions come from the linked reproducible Docker lab, not Fortex production systems.

A Journey at Fortex · Chapter 13

Incident Room at 21:17 and Ben's Premature Confidence

The clock in the incident room showed 21:17. The dim blue glow of the Grafana dashboard reflected across Ben’s tense face.

Just this afternoon, Ben had proudly shown the team his pull request optimizing the checkout cart update flow. Instead of executing clunky queries across multiple tables as before, he had streamlined the logic into a single compact UPDATE statement targeting solely the cart_items table. P50 latency during staging tests looked pristine. Yet, at 21:00 sharp when the evening Flash Sale kicked off, the MySQL cluster logs began flooding with crimson alerts:

ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

Ben swivelled his laptop toward Tom, completely bewildered:

“I honestly don't get it, Tom! In college, textbooks always taught that deadlocks only happen when Transaction 1 locks Table A waiting for Table B, while Transaction 2 locks Table B waiting for Table A. But in my code, both requests touch only one single table: cart_items! What’s more, these two customers are modifying two entirely different rows. How on earth can two separate rows in the same table cross-lock each other into a deadlock? Shouldn't I just wrap it in a try-catch and retry three times?”

Tom did not rush to dismiss Ben. He pulled up a chair and asked gently:

“When two customers update their shopping carts with multiple items, does your system need to update the entire cart atomically, or can each item be updated independently?”

Ben hesitated: “Atomically, within a single database transaction, of course. If a customer buys two items and one succeeds while the other fails, the cart state would be corrupt.”

“Good. Now grab a marker, and trace the sequence of statements those two concurrent requests send down to the database.” Tom smiled.

Ben drew the two parallel execution paths on the whiteboard:

• Customer A’s cart contains [SKU 1, SKU 2]. Ben’s code iterates through the array: update SKU 1 first, then update SKU 2.
• Customer B receives the item list in the order returned by the mobile UI: [SKU 2, SKU 1]. Code runs: update SKU 2 first, then update SKU 1.

Ben’s hand froze mid-air. He stared at the criss-crossing arrows on the board. Before Tom even uttered a word, Ben gasped:

“Wait... Modifying the same table doesn't mean acquiring locks in the same order!”

A Deadlock is a Wait Cycle, Not a Table Count

“Exactly,” Tom nodded. “The database engine has never cared whether you are touching one table, two tables, or ten tables. The only thing the Deadlock Detector searches for is: Does the Wait-for Graph form a closed cycle?”

The minimal model of a deadlock always follows the classic formula: Transaction 1 holds Resource A and waits for Resource B; while Transaction 2 holds Resource B and waits for Resource A.

And resources here can be anything the database engine manages:

• Two different rows in the same table.
• Two entries across a Secondary Index and Clustered Index.
• A parent row protected by a Foreign Key constraint.
• Or even a gap between index keys where no physical row exists at all!

PostgreSQL’s official documentation makes this crystal clear: Deadlocks can occur purely at the row-level lock tier even when an application never issues an explicit LOCK TABLE command. When a cycle is detected, the engine automatically intervenes by choosing one transaction as a victim and aborting it to unblock the other (PostgreSQL explicit locking).

Ben looked back at his cart code: Both SKU arrays sent from the clients were completely valid, but their ordering depended on the arbitrary sequence in which users clicked items on screen.

“So the first line of defense is deterministic ordering!” Ben realized. “Before opening the transaction and running the update loop, I just need to sort the ID list in ascending order: items.sort((a, b) => a.id - b.id). When both Request A and Request B are forced to acquire SKU 1 before SKU 2, the cross-wait cycle vanishes completely!”

Tom nodded in approval, but kept the terminal open:

“Consistent lock ordering (Deterministic Lock Ordering) is indeed a golden rule. But never assume that sorting IDs solves every deadlock in existence. PostgreSQL and MySQL InnoDB have fundamentally different locking internals. If you don't understand the underlying mechanics, you will encounter deadlocks where you can't even see where the second lock came from.”

Invisible Foreign Key Cycles in PostgreSQL: When INSERT Secretly Locks the Parent Row

“Take PostgreSQL for example,” Tom continued. “At Fortex, we have a parent order table (orders) and a child line-item table (order_items). You might think that an INSERT into the child table only touches new rows in the child table, right?”

“Well, inserting a row only creates a new entry, why would it lock the parent row?” Ben wondered.

“In reality, it does. When you insert a child row referencing a foreign key (parent_id = 1), PostgreSQL must guarantee that the parent record with ID = 1 cannot be deleted or have its primary key modified while the child transaction is running!”

To achieve this, PostgreSQL automatically places a row-level lock called FOR KEY SHARE on the parent record (PostgreSQL row-level lock modes). This lock allows other transactions to read or update non-key columns of the parent, but strictly blocks any DELETE or UPDATE that modifies the primary key columns of that parent.

Conversely, if another transaction attempts to update the parent’s primary key, it must acquire a much stronger exclusive lock.

In WhyBit’s reproducible lab, two concurrent transactions were executed in PostgreSQL:

• Transaction 151: Inserts a child row referencing parent 1 (Postgres quietly grants a FOR KEY SHARE lock on parent 1). Immediately after, Transaction 151 attempts to change the primary key of parent 2: UPDATE parent SET id = 99 WHERE id = 2.
• Transaction 152: Inserts a child row referencing parent 2 (Postgres quietly grants a FOR KEY SHARE lock on parent 2). Immediately after, Transaction 152 attempts to change the primary key of parent 1: UPDATE parent SET id = 88 WHERE id = 1.

Before PostgreSQL's Deadlock Detector kicked in, querying pg_blocking_pids() captured the live wait-for graph:

151 waits_for 152
152 waits_for 151

The two transactions choked each other! PostgreSQL promptly selected one as a victim and raised deadlock detected, allowing the other to proceed.

“See that?” Tom pointed at the output. “If developers only look at the two UPDATE parent statements, they would swear a deadlock is impossible. They completely overlook that the preceding INSERT child had already grabbed a lock on the parent row!”

MySQL InnoDB: Record Locks on Indexes and Next-Key Locks Guarding the Voids

Switching to the MySQL 8.4 branch, Tom walked Ben through the specific locking mechanics of the InnoDB engine:

“In MySQL InnoDB, locks do not float over raw data rows; locks are always anchored to Index Records. When a query scans index entries, InnoDB places locks directly on those entries.”

When updating data through a Secondary Index, InnoDB first locks the record on that Secondary Index, then traverses the pointer to locate and lock the corresponding clustered index record (Primary Key). While some blog posts simplify this as a rigid rule that 'secondary always locks before primary', the actual execution plan dictates the true traversal and locking sequence (MySQL 8.4 locks set by statements).

However, the most dangerous surprise for backend engineers lies in MySQL’s default isolation level: REPEATABLE READ.

To prevent Phantom Reads according to ANSI SQL standards, InnoDB employs Next-Key Locking — the combination of a Record Lock (on the index record) and a Gap Lock (on the gap preceding that index record).

“What does that mean in practice?” Ben asked with wide eyes.

“It means InnoDB locks not only existing records, but also the entire empty space between them!” Tom emphasized.

In the verification lab:

1. Transaction 1 executes a range query: SELECT * FROM items WHERE id BETWEEN 10 AND 20 FOR UPDATE.
2. While Transaction 1 remains uncommitted, Transaction 2 attempts to insert a brand new record with id = 15.

Even though id = 15 did not exist at all in the database, Transaction 2’s INSERT was completely blocked! Transaction 2 was forced to wait for 1,584 ms in the lab until Transaction 1 finally executed COMMIT.

“That is a Lock Wait,” Tom analyzed. “In isolation, waiting is not a deadlock. But if Transaction 2 happened to hold another resource that Transaction 1 needed in its next step, a classic deadlock would instantly erupt over an empty void!” This mechanism is detailed in InnoDB locking.

Three Production Defense Layers: Inspect the Graph Before Reaching for Retries

Ben filled two pages of his notebook. He synthesized his production strategy for Fortex into three distinct defense tiers:

Layer 1: Prevention by Design

• Deterministic Lock Ordering: Always sort business identifiers (Primary Keys, SKU codes) in a strict, consistent order before executing bulk mutation queries.
• Keep Transactions Lean: Open transactions at the last possible moment and commit promptly. Never make third-party HTTP calls, render templates, or perform heavy cryptographic hashing while holding database locks.

Layer 2: Precise Exception Handling (Transaction-Level Retry)

• When the Deadlock Detector aborts a transaction, the engine automatically rolls it back completely. The application must catch the specific deadlock error code (MySQL error 1213 / SQLSTATE 40001, PostgreSQL SQLSTATE 40P01) and retry the entire transaction from the start.
• Never retry only the failed SQL statement in isolation, as the surrounding transaction has already been invalidated by the engine.
• Always employ Exponential Backoff with Random Jitter during retries to avoid having two colliding transactions wake up at the exact same millisecond and crash into each other again.

Layer 3: Rigorous Observability

• Log transaction names, targeted keys, SQLSTATE error codes, and attempt counts.
• During active incidents:
  • In PostgreSQL: Query pg_locks, pg_stat_activity, and pg_blocking_pids() to reconstruct the live wait-for graph.
  • In MySQL InnoDB: Execute SHOW ENGINE INNODB STATUS and inspect LATEST DETECTED DEADLOCK to reveal the exact statements and lock types involved.

Tom smiled and nodded, but added a vital warning:

“Remember this cardinal rule: Never blindly retry if the transaction has already produced external side-effects! If your transaction already called a payment gateway to charge a credit card before the database aborted it as a deadlock victim, an automated retry will charge the customer a second time! That is why robust distributed architectures must combine Transactional Outbox with Idempotency Keys.”

Lab Verification Evidence

All hypotheses and locking mechanics were independently verified inside isolated Docker containers running official PostgreSQL 17.6 and MySQL 8.4.7 images:

This report image is generated from run d810f6c6-1a64-4ea6-8534-bc327cd22e17: PID cycle 151 ↔ 152 and a 1,584 ms gap-insert wait. It is not a Fortex production screenshot.

Report JSON · Raw log · Lab Source Code · Run d810f6c6-1a64-4ea6-8534-bc327cd22e17

Scope & Limitations: The lab runs on a single local container node to isolate the engine's locking logic; it does not simulate production network latency or high-concurrency connection pool exhaustion. The gap lock experiment proves that non-existent keys can be blocked; it does not claim that every two-key update will deadlock.

The next morning at Fortex, Ben submitted his revised pull request:

• Cart SKU arrays were normalized and sorted ascending at the API service boundary before opening database transactions.
• Integration tests simulating concurrent requests with inverted order were added to the CI pipeline.
• Monitoring metrics were renamed from generic db_error_retry to deadlock_victim_retry — because for the first time, the engineering team understood precisely what the storage engine was doing.

Tom reviewed the PR, looked up, and asked with a grin:

“What if tomorrow’s wait-for graph doesn't involve two cart items?”

Ben smiled back confidently:

“I’ll inspect pg_blocking_pids() or SHOW ENGINE INNODB STATUS to trace the actual wait edges. I'm done guessing from table names!”

Fortex and dialogue are fictional narrative devices. All measurements, lock graphs, and technical logs are from the linked reproducible lab run.

Next: Chapter 14 — Delete Cache First or Update Database First?