基于版本：

MySQL 5.5.16

MySQL 5.6.4

测试表结构：

mysql> show create table nkeys;

+——-+—————————-

| Table | Create Table

+——-+—————————-

| nkeys | CREATE TABLE `nkeys` (

`c1` int(11) NOT NULL,

`c2` int(11) DEFAULT NULL,

`c3` int(11) DEFAULT NULL,

`c4` int(11) DEFAULT NULL,

`c5` int(11) DEFAULT NULL,

PRIMARY KEY (`c1`),

UNIQUE KEY `c4` (`c4`),

KEY `nkey1` (`c3`,`c5`)

) ENGINE=InnoDB DEFAULT CHARSET=gbk |

+——-+—————————-

并且在nkeys表中预先插入50000条数据，保证索引有两层。

2.Insert Buffer

Insert Buffer，是Innodb处理非唯一索引更新操作时的一个优化。

Insert Buffer，经历多次的版本变迁，其功能越来越强。最早的Insert Buffer，仅仅实现Insert操作的Buffer，这也是Insert Buffer名称的由来。在后续版本中，Innodb多次对Insert Buffer进行增强，到Innodb 5.5版本，Insert Buffer除了支持Insert，还新增了包括Update/Delete/Purge等操作的buffer功能，Insert Buffer也随之更名为Change Buffer。但是在Innodb5.5-5.6的代码之中，Insert Buffer对应的文件仍旧是ibuf，所有的函数，也都以ibuf前缀命名。

Mysql 5.5的Insert Buffer功能，可参考文档：MYSQL 5.5: InnoDB Change Buffering [1].

3.Insert Buffer流程

3.1Insert Buffer for Insert

insert into nkeys values (20,20,20,20,20);

函数调用流程 (针对与nkeys表的nkey1索引，其余两个索引，一个主键，一个Unique，无法使用insert buffer)：

write_row -> ha_innobase::write_row -> row_insert_for_mysql -> … -> row_insert_entry_low ->

3.2插入nkey1索引，准备阶段函数流程

btr0cur.cc::btr_cur_search_to_nth_level ->

3.3 insert buffer功能，在search path函数中完成

1. ibuf_should_try ->

   1. 判断当前索引，是否可以使用insert buffer。非主键索引，非唯一索引，可以使用insert buffer

   buf_page_get_gen ->

   1. 读取页面，若叶页面不在buffer pool中，同时可以进行insert buffer，则返回NULL

   ibuf_insert -> ibuf_insert_low -> ibuf_entry_build ->

   btr_pcur_open(btr_pcur_open_func - > btr_cur_search_to_nth_level) ->

   ibuf_get_volume_bufferd ->

   ibuf_bitmap_get_map_page -> ibuf_bitmap_page_get_bits -> ibuf_index_page_calc_free_from_bits ->

   1. 叶页面不在buffer pool之中，进行insert buffer
   2. ibuf_entry_build: 构造insert buffer中的记录，记录组织结构如下：
      1. 4 bytes：space_id
      2. 1 byte： marker = 0
      3. 4 bytes：page number
      4. type info：
         1. 2 bytes：counter，标识当前记录属于同一页面中的第几条insert buffer记录
         2. 1 byte： 操作类型：IBUF_OP_INSERT; IBUF_OP_DELETE_MARK; IBUF_OP_DELETE;
         3. 1 byte： Flags. 当前只能是IBUF_REC_COMPACT
      5. entry fields：之后就是索引记录
      6. 由于前9个字节[space_id, marker, page_numer, counter]组合，前三个字段，相同页面是一样的，这也保证了相同页面的记录，一定是存储在一起。第四个字段，标识页面中的第几次更新，保证同一页面buffer的操作，按照顺序存储。
   3. btr_pcur_open: 根据insert buffer表SYS_IBUF_TABLE的索引CLUST_IND，进行search path找到当前记录应该操作的insert buffer页面
   4. ibuf_get_volume_bufferd: 在insert buffer中已存在的项，同时返回这些项占用的空间大小buffered。首先遍历当前页面的前页面，比较前页面中的项，若[space_id, page_num]相同，则增加buffered；然后遍历当前页面的后页面，同样增加相同页面的项。
   5. 函数ibuf_bitmap_get_map_page，获取当前insert页面对应的bitmap管理页面，根据bitmap，计算索引页面中的空余空间，是否足够存放当前记录，并且不引起页面分裂
      1. buffered + entry_size + reserved_space <= ibuf_index_page_calc_free_from_bit

   ibuf_insert -> ibuf_insert_low -> btr_cur_optimistic_insert ->

   1. 将entry插入到SYS_IBUF_TABLE系统表之中，该系统表实现了insert buffer的管理功能

   1. Ibuf Bitmap page

   
   

