Concurrency Catalog

Canonical Scenarios & Fixes

Inspect 10 concurrency failure scenarios based on academic isolation literature and real-world financial/distributed systems.

G-DL

Foreign Key Cascade Deadlock

Concurrent inserts into child items and cascaded parent order deletes invert the lock hierarchy.

Schema and seed data

schema.sql & seed.sql

-- Schema
CREATE TABLE parent_orders (
    id INT PRIMARY KEY,
    status TEXT NOT NULL,
    total_cents INT NOT NULL
);

CREATE TABLE child_items (
    id INT PRIMARY KEY,
    order_id INT NOT NULL REFERENCES parent_orders(id) ON DELETE CASCADE,
    sku TEXT NOT NULL,
    price_cents INT NOT NULL
);

-- Seed
INSERT INTO parent_orders VALUES (1, 'OPEN', 5000);
INSERT INTO child_items VALUES (1, 1, 'ITEM-A', 2500), (2, 1, 'ITEM-B', 2500);

Concurrent workload (chaos.yaml)

chaos.yaml

version: "1.0"
name: "foreign_key_cascade_deadlock"
operations:
  - name: "add_order_item"
    steps:
      - "INSERT INTO child_items VALUES ($monotonic_counter(10, 1), 1, 'ITEM-NEW', 1500)"
      - "UPDATE parent_orders SET total_cents = total_cents + 1500 WHERE id = 1"
  - name: "cancel_order_cascade"
    steps:
      - "UPDATE parent_orders SET status = 'CANCELLED' WHERE id = 1"
      - "DELETE FROM parent_orders WHERE id = 1"
invariants:
  - name: "referential_integrity"
    query: "SELECT count(*) AS orphan_items FROM child_items LEFT JOIN parent_orders ON child_items.order_id = parent_orders.id WHERE parent_orders.id IS NULL;"
    assert: "orphan_items == 0"

Why the invariant breaks

T1 locks child row and requests parent lock to update total; T2 locks parent row and requests cascaded child locks to delete. Lock hierarchy inversion creates deadlock (WFG cycle).

T1: Child ──► Parent ◄──► T2: Parent ──► Child

Delta debugging reduces 20 operations to the 2 that cause the failure.

Production fix

Foreign Key Indexing and Parent-First Lock Standardization

Foreign key cascade deadlocks occur because: (1) missing indexes on FK columns force table scans on child tables, acquiring broad table-level locks; and (2) insert transactions lock child first then parent, while cascades lock parent then child. Adding a dedicated B-tree index on the child FK and explicitly locking the parent record first (FOR UPDATE) normalizes the locking hierarchy and eliminates deadlock cycles.

✓ PostgreSQL✓ MySQL (InnoDB), SQLite

PostgreSQL, MySQL (InnoDB), SQLite

remediation_fix.sql

-- 1. Add Dedicated Index on Child Foreign Key Column (CRITICAL!)
CREATE INDEX idx_child_items_order_id ON child_items(order_id);

-- 2. Standardize Parent -> Child Lock Sequence during Order Cancellation:
BEGIN;
-- Explicitly lock parent row before triggering deletions:
SELECT id FROM parent_orders WHERE id = 1 FOR UPDATE;

-- Explicitly delete child items:
DELETE FROM child_items WHERE order_id = 1;

-- Delete parent order:
DELETE FROM parent_orders WHERE id = 1;
COMMIT;