Galera: parallel applier deadlocks permanently on FK parent S-lock held by a higher-seqno applier in commit-order wait; whole cluster stalls

Summary


On a 3-node Galera cluster running 11.8.6-4 (provider 26.4.26) with
wsrep_slave_threads=4 and wsrep_slave_fk_checks=ON, two parallel
applier threads on the same node reach a permanent deadlock that InnoDB
cannot detect and no timeout can break:

* Applier A holds the lowest uncommitted seqno (next in commit order) and
blocks in InnoDB waiting for a shared lock on a foreign-key parent row.

• Applier B holds the X lock on that exact parent row, carries a
  strictly higher seqno, and is itself parked in wsrep commit-order wait —
  which cannot be released until applier A commits.
  
The cycle is closed and unbreakable. Only one of the two edges is an InnoDB
  lock wait, so the InnoDB deadlock detector never fires (no
  LATEST DETECTED DEADLOCK section is produced), and appliers do not honour
  innodb_lock_wait_timeout. Apply on that node stops permanently.
  
The node then fills its receive queue, raises Galera flow control, and the
  entire cluster — including the healthy writer node — stops committing.
  Only a restart of the deadlocked node recovers the cluster.
  
This occurs in steady-state row-based apply with FK checks enabled. No DDL,
  no TOI, no bulk load, no LOAD DATA, no certification failure, no BF abort
  is involved.
h2. Impact
  
* Complete cluster-wide write stall, indefinite duration, no self-recovery.
• Flow control propagates the stall from the stuck node to the writer, so the
  node that is not faulty is the one that appears to hang to applications.
• Application connection pools saturate; user transactions sit in
  COMMIT / Waiting for certification for minutes while holding row X locks,
  producing secondary lock convoys and a rollback/retry storm as
  innodb_lock_wait_timeout expires on client sessions.
• Recovery requires operator intervention (restart of the stalled node).
• The stalled node reports Synced / Primary / wsrep_ready=ON
  throughout, so nothing in wsrep status indicates a fault.
  
h2. Environment
  


  MariaDB Enterprise Server 11.8.6-4

  wsrep provider 26.4.26

  RHEL 9.8, 3 nodes: node-a / node-b / node-c

  Writer routing: single writer (node-a); node-b and node-c apply only

  Schema: InnoDB, BINARY(16) UUID primary keys, foreign keys enforced

  Workload: Java / JPA-Hibernate, row-based replication, ~130 trx/s peak

  
  
Note on identifiers: schema, table, column, host, user and key values in this
  report are consistently pseudonymised. Structure, cardinality, lock modes,
  byte layout, counters and timings are verbatim from the capture.
  
Relevant configuration at the time of the incident:
  


  wsrep_slave_threads = 4

  wsrep_certification_rules = strict

  wsrep_slave_fk_checks = ON

  wsrep_slave_uk_checks = OFF

  wsrep_osu_method = TOI

  
  
Schema shape (the only part that matters):
  


  parent_tbl (parent_id BINARY(16) PRIMARY KEY, ... 34 columns)

  child_tbl (child_id BINARY(16) PRIMARY KEY,

  parent_id BINARY(16) NOT NULL,

  ...,

  FOREIGN KEY (parent_id) REFERENCES parent_tbl (parent_id))

  
  
h2. Steps to reproduce
  
No deterministic reproducer yet. The conditions present when it triggered:
  
# 3-node Galera cluster, single writer, wsrep_slave_threads=4 on the
  applying nodes, wsrep_slave_fk_checks=ON.

1. Parent/child tables with an enforced FK on a BINARY(16) column.
2. Concurrent write stream where multiple write-sets in a short seqno windowtouch the same FK parent row: child-row {{UPDATE}}s that write the FK column
   (even when its value is unchanged — Hibernate emits the full column list, so
   every child UPDATE re-validates the FK and takes an S lock on the parent),
   interleaved with write-sets that take an X lock on the same parent row.
3. Sustain until two such write-sets land in the same parallel-apply window with
   the X-holder at the higher seqno.
   
