InnoDB Insert Buffer实现详解

4月 18th, 2012
  1. 测试准备

基于版本:

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条数据,保证索引有两层。

  1. 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].

  1. Insert Buffer流程

    1. Insert 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 ->

  1. 插入nkey1索引,准备阶段函数流程

btr0cur.cc::btr_cur_search_to_nth_level ->

  1. insert buffer功能,在search path函数中完成

    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)。如下图所示:

InnoDB Bitmap Page

图表 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功能。