From S Locks To Sx Locks: From Mysql 5.6 To 8.0 A Concurrency Journey

Table of Contents

1. Introduction
2. Understanding B+ Trees
   • Basic Structure
   • Node Types
   • Insertion and Search Operations
3. Locking Mechanisms in Databases
   • Shared Locks (S-Locks)
   • Exclusive Locks (X-Locks)
   • Lock Compatibility Matrix
4. MySQL 5.6 Implementation
   • Index-Level Locking
   • Page-Level Locking
   • Limitations and Performance Impact
5. MySQL 8.0 Improvements
   • Introduction of SX Locks
   • Non-leaf Page Locking
   • Latch Coupling
6. Practical Examples
   • Basic Operations
   • Schema Modification Operations
7. Performance Implications
   • Read Operations
   • Write Operations
   • Concurrent Access Patterns
8. Further Reading
9. Conclusion

1. Introduction

The evolution of MySQL’s B-tree implementation represents a fascinating journey in database engineering, particularly in how it handles concurrency and locking mechanisms. This article deep dives into the changes between MySQL 5.6 and MySQL 8.0, focusing on the B-tree indexing structure and its locking mechanisms.

The story begins with MySQL 5.6’s simpler but sometimes limiting approach and progresses to MySQL 8.0’s more sophisticated implementation. Understanding these changes is crucial for database administrators and developers working with high-concurrency systems.

2. Understanding B+ Trees

Basic Structure

B+ trees are the fundamental data structure used in most modern database systems for indexing. Unlike regular B-trees, B+ trees store all actual data in the leaf nodes, with internal nodes serving purely as a navigation structure.

The core characteristics of B+ trees in MySQL include:

• All leaf nodes are at the same level, ensuring balanced tree structure
• Leaf nodes contain the actual data or pointers to the data
• Internal nodes contain only keys used for navigation
• Nodes are typically the size of a database page (16KB in MySQL by default)

Node Types

The B+ tree structure consists of three types of nodes:

1. Root Node
   • The topmost node in the tree
   • Can be both a leaf node (in small trees) or an internal node
   • Minimum of two children unless it’s also a leaf node
2. Internal Nodes (Non-leaf Nodes)
   • Contains keys and pointers to child nodes
   • Must be at least half full
   • Used purely for navigation
   • No actual data stored here
3. Leaf Nodes
   • Contains the actual indexed data or references to the data
   • Linked together in a doubly-linked list
   • Allows for efficient range scans
   • Must maintain sorted order

Insertion and Search Operations

Search operations in a B+ tree follow a path from root to leaf:

-- Creating a sample table with B-tree index
CREATE TABLE example (
    id INTEGER PRIMARY KEY,
    data TEXT
);

-- Insert some sample data
INSERT INTO example VALUES (1, 'A'), (2, 'B'), (3, 'C');

-- This search operation will traverse the B-tree
EXPLAIN QUERY PLAN SELECT * FROM example WHERE id = 2;

Insert operations are more complex:

-- This insertion might cause node splits
INSERT INTO example VALUES (1.5, 'Between A and B');

-- Creating an index will build a B-tree
CREATE INDEX idx_data ON example(data);

3. Locking Mechanisms in Databases

Shared Locks (S-Locks)

Shared locks are used for read operations and have the following characteristics:

• Multiple transactions can hold shared locks on the same resource
• Prevents other transactions from modifying the data
• Does not block other shared locks

-- Example of acquiring a shared lock (in SQLite syntax)
BEGIN IMMEDIATE TRANSACTION;
SELECT * FROM example WHERE id = 1;
-- This implicitly acquires a shared lock
COMMIT;

Exclusive Locks (X-Locks)

Exclusive locks are used for write operations and have these properties:

• Only one transaction can hold an exclusive lock
• Blocks both shared and exclusive lock requests
• Required for any modification operation

-- Example of acquiring an exclusive lock
BEGIN IMMEDIATE TRANSACTION;
UPDATE example SET data = 'Modified' WHERE id = 1;
-- This implicitly acquires an exclusive lock
COMMIT;