Observed dependency density at the time: wsrep_cert_deps_distance = 64.3,
   wsrep_apply_window = 1.71 — i.e. the apply window regularly contained
   mutually-dependent write-sets.
   
h2. Evidence
   
From a diagnostic capture of 24 samples at ~5 s intervals per node, taken on
   the affected cluster. Node node-c, sample 24, 2026-08-18 16:31:41.
   
h3. 1. The deadlock, from SHOW ENGINE INNODB STATUS
   


   Trx id counter 33699569

   Purge done for trx's n:o < 33699565 undo n:o < 0 state: running but idle

   History list length 0

   LIST OF TRANSACTIONS FOR EACH SESSION:

   ...

   ---TRANSACTION 33699567, ACTIVE 41 sec

   96 lock struct(s), heap size 17856, 98 row lock(s), undo log entries 1000

   MariaDB thread id 9, OS thread handle 140536564938304, query id 1487639 <wsrep_applier> Waiting for certification

   ---TRANSACTION 33699568, ACTIVE 41 sec

   7 lock struct(s), heap size 1120, 3 row lock(s), undo log entries 1

   MariaDB thread id 5, OS thread handle 140536565552704, query id 1487640 <wsrep_applier> Waiting for certification

   ---TRANSACTION 33699566, ACTIVE 41 sec

   4 lock struct(s), heap size 1120, 2 row lock(s), undo log entries 1

   MariaDB thread id 6, OS thread handle 140536565245504, query id 1487637 <wsrep_applier> Waiting for certification

   ---TRANSACTION 33699565, ACTIVE 41 sec updating or deleting

   mysql tables in use 1, locked 1

   LOCK WAIT 6 lock struct(s), heap size 1120, 3 row lock(s), undo log entries 1

   MariaDB thread id 2, OS thread handle 140538779006528, query id 1487636 <wsrep_applier> Update_rows_log_event::ha_update_row()

   update child_tbl set col_a='5b91c7a2-4e30-4d18-8f6b-2a71c0e94d55',

   col_json='{}',col_b='d3407f6e-91ab-4c52-b70d-6e1f83a2c904',

   col_c='7e2b45c9-0d63-4f81-9a24-51cb7e08d3f6',

   parent_id='8f2cd346-e507-4b60-9a1d-b7e39104c2f8',

   col_status='a814d2f7-6c05-4b93-8e51-3f92a6c17b48'

   where child_id='2f6c81d4-9b37-4a05-b1e8-70d4c53f9a26'

   ------- TRX HAS BEEN WAITING 40711424 us FOR THIS LOCK TO BE GRANTED:

   RECORD LOCKS space id 91008 page no 3526 n bits 320 index PRIMARY

   of table `APPDB`.`parent_tbl` trx id 33699565

   lock mode S locks rec but not gap waiting

   Record lock, heap no 71 PHYSICAL RECORD: n_fields 34; compact format; info bits 0

   0: len 16; hex b7e39104c2f89a1d4b60e5078f2cd346; asc K` , F;;

   
   
The waiting S lock is on the FK parent table, taken by
   row_upd_check_references_constraints() because the child UPDATE writes
   the parent_id column.
   
The locked record is provably the parent row named in the SQL: the application
   stores UUIDs in BINARY(16) with the byte-groups reversed, so{{parent_id='8f2cd346-e507-4b60-9a1d-b7e39104c2f8'}} is stored as
   b7e39104c2f8 + 9a1d + 4b60 + e507 + 8f2cd346 =
   b7e39104c2f89a1d4b60e5078f2cd346, which is exactly the record key above.
   
h3. 2. Both sides of the cycle, from information_schema
   


   waiting_trx waiting_thd waiting_state wait_s blocking_trx blocking_thd blocking_state

   33699565 2 LOCK WAIT 40 33699566 6 RUNNING

   waiting: `APPDB`.`parent_tbl` PRIMARY RECORD S 0xB7E39104C2F89A1D4B60E5078F2CD346

   blocking: `APPDB`.`parent_tbl` PRIMARY RECORD X 0xB7E39104C2F89A1D4B60E5078F2CD346

   
   
Same table, same index, same record. Note that trx 33699566 is RUNNING at
   the InnoDB level — it is not waiting on any lock — while its thread state is
   Waiting for certification. That is the crux: it is parked in wsrep
   commit-order wait, not in InnoDB.
   
h3. 3. All four appliers are stuck; the same is visible in the processlist
   


   Id User db Command Time State Info

   2 system user APPDB Sleep 40 Update_rows_log_event::ha_update_row() update child_tbl set ...

   5 system user NULL Sleep 39 Waiting for certification NULL

   6 system user NULL Sleep 40 Waiting for certification NULL

   9 system user NULL Sleep 39 Waiting for certification NULL

   1 system user NULL Sleep 80963 wsrep aborter idle NULL

   
   
Side note on diagnosability: appliers never certify — certification happens
   before an applier picks up a write-set. Reporting applier commit-order wait as
   Waiting for certification actively misleads operators; it sent the initial
   triage of this incident after a certification problem that did not exist. A
   distinct state string (e.g. Waiting for commit order) would be a
   worthwhile improvement in its own right.
   
h3. 4. Proof that the blocker holds a higher seqno
   
This does not rely on trx-id ordering.
   


   node-a (writer) wsrep_last_committed = 17909941 (frozen; last certified seqno)

   node-c wsrep_last_committed = 17909714 (frozen since 16:31:02)

   node-c wsrep_local_recv_queue = 223

   node-c applier threads busy = 4

   17909941 - 17909714 = 227 = 223 queued + 4 in flight (exact)

   
   
So the four appliers hold seqnos 17909715 .. 17909718.
   
Three of them (33699566, 33699567, 33699568) report commit-order
   wait, meaning each is waiting for a lower seqno to commit first — therefore
   none of them holds the lowest. By elimination the fourth, 33699565
   (thread 2, the one in LOCK WAIT), holds 17909715 and is next to commit.
   Its blocker 33699566 therefore holds one of 17909716..17909718 — strictly
   higher — and its commit-order wait cannot be satisfied until 17909715 commits.
   


   seqno 17909715 (trx 33699565, thd 2) --[InnoDB: needs S on parent row]-->

   seqno 1790971x (trx 33699566, thd 6) --[wsrep: commit-order wait]------->

   seqno 17909715

   
   
h3. 5. Why InnoDB cannot break it
   
Only the first edge is an InnoDB lock wait. The second is a wsrep commit-order
   wait, invisible to the InnoDB lock graph. Consistent with this, no
   LATEST DETECTED DEADLOCK section appears in any of the 168 captured
   samples across all three nodes. Appliers also do not honour
   innodb_lock_wait_timeout, so the wait grows without bound — measured from
   3 s to 40 s across samples 17-24 and still climbing when the node was
   restarted:
   


   sample 17 33699565 LOCK WAIT 3 s blocked by 33699566 (thd 6)

   sample 18 33699565 LOCK WAIT 8 s blocked by 33699566 (thd 6)

   sample 19 33699565 LOCK WAIT 13 s blocked by 33699566 (thd 6)

   sample 20 33699565 LOCK WAIT 19 s blocked by 33699566 (thd 6)

   sample 21 33699565 LOCK WAIT 24 s blocked by 33699566 (thd 6)

   sample 22 33699565 LOCK WAIT 30 s blocked by 33699566 (thd 6)

   sample 23 33699565 LOCK WAIT 35 s blocked by 33699566 (thd 6)

   sample 24 33699565 LOCK WAIT 40 s blocked by 33699566 (thd 6)

   
   
Same waiter, same blocker, same record, monotonically increasing — no
   progress, no rotation, no timeout.
   
h3. 6. Apply progress stops dead at the moment of the deadlock
   
node-c, wsrep_last_committed / wsrep_local_recv_queue /
   wsrep_flow_control_sent / wsrep_apply_waits per 5 s sample:
   


   16:30:41 it=13 lc=17909529 recvq=0 fc_sent=3 apply_waits=32

   16:30:46 it=14 lc=17909602 recvq=0 fc_sent=3 apply_waits=32

   16:30:52 it=15 lc=17909641 recvq=0 fc_sent=3 apply_waits=32

   16:30:57 it=16 lc=17909686 recvq=0 fc_sent=3 apply_waits=32

   16:31:02 it=17 lc=17909714 recvq=20 fc_sent=3 apply_waits=32 <-- freeze

   16:31:08 it=18 lc=17909714 recvq=74 fc_sent=3 apply_waits=32

   16:31:13 it=19 lc=17909714 recvq=121 fc_sent=3 apply_waits=32

   16:31:19 it=20 lc=17909714 recvq=191 fc_sent=3 apply_waits=32

   16:31:24 it=21 lc=17909714 recvq=223 fc_sent=4 apply_waits=32 <-- flow control

   16:31:29 it=22 lc=17909714 recvq=223 fc_sent=4 apply_waits=32

   16:31:35 it=23 lc=17909714 recvq=223 fc_sent=4 apply_waits=32

   16:31:40 it=24 lc=17909714 recvq=223 fc_sent=4 apply_waits=32

   
   
wsrep_last_committed is bit-for-bit static for 40 s while the receive queue
   climbs to its maximum and the node raises flow control. wsrep_apply_waits
   also freezes at 32 — not one applier makes any progress after the deadlock
   forms. The node remains Synced, Primary, wsrep_ready=ON,cluster_size=3, conf_id=3 throughout.
   
h3. 7. Cluster-wide cascade on the writer
   
node-a is the sole writer and is not the faulty node, yet it stops
   committing. Per 5 s sample, 16:31:33 -> 16:33:36:
   


   sample wsrep_last_committed send_q sessions in "Waiting for certification" oldest (s) sessions in LOCK WAIT

   01 17909941 9 10 11 0

   05 17909941 10 11 33 4

   11 17909941 19 19 65 12

   16 17909941 20 20 92 19

   22 17909941 27 27 124 28

   24 17909941 26 27 134 28

   
   
Notes:
   
* wsrep_last_committed on the writer never advances past 17909941 for the
   whole 2-minute window.

• The count of sessions in COMMIT / Waiting for certification tracks
  wsrep_local_send_queue exactly at every sample — these are user
  transactions blocked in replication, not in application locking.
• LOCK WAIT sessions first appear 33 s after the certification waits
  begin, and grow 0 -> 28. The direction of causation is therefore
  unambiguous: the replication stall creates the lock convoys, not the reverse.
• node-a wsrep_apply_waits=0 with send_queue >= 9 confirms
  single-writer routing (originates, does not apply).
  
Example blocked user sessions on node-a (sample 24):
  


  Id User Host db Command Time State Info

  39644 appuser localhost:xxxxx APPDB Query 134 Waiting for certification COMMIT

  39621 appuser localhost:xxxxx APPDB Query 134 Waiting for certification COMMIT

  39574 appuser localhost:xxxxx APPDB Query 134 Waiting for certification COMMIT

  39573 appuser localhost:xxxxx APPDB Query 134 Waiting for certification COMMIT

  
  
62 lock-wait edges were present on node-a in the final sample, all secondary
  convoys behind these stalled COMMITs.
  
h3. 8. Alternative explanations ruled out
  
Across all 168 samples on all 3 nodes:
  


  wsrep_local_cert_failures = 0 -> not a certification conflict

  wsrep_local_bf_aborts = 0 -> no brute-force abort involved

  wsrep_local_replays = 0 -> no transaction replay involved

  wsrep_cluster_status = Primary, size 3, conf_id 3 (stable)

  all metadata-lock captures empty -> no MDL, no TOI, no DDL involved

  
  
Earlier capture windows (16:19 and 16:27) show the same parent-row contention
  pattern between appliers resolving in under one sample interval — so thecontention is routine; only the seqno ordering makes it fatal.
  
Thread stacks (via ps wchan) show all threads in futex_do_wait — a
  clean lock wait, not a spin or a livelock.
  
h2. Relationship to MDEV-36360
  
MDEV-36360 describes the same topology in MariaDB's own wording — an applier
  holding a lock needed by a lower-seqno applier that must commit first. Our
  reading is that this is a different instance of that topology and that this
  one is not fixed:
  
|| || MDEV-36360 || This report ||

  Fix version	Fixed in 11.8.2	Reproduced on 11.8.6-4 (i.e. after the fix)
  Lock granularity	Table-level lock (bulk insert)	Record-level S lock on an FK parent row
  Statement type	Bulk INSERT	Single-row UPDATE of a child row
  FK checks	Disabled	Enabled (wsrep_slave_fk_checks=ON)
  Trigger	Bulk-load optimisation path	Ordinary steady-state row apply

  
The affected deployment is already on a release containing the MDEV-36360 fix,
  and the captured lock is a record lock taken by FK validation with checks
  enabled — the opposite of the MDEV-36360 precondition. We have also reviewed
  11.8.7 and found no change addressing this path.
  
We would ask engineering to confirm whether the MDEV-36360 fix was scoped
  narrowly to the bulk-insert table-lock case, leaving the general
  "applier holds a lock the next-to-commit applier needs" class open for
  record-level FK locks.
  
h2. Why the obvious workarounds do not apply
  
* wsrep_slave_fk_checks=OFF would remove the parent S lock and thus this
  specific edge — but MDEV-38787 (Critical, affects 11.8.6) reports that this
  setting causes large-scale replica data inconsistency and a master-node
  abort. It is not usable on this version. It is also itself named as an
  MDEV-36360 trigger.

• wsrep_certification_rules=optimized would widen the parallel-apply
  window and make the collision more likely, not less.
• innodb_lock_wait_timeout does not apply to applier threads, so no timeout
  breaks the cycle.
• Reducing the write-set column list (application-side, e.g. JPA
  @JoinColumn(updatable=false) so unchanged FK columns are not written)
  removes the FK check on the UPDATE path only. Child {{INSERT}}s still take
  the parent S lock, so the defect remains reachable.
  
The only effective mitigation found is wsrep_slave_threads=1, which
  eliminates parallel apply entirely. Measured cost is low in this workload
  (wsrep_apply_window was only 1.71 with 4 threads, and
  wsrep_commit_oooe / wsrep_commit_oool were both 0), but it removes a
  supported performance feature and does not scale to heavier write rates.
  
h2. Expected behaviour
  
A parallel applier that cannot acquire a lock because the holder is a
  higher-seqno applier in commit-order wait should not hang indefinitely.
  Any of the following would be acceptable:

1. Detect the wsrep commit-order edge in the deadlock graph (or apply a
   dedicated applier-side detector) and roll back the higher-seqno applier,
   which is safe — it has not yet committed and will simply be re-applied in
   order.
2. Do not schedule for parallel apply two write-sets that both touch an FK
   parent row when wsrep_slave_fk_checks=ON; i.e. include implicit FK parent
   references in the certification/dependency keys so they serialise.
3. At minimum: bound the wait, log the condition explicitly, and fail the node
   loudly instead of stalling the whole cluster silently while reporting
   Synced / wsrep_ready=ON.
   
Additionally, and separately: report applier commit-order wait with a state
   string other than Waiting for certification.
   
h2. Actual behaviour
   
Permanent applier hang, no detection, no timeout, no error log entry. Node
   continues to report Synced / Primary / wsrep_ready=ON. Flow control
   propagates the stall cluster-wide. Recovery only by restarting the stalled node.
   
h2. Capture inventory
   
7 diagnostic bundles, 24 samples each (~5 s interval), covering a healthy
   baseline window and the failure:
   


   20260818-161919-node-a 16:19-16:21 baseline

   20260818-161916-node-b 16:19-16:21 baseline

   20260818-161919-node-c 16:19-16:21 baseline

   20260818-162751-node-a 16:27-16:31

   20260818-162810-node-b 16:28-16:31

   20260818-162926-node-c 16:29-16:31 *** the applier deadlock ***

   20260818-163123-node-a 16:31-16:33 *** the cluster-wide cascade ***