原创 | InnoDB 的 Change Buffer

腾讯数据库技术 2022-11-24 18:55

介绍

change buffer(在 MySQL 5.6 之前叫 insert buffer,简称 ibuf )是 InnoDB 5.5 引入的一种优化策略,若二级索引页不在 buffer pool 中,则将针对二级索引页的操作暂时缓存起来,等到该页从磁盘读到 buffer pool 中时再批量的(batch)apply 这些操作,从而达到减少磁盘 I/O 的目的。具体一点就是:

  1. 事务 1 执行写操作(e.g update),但针对的二级索引页 P1 并不在 buffer pool 中

  2. 于是 client 1 将这个操作缓存到 change buffer 里,即添加一个 entry(ibuf insert)

  3. 事务 2 需要读操作,将 P1 读到 buffer pool 中

  4. 将 change buffer 里相关的缓存的操作全部合并(merge)至 P1(ibuf merge)

  5. 将 P1 返回给用户线程


为什么必须是二级索引页,不能是主键索引页?很简单,因为主键索引要保证唯一性的约束,如果把 insert id=1 缓存起来,再次有要 insert id=1 时再缓存起来,则等批量的 apply 时就会出错。change buffer 缓存的操作有三种:

  • BTR_INSERT_OP:普通的 insert

  • BTR_DELMARK_OP:在用户线程执行 update 和 delete 中,如果发生数据删除行为,会将记录标记为 delete mark

  • BTR_DELETE_OP:purge 线程删除二级索引中 delete mark 的数据行


