Implement B-link tree structural modification operations in InnoDB

Background

InnoDB structural modification operations (SMOs), especially page splits and parent cascades, can serialize concurrent inserts through index-wide latching. Split-heavy workloads therefore lose scalability when many sessions insert concurrently.

Implement B-link-tree-style SMOs for MariaDB InnoDB, based on Zhao Song's design proposal:

https://kernelmaker.github.io/MySQL-proposal-1

The implementation should let readers and writers make progress while a split is published at a lower level but its separator has not yet been installed in the parent.

Goal

Implement an optional B-link representation and concurrent SMO path in InnoDB with:

• right sibling links and high-key fence records;
• two-phase split publication;
• non-latch-coupled descent with right-link traversal;
• concurrent leaf and internal-page splits;
• recursive parent cascade without normal-path global X(index) serialization;
• root raises;
• bounded retry and interruption handling;
• crash recovery of published but incomplete splits;
• per-index page-pool preallocation;
• persistent per-index feature gating and safe DDL behavior.

Functional requirements

Page and index representation

• Add a persistent dictionary flag identifying B-link indexes.
• Store a high-key fence record and right-link metadata on split pages.
• Ensure high-key records are never returned as user rows, locked as user records, counted by statistics, purged as user records, or interpreted as child pointers.
• Preserve existing page metadata such as PAGE_MAX_TRX_ID, instant-column bits, page direction hints, and segment headers.
• Existing indexes must retain their current representation. Enabling the feature affects only newly created or explicitly rebuilt supported indexes.

Search and modification

• Descend without holding parent page latches across child acquisition.
• Validate the child after acquisition and move right while the search key is outside the page's high-key fence.
• Publish the left page, right sibling, fence record, and incomplete-split marker atomically in the leaf/internal split MTR.
• Install the separator and clear the child marker in a later parent MTR.
• Support recursive internal splits and cascade-driven root raises.
• Deep-copy pending separator tuples so page reorganization or concurrent inserts cannot invalidate cascade state.
• Keep DB_BLINK_RETRY internal after a split has become durable.
• Handle KILL/interruption by rolling back the SQL statement and scheduling completion of abandoned split debt.
• Retain an explicitly serialized fallback for operations that require X(index), including row-growing pessimistic updates and undo paths.

Page allocation and lifecycle

• Writers must obtain split pages from non-blocking per-index leaf/internal pools rather than enter FSP while holding conflicting tree latches.
• Refill pools asynchronously with configurable low/high watermarks.
• Handle empty pools through bounded retry, not a fatal error.
• Make registration, refill, unregister, DROP/TRUNCATE, dictionary eviction, and shutdown safe against use-after-free, leaked pages, double-free, and latch inversion.
• Expose pool depth, refill, retry, split, cascade, right-move, and fallback counters through InnoDB status.

Crash recovery

• Detect pages carrying a durable incomplete-split marker during recovery, including pages already current on disk for which no redo record needs to be applied.
• Before normal background activity starts, install missing parent separators and clear incomplete markers.
• Complete recursive parent cascades and root raises during recovery without depending on a warm page pool.
• Keep committed bootstrap data reachable and roll back rows belonging to the transaction interrupted by the crash.
• A crash after the lower-level split MTR must not cause checksum mismatches, startup hangs, corruption reports, or permanently unsplittable pages.

Compatibility and DDL

• Gate all behavior on the persistent index flag rather than the current global sysvar.
• Define and enforce the supported index shapes and DDL operations.
• Reject unsupported online rebuild/import paths before modifying persistent state.
• Ensure CHECK TABLE, persistent statistics, purge, rollback, forward scans, and backward scans understand structural fence records.

Testing

Add deterministic MTR coverage for at least:

• index stamping and unsupported DDL;
• high-key-aware descent, forward scans, and backward scans;
• leaf split publication before parent installation;
• separator stability across right-page reorganization;
• append and balanced split selection;
• recursive internal cascade and root raise;
• IS-on-target retry and KILL during a pending cascade;
• pessimistic UPDATE, insert-by-modify, and fresh-insert undo;
• pool-empty retry, warmup, drain, and unregister/refill races;
• recovery after a crash immediately following the lower-level split MTR;
• recovery when the flagged page was flushed before the crash;
• CHECK TABLE and exact row-count/read-back validation after restart.

Performance validation

Provide a reproducible socket-based benchmark against an unmodified MariaDB build using the same server settings and dataset. The workload should be memory-resident and split-heavy, with wide primary-key records and concurrent inserts. Report throughput, latency, physical IO during the measured phase, split/cascade counters, pool-empty retries, and normal-path X(index) acquisitions.

Performance results using relaxed durability settings such as innodb_flush_log_at_trx_commit=2 must be identified as non-durability-equivalent and must not be presented as production durability results.

Acceptance criteria

*Supported newly created indexes can use the B-link path while existing unstamped indexes remain compatible.

• Concurrent leaf/internal splits and recursive parent cascades complete without normal-path X(index) serialization.
• Point lookups and forward/backward range scans remain correct while a split is published but parent installation is pending.
• Root raises, retry, KILL, rollback, purge, statistics, and CHECK TABLE complete without corruption or leaked structural records.
• Page pools refill asynchronously and survive empty-pool and lifecycle races.
• Crash tests recover both redo-only and preflushed incomplete splits without checksum failures or startup hangs.
• The complete B-link MTR regression set passes in a Debug build.
• A documented split-heavy benchmark demonstrates the scalability impact relative to vanilla MariaDB without correctness failures.