在上一章节，有一个流程，用于判断本次Insert操作是否会导致索引页面split。若会split，那么就不能进行Insert Buffer优化。并且简单的提到，bitmap管理页面。此处，专门开出一小节，说一说InnoDB是如何管理每个页面的剩余空闲空间的？

InnoDB采用所谓的Ibuf Bitmap page来管理页面剩余空闲空间，这是一个十分经典的算法，据我所知，在Postgres中，也有类似的管理方式。

在InnoDB tablespace中，每隔page_size个页面，就是一个Ibuf Bitmap page。例如：若page_size = 16384(16k)，那么page_no为0，16384，32768，…的page，就是Ibuf Bitmap page，Bitmap page的功能，就是管理其后连续的page_size - 1个page的空间使用率。每个page，在Bitmap page中占用一项(小于1 byte)。如下图所示：

                                                                             图表 21 Bitmap Page示意图

图2.1中，page_size = 5。page 0，5为Bitmap Page，其中的record记录了紧随其后的4个page的剩余空闲空间。例如，Bitmap Page 1中的record 0记录了page_no = 1的page的剩余空闲空间。而如果想要知道Page No 8的剩余空闲空间，定位到Bitmap Page 1中的record 2即可。

Bitmap Page中的每一个record，占用4 bits，以这4 bits来标识其对应的page的剩余空闲空间。那么这4 bits是如何转换为剩余空闲空间的呢？

4 bits根据功能，又可以拆分为两份，分别为 2 bits

[0, 1] bits：对应页面的剩余空闲空间

[2, 3] bits：对应页面的insert buffer优化占用多少空间

函数ibuf0ibuf.ic::ibuf_index_page_calc_free_from_bits给出了剩余空闲空间的计算方式：

ut_ad(bits < 4); 
  
    if (bits == 3) 
  
        return(4 * UNIV_PAGE_SIZE / IBUF_PAGE_SIZE_PER_FREE_SPACE); 
  
    return(bits * (UNIV_PAGE_SIZE / IBUF_PAGE_SIZE_PER_FREE_SPACE)); 
  
    #define IBUF_PAGE_SIZE_PER_FREE_SPACE    32

首先，bits必须小于4 (2 bits)；其次，剩余空闲空间必须大于页面大小的1/32，才能进行Insert Buffer优化；最后，剩余空间越小，bits越精确，当剩余空间大于页面大小的3/32时，就已经不能通过bits准确计算剩余空间的大小了。

1. Ibuf Root Page

在一个InnoDB系统中，insert buffer的内存占用是比较大的，最大可以达到buffer pool的1/2。为了保证insert buffer的恢复能在较短时间内完成，insert buffer pages也会由dirty page flush操作写回disk。系统崩溃时，就能够保证insert buffer table (SYS_IBUF_TABLE)能够较快恢复。

Insert buffer对应的page，都在system tablespace (tablespace 0)中分配，并且Insert buffer聚簇表对应的root page是恒定的，是system tablespace中的第5个页面。定义如下：

#define FSP_IBUF_TREE_ROOT_PAGE_NO    4

/*!< insert buffer B-tree root page in tablespace 0 */

tablespace 0的第5个page，就是Insert buffer聚簇表的根页面。

在系统崩溃恢复完成之后，重建SYS_IBUF_TABLE，重建对应的聚簇索引CLUST_ID。然后将聚簇索引的root page设置为[0, 4]即可(space_id = 0，page_no = 4)。

此处为何是重建Ibuf table？我的理解，因为Ibuf table的表定义是不变的，并且表的root page也是不变的。因此不需要持久化Ibuf table数据字典信息，直接重建最省。

