王康 https://catkang.github.io/2025/03/03/mysql-btree.html
并发控制
回顾之前讲到的，B+Tree数据库的并发控制一直沿着更小的加锁粒度的方向发展，从对整个树加锁的2PL，到只对两层节点加锁的Lock Coupling，再到只对当前节点加锁的Blink，最后ARIES区分了逻辑层和物理层，将保护B+Tree结构在多线程之间完整的Latch和保证事务之间的隔离性的Lock解耦开来。本章节关注的就是InnoDB中B+Tree上的Latch这一层的实现，在Latch这一维度，从整个树加Latch，到对两层节点加Latch的Latch Coupling，再到只对当前节点加Latch的Blink的优化方向也是同样适用的。InnoDB中的B+Tree的Latch并发控制的的发展也确实是演这个这个方向进行的。比如在5.7之前，采用的就是类似锁整个Tree的方案，而5.7和8.0对这个锁粒度做了进一步的优化， 这里我们还是以8.0为例来进行介绍。
对B+Tree多线程并发访问影响最大的其实是B+Tree结构的变化，也就是B+Tree节点的分裂、合并，以及B+Tree层数的升高或将低，也统称为SMO（Structure Modification Operation），试想如果没有SMO，也就是B+Tree树结构保持稳定不变，那么B+Tree的多线程并发访问的实现，将是非常的简单高效的：所有的读写都可以无锁的在B+Tree上做记录的搜索定位，直到找到需要读写的记录所在的叶子节点，然后对这个节点加读写锁操作即可。当然这么理想的情况在现实中通常是不存在的，但考虑到SMO相对于记录的读写可以认为是极少的，因此在实现上InnoDB采用了先乐观再悲观的写入方式：
- 先假设本次修改不会导致树结构的变化，持有较轻量的锁：
- 如果发现需要造成树结构的变化，也就是上一节提到的插入发现Page放不下需要分裂，或者删除发现小于merge_threshold需要合并
- 那么退出乐观过程，再加较重的树结构锁，也就是悲观的方式重新完成写入。
这也是代码中看到B+Tree的insert、update和delete都会有optimistic以及pessimistic两个版本的原因，比如btr_cur_optimistic_insert和btr_cur_pessimistic_insert。上一个章节介绍了， InooDB中对B+Tree的访问包括读、插入、修改、删除四种，其中读取和乐观的写（插入、修改、删除）的加锁逻辑的类似的，区别只在搜索到最后的叶子结点后，对这个叶子节点加读锁还是写锁而已。因此，这里我们对B+Tree加锁的讨论将分为乐观操作和悲观操作来进行，其中乐观操作包括读和乐观写。这里Latch的加锁策略需要保证：
- 任何乐观操作不应该看到悲观操作导致的树结构变化的中间状态；
- 任何悲观操作不应该基于其他悲观操作导致的树结构变化的中间状态。
InnoDB的Latch实现主要包括两把锁，保护整个树结构的大锁index->lock，以及保护每个节点的block->lock，注意这两个锁名称虽然叫做lock，但跟上面讲的保证事务之间隔离性的Lock是没关系的，他们两个其实就是我们理论上所说的线程间同步的Latch的实现，是InnoDB中的读写锁rw_lock_t类型，加锁类型包括s lock、x lock及sx lock三种，也就是除了读写两种模式外，增加了一种不跟读锁互斥的sx lock。上一章节介绍过，对B+Tree的所有访问都需要先通过btr_cur_search_to_nth_level做记录在B+Tree上的搜索定位，实现上对index->lock及block->lock的加锁也都是在这个函数内完成的。为了实现上面的互斥保证，最简单的，也是InnoDB在5.6及之前版本的实现方式，如下图所示：
就是乐观操作对index->lock加slock，悲观操作对index->lock加xlock，然后无锁的搜索到叶子节点，之后根据读写类型对这个叶子结点加xlock或者slock即可。显然这种实现的瓶颈是很明显的，一次悲观操作带来的树结构变化，会阻塞整个B+Tree的读写。《B+Tree加锁历史中》提到的Tree Protcol(Latch Coupling)为解决这种树级别的加锁粒度问题提供了一种思路：利用B+Tree从上到下的搜索方式，持有上层节点的lock来对下层节点加lock，之后释放上层节点的lock并重复这个过程，就像两脚交替下梯子一样。InnoDB从5.7开始对这里也做了优化，但遗憾的是，可能由于工程实现上的复杂度，并没有完全的实现到Latch Coupling这一步。
从锁Tree到锁Subtree
InnoDB在5.7及以后的版本中，首先将悲观操作对index->lock的xlock改为sx lock，保留了悲观操作之间的互斥，同时允许SMO过程中持有slock的乐观操作并发访问，如此一来带来的问题就是，如何保证乐观操作不看到悲观操作导致的树结构变化的中间状态？InnoDB的答案是通过子树根节点的互斥访问实现锁子树，其实现过程如下：
- 对于乐观操作，btr_cur_search_to_nth_level中会获取index->lock的slock，然后在向下搜索的过程中，对经过的每一个节点的block->lock获取slock，直到到达叶子节点获取对应的读锁或写锁，之后释放index->lock的slock，以及上层节点的slock。
- 对应的悲观操作会先获得index->lock的sxlock，并且需要对所有发生树结构变化的节点加写锁，上一节中提到节点的分裂合并是可能级联向上的，因此这里可能需要对多层祖先节点加写锁。实现上这里有个矛盾：在开始做SMO之后才能知道会级联到哪一层的节点，但在做SMO之前就需要持有所有影响节点的block->lock的xlock。因此就需要对哪些Page会受影响提前做一个预估，InnoDB中这个实现在函数btr_cur_will_modify_tree中，悲观操作在btr_cur_search_to_nth_level搜索过程中会对每一个经过Page通过btr_cur_will_modify_tree做这个判断。其实在理论上在B+Tree上做这个判断是相对简单的，举个例子，当要做一次插入操作的时候，在经过祖先节点的时候，至少要保证这个祖先节点的剩余空间可以放下一个新的元素（InnoDB实现上由于存在分裂成三个节点的情况，这里需要保证两个元素的空间），否则就存在SMO最终会级联到当前这个节点的可能。可以看出，这里是一种很严格的判断方式，也就是本次操作只要有一丁点发生SMO的可能，就需要提前获取这个Page的xlock。为了尽量减少对乐观操作的影响，btr_cur_search_to_nth_level在搜索过程中并不会对中间节点加任何锁，而是在一个中间数据结构tree_blocks中记录所有btr_cur_will_modify_tree判断为true的节点，当到达level=1的节点，也就是叶子结点的父节点时，会对仍然在tree_blocks数组中的所有节点加xlock，并且在搜索到叶子结点后对叶子节点及前后兄弟节点加xlock。
综合上面对乐观操作和悲观操作的加锁处理，可以看出悲观操作和乐观操作其实是通过子树根节点上的读写锁实现整个子树的互斥访问，如下图所示：
当然这样的实现还是会有严重的瓶颈的。首先， 悲观操作互相互斥，导致同一时刻无论多大的B+Tree都只能有一个SMO发生；其次，乐观操作和悲观操作之间，由于btr_cur_will_modify_tree必须做严格的判断，导致大多数情况下会block一个比需要更大的子树范围；最后，乐观操作持有了全搜索路径的s lock也限制了需要xlock的SMO悲观操作。这些其实都是Tree Protocol（Latch Coupling）可以迎刃而解的。那么有没有可能在InnoDB中做到这一点呢，答案是肯定得，阿里云的PolarDB中就做了相应的实现，并且更进一步将这种锁优化推进到接近只需要锁当前节点的Blink实现。《路在脚下, 从BTree 到Polar Index》[7]一文中中有详细的讨论，这里就不在赘述了。
文件组织
InnoDB数据最终是存储在磁盘上的文件中的，通常会设置innodb_file_per_table来让每个用户的表独占一个数据IBD文件，那么一张表中的聚簇索引B+Tree与所有可能存在的二级索引B+Tree都会共享这样一个文件，
我们上面讲到的B+Tree在创建删除、或者节点的分裂及合并的过程中，会不断的从文件中分配或者归还Page，IBD文件也会随着B+Tree中数据的增加而向后扩展。一个IBD文件内，不同的B+Tree，或者同一个B+Tree中的叶子或者非叶子节点，他们内部在访问上是有相关性的，比如一些Page在被访问的时候，很大概率意味着其兄弟节点也很快会被访问到，而磁盘的特性是顺序访问的速度远远的好于随机读写的速度，因此一种良好的设计思路是让逻辑上相关的Page在物理上也尽量的连续，这样有相关性的Page访问的时候就会有更大的概率以顺序读写的方式来进行IO，从而获得高效的读写性能。为了实现这一点，需要两部分的工作：
- 需要一种连续Page的元信息维护方式。
- 需要一种按照逻辑相关性尽量分配连续Page的方法。
对于第一个问题，以16KB的Page大小为例，InnoDB中将连续的64个Page也就是连续1MB的空间划分为一个Extent，每个Extent都需要一个XDES Entry来维护一些元信息，其中主要包括这个Extend的是空闲、分配了部分还是全部分配的状态，以及其中每一个Page是不是被使用的Bitmap。这个元信息需要能方便的找到，并且随着文件的向后扩张，Page不断的增多，有足够的位置来进行存储。InnoDB的实现是每隔256MB就在这个固定位置放一个特殊的XDES Page，其中维护其向后256个Extent的元信息。这个Page的格式如下：
对于第二个逻辑相关的问题，在InnoDB中维护了Segment的概念，这是一个逻辑概念，对应的是一组逻辑上相关的Page集合，每个Segment会尽量的获取一些连续的Page（Extent）并持有，当这个Segment中得节点想要分配Page的时候，就优先从这些连续的Page中来获得。目前的InnoDB实现里，对每一个B+Tree维护了两个Segment，一个负责叶子节点，一个负责非叶子节点。这部分信息维护在B+Tree的Root Page中，上面介绍B+Tree的Page结构的时候，遗留的最后一段FSEG Header就是这个作用，只是这个信息只有在Root Page上有用，非Root节点上是空闲的，Root Page多出来的FSEG Header中就维护了当前的B+Tree所持有的的两个Segment信息：
可以看出，这里对每个Segment其实都是用SpaceID + PageNO + Offset唯一锁定了一个叫做Inode Entry的文件偏移，通常一个IBD文件的第三个Page就是Inode Page，其中维护了最多84个Inode Entry，也就是最多84个Segment，绝大多数情况下都是足够的，当然如果不足就需要动态分配新的Inode Page。Inode Entry如下图所示：
可以看出，其中维护了一组其持有的Extent的链表，包括完全空闲、部分分配，或全部已分配三个链表，除此之外，还有32个碎片Page的位置，这个其实是一种分配策略上的权衡，一个连续Extent有64个Page，如果每个Segment最少都分配一个Extent，显然会有极大的空间浪费，因此对于小的Segment会优先按照单个Page的方式进行分配，直到这个Segment得Inode Entry里的32个碎片Page的槽位已经用满。而文件的第一个Page，FSP_HDR作为一个特殊的XDES Page，除了XDES Entry外，还会维护一些文件相关的FSP_HEADER信息，如下图所示：
其中除了Space ID，当前文件大小，以及完成初始化的文件大小等常规信息外，还包括了文件内全局空闲、部分分配或全部分配的Extent链表，以及按照碎片Page分配的Extent链表，属于全局的Extent及Page资源，会在需要的时候按需分配给不同的Segment，并允许其持有，Segment中归还的Extent及Page资源也会加入到FSP Header上的全局链表中，来满足后续需求。全局空间资源不足的时候，也会通过文件的向后扩张以及初始化来获得新的Extent及Page资源。
上图是一个B+Tree文件空间组织的示意图，Page 3作为一个B+Tree的Root Page，在FSEG Header位置记录了其持有的两个Segment的Inode Entry位置，比如叶子节点在Segment ID为2的Segment上，这个Segment的信息记录在Page 2，也就Inode Page上的一个Inode Entry中，包括32个碎片Page的位置，已经用满的Extent链表，还没有用满的Extent链表，以及空闲的Extent链表，这些Extent通过对应的XDES Entry上的指针相互串联起来，图中Page 0是FSP Header，Page 16384是另一个XDES Page，这两个Page中都包含256个XDES Entry，管理着IBD上的每一个64 Page组成的Extent。
综上所述，为了高效地满足IBD文件内多个B+Tree所需空间的分配及释放需求，InnoDB首先将连续64个16KB的Page组织成一个Extent，从Page 0开始每隔256MB的空间就会放一个特殊XDES Page，每个XDES Page会有256个40B的XDES Entry来维护对应Extent中的Page分配情况。同时，还为逻辑上相关的Page设计了Segment的概念，每个B+Tree的叶子和非叶子节点分别对应一个Segment，IBD可以按照Extent或者Page为单位为Segment分配需要的节点空间，每个Segment会指向一个Inode Page上的192字节的Inode Entry，作为其当前持有的Page或Extent空间的元信息。
总结
本文首先简单介绍了理论上B+Tree的背景；紧接着从数据索引、并发控制及故障恢复三个方向介绍了B+Tree在InnoDB中的位置以及其不可或缺的作用；之后从B+Tree上维护的行数据入手，从Record到Page，再到B+Tree的从小到大顺序介绍了B+Tree中的数据组织；然后介绍了B+Tree上对数据的查询、修改、插入及删除等操作的基本流程，以及随之带来的树结构的变化，节点分裂合并及树整体的升高降低实现。有了这个准备后，又详细的分析了B+Tree上的并发控制实现及发展过程；最后将B+Tree放回到文件中，介绍B+Tree是如何从文件中申请及释放Page空间的，以及其中的一些实现考虑。
参考
[2] 浅析数据库并发控制机制
[4] B+树数据库加锁历史
[6] B+树数据库故障恢复概述
[11] Innodb 中的 Btree 实现 (一) · 引言 & insert 篇
[12] Innodb 中的 Btree 实现 (二) · select 篇
[13] innodb_diagrams
[14] Jeremy Cole Blog
