听原作者为你深度解读InnoDB批量建索引原理

InnoDB批量建索引深度揭秘

InnoDB在MySQL 5.7版本中推出了批量建索引的功能。WL#7277 InnoDB: Bulk Load for Create Index这个功能就由本人设计与实现的。本文将对该功能的设计与实现进行详尽的介绍。

一、InnoDB Fast Index Build介绍

最简单的建索引的方法就是走正常的数据库插入流程,将数据逐条插入到索引B树中。要对B树进行查找合适的插入位置,对B树节点进行正常的加锁,对页面记录redo log,undo log,当页面满时进行分裂(split)。这样做最大的缺点就是建立索引速度慢,另外事务回滚慢,系统故障恢复(crash recovery)也慢(因为redo log apply + undo)。

MySQL从5.5开始提供了快速建索引的功能(Fast Index Build)。在这个功能中,把建索引的过程分成了三个阶段:

1.1读取阶段:读取聚簇索引(cluster index)

在InnoDB中,表的所有数据都在聚簇索引中。我们需要扫描聚簇索引,生成要创建的索引的记录,并写到排序缓冲区中(innodb_sort_buffer_size),默认大小是1G。当缓冲区写满后,先进行排序(quick sort),然后写入临时文件中。如果一次建立多个索引,聚簇索引的扫描只扫描一次。每个新建的索引用有独立的排序缓冲区。

1.2 排序阶段:对索引临时文件进行排序

如果索引的临时文件有多个,则对多个文进行外排序。采用的算法则是经典二路归并(two way merge sort)。排序的时间主要取决于归并的轮数(run),每一轮都读取和写入同样数量的文件。

以上两个阶段都涉及到排序。如果要创建的索引是唯一索引,在排序过程中发现重复的键值(duplicate key),则会直接报错。

1.3建立阶段:插入记录建索引

读取临时文件,依次将记录插入到索引B树中。与最原始的插入方案相比,这里对B树节点不上锁,不记录undo日志,每次默认都是从叶子节点的最右边(rightmost)插入新的记录,因为索引记录是有序的。因此快速建索引要快很多。

这里有一个实现细节值得注意。在没有排序插入的时候,节点分裂会比较多,由此带来的另外一个问题是很多节点处于没有填满的状态,有的甚至为半满状态。快速建索引解决了这个问题,保证叶子节点为满的状态(最左和最右节点除外,稍后解释)。具体实现如下:当一个子节点无法插入新的记录时,如果当前要插入的位置和上一次插入的位置相同,而且当前位置的下一条记录为最大记录标识时,不分裂该节点,分配新的节点,新记录插入该节点,作为该节点第一条记录。

最右的节点会因为插入的记录少而达不到满的状态,而最左叶子(中间节点除外)的节点为什么会出现半满状态呢?当根节点进行第一次分裂的时候,一半的记录移到了新的最左叶子节点,另一半移到了新的最右节点,新插入的记录则继续在右节点插入。根节点作为B树的入口,最先分配,一般是保持不变的。

二、自底向上建索引(Bottom up Index Build)2.1自底向上建索引原理

记录首先插入到叶子节点,当叶子节点填满时,在往中间节点插入一条记录。这样为什么会快?其一,省去了每次从根节点到最右节点的寻路过程,因为我们为每层保存当前插入页和插入位置;其二,一个页的所有记录插入用一个mtr(mini-transaction)完成,而之前都是一条记录使用一个mtr完成;其三,数据页不记录redo日志,页面的分配依然记redo日志,保证系统崩溃后,数据页可以正常回收。

2.2 脏页写盘方案

因为没有记redo日志,那么在索引创建完成,变成可用之前,需要把所有索引叶写入磁盘。最初的实现方案就是等待系统所有脏页写盘(做一个检查点),测试中发现系统负载大的时候,等待时间太长。新的优化方案则是利用观察者模式(observer)进行处理,只等待相关的脏页写盘。在建索引之前,我们创建一个flush observer对象,然后脏页进入flush list之前,设置该页的flush observer对象,并将flush计数器加一。当这个脏页被写入磁盘之后,则对flush observer对象的remove计数器加一。索引创建完成之后,等待flush计数和remove计数相等,则所有脏页写盘完成。注意:这里的计数器是针对单个buffer pool实例的。如果索引创建失败,在flush list中所有含有该flush observer对象的脏页都会被清除。

2.3 压缩表(compressed table)的处理

压缩表正常的插入流程是同时插入到压缩页和非压缩页中。为了简化流程,在批量建索引中,记录只插入到非压缩页中。当页面填满时,再对整页进行压缩。如果达不到设定的大小,则进行分裂。

2.4 填充因子(fillfactor)

在批量建索引中,我们添加了全局配置参数innodb_fill_factor,其取值范围为10-100,即数据页(包括叶子节点和非叶子节点)的填充比例从10%到100%。保持页面有一定的空闲空间,为将来的数据的增删改预留,否则,如果页面都填满的话,新的插入必然导致页的分裂,影响插入的效率。

对于压缩页,我们则依然保持了原有插入的自适应padding机制。

2.5 其他

在对批量建索引进行设计的时候,有一个不经过buffer pool的方案:直接分配页面,进行插入,单独写盘。最终因为实现稍复杂而放弃。另外对于是否写redo日志也有过讨论。写redo日志相对简单,因为只需要在页面填满时,对整页进行写日志即可。但考虑到如果系统崩溃之后,恢复的时间长而舍弃。

三、结语

在批量建索引中,还有一些值得优化的地方。比如填充因子可以根据单表指定(即DDL中进行语法支持);Online DDL时,online log的应用也可以不写redo日志,直接利用现行机制写脏页等等。

在批量建索引的基础上,我们还可以做如下工作:

LOAD DATA时,如果表为空,则可以直接利用批量建索引接口进数据的加载。

优化建索引的第一和第二阶段。第一阶段读取可以采用逻辑预读(Logical Read Ahead);第二阶段可以才用多路归并,以及多线程排序。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180202G0DDL200?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券