InnoDB utilizes B-tree as the dominating index data structure. It not only guarantees balanced search complexity (O(log(n))), but also reduces external storage access efficiently. Most of DDL/DML operations are required to travel through B-tree to locate the targeted data. Therefore, the design of B-tree has a significant impact on system performance, especially in the concurrency control mechanism.
This presentation will introduce you to the inner working of concurrent B-Tree in InnoDB. We will introduce the development of optimizations in concurrent B-Tree from the 1970s to now. We will cover the main optimization strategies, simplified pseudo-code, and future optimization directions. This presentation gives you insight into the working principle of concurrent B-tree and how to improve the performance of index structure in new hardware (SSD/NVM).
InnoDB uses the Write-Ahead-Log (WAL) protocol to modify data in an atomic and persistent state. The data must be written into the redo log before being written to the buffer pool. The advantage of WAL is that it converts a large number of random writes into sequential writes. However, the challenge is that it needs to design concurrency control mechanism to write the redo log safely and efficiently. On MySQL 5.6, the coarse-grained lock can't maximized the utilization of multi-core processors. On MySQL 8.0, InnoDB adopts lock-free redo log design to improves the concurrent write performance of redo log. This part mainly introduces how the concurrency control of InnoDB redo log is implemented on MySQL 8.0.
Qingda Hu is a Senior Engineer in Alibaba Cloud, where he works in the Database Products Group PolarDB team. Now, Qingda is focused on the InnoDB engine of MySQL, mainly in DDL, index and redo log.
Before joining Alibaba, he received a PhD degree in Computer Science from Tsinghua University. He majored in transaction memory system, memory allocator, concurrent data structure, and file system in non-volatile main memory. Qingda is a native Chinese, currently lives in Hangzhou, China.
Zechao Zhuang is a Senior Engineer in Alibaba Cloud, where he works in the Database Products Group PolarDB team. Now, Zechao is focus on InnoDB engine of mysql, mainly in buffer pool and redo log.
Before joining Alibaba, Zechao worked for 3 years in the distribute storage team at Qihoo 360. He is mainly involved in the R&D work related to the Cassandra platform, and he has a deep understanding of the LSM-tree engine, and know well the consistency protocols such as Raft and Gossip.
Zechao has some exploration and practical experience in the database field. He graduated from Xinjiang University with a major in software engineering.