说到这儿，那么表空间的前几个页面，是否也是有特殊用途的呢？答案是肯定的，可以在Fsp0types.h文件中找到表空间前几个页面的特殊用途，提取如下所示：

/*————————————-*/
  
#define 
FSP_XDES_OFFSET            0    /* !< extent descriptor */
  
#define 
FSP_IBUF_BITMAP_OFFSET        1    /* !< insert buffer bitmap */
  
                /* 此页面开始，每隔XDES_DESCRIBED_PER_PAGE个页面，就是一个Bitmap Page*/
  
#define 
FSP_FIRST_INODE_PAGE_NO        2    /*!< in every tablespace */
  
#define 
FSP_IBUF_HEADER_PAGE_NO        3    /*!< ibuf header page, in tablespace 0, 用于管理Ibuf中的 page 的分配与释放 */
  
#define FSP_IBUF_TREE_ROOT_PAGE_NO    4    /*!< ibuf B-tree root page in tablespace 0 */ 
  
#define 
FSP_TRX_SYS_PAGE_NO        5    /*!< transaction system header in tablespace 0 */
  
#define    FSP_FIRST_RSEG_PAGE_NO        6    /*!< first rb segment    page, in tablespace 0 */ 
  
#define 
FSP_DICT_HDR_PAGE_NO        7    /*!< data dict header    page, in tablespace 0 */
  
/*————————————-*/

1. Insert Buffer for Purge

在前面的章节中，主要针对的是buffer insert操作。在5.5之后，Insert Buffer不仅能够buffer insert操作，并且能够buffer delete mark/purge等操作。

提到delete mark操作，不得不简单说一下InnoDB的多版本。为了实现多版本，InnoDB的索引在进行delete操作时，并不是直接将记录从索引中删除，而 是仅仅将记录标识为delete状态(delete mark)，每条记录上，都有一个delete bit。

记录何时被真正删除，要等到InnoDB的purge线程，根据redo log，回收索引上被标识为delete bit的项。

从以上的简单描述可以看出，delete mark操作并不会删除记录，因此也不会对索引页面的利用率产生影响。但是purge操作却是真正的删除数据，会减少索引页面的利用率，甚至将页面删空。 空页面会导致索引进行SMO操作，而Insert Buffer是不支持SMO的，因此，必须能够监控这种情况，保证purge操作的buffer不至于删空整个索引页面，InnoDB如何实现这个监控？

代码流程：

ibuf0ibuf.cc::ibuf_insert_low

// purge操作在insert buffer中被映射为IBUF_OP_DELETE操作

// delete操作在insert buffer中被映射为IBUF_OP_DELETE_MARK操作

if (op == IBUF_OP_DELETE &&

(min_n_recs < 2

|| buf_pool_watch_occured(space, page_no)))

// 若min_n_recs < 2，则不能进行purge的buffer操作

// 因为页面有可能因为本次purge而被删空，产生SMO

那么InnoDB是如何计算min_n_recs的呢？此时则又需要转到我们前面提到过的ibuf_get_volume_buffered函数。

ibuf_get_volume_buffered函数的第一个功能，前面已经提到，统计insert buffer中对于同一page，buffer了多少空间。其实该函数还有第二个功能，如下：

ibuf0ibuf.cc::ibuf_get_volume_buffered

ibuf_get_volume_buffered_count

case IBUF_OP_INSERT:

case IBUF_OP_DELETE_MARK:

if (ibuf_get_volume_buffered_hash(…))

(*n_recs)++;

min_n_recs的取值，并不是页面中真实剩余记录的数量，而是页面进入Insert Buffer的Insert/Delete_Mard操作的数量。Insert操作，由于有可能不会增加记录数量，因此此处不考虑；而 Delete_Mark的buffer，并不会减少记录，一个Delete_Mark操作，一定对应于page中的一项，因此可以将recs++。

但是此处又有一个例外：是否每一个Delete_Mark操作，都对应于一条不同的记录？这个是不能保证的，一条记录的多次 Insert/Delete_Mark操作，最终对应的仍旧是一条记录。因此，需要区分不同的Delete_Mark，操作的记录是否相同，通过函数 ibuf_get_volume_buffered_hash实现。