组织形式(B-tree

change buffer 本质是一块写缓存,组织形式是 B-tree,存在于系统表空间中。其根节点位于系统表空间的第四页面(FSP_IBUF_TREE_ROOT_PAGE_NO)

ibuf entry layout

其缓存的每一个操作叫做一个 entry,物理结构是(详见 ibuf_entry_build):

  • IBUF_REC_FIELD_SPACE:对应二级索引页的 space id

  • IBUF_REC_FIELD_MARKER:用于区分新旧版本的 entry 格式,目前默认值为 0

  • IBUF_REC_FIELD_PAGE_NO:对应二级索引页的 page no

  • IBUF_REC_OFFSET_COUNTER:对于同一个二级索引页,其 entry 的递增序号(非单调递增,详见下文)

  • IBUF_REC_OFFSET_TYPE:缓存的操作的类型,IBUF_OP_INSERT / IBUF_OP_DELETE_MARK / IBUF_OP_DELETE

  • IBUF_REC_OFFSET_FLAGS:待操作的用户记录格式,REDUNDANT / COMPACT

  • IBUF_REC_FIELD_USER:用户记录

ibuf entry counter

ibuf entry counter 的存在是为了与 space_id 和 page_no 一起构成 entry 的主键,在 change buffer 里对于同一二级索引页的 entry,其 entry counter 是递增的

在 change buffer 中插入 entry 时,先定位到待插入的位置(btr_pcur_open):

  • search tuple: (space_id, page_no, 0xFFFF)为主键

  • mode PAGE_CUR_LE(<=)模式搜索 B-tree

  • latch_mode 是 BTR_MODIFY_PREV 或 BTR_MODIFY_TREE

0xFFFF 是最大的 entry counter(IBUF_REC_OFFSET_COUNTER 域为两个字节),所以 cursor 会定位到对应于同一二级索引页的具有最大 counter 的 entry,记为 max_counter。max_counter+1 即为待插入 entry 的 counter。
但在每一次 ibuf merge ,清空了该二级索引页的所有 entry 后,再插入针对该索引页的新的 ibuf entry,counter 又从 0 开始

Change Buffer 的约束:不能引起 index SMO

需要注意的是如果一个操作可能引起二级索引页的 SMO,则该操作不能缓存在 change buffer 中。这个约束可以理解,比如针二级索引页P1 缓存了三个 entry:entry1 / entry2 / entry3,在 ibuf merge 时,如果 entry2 使得 P1 发生分裂,那么 entry3 无法正确的 merge 至分裂后的 P1。因此 change buffer 在缓存新的操作时,新的操作不能引发这两种情况发生:

  • 索引页的空间被填满(索引页分裂)

  • 索引页内只剩下一条记录(索引页合并)


追踪每个页的剩余空间

如何得知一个操作是否会引起二级索引页的溢出?这需要我们追踪每个页的剩余空间。通过 ibuf bitmap page 来实现(Skywalker:InnoDB:Tablespace management(1)),ibuf bitmap page 用 4 bits 描述每个页:

  • IBUF_BITMAP_FREE(2 bits):描述页的空闲空间范围

  • IBUF_BITMAP_BUFFERED(1 bit):ibuf 中是否缓存着这个页的操作

  • IBUF_BITMAP_IBUF(1 bit):该页是否是 ibuf B-tree 的节点


IBUF_BITMAP_FREE 2 bits 的计算方式是:

UNIV_INLINEulint ibuf_index_page_calc_free_bits(ulint page_size, ulint max_ins_size) {  // max_ins_size 是这个页中目前的全部剩余空间,IBUF_PAGE_SIZE_PER_FREE_SPACE 是 32  // page_size / IBUF_PAGE_SIZE_PER_FREE_SPACE 就是 512 bytes,可以看出这里只是粗糙  // 的统计 max_ins_size 是 512 bytes 的几倍,max_ins_size / 512:  //  - 大于 3(max_ins_size > 2048):IBUF_BITMAP_FREE 记录 3  //  - 3(1536 < max_ins_size < 2048):IBUF_BITMAP_FREE 记录 3  //  - 2(1024 < max_ins_size < 1536):IBUF_BITMAP_FREE 记录 2  //  - 1(512  < max_ins_size < 1024):IBUF_BITMAP_FREE 记录 1  //  - 0(max_ins_size < 512):IBUF_BITMAP_FREE 记录 0  n = max_ins_size / (page_size / IBUF_PAGE_SIZE_PER_FREE_SPACE);
if (n == 3) { n = 2; }
if (n > 3) { n = 3; }
return (n);}

在每次 insert / update / delete 后会更新 IBUF_BITMAP_FREE(ibuf_update_free_bits_if_full / ibuf_update_free_bits_low)。

防止页的分裂

只有在缓存 IBUF_OP_INSERT 时才需要防止页的分裂发生。这里涉及到一个函数 ibuf_get_volume_buffered。该函数用于计算对于特定的二级索引页( 设为 P1 ),change buffer 里缓存的操作 merge 完会导致此页增长的数据量是多少(affect the available space on the page),然后与该页的剩余空间做比较。因为 IBUF_BITMAP_FREE 最大就是 3,可见能缓存的操作最多只能占用 2048 bytes。
首先把 pcur 在 ibuf B-tree 中定位到缓存的关于 P1 的最大的 ibuf record。采用的依然是 B-tree 的函数,search tuple 是( P1 space id, P1 page no,0xFFFF),search mode 是 PAGE_CUR_LE,latch mode 是 BTR_MODIFY_PREV(x-latch 左兄弟节点和当前节点) 或 BTR_MODIFY_TREE(x-latch 左兄弟节点、当前节点和右兄弟节点)。定位完成 pcur 指向 之后从 pcur 开始:

  1. 首先逆向搜索,直至得到的 ibuf entry 不再是关于 P1。若直到左兄弟节点的 infimum record 还未停止,则放弃(根据 latch order,无法再 latch 左兄弟的左兄弟)

  2. 然后正向搜索,直至得到的 ibuf entry 不再是关于 P1。若直到右兄弟节点的 supremum record 还未停止,则放弃(认为缓存的操作足够多了,会引起 P1 的分裂)


放弃的意思是认为 change buffer 缓存的操作已经够多了,不能再缓存了。

ibuf_insert_low {  ...  /* Find out the volume of already buffered inserts for the same index  page */  min_n_recs = 0;  buffered = ibuf_get_volume_buffered(&pcur,    page_id.space(),    page_id.page_no(),    op == IBUF_OP_DELETE? &min_n_recs: NULL, &mtr);

if (op == IBUF_OP_INSERT) { ulint bits = ibuf_bitmap_page_get_bits( bitmap_page, page_id, page_size, IBUF_BITMAP_FREE, &bitmap_mtr);
// 若 ibuf_get_volume_buffered 返回 UNIV_PAGE_SIZE,那么 if 里一定是 TRUE if (buffered + entry_size + page_dir_calc_reserved_space(1) > // 根据 IBUF_FREE_BITS 计算 Page 内的剩余空间,0 / 512 / 1024 / 2048 Bytes // change buffer 里缓存的针对 Page X 的最大容量不能超过 2048 Bytes ibuf_index_page_calc_free_from_bits(page_size, bits)) { /* Release the bitmap page latch early. */ ibuf_mtr_commit(&bitmap_mtr);
/* It may not fit */ do_merge = TRUE;
ibuf_get_merge_page_nos(FALSE, btr_pcur_get_rec(&pcur), &mtr, space_ids, page_nos, &n_stored); goto fail_exit; } }}

在上述正向 / 逆向遍历的过程中,对于每一个 ibuf entry,计算其对于二级索引页 Px 的可能占用的空间(ibuf_get_volume_buffered_count),并累加该值。计算方式依据 ibuf entry type,如果是 IBUF_OP_DELETE_MARK 则无影响,若是 IBUF_OP_INSERT 则会计算其可能占据的空间。

...ut_ad(ibuf_op == IBUF_OP_INSERT);
get_volume_comp : { dtuple_t *entry; ulint volume; dict_index_t *dummy_index; mem_heap_t *heap = mem_heap_create(500);
entry = ibuf_build_entry_from_ibuf_rec(mtr, rec, heap, &dummy_index);
volume = rec_get_converted_size(dummy_index, entry, 0);
ibuf_dummy_index_free(dummy_index); mem_heap_free(heap);
return (volume + page_dir_calc_reserved_space(1));}

