InnoDB中的页合并与分裂

原文链接:
https://www.percona.com/blog/2017/04/10/innodb-page-merging-and-page-splitting/
https://www.percona.com/blog/2020/06/24/mysql-table-fragmentation-beware-of-bulk-insert-with-failure-or-rollback/

如果您遇到了全球(为数不多的)MySQL 顾问之一并要求他/她审查您的查询和/或模式,我相信他/她会告诉您有关良好主键设计的重要性的一些信息. 特别是在 InnoDB 的情况下,我相信他们已经开始向您解释索引合并和页面拆分。这两个概念与性能密切相关,您在设计任何索引(不仅仅是 PK)时都应该考虑这种关系。

这对你来说可能听起来像笨蛋,你可能是对的。这不是一件容易的事情,尤其是在谈论内部结构时。这不是您经常处理的事情,而且通常您根本不想处理它。
但有时它是必需的。如果是这样,这篇文章适合你。

在本文中,我想解释一些最不清楚的 InnoDB 幕后操作:页面索引创建、页面合并和页面拆分。
在 Innodb 中,所有数据都是一个索引。你可能也听说过吧?但这究竟是什么意思?

文件表组件

假设您安装了 MySQL,最新的 5.7 版本(Percona Server for MySQL,对吗?),并且在架构 windmills 中有一个名为 wmills 的表。在数据目录(通常为 /var/lib/mysql/)中,您将看到它包含:

data/
  windmills/
      wmills.ibd
      wmills.frm

这是因为参数 innodb_file_per_table 从 MySQL5.6 开始已经设置为 1。这样设置,schema 中每个表都是一个文件(如果是分区表,则有多个文件)。
这里重要的是名为 wmills.ibd 的文件。这个文件被分为 N 个段(Segment) 。每个段 都与一个索引相关联。
尽管文件不会因删除数据而收缩,段本身会增长或收缩,下一级为区。一个区仅存在一个段中,并且固定尺寸为 1MB(在默认页大小的情况下)。页(page)是区(extent)的下一级,默认大小为 16KB。
因此,一个区(extent)最多可包含 64 页(page)。一个页可以包含 2 到 N 行。一个页可以容纳的行数与行大小有关,这是表结构设计时定义的。InnoDB 中有一条规则说,至少两行必须适合一个页面。因此,我们有 8000 字节的行大小限制。如果您认为这听起来就像俄罗斯娃娃(Matryoshka dolls),没错下面这张图能帮助你理解:
image.png

根,分支与叶子

每个页(逻辑上讲即叶子节点)是包含了 2-N 行数据,根据主键排列。树有着特殊的页区管理不同的分支,即内部节点(INodes)。
image.png
这个图片仅是示例,并不能说明下面的实际输出。
具体来看一下:

ROOT NODE #3: 4 records, 68 bytes
NODE POINTER RECORD ≥ (id=2) → #197
INTERNAL NODE #197: 464 records, 7888 bytes
NODE POINTER RECORD ≥ (id=2) → #5
LEAF NODE #5: 57 records, 7524 bytes
 RECORD: (id=2) → (uuid="884e471c-0e82-11e7-8bf6-08002734ed50", millid=139, kwatts_s=1956, date="2017-05-01", location="For beauty's pattern to succeeding men.Yet do thy", active=1, time="2017-03-21 22:05:45", strrecordtype="Wit")

下面是表结构:

