理解 InnoDB 的 Change Buffer

背景

MySQL 版本：8.0.23

Change Buffer 是 InnoDB 系统表空间(space id = 0) 的一个 B+ tree 索引，它的作用是为满足指定条件下而数据 Page 不在 Buffer Pool 的二级索引操作进行缓存，包括一开始的 INSERT 和后来加入的 UPDATE, DELETE。聚簇索引的顺序插入，可能体现在二级索引中字段并不是顺序的，所以存在大量的随机读取和写入，将二级索引的数据操作顺序写入 Change Buffer 的 B+ tree，以此达到与聚簇索引一致的顺序写入。当我们需要读取时，会将对应的数据 Page 从磁盘读取至 Buffer Pool 并与 Change Buffer 中对应的 records 进行 merge 操作。

Change buffer 使用

参数

innodb_change_buffering：设置缓存的操作类型，包括 none, all, inserts, deletes, changes, purges.
innodb_change_buffer_max_size：设置 Change Buffer 所占 Buffer Pool 的大小，默认 25%，最大50%. (假如超过了阈值，会阻止进行 Change Buffer 写入，转而使用通常的写入方式，然后进行主动 merge，即将数据 Page 读至 Buffer Pool，并将 Change Buffer 的 records 与数据 Page 进行合并)

触发条件

除了设置上述的参数打开 Change Buffer 以外，真正使用 Change Buffer 还需要经过一些条件判断：

ibool ibuf_should_try(dict_index_t *index,     /*!< in: index where to insert */
                      ulint ignore_sec_unique) /*!< in: if != 0, we should
                                               ignore UNIQUE constraint on
                                               a secondary index when we
                                               decide */
{
  return (innodb_change_buffering != IBUF_USE_NONE && ibuf->max_size != 0 &&
          index->space != dict_sys_t::s_space_id && !index->is_clustered() &&
          !dict_index_is_spatial(index) && !dict_index_has_desc(index) &&
          index->table->quiesce == QUIESCE_NONE &&
          (ignore_sec_unique || !dict_index_is_unique(index)) &&
          srv_force_recovery < SRV_FORCE_NO_IBUF_MERGE);
}

设置 innodb_change_buffering 不为 IBUF_USE_NONE.
设置 innodb_change_buffer_max_size 不为0.
待缓存的索引不为数据字典表。
待缓存的索引不是聚簇索引。
待缓存的索引不是 Spatial Index.
待缓存的索引包含递减列。
待缓存的表上没有 flush 操作。
待缓存的索引包含唯一列(唯一列需要全局判断，可以缓存删除操作，但无法缓存插入操作).
设置 srv_force_recovery 不允许 ibuf merge 操作。

所以我们在打开 Change Buffer 的同时也需要判断以上的条件是否符合。对于唯一索引和写入立即需要读取的数据并不适合打开 Change Buffer.

Change Buffer 原理

Change Buffer 的调用逻辑是当我们需要进行支持的 DML 操作时，尝试从 Buffer Pool 读取 Page 时，假如 Page 不在 Buffer Pool 中并符合上述的触发条件，会通过 ibuf_insert() 来针对不同类型的操作进行 Change Buffer 的缓存。

Change Buffer 最初的功能只有缓存 INSERT 操作，所以也作 ibuf，代码中均使用 ibuf 代替 Change Buffer.

Change Buffer 中有几个重要的概念：

Change Buffer Record

Change Buffer 的 Page 缓存对应二级索引的 DML 操作，使用 <space_id, page_no, counter> 作为 key，当需要查找的时，使用 <space_id, page_no> 就可以定位到具体的 record，而 counter 作为一个递增的值，记录着 DML 的操作顺序。

Change Buffer Bitmap Page

在每个 Tablespace 中 Extent 的第二个 Page 会作为 Change Buffer 的元信息 Page，即为 ibuf bitmap page, bitmap page 会使用 4 bits 来记录 Tablespace 中关于数据 Page 的 Change Buffer 信息，以下方法可以计算 bitmap page no:

