From a Chocolate Wrapper to Concurrent InnoDB Page Splits
This work started from a conversation with Monty Widenius at Meet Magento Czech in August. We discussed possible ways to improve the scalability of the InnoDB B+Tree, especially its insert path and page splits.
Monty explained several ideas about reducing synchronization during structural changes and allowing independent parts of the tree to make progress concurrently. We did not have a whiteboard, so we made the first design sketch on the back of a dark chocolate wrapper.
The sketch contained a small B+Tree, several page links, and the basic idea of moving structural work outside the globally serialized path. It was only an informal drawing, but it defined the direction of the experiment.
Where the experiment started: a B+Tree split sketch made with Monty Widenius on the back of a dark chocolate wrapper at Meet Magento Czech.
After the conference, I started researching whether there is B-link-related works in the M-ecosystem. The main technical source for this work was Zhao Song’s proposal for improving the InnoDB insert path with B-link-style concurrent page splits. I want to express my gratitude to Zhao Song for his work that enables this feature.
The proposal describes a fundamental limitation of the traditional insert path: structural modification operations are serialized through an index-wide latch, even when different threads split unrelated leaf pages. I used its architectural ideas as the starting point for designing and implementing B-link-style indexes in MariaDB.
The resulting prototype reached 102,838 inserts per second on a controlled split-heavy workload. Vanilla MariaDB reached 19,676 inserts per second under the same conditions. This is a 5.23x throughput improvement.
Why page splits are difficult to scale
A regular optimistic insert is relatively simple. InnoDB locates the target leaf page, takes an X latch on this page, and inserts the new record if enough free space is available.
The situation changes when the page is full. InnoDB must allocate another page, distribute records between the old and new pages, update sibling links, and install a new node pointer into the parent. If the parent is also full, the split continues to the next level.
search leaf
→ optimistic insert fails
→ enter pessimistic insert path
→ acquire index-wide latch
→ allocate a page
→ split the leaf
→ update the parent
→ possibly split the parent
→ release the latchesThe index-wide latch makes the operation easier to reason about, but it serializes unrelated structural changes.
Thread A: split leaf 100 ─┐
Thread B: split leaf 500 ─┼─ one index latch ─ one split at a time
Thread C: split leaf 900 ─┘The B-link approach
A B-link tree allows a child split to become visible before the parent contains the final node pointer. The left page receives a high key and a right link to the new page. A concurrent search compares its target with the high key and follows the right link when necessary.
The split is published in two phases:
- Publish the new sibling, right link, high key, and incomplete-split marker.
- Install the node pointer into the parent and clear the incomplete-split marker.
Before: After publication: After completion:
Parent Parent Parent
| | | |
L L --right-link--> N L N
high-keyBetween the phases, the tree is temporarily incomplete, but it remains searchable. This removes the requirement to hold the complete affected subtree until the parent cascade finishes.
Implementing the design in MariaDB
Applying the design to MariaDB required coordinated changes in several areas:
- Page representation and validation
- Cursor navigation
- Mini-transaction ownership
- Page and index latch management
- Leaf and internal page splits
- Parent cascade and root raise
- Page preallocation
- Dictionary object lifetime
- Recovery of interrupted splits
- DDL and adaptive hash restrictions
Persistent index type
B-link indexes are marked with a persistent DICT_BLINK flag. The innodb_blink_enabled variable is only a creation policy. It does not convert an existing index.
SET GLOBAL innodb_blink_enabled=OFF;
CREATE TABLE vanilla_table (...);
SET GLOBAL innodb_blink_enabled=ON;
CREATE TABLE blink_table (...);Changing the type of an existing index requires a physical rebuild.
High-key records and descent
A non-rightmost B-link page contains a structural high-key record immediately before supremum. It has a node-pointer shape and uses FIL_NULL as a child-page sentinel. Cursor navigation, statistics, purge, rollback, record locking, and validation must recognize and skip it.
B-link descent keeps a shared index latch but does not retain page latches for the full root-to-leaf path. If a concurrent split makes a selected page stale, the search follows the right link.
page = root
while page.level > target_level:
latch(page, S)
while key > page.high_key:
page = page.right
child = select_child(page, key)
unlatch(page)
page = childPer-level mini-transactions
The leaf split and every parent-cascade level are committed in separate mini-transactions. MariaDB did not have the required operation for transferring index-latch ownership between them, so an explicit mtr_t::transfer_to() mechanism was added.
Adaptive append splits
My first chooser always selected a byte-balanced boundary. It was correct, but it left two half-full pages during preload. Later middle inserts fitted without splitting, so the measured phase did not exercise split contention.
Balanced split:
L: approximately 50% full
N: approximately 50% full
Append/no-move split:
L: all old records plus the new high key
N: the newly inserted recordThe final implementation uses the page-local last-insert direction. A real right-edge append can keep all old records on the left page. This leaves old pages densely packed. Before this change the measured phase produced zero leaf splits; afterwards almost every measured insert caused one.
Preallocating split pages
A split cannot safely enter an arbitrary blocking tablespace allocation path while holding the leaf X latch. Each B-link index therefore owns a pool of allocated but not yet linked pages. Writers only pop page numbers; a background thread refills the pool outside the split mini-transaction.
The preallocator uses registry snapshots, separate leaf and internal watermarks, per-pool refill requirements, round-robin allocation, and a limit of 256 allocations per wake. It sleeps for 100 ms only when no work was completed.
For the final benchmark it prepared 450,000 leaf pages and 512 internal pages in 5.2 seconds. Such a large pool is useful for an isolated benchmark, but it is not a practical production default.
Correctness and recovery
The prototype has runtime completion for abandoned cascades and startup recovery for persistent incomplete splits. It disables adaptive hash for B-link indexes and rejects DDL operations that cannot preserve the new invariants.
Targeted tests cover index creation, descent, pool lifecycle, append splits, recursive and concurrent cascades, purge behavior, and rejected DDL operations. Every measured run additionally verified row count, forward and backward scans, and CHECK TABLE.
Benchmark methodology
The benchmark follows the split-heavy workload from Zhao Song’s proposal. The preload uses monotonically increasing keys. Measured keys are deterministically permuted across the existing key space, so almost every measured insert causes a middle-page split.
| Parameter | Value |
|---|---|
| Preload rows | 2,500,000 |
| Measured inserts | 400,000 |
| Payload | 2,500 bytes |
| Threads | 32 |
| Online CPUs | 20, no affinity restriction |
| Buffer pool | 24 GiB |
| Redo log | 8 GiB |
| Adaptive hash index | OFF |
| Performance Schema | OFF |
| innodb_flush_log_at_trx_commit | 2 |
Both variants used a clean data directory. After preload, all preparation dirty pages were flushed. A full table scan warmed the dataset, and the run started only after verifying zero physical reads.
innodb_flush_log_at_trx_commit=2does not provide the same operating-system crash durability as value1. It may lose approximately the latest second of committed transactions after an operating-system or power failure. It was used for both variants to isolate B-tree contention from synchronous storage latency.
Why early results were misleading
Small buffer pool
With a 128 MiB buffer pool, the measured phase read about 26.7 GB from storage and reached only 2,257 TPS. This was mainly a storage benchmark.
Dirty preparation
A larger buffer pool removed reads, but pool preallocation left hundreds of thousands of dirty pages. Flushing this debt during measurement reduced throughput to 2,061 TPS.
Synchronous redo
With an 8 GiB redo log and innodb_flush_log_at_trx_commit=1, B-link reached 8,695 TPS and performed about 25,000 fsync operations. With value 2, it reached 102,838 TPS.
Performance results
| Metric | Vanilla MariaDB | B-link MariaDB | Change |
|---|---|---|---|
| TPS | 19,675.94 | 102,837.80 | 5.23x |
| Total time | 20.3285 s | 3.8886 s | −80.9% |
| Average latency | 1.63 ms | 0.31 ms | −81.0% |
| P95 latency | 8.28 ms | 0.56 ms | −93.2% |
| Maximum latency | 401.29 ms | 220.07 ms | −45.2% |
| Structural splits | 392,893 | 396,456 | Comparable |
Both variants performed approximately the same number of structural splits. The improvement was not caused by doing less work. It came from allowing independent structural modifications to progress concurrently.
B-link leaf splits 396,455
B-link internal splits 1
Parent installations 396,456
Normal X(index) 0
Right moves 0
Incomplete retries 0
Pool-empty retries 0
Pool refills 0Comparison with the original proposal
| Implementation | TPS |
|---|---|
| Zhao Song’s vanilla result | 5,666 |
| Zhao Song’s optimized result | 91,524 |
| MariaDB 13.1 vanilla bab03b | 19,676 |
| MariaDB 13.1 B-link | 102,838 |
The absolute values are not directly comparable because they were collected on different systems and possibly with different server settings. The important result is qualitative: removing index-wide SMO serialization allows the split-heavy workload to reach much higher throughput.
Current limitations
This implementation is a research prototype, not a production-ready feature.
- Existing indexes cannot be converted by changing a variable.
- Some DDL operations are rejected.
- Page merge and discard remain restricted.
- Pool state is not persistent across restart.
- The benchmark pool is intentionally much larger than a production pool.
- Recovery needs additional forced-crash stress testing.
- Mixed and secondary-index-heavy workloads require more evaluation.
Future work
- Investigate differences in redo writes and fsync operations.
- Run forced-crash and recovery stress tests.
- Add persistent or reconstructable pool accounting.
- Evaluate smaller continuously refilled production pools.
- Test the patch with HammerDB’s TPRO-C implementation of TPC-C using a bigger box.
Conclusion
The experiment confirms that index-wide serialization of structural modification operations is a substantial limitation for MariaDB InnoDB under a split-heavy workload.
The final implementation completed approximately 396 thousand structural splits without entering the normal index-wide X-latch path.
Under controlled memory-resident conditions, vanilla MariaDB reached 19.7 thousand inserts per second. B-link MariaDB reached 102.8 thousand inserts per second, improving throughput by 5.23x and reducing p95 latency from 8.28 ms to 0.56 ms.
This is still a proof of concept, available here, but it demonstrates that concurrent B-link-style structural modifications can provide a significant performance improvement in MariaDB InnoDB to support performance optimization work of Alessandro Vetere.