ibuf_get_volume_buffered_hash函数，简单说来，就是将每次看到的Delete_Mark操作对应的data映射到一 个unsigned long int值，然后将此值映射到128位中的一位，判断此位在已有的hash中是否已经设置，若设置，证明记录前面已经存在，此次count不能增加；若未设 置，证明是不同的记录，增加count，并更新hash取值。

目前，InnoDB针对purge操作的buffer有bug，具体可见网文：InnoDB: Failing assertion: page_get_n_recs(page) > 1。此bug，目前尚未有patch发布，因此在使用MySQL 5.5及以上版本时，慎用Insert Buffer的新功能。

1. Insert Buffer Merge流程

   1. 主动Merge

      1. 主动Merge原理

主动merge在Innodb主线程(srv0srv.c::srv_master_thread)中判断，判断原理很简单易懂：

若过去1s之内发生的I/O，小于系统I/O能力的5%，则主动进行一次Insert buffer的merge操作。Merge的页面数为系统I/O能力的5%，读取page采用async io模式。

每10s，必定触发一次insert buffer merge动作。Merge的页面数仍旧为系统I/O能力的5%。

函数代码段如下：

buf_get_total_stat(&buf_stat);

n_pend_ios = buf_get_n_pending_ios()

+ log_sys->n_pending_writes;

n_ios = log_sys->n_log_ios + buf_stat.n_pages_read

+ buf_stat.n_pages_written;

if (n_pend_ios < SRV_PEND_IO_THRESHOLD

&& (n_ios - n_ios_old < SRV_RECENT_IO_ACTIVITY)) {

srv_main_thread_op_info = “doing insert buffer merge”;

ibuf_contract_for_n_pages(FALSE, PCT_IO(5));

/* Flush logs if needed */

srv_sync_log_buffer_in_background();

}

n_pend_ios：                 系统目前pend的I/O操作数

n_ios：                     系统启动到目前为止一共进行的I/O操作数

SRV_PEND_IO_THRESHOLD：     系统pend的I/O上限

SRV_RECENT_IO_ACTIVITY：    系统当前一段时间之内的活跃I/O数

#define
SRV_PEND_IO_THRESHOLD    (PCT_IO(3))

#define
SRV_RECENT_IO_ACTIVITY    (PCT_IO(5))

#define
PCT_IO(p) ((ulong) (srv_io_capacity * ((double) p / 100.0)))

/* Number of IO operations per second the server can do */

UNIV_INTERN ulong    srv_io_capacity = 200;

系统的I/O能力，Innodb默认设置为200，可以根据自身的系统进行相应的调整

在清楚主动Merge操作的原理之后，接下来分析主动Merge操作的实现。主动merge的实现流程，主要分为两步：

步骤一： 主线程发出异步I/O请求，异步读取需要被merge的页面

步骤二： I/O handler线程，在接收到完成的异步I/O之后，进行merge

1. 步骤一：异步I/O流程

主线程调用函数ibuf_contract_for_n_pages进行索引页面的异步I/O读取，进行insert buffer的merge操作。

函数ibuf_contract_for_n_pages流程如下：

srv0srv.c::srv_master_thread ->

ibuf0ibuf.c::ibuf_contract_for_n_pages(系统能力的5%，200*5% = 10个page) ->

ibuf_contract_ext -> btr_pcur_open_at_rnd_pos -> ibuf_get_merge_page_nos ->

• 随机定位一个insert buffer的页面，读取页面中所有需要合并的insert buffer记录，以及记录对应的space_id，page_no至space_ids，page_nos数组之中

buf0rea.c::buf_read_ibuf_merge_pages -> buf_read_page_low ->

• 将数组中的(space_id, page_no)组合悉数读出

fil_io -> os_aio_func(type, mode) ->

• 具体Innodb aio的流程分析，可见 InnoDB异步IO实现详解。
• 此处，type = OS_FILE_READ; mode = OS_AIO_NORMAL; 使用os_aio_read_array

  由于mode != OS_AIO_SYNC，因此此处发出AIO命令之后，不需要等待I/O操作完成，直接返回即可。

  AIO完成之后，io_handler_thread线程将会接收到I/O完成的信号(os_aio_windows/linux_handle函数)，处理余下的insert buffer merge操作，就是接下来将要分析的 步骤二：Merge流程。

1. 步骤二：Merge流程