CREATE TABLE `wmills` (
  `id` bigint(11) NOT NULL AUTO_INCREMENT,
  `uuid` char(36) COLLATE utf8_bin NOT NULL,
  `millid` smallint(6) NOT NULL,
  `kwatts_s` int(11) NOT NULL,
  `date` date NOT NULL,
  `location` varchar(50) COLLATE utf8_bin DEFAULT NULL,
  `active` tinyint(2) NOT NULL DEFAULT '1',
  `time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  `strrecordtype` char(3) COLLATE utf8_bin NOT NULL,
  PRIMARY KEY (`id`),
  KEY `IDX_millid` (`millid`)
) ENGINE=InnoDB;

所有的 B 树都有着一个入口,也就是根节点,在上图中#3 就是根节点。根节点(页)包含了如索引 ID、INodes 数量等信息。INode 页包含了关于页本身的信息、值的范围等。最后还有叶子节点,也就是我们数据实际所在的位置。在示例中,我们可以看到叶子节点#5 有 57 行记录,共 7524 bytes。在这行信息后是具体的记录,可以看到数据行内容。
这里想引出的概念是当你使用 InnoDB 管理表和行,InnoDB 会将他们会以分支、页和记录的形式组织起来。InnoDB 不是按行的来操作的,它可操作的最小粒度是页,页加载进内存后才会通过扫描页来获取行/记录。
现在页的结构清楚了吗?好,我们继续。

页的内部原理

页可以空或者填充满(100%),行记录会按照主键顺序来排列。例如在使用 AUTO_INCREMENT 时,你会有顺序的 ID 1、2、3、4 等。
image.png
页还有另一个重要的属性:MERGE_THRESHOLD。该参数的默认值是 50%页的大小,它在 InnoDB 的合并操作中扮演了很重要的角色。
image.png
当你插入数据时,如果数据(大小)能够放的进页中的话,那他们是按顺序将页填满的。
若当前页满,则下一行记录会被插入下一页(NEXT)中。
image.png
根据 B 树的特性,它可以自顶向下遍历,但也可以在各叶子节点水平遍历。因为每个叶子节点都有着一个指向包含下一条(顺序)记录的页的指针。例如,页#5 有指向页#6 的指针,页#6 有指向前一页(#5)的指针和后一页(#7)的指针。
这种机制下可以做到快速的顺序扫描(如范围扫描)。之前提到过,这就是当你基于自增主键进行插入的情况。但如果你不仅插入还进行删除呢?

页合并

当你删了一行记录时,实际上记录并没有被物理删除,记录被标记(flaged)为删除并且它的空间变得允许被其他记录声明使用。
image.png
当页中删除的记录达到 MERGE_THRESHOLD(默认页体积的 50%),InnoDB 会开始寻找最靠近的页(前或后)看看是否可以将两个页合并以优化空间使用。
image.png
在示例中,页#6 使用了不到一半的空间,页#5 又有足够的删除数量,现在同样处于 50%使用以下。从 InnoDB 的角度来看,它们能够进行合并。
image.png
合并操作使得页#5 保留它之前的数据,并且容纳来自页#6 的数据。页#6 变成一个空页,可以接纳新数据。
image.png
如果我们在 UPDATE 操作中让页中数据体积达到类似的阈值点,InnoDB 也会进行一样的操作。
规则就是:页合并发生在删除或更新操作中,关联到当前页的相邻页。如果页合并成功,在 INFOMATION_SCHEMA.INNODB_METRICS 中的 index_page_merge_successful 将会增加。

页分裂

前面提到,页可能填充至 100%,在页填满了之后,下一页会继续接管新的记录。但如果有下面这种情况呢?
image.png
页#10 没有足够空间去容纳新(或更新)的记录。根据“下一页”的逻辑,记录应该由页#11 负责。然而:
image.png
页#11 也同样满了,数据也不可能不按顺序地插入。怎么办?
还记得之前说的链表吗(译注:指 B+树的每一层都是双向链表)?页#10 有指向页#9 和页#11 的指针。
InnoDB 的做法是(简化版):

  1. 创建新页
  2. 判断当前页(页#10)可以从哪里进行分裂(记录行层面)
  3. 移动记录行
  4. 重新定义页之间的关系

image.png
新的页#12 被创建:
image.png
页#11 保持原样,只有页之间的关系发生了改变:

  • 页#10 相邻的前一页为页#9,后一页为页#12
  • 页#12 相邻的前一页为页#10,后一页为页#11
  • 页#11 相邻的前一页为页#10,后一页为页#13

(译注:页#13 可能本来就有,这里意思为页#10 与页#11 之间插入了页#12)
这样 B 树水平方向的一致性仍然满足,因为满足原定的顺序排列逻辑。然而从物理存储上讲页是乱序的,而且大概率会落到不同的区。
规律总结:页分裂会发生在插入或更新,并且造成页的错位(dislocation,落入不同的区)
InnoDB 用 INFORMATION_SCHEMA.INNODB_METRICS 表来跟踪页的分裂数。可以查看其中的 index_page_splits 和 index_page_reorg_attempts/successful 统计。
一旦创建分裂的页,唯一(译注:实则仍有其他方法,见下文)将原先顺序恢复的办法就是新分裂出来的页因为低于合并阈值(merge threshold)被删掉。这时候 InnoDB 用页合并将数据合并回来。
另一种方式就是用 OPTIMIZE 重新整理表。这可能是个很重量级和耗时的过程,但可能是唯一将大量分布在不同区的页理顺的方法。
另一方面,要记住在合并和分裂的过程,InnoDB 会在索引树上加写锁(x-latch)。在操作频繁的系统中这可能会是个隐患。它可能会导致索引的锁争用(index latch contention)。如果表中没有合并和分裂(也就是写操作)的操作,称为“乐观”更新,只需要使用读锁(S)。带有合并也分裂操作则称为“悲观”更新,使用写锁(X)。

我的主键

好的主键不仅对于数据查找很重要,而且也影响写操作时数据在区上的分布(也就是与页分裂和页合并操作相关)。
在第一个测试中我使用的是是自增主键,第二个测试主键是基于一个 1-200 的 ID 与自增值的,第三个测试也是 1-200 的 ID 不过与 UUID 联合。
插入操作时,InnoDB 需要增加页,视为“分裂”操作:
image.png
表现因不同主键而异。
在头两种情况中数据的分布更为紧凑,也就是说他们拥有更好的空间利用率。对比半随机(semi-random)特性的 UUID 会导致明显的页稀疏分布(页数量更多,相关分裂操作更多)。
在页合并的情况中,尝试合并的次数因主键类型的不同而表现得更加不一致。
image.png
在插入-更新-删除操作中,自增主键有更少的合并尝试次数,成功比例比其他两种类型低 9.45%。UUID 型主键(图表的右一侧)有更多的合并尝试,但是合并成功率明显更高,达 22.34%,因为数据稀疏分布让很多页都有部分空闲空间。
在辅助索引与上面主键索引相似的情况下,测试的表现也是类似的。

总结

MySQL/InnoDB 不断地进行这些操作,你可能只能了解到很少的信息。但他们可能给你造成伤害,特别是比起用 SSD,你还在用传统的机械存储(spindle storage)的时候(顺便提一下 SSD 会有另外的问题)。
坏消息就是我们用什么参数或者魔法去改变服务端。但好消息是我们可以在设计的时候做很多(有帮助)的事。
恰当地使用主键和设计辅助索引,并且记住不要滥用(索引)。如果你已经预计到会有很多插入/删除/更新操作,规划一个合适的时间窗来管理(整理)表。
有个很重要的点,InnoDB 中你不会有断断续续的行记录,但是你会在页-区的维度上遇到这些问题。忽略表的管理工作会导致需要在 IO 层面、内存层面和 InnoDB 缓冲池层面做更多工作。
你必须不时(at regular intervals)重建一些表。可以采用一些技巧,比如分区和外部的工具(pt-osc)。不要让表变得过大和过于碎片化(fragmented)。
磁盘空间浪费?需要读多个表去获取需要的数据而不是一次搞定?每次搜索导致明显更多的读操作?那是你的锅,不要找借口!

https://alicharles.oss-cn-hangzhou.aliyuncs.com/static/images/mp_qrcode.jpg
文章目录
  1. 文件表组件
  2. 根,分支与叶子
  3. 页的内部原理
  4. 页合并
  5. 页分裂
  6. 我的主键
  7. 总结