问题背景

今天,看到Twitter的DBA团队发布了其最新的MySQL分支:Changes in Twitter MySQL 5.5.28.t9,此分支最重要的一个改进,就是修复了MySQL 的Bug #67718:InnoDB drastically under-fills pages in certain conditions。关于此Bug的详细描述,以及如何重现此问题,可以阅读以上的Bug链接,以下简单描述下此Bug对应的问题:

InnoDB的索引分裂策略,在特定的情况下,索引页面的分裂存在问题,导致每个分裂出来的页面,仅仅存储一条记录,页面的空间利用率极低。

此Bug引起了我的兴趣,因此准备跟大家简单聊聊B+树索引的结构、B+树的分裂、B+树分裂操作的优化、Bug #67718的成因,以及个人对如何修复此Bug的一些建议等。

B+树索引结构

传统关系型数据库(Oracle/MySQL/PostgreSQL…),其主要的索引结构,使用的都是B+树。更有甚者,InnoDB引擎的表数据,整个都是以B+树的组织形式存放的。下图,是一个经典的B+树组织结构图(2层B+树,每个页面的扇出为4):

B+tree

注意:

  • 此B+树,以InnoDB实现的B+树结构为准;
  • 此B+树,有5条用户记录,分别是1,2,3,4,5
  • B+树上层页面中的记录,存储的是下层页面中的最小值(Low Key);
  • B+树的所有数据,均存储在B+树的叶节点;
  • B+树叶节点的所有页面,通过双向链表链接起来;

B+树的分裂

在上图B+树的基础上,继续插入记录 67,B+树结构会产生以下的一系列变化:

插入记录 6,新的B+树结构如下:

insert 6

插入记录 7,由于叶页面中只能存放 4 条记录,插入记录 7,导致叶页面分裂,产生一个新的叶页面。

insert 7

传统B+树页面分裂操作分析:

  • 按照原页面中50%的数据量进行分裂,针对当前这个分裂操作,3,4记录保留在原有页面,5,6记录,移动到新的页面。最后将新纪录 7 插入到新的页面中;
  • 50%分裂策略的优势:
    • 分裂之后,两个页面的空间利用率是一样的;如果新的插入是随机在两个页面中挑选进行,那么下一次分裂的操作就会更晚触发;
  • 50%分裂策略的劣势:
    • 空间利用率不高:按照传统50%的页面分裂策略,索引页面的空间利用率在50%左右;
    • 分裂频率较大:针对如上所示的递增插入(递减插入),每新插入两条记录,就会导致最右的叶页面再次发生分裂;

疑问:

传统50%分裂的策略,有不足之处,如何优化?接着往下看。

B+树分裂操作的优化

由于传统50%分裂的策略,有不足之处,因此,目前所有的关系型数据库,包括Oracle/InnoDB/PostgreSQL,以及本人以前参与研发的Oscar数据库,目前正在研发的NTSE、TNT存储引擎,都针对B+树索引的递增/递减插入进行了优化。经过优化,以上的B+树索引,在记录 6 插入完毕,记录 7 插入引起分裂之后,新的B+树结构如下图所示:

insert 7

对比上下两个插入记录 7 之后,B+树索引的结构图,可以发现二者有很多的不同之处:

  • 新的分裂策略,在插入 7 时,不移动原有页面的任何记录,只是将新插入的记录 7 写到新页面之中;
  • 原有页面的利用率,仍旧是100%;
  • 优化分裂策略的优势:
    • 索引分裂的代价小:不需要移动记录;
    • 索引分裂的概率降低:如果接下来的插入,仍旧是递增插入,那么需要插入4条记录,才能再次引起页面的分裂。相对于50%分裂策略,分裂的概率降低了一半;
    • 索引页面的空间利用率提高:新的分裂策略,能够保证分裂前的页面,仍旧保持100%的利用率,提高了索引的空间利用率;
  • 优化分裂策略的劣势:
    • 如果新的插入,不再满足递增插入的条件,而是插入到原有页面,那么就会导致原有页面再次分裂,增加了分裂的概率。

因此,此优化分裂策略,仅仅是针对递增递减插入有效,针对随机插入,就失去了优化的意义,反而带来了更高的分裂概率。

在InnoDB的实现中,为每个索引页面维护了一个上次插入的位置,以及上次的插入是递增/递减的标识。根据这些信息,InnoDB能够判断出新插入到页面中的记录,是否仍旧满足递增/递减的约束,若满足约束,则采用优化后的分裂策略;若不满足约束,则退回到50%的分裂策略。

但是,InnoDB的实现,有不足之处,会导致下面提到的一个Bug。

Bug#67718的成因

在Bug#67718中提到,在特定的插入情况下,InnoDB的索引页面利用率极低,这是由于InnoDB不正确的使用优化分裂策略导致的。

考虑以下的一个B+树,已有的用户数据是1,2,3,4,5,6,100,并且在插入记录 100 之后,引起索引页面分裂,记录 100 在分裂后被插入到新的页面:

insert 100

由于插入 100 能够满足递增的判断条件,因此采用了优化分裂策略,分裂不移动数据,新纪录 100 插入到新页面之中,原有页面的最后插入位置仍旧是 6 号记录不变,原有页面仍旧保持递增的插入标识不变。

此时,考虑连续插入 9,8,7 这几条记录,会得到什么样的B+树?此时,全局递增插入变为全局递减插入。

插入记录 9 后的B+树结构:

insert 9

由于InnoDB的B+树,上层节点保存的是下层页面中的最小值(Low Key),因此记录 9 仍旧会插入到【3,4,5,6】页面,此时页面已满,需要分裂。而且判断出记录 9 仍旧满足页面中的递增判断条件(Last_Insert_Pos = 69 插入到 6 之后,并且原来是递增插入的)。因此,采用优化的分裂策略,产生新的页面插入记录 9 ,原有页面记录保持不变。

插入记录 8 后的B+树结构:

insert 8

插入记录 7,也一样。采用优化的分裂策略,记录 7 独占一个页面。

分析:

Bug#67718的主要副作用

  • 是页面的利用率极低,每个索引叶页面,只能存放一条记录;

Bug#67718的主要原因

  • InnoDB错误的采用了优化的索引分裂策略。InnoDB判断是否满足递增/递减的插入模式,采用的是页面级的判断,哪怕全局的模式发生了变化,只要页面内记录的模式未变,仍旧会选择优化后的索引分裂策略;

修复Bug#67718的建议

在本人做Oscar数据库的索引分裂优化时,当时也同样碰到了此问题。当时的解决方案是:每次分裂,若插入的记录是页面中的最后一条记录,则至少将此记录前一条记录分裂到新页面之中。采用此策略,针对 100,9,8 这一个系列的插入,会产生以下的系列B+树:

插入100,9,8后的B+树:

insert

插入 100 时,移动原有页面最后一条记录到新的页面(将 6 移动到新页面),此时新页面中的记录为【6,100】。接下来插入9,8,都会插入到新的页面之中,不会产生分裂操作,空间利用率提高,减少了索引页面分裂,解决了Bug#67718的问题。

当然,肯定还有更优的策略,欢迎感兴趣的朋友们一起讨论!

参考文献