Innodb的io_handler_thread线程，在接收到主线程发出的异步I/O完成的信号之后，对页面进行merge操作。

执行：insert into nkeys values (60,60,60,60,60); 索引nkey1会使用insert buffer，在insert buffer操作完成之后，io_handler_thread线程调度，将记录merge到原有页面。

函数调用流程如下：

srv0start.c::io_handler_thread ->

1. innodb的io线程，在数据库启动(innodb/innobase_start_or_create_for_mysql)时创建，通过参数innodb/innobase_file_io_threads参数控制io线程的数量.

fil0fil.c::fil_aio_wait() ->

1. 等待asyc io，根据block类型进行分发，buf_page_io_complete or log_io_complete ?

os0file.cc::os_aio_linux/windows_handle(&fil_node, &message) ->

1. 调用操作系统相关的方法，完成aio操作，并填充file头与block头

buf0buf.c::buf_page_io_complete(message) ->

1. message 参数，fil_io_wait传入，buf0buf.h::buf_page_struct结构，block通用头结构，其前两个属性为 space:32, offset:32，分别为0，405，就是insert buffer中对应的nkey1索引的page。

ibuf0ibuf.c::ibuf_merge_or_delete_for_page -> ibuf_bitmap_page_get_bits(判断当前页面是否存在insert buffer项) -> ibuf_new_search_tuple_build(insert buffer记录定位) -> btr_pcur_open_on_user_rec(index scan，在insert buffer中查找第一条记录) -> page_update_max_trx_id -> ibuf_insert_to_index_page -> ibuf_delete_rec

1. 调用此函数，将insert buffer中的修改，merge到原有page之中(0, 405).
   1. 首先判断当前页面是否存在Insert buffer项
   2. 根据页面space_id，page_no构造search key定位到insert buffer记录，search key为insert buffer记录的前三个属性(space_id, marker, page_no)
   3. 修改index page中的max_trx_id系统列
   4. 构造完整索引项，并插入到index page之中
   5. 删除ibuf中的记录
   6. 设置ibuf bitmap

buf_pool->n_pend_reads-;

buf_pool->stat.n_pages_read++;

1. 一次aio merge操作完成，将n_pend_reads参数减减

n_pend_reads参数，在buf_page_get_gen -> buf_read_page -> buf_read_page_low -> buf_page_init_for_read 函数中设置。

1. 被动Merge

上一章节提到的主动Merge，指的是Innodb系统在主线程中，定期主动尝试读取索引的page，然后将insert buffer中的修改merge到对应的page之中。用户线程无法感知。

而我所谓的被动Merge，则主要是指在用户线程执行的过程中，由于种种原因，需要将insert buffer的修改merge到page之中。被动Merge由用户线程完成，因此用户能够感知到merge操作带来的性能影响。

被动Merge主要有以下几种情况.

1. 被动Merge-情况一

Insert操作，导致页面空间不足，需要分裂。由于insert buffer只能针对单页面，不能buffer page split，因此引起页面的被动Merge。

函数判断流程如下：

ibuf0ibuf.cc::ibuf_insert_low 
  
do_merge = FALSE; 
  
if (buffered + entry_size + reserved_space <= ibuf_index_page_calc_free_from_bits) 
  
    do_merge = TRUE; 
  
    ibuf_get_merge_page_nos(); 
  
func_exit: 
  
if (do_merge) 
  
    buf_read_ibuf_merge_pages();

在btr0cur.cc:: btr_cur_search_to_nth_level函数中，若判断出insert buffer失败，则会将buf_mode设置为BUF_GET，必定读取page，然后重新进行search path，读取当前页面。

同理，还有update操作导致页面空间不足；purge导致页面为空等。

换言之，若当前操作引起页面split or merge，那么就会导致被动Merge。

1. 被动Merge-情况二

insert操作，由于其他各种原因，insert buffer优化返回失败，需要真正读取page时，也需要进行被动Merge

代码处理流程如下：

buf0buf.c::buf_page_get_gen 
  
        if (UNIV_LIKELY(!recv_no_ibuf_operations)) 
  
            ibuf_merge_or_delete_for_page(block, space, offset, zip_size, TRUE);

参数recv_no_ibuf_operations    在恢复阶段设置为TRUE，正常运行阶段设置为FALSE；