/* #define FSP_IBUF_BITMAP_OFFSET 1 */
ulint bitmap_page_no = FSP_IBUF_BITMAP_OFFSET + ((page_no / page_size) * page_size)

其中包括以下几个信息：

IBUF_BITMAP_FREE：长度 2 bit，记录该 Page 空闲空间，使用 2个 bit 来描述空闲空间大小，以 16KB 的 page size 为例，能表示的空闲空间范围为0 (0 bytes)、1 (512 bytes)、2 (1024 bytes)、3 (2048 bytes)。注意此处2048 bytes 意为用户的累计插入 records 长度不能超过 2048 bytes，并不单单指一次插入，假如累积缓存的 record 长度超过了 2048bytes，就会触发 ibuf merge 操作。
IBUF_BITMAP_BUFFERED：长度 1 bit，代表该 Page 上存在被缓存了的 DML 操作。
IBUF_BITMAP_IBUF：长度 1 bit，代表该 Page 属于 ibuf 类型，供 AIO 线程判断。

使用函数 ibuf_index_page_calc_free_from_bits() 可以计算 Page 的空闲空间：

if (ibuf_code == 3) {
      ibuf_code = 4;
}
free_space = ibuf_code * (page_size / IBUF_PAGE_SIZE_PER_FREE_SPACE);

在正常的 DML 操作成功后会更新对应数据 Page 的 IBUF_BITMAP_BUFFERED, IBUF_BITMAP_BUFFERED 并不是准确的记录数据 Page 的空闲空间，最大只能记录 2kb，所以用户在写入 record 导致 Page 的剩余空闲空间小于 2kb 之后才会更新。而 Change Buffer 的缓存操作也通过 IBUF_BITMAP_BUFFERED 最大缓存 2kb 的 records.

Change Buffer 写入