防止页的合并

这里需要计算 apply 完 change buffer 里的缓存,该索引页的剩余记录是多少。依然通过函数 ibuf_get_volume_buffered_count,以参数 n_rec 传递出来。

static ulint ibuf_get_volume_buffered(...lint *n_recs,           /*!< in/out: minimum number of records on the                            page after the buffered changes have been                            applied, or NULL to disable the counting */)

计算方式就是遇到 IBUF_OP_DELETE 就把 n_recs --,遇到 IBUF_OP_INSERT或 IBUF_OP_DELETE_MARK 要注意:

  • ibuf entry 中的 user data 在 hashtable 中若没找到,说明这个 user data 是第一次遇到,插到 hashtable 中并把 n_recs ++。原因如下是:


Inserts can be done by updating a delete-marked record. Because delete-mark and insert operations can be pointing to the same records,we must not count duplicates.

如果要缓存的操作是 IBUF_OP_DELETE 且 n_recs < 2,说明这个操作可能导致页面变空,则不缓存到 ibuf 中。

Change Buffer 的写流程

当需要把一个关于二级索引页 P1 的操作缓存在 change buffer 中时,分为四步:

  1. 构造 ibuf entry,暂时以(P1 space id, P1 page no, 0xFFFF)为主键,注:0xFFFF 是最大的 ibuf entry counter

  2. 以 PAGE_CUR_LE 模式搜索 ibuf B-Tree,cursor 最终会落在关于 P1 的最有最大 ibuf entry counter 的 ibuf entry 上,把该 counter + 1 作为新的 counter

  3. 更新第一步中构造的 ibuf entry 中的 IBUF_REC_OFFSET_COUNTER 为新的 counter

  4. 调用 B-Tree 通用的 API 函数(btr_cur_optimistic_insert/btr_cur_pessimistic_insert)把 ibuf entry插入到 ibuf B-Tree 中


缓存 purge 操作的特殊性

change buffer 会缓存三种操作:insert / delete mark / delete,前两种是用户事务的操作,最后一种是 purge 线程的操作。
首先我们需要知道在准备 purge 一个二级索引记录之前,均会判断这个记录是否可以被删除(row_purge_del_mark -> row_purge_remove_sec_if_poss)。拿到该二级索引记录中保存的主键,找到主键索引记录(row_search_index_entry),如果该主键索引记录存在某个 old version 满足下述三点,则该二级索引记录不能被删除(row_purge_poss_sec):

  1. old version 不是 delete mark

  2. old version 的 ROW_TRX_ID 大于 purge view,即可能被活跃的 reader 访问

  3. old version 与该二级索引记录的主键和二级索引列均相同


这三点表示主键索引还存在可能还需要被访问的旧版本,并且可能通过该二级索引记录检索,因此不能被 purge。


但如果使用 change buffer,上述的检查是不够的。比如这个场景:

  1. 用户线程:delete mark (1, A),然后数据页被淘汰出 buffer pool ...

  2. purge 线程:delete (1, A) ;通过 row_purge_poss_sec 的检查,因为新的 (1, A) 在下一步才会出现。准备把操作缓存到 change buffer

  3. 用户线程:insert (1, A),准备把操作缓存到 change buffer

  4. 先把 insert (1, A) 缓存到 change buffer

  5. 再把 delete (1, A) 缓存到 change buffer


在 merge 的时候 insert (1, A) 可能会重用原来被 delete mark 的记录 (1, A),即 "delete unmark";导致 purge 直接删除 (1, A) 后,相当于事务 insert (1, A) 丢失。


解决的办法很简单,当发现有 purge 线程准备缓存操作到 change buffer 中时,第 4 步中放弃缓存 insert。那么怎么发现 purge 线程准备缓存操作到 change buffer?首先在 buffer pool 中保存着这样一些 buf_block_t 结构体,它们不在 buffer chunk 中而是单独的内存区域,即 buf_pool->watch 数组,buf_block_t::state 初始状态是 BUF_BLOCK_POOL_WATCH。然后:

  • 当 purge 线程从 buffer pool 中拿索引页时,如果不在,则在 buf_pool->watch 申请一个空闲的 buf_block_t,并设置其 page_id,还有 state 为 BUF_BLOCK_ZIP_PAG,并放到 page_hash 中。

bpage->state = BUF_BLOCK_ZIP_PAGE;bpage->id = page_id;bpage->buf_fix_count = 1;
ut_d(bpage->in_page_hash = TRUE);HASH_INSERT(buf_page_t, hash, buf_pool->page_hash, page_id.fold(), bpage);

这样的话在第 4 步再去检查这个页是否被设置为 watch,即在 buf_pool->watch 数组中(buf_page_get_also_watch),如果是的话直接放弃。



推荐阅读