理解 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);
}

1. 设置innodb_change_buffering不为IBUF_USE_NONE.
2. 设置innodb_change_buffer_max_size不为0.
3. 待缓存的索引不为数据字典表.
4. 待缓存的索引不是聚簇索引.
5. 待缓存的索引不是 Spatial Index.
6. 待缓存的索引包含递减列.
7. 待缓存的表上没有 flush 操作.
8. 待缓存的索引包含唯一列(唯一列需要全局判断, 可以缓存删除操作, 但无法缓存插入操作).
9. 设置 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

1. 我们讲到对于普通索引来说，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 的空闲空间.