因此正常运行阶段，如果读取了一个ZIP_PAGE，就需要判断其是否应该做insert bufferMerge

情况二与情况一的不 同之处在于，情况一判断出页面split之后，会自动进行一次Merge，search path restart时，page已经在内存之中；情况二，页面仍旧在disk上，读取之后，判断页面类型为ZIP_PAGE，解压之后，进行一次Merge操 作。

1. 被动Merge-情况三

在进行insert buffer操作时，发现insert buffer已经太大，需要压缩insert buffer

判断流程如下：

if (ibuf->size >= ibuf->max_size + IBUF_CONTRACT_DO_NOT_INSERT) 
 
       ibuf_contract(sync = TRUE); 
 
           ibuf_contract_ext(); 
 
               btr_pcur_open_at_rnd_pos(ibuf->index, BTR_SEARCH_LEAF, &pcur, &mtr); 
 
                   buf_read_ibuf_merge_pages(sync, space_ids, space_versions, page_nos, 
 
                *n_pages); 
 
   ibuf->max_size 
 
   ibuf->max_size = buf_pool_get_curr_size() / UNIV_PAGE_SIZE 
 
   / IBUF_POOL_SIZE_PER_MAX_SIZE; 
 
   IBUF_POOL_SIZE_PER_MAX_SIZE = 2;

因此ibuf的最大大小为buf_pool的1/2

• IBUF_CONTRACT_DO_NOT_INSERT = 10

超过ibuf最大大小10个page，需要强制进行被动Merge

• sync = TRUE

Merge操作同步I/O，不允许Insert操作进行

• 算法

在insert buffer tree中随机定位一个页面，将该页面中buffer的更新全部合并到原有page之中，并且返回最终merge了多少个page。

1. Insert Buffer & Merge优化

Percona XtraDB除了优化Checkpoint策略，同时也对Insert Buffer的Merge操作做了部分优化。

优化Insert Buffer的目的，主要有两个：

• 目的一：加快Insert Buffer的Merge与内存的回收

  通过前面的分析可以发现，Insert Buffer每次Merge操作，最多Merge一个Insert Buffer页面，繁忙的系统，很容易就达到了Insert Buffer可用内存的上限。

  针对目的一，Percona增加了两个系统参数：innodb_ibuf_accel_rate 与 innodb_ibuf_active_contract

• 目的二：减少Insert Buffer的内存开销

  原生Innodb的Insert Buffer，内存消耗上限为Buffer pool内存的一半。而在现阶段的应用中，大内存随处可见。因此有必要降低Insert Buffer的内存上限。

  针对目的二，Percona增加了一个系统参数：innodb_ibuf_max_size

分析可看出，优化Insert Buffer的两个目的是相辅相成的。只有实现了目的一，才有减少Insert Buffer内存开销的可能。

1. innodb_ibuf_accel_rate

此系统参数的使用十分简单，参考 主动Merge 章节，Percona只是将每次Merge操作的pages数量，由宏定义PCT_IO修改为PCT_IBUF_IO。而PCT_IBUF_IO的定义如下：

#define PCT_IBUF_IO(pct)    

((ulint) (srv_io_capacity * srv_ibuf_accel_rate * ((double) pct / 10000.0)))

因此，如果想加快Merge，只需要设置较大的innodb_ibuf_accel_rate参数即可。

1. innodb_ibuf_active_contract

与innodb_ibuf_accel_rate参数类似，innodb_ibuf_active_contract参数的处理也是十分简单。只是在ibuf0ibuf.c::ibuf_contract_after_insert函数中，增加了一行判断：

if (!srv_ibuf_active_contract) { 
 
       // #define IBUF_CONTRACT_ON_INSERT_NON_SYNC    0 
 
       if (size < max_size + IBUF_CONTRACT_ON_INSERT_NON_SYNC) { 
 
           return; 
 
       } 
 
   }

绿色部分为Innodb的原生代码，每次Insert 操作导致Insert Buffer的索引页面split，产生SMO时，都会调用。若Insert Buffer的大小未超出上限，则不进行Merge；

Percona增加innodb_ibuf_active_contract参数之后，哪怕Insert Buffer未超上限，Insert Buffer split SMO之后都会调用Merge功能。