Lock Compatibility Matrix

The following matrix shows lock compatibility:

Lock Type	Shared (S)	Exclusive (X)	SX
Shared (S)	Yes	No	Yes
Exclusive (X)	No	No	No
SX	Yes	No	No

4. MySQL 5.6 Implementation

Index-Level Locking

MySQL 5.6 implemented a relatively simple locking strategy:

• The entire index is locked with an S-lock for read operations
• The index receives an X-lock for structural modifications
• This approach simplified implementation but limited concurrency

The process in MySQL 5.6:

-- Example showing how 5.6 handles index operations
BEGIN;
-- This would acquire an index-level S-lock
SELECT * FROM example WHERE id BETWEEN 1 AND 10;
COMMIT;

BEGIN;
-- This would acquire an index-level X-lock
INSERT INTO example VALUES (5, 'New Value');
COMMIT;

Page-Level Locking

Page-level locks in 5.6 were simpler:

• Only leaf pages received explicit locks
• Internal nodes were protected by the index-level lock
• Reduced lock management overhead but increased contention

Limitations and Performance Impact

The main limitations of the 5.6 approach were:

• High contention during structural modifications
• Reader starvation during heavy write workloads
• Limited concurrency during mixed workloads

5. MySQL 8.0 Improvements

Introduction of SX Locks

MySQL 8.0 introduced Schema modification (SX) locks:

• Compatible with shared locks
• Allows reads during structural modifications
• Blocks other structural modifications

-- Example of operations that would use SX locks in 8.0
BEGIN;
-- This operation might trigger an SX lock
INSERT INTO example VALUES (15, 'Causing Split');
COMMIT;

Non-leaf Page Locking

The 8.0 implementation added explicit locking for non-leaf pages:

• Each internal node can be locked independently
• Reduces contention during tree traversal
• Enables more granular concurrency control

Latch Coupling

Latch coupling in 8.0 works as follows:

• Child node locks are acquired before releasing parent locks
• Ensures consistent tree traversal
• Reduces the duration of high-level locks

Below image can help visualize well

6. Practical Examples

Basic Operations

Let’s look at some common operations and their locking behavior:

-- Read operation
SELECT * FROM example WHERE id = 5;

-- Insert operation that doesn't cause splits
INSERT INTO example VALUES (6, 'Simple Insert');

-- Update operation
UPDATE example SET data = 'Modified' WHERE id = 5;

Schema Modification Operations

Operations that modify the tree structure:

-- Operation causing page split
INSERT INTO example 
SELECT i, 'Value ' || i 
FROM generate_series(1, 1000) i;

-- Creating new index (bulk loading)
CREATE INDEX idx_large ON example(data);

7. Performance Implications

Read Operations

Read performance characteristics:

• Improved concurrency in 8.0 during structural modifications
• Better handling of hot pages
• More predictable performance under mixed workloads

Write Operations

Write operation improvements:

• Reduced contention during page splits
• Better handling of concurrent modifications
• More efficient space utilization

Concurrent Access Patterns

Impact on different access patterns:

• Range scans benefit from reduced lock duration
• Point queries show improved concurrency
• Bulk operations have better throughput

8. Further Reading

For deeper understanding, consider these resources:

1. MySQL 8.0 Reference Manual - InnoDB Storage Engine
2. “InnoDB B-tree Locking” by Biao’s Blog
3. “High Performance MySQL” by Baron Schwartz et al.
4. “Database Internals” by Alex Petrov

9. Conclusion

The evolution from MySQL 5.6 to 8.0 represents a significant advancement in B-tree implementation. The introduction of SX locks and more granular locking mechanisms has improved concurrency while maintaining data consistency. While the implementation is more complex, the benefits in terms of scalability and performance make it a worthwhile trade-off.

The key takeaways are:

• More granular locking improves concurrency
• Complexity is sometimes necessary for performance
• Understanding these mechanisms helps in database design and optimization