Implement Contention-Aware Transaction Scheduling (CATS) for InnoDB

1. Objective and Description of Value

Objective:
Replace or augment the current First-In-First-Out (FIFO) lock scheduling in InnoDB with a weight-based scheduling algorithm (CATS).

Value Proposition:

Throughput at Scale
Traditional FIFO scheduling is blind to the dependency structure of transactions. CATS prioritizes transactions blocking the largest number of other threads, clearing bottlenecks faster and improving overall system throughput.

Reduced Tail Latency
Under high contention (e.g., hot rows in TPC-C workloads), FIFO leads to the convoy effect. CATS has demonstrated up to 300x reduction in transaction latency during peak contention scenarios.

Modern Hardware Utilization
As CPU core counts increase, bottlenecks shift from disk I/O to internal lock manager contention. CATS enables MariaDB to maintain performance as concurrency scales into the hundreds or thousands of connections.

2. Competitive Approaches

PostgreSQL 16
Primarily relies on FIFO for heavy-weight locks. Uses Fast Path Locking for non-conflicting weak locks to bypass the lock manager. While stable, it lacks autonomous structural prioritization for high-contention write workloads.

Oracle 23ai
Introduced Priority Transactions (LOW, MEDIUM, HIGH). This policy-driven model may automatically roll back lower-priority transactions if they block higher-priority ones for too long.

SQL Server 2023
Uses Optimized Locking and Transaction ID (TID) locking. Reduces contention by consolidating row/page locks into a TID lock and uses DEADLOCK_PRIORITY to resolve conflicts.

3. MySQL’s Approach

MySQL 8.0 implemented CATS based on the Largest-Dependency-Set-First (LDSF) algorithm.

Weight Calculation
Each waiting transaction is assigned a weight equal to the number of transactions it blocks (directly and indirectly).

Selection Logic
When a lock is released, the transaction with the highest weight is granted the lock next. If weights are equal, FIFO (arrival time) is used as a tie-breaker.

Evolution
Initially enabled only under heavy contention, MySQL removed the FIFO path entirely in version 8.0.20, as CATS overhead was negligible even in low-contention scenarios.

Reference:
https://dev.mysql.com/blog-archive/contention-aware-transaction-scheduling-arriving-in-innodb-to-boost-performance/

4. Management and Observability Requirements

To ensure this feature is enterprise-ready, the following SQL-level instrumentation must be included:

Transaction Visibility
Add TRX_SCHEDULE_WEIGHT to INFORMATION_SCHEMA.INNODB_TRX.
Enables DBAs to identify “master blockers” — transactions causing the greatest system-wide delay.

System Metrics (INNODB_METRICS)
Introduce new counters:

• • lock_schedule_refreshes — Frequency of wait-for-graph analysis
  • lock_rec_grant_attempts — Lock manager grant efficiency

Autonomous Tuning
Unlike Oracle’s manual priority configuration, CATS is fully autonomous. Provides a “set-and-forget” optimization suitable for high-concurrency cloud deployments.

Thread Pool Synergy (MariaDB-specific)
Reduces stall events that trigger unnecessary thread creation in the MariaDB Thread Pool, improving CPU cache locality and reducing memory pressure.