static MY_ATTRIBUTE((warn_unused_result)) dberr_t
    ibuf_insert_low(ulint mode, ibuf_op_t op, ibool no_counter,
                    const dtuple_t *entry, ulint entry_size,
                    dict_index_t *index, const page_id_t &page_id,
                    const page_size_t &page_size, que_thr_t *thr) {
  /* ... */

  /* 假如当前的 ibuf 大小超过了设置的阈值, 调用 ibuf_contract() 进行
   * 部分 ibuf merge 操作以缓解 ibuf 的空间问题. */
  if (ibuf->size >= ibuf->max_size + IBUF_CONTRACT_DO_NOT_INSERT) {
    /* Insert buffer is now too big, contract it but do not try
    to insert */

#ifdef UNIV_IBUF_DEBUG
    fputs("Ibuf too big\n", stderr);
#endif
    ibuf_contract(true);

    return (DB_STRONG_FAIL);
  }

  heap = mem_heap_create(1024);

  /* 构建插入 ibuf 的 entry:
   * entry 是以 <space_id, page_no, counter> 为 Key,
   * counter 的作用是来保证 DML 操作的顺序, 每次 DML 自增 1.
   * space_id, pae_no 是已知, counter 先默认设为 0xFFFF. */
  ibuf_entry =
      ibuf_entry_build(op, index, entry, page_id.space(), page_id.page_no(),
                       no_counter ? ULINT_UNDEFINED : 0xFFFF, heap);


  /* 针对 DML 操作判断 ibuf 的数据 Page 是否充裕，否则要进行分配直到满足写入. */
  if (BTR_LATCH_MODE_WITHOUT_INTENTION(mode) == BTR_MODIFY_TREE) {
    for (;;) {
      mutex_enter(&ibuf_pessimistic_insert_mutex);
      mutex_enter(&ibuf_mutex);

      if (UNIV_LIKELY(ibuf_data_enough_free_for_insert())) {
        break;
      }

      mutex_exit(&ibuf_mutex);
      mutex_exit(&ibuf_pessimistic_insert_mutex);

      if (!ibuf_add_free_page()) {
        mem_heap_free(heap);
        return (DB_STRONG_FAIL);
      }
    }
  }

  ibuf_mtr_start(&mtr);

  /* 使用先前创建的 entry 对 ibuf->index 进行 search, 注意使用的是 PAGE_CUR_LE, 即 pcur 是落在一个小于等于的 record 上. */
  btr_pcur_open(ibuf->index, ibuf_entry, PAGE_CUR_LE, mode, &pcur, &mtr);
  ut_ad(page_validate(btr_pcur_get_page(&pcur), ibuf->index));

  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);

  /* 假如是 IBUF_OP_DELETE 操作并且待缓存的 Page 上的 record 数量小于 2 则不能进行 ibuf 缓存操作, 因为会导致 SMO. */
  if (op == IBUF_OP_DELETE &&
      (min_n_recs < 2 || buf_pool_watch_occurred(page_id))) {
    /* ... */
  fail_exit:
    if (BTR_LATCH_MODE_WITHOUT_INTENTION(mode) == BTR_MODIFY_TREE) {
      mutex_exit(&ibuf_mutex);
      mutex_exit(&ibuf_pessimistic_insert_mutex);
    }

    err = DB_STRONG_FAIL;
    goto func_exit;
  }

  ibuf_mtr_start(&bitmap_mtr);

  /* 获取 bitmap page. */
  bitmap_page = ibuf_bitmap_get_map_page(page_id, page_size, &bitmap_mtr);

  /* 1. 检查对应的数据 Page 是否被 load 进 Buffer Pool.
   * 2. 检查对应的数据 Page 上是否存在隐式的插入锁. */
  if (buf_page_peek(page_id) ||
      lock_rec_expl_exist_on_page(page_id.space(), page_id.page_no())) {
    ibuf_mtr_commit(&bitmap_mtr);
    goto fail_exit;
  }


  /* 对于没有指定 counter 的 record, 我们需要通过 ibuf_get_entry_counter() 获取前一个 reocrd 的 counter, 并自增 1, 以此作为当前的 record 的 counter 值.
   * 对于当前 Page 的第一个 record, 则从 0 开始.*/
  if (!no_counter) {
    ulint counter = ibuf_get_entry_counter(
        page_id.space(), page_id.page_no(), btr_pcur_get_rec(&pcur), &mtr,
        btr_pcur_get_btr_cur(&pcur)->low_match < IBUF_REC_FIELD_METADATA);
    dfield_t *field;

    if (counter == ULINT_UNDEFINED) {
      ibuf_mtr_commit(&bitmap_mtr);
      goto fail_exit;
    }

    field = dtuple_get_nth_field(ibuf_entry, IBUF_REC_FIELD_METADATA);
    /* 写入 counter 值. */
    mach_write_to_2((byte *)dfield_get_data(field) + IBUF_REC_OFFSET_COUNTER,
                    counter);
  }

  /* Set the bitmap bit denoting that the insert buffer contains
  buffered entries for this index page, if the bit is not set yet */

  /* 设置 bitmap page 的 IBUF_BITMAP_BUFFERED 位, 意为当前 Page 存在 Change Buffer 操作. */
  old_bit_value = ibuf_bitmap_page_get_bits(bitmap_page, page_id, page_size,
                                            IBUF_BITMAP_BUFFERED, &bitmap_mtr);

  if (!old_bit_value) {
    ibuf_bitmap_page_set_bits(bitmap_page, page_id, page_size,
                              IBUF_BITMAP_BUFFERED, TRUE, &bitmap_mtr);
  }

  ibuf_mtr_commit(&bitmap_mtr);

  cursor = btr_pcur_get_btr_cur(&pcur);

  if (mode == BTR_MODIFY_PREV) {
    err = btr_cur_optimistic_insert(BTR_NO_LOCKING_FLAG, cursor, &offsets,
                                    &offsets_heap, ibuf_entry, &ins_rec,
                                    &dummy_big_rec, 0, thr, &mtr);
    /* ... */
  } else {
    ut_ad(BTR_LATCH_MODE_WITHOUT_INTENTION(mode) == BTR_MODIFY_TREE);
    /* ... */
    /* 进行乐观插入. */
    err = btr_cur_optimistic_insert(BTR_NO_LOCKING_FLAG | BTR_NO_UNDO_LOG_FLAG,
                                    cursor, &offsets, &offsets_heap, ibuf_entry,
                                    &ins_rec, &dummy_big_rec, 0, thr, &mtr);

    if (err == DB_FAIL) {
      /* 乐观插入失败则进行悲观插入. */
      err = btr_cur_pessimistic_insert(
          BTR_NO_LOCKING_FLAG | BTR_NO_UNDO_LOG_FLAG, cursor, &offsets,
          &offsets_heap, ibuf_entry, &ins_rec, &dummy_big_rec, 0, thr, &mtr);
    }

    mutex_exit(&ibuf_pessimistic_insert_mutex);
    ibuf_size_update(root);
    mutex_exit(&ibuf_mutex);
    ibuf->empty = page_is_empty(root);

    block = btr_cur_get_block(cursor);
    ut_ad(block->page.id.space() == IBUF_SPACE_ID);
  }


  /* ... */
  if (err == DB_SUCCESS && op != IBUF_OP_DELETE) {
    /* Update the page max trx id field */
    page_update_max_trx_id(block, NULL, thr_get_trx(thr)->id, &mtr);
  }

func_exit:
  /* ... */
  ibuf_mtr_commit(&mtr);
  btr_pcur_close(&pcur);

  mem_heap_free(heap);

  if (err == DB_SUCCESS &&
      BTR_LATCH_MODE_WITHOUT_INTENTION(mode) == BTR_MODIFY_TREE) {
    /* 插入后判断是否需要对数据 Page 进行 merge 操作. */
    ibuf_contract_after_insert(entry_size);
  }

  if (do_merge) {
#ifdef UNIV_IBUF_DEBUG
    ut_a(n_stored <= IBUF_MAX_N_PAGES_MERGED);
#endif
    /* 对于读取的 Page 进行 merge 操作. */
    buf_read_ibuf_merge_pages(false, space_ids, page_nos, n_stored);
  }

  return (err);
}

Change Buffer 合并(ibuf merge)

有以下几个场景会触发 Change Buffer 的 merge 操作，即将 ibuf Page 的 records 和原数据 Page 进行合并操作 (ibuf_merge_or_delete_for_page()):

ibuf_insert_low() 中存在部分判断逻辑会导致无法使用 Change Buffer 写入，从而触发 ibuf merge.
当二级索引数据 Page 从磁盘读入至 Buffer Pool 之后，会触发 merge 操作(buf_page_get_gen()).
ibuf_merge_in_background() 会在后台触发 ibuf Page 进行 merge.
在 Recover 阶段会对 ibuf Page 的 Records 和数据 Page 进行 merge.
当执行 slow shutdown 时，会强制做一次全部的ibuf merge.

ibuf 的 merge 操作原理比较简单，就是根据操作类型将 records 从 ibuf Page 合并至数据 Page (ibuf_insert_to_index_page()/ibuf_set_del_mark()/ibuf_delete())

FAQ

我们讲到对于普通索引来说，Change Buffer 可以避免 Update/Delete/Insert 等修改操作的时候访问磁盘。后续查询的时候再从磁盘中读出并 merge，对于 Delete 操作，删除一行不存在的数据，这时候 Change Buffer 如何处理？

InnoDB 的删除逻辑是先删聚簇索引，再删除二级索引(标记删除)，所以当主键索引发现 DB_RECORD_NOT_FOUND 就会返回，所以不会触发缓存不存在的索引数据。

总结

InnoDB 实现了 Change buffer 来优化用户在二级索引上的随机写入问题，用户可以根据自己的需求结合 Change buffer 的一些条件来判断是否启用 Change buffer，但需要注意的是 Change buffer 的阈值只有 2kb，假如在一个二级索引的数据 Page 写入的 record 长度超过 2kb，就会触发 ibuf merge，从而使后续的 ibuf 缓存条件失效，但这也符合 IO-bound 的场景需求。本文也介绍了 Change buffer 如何使用 Bitmap Page 跟踪数据 Page 的空闲空间。