背景

InnoDB 作为目前 MySQL 的主要存储引擎，其中 record 细节繁琐，这里仅做整理以便查阅. 版本基于 MySQL-8.0.25.

数据结构

InnoDB record 的逻辑格式: dtuple_t

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/** Structure for an SQL data tuple of fields (logical record) */
struct dtuple_t {
  /* ... */

  /** Number of fields in dtuple */
  ulint n_fields; /* 当前 dtuple 记录的字段数量. */

  /** number of fields which should be used in comparison services of rem0cmp.*;
  the index search is performed by comparing only these fields, others are
  ignored; the default value in dtuple creation is the same value as n_fields */
  ulint n_fields_cmp; /* 当前 dtuple 中可以用来比较的字段数量, 可以通过
                       * dtuple_set_n_fields_cmp() 设置. */

  /** Fields. */
  dfield_t *fields; /* 当前 dtuple 的字段内容. */
    /** Structure for an SQL data field */
    struct dfield_t {
      void *data;       /*!< pointer to data */
      unsigned ext : 1; /*!< TRUE=externally stored, FALSE=local */
      unsigned spatial_status : 2;
      /*!< spatial status of externally stored field
        in undo log for purge */
      unsigned len; /*!< data length; UNIV_SQL_NULL if SQL null 数据长度 */
      dtype_t type; /*!< type of data  数据类型*/
      
      /* ... */
    } */

  /** ... */

  /** Compare a data tuple to a physical record.
    * dtuple_t 与 rec_t 的比较函数. */
  int compare(const rec_t *rec, const dict_index_t *index, const ulint *offsets,
              ulint *matched_fields) const;

  /** ... */
};

MySQL SQL 层的 record 可以通过row_sel_convert_mysql_key_to_innobase()转换为 InnoDB 可识别的dtuple_t结构.

索引内存结构: dict_index_t

  • index->table->n_cols: table 的列数，包含用户定义的列 + 3 列系统列(DB_ROW_ID, DB_TRX_ID, DB_ROLL_PTR).
  • index->table->cols: 存上面 n_cols 个列的数组, 系统列在倒数后3个.
  • index->n_fields: 当前索引包含的列数，小于等于上面的 index->table->n_cols.
  • index->fields: 记录当前索引 column 的描述信息, 列名，长度, 顺序 or 倒序

Record Node:

  • 对于主键索引 leaf node:

      1. 如果定义了主键, 那么系统列就没有 DB_ROW_ID，那么此时 n_fields 比 n_cols 小 1.
      1. 如果没有定义主键, 那么系统列就包含 DB_ROW_ID，那么此时 n_fields 和 n_cols 值一样.

  • 对于主键索引 non-leaf node:

      1. n_fields 包含所有唯一字段 + Page Number, 数量为 index->n_uniq + 1.

  • 对于二级索引 leaf node:

      1. n_fields 就是包含二级索引定义的列数 + 主键列数.

  • 对于二级索引 non-leaf node:

      1. n_fields 就是包含二级索引定义的列数 + Page Number, 数量为 index->n_fields + 1.

使用dict_index_build_node_ptr()构建 non-leaf node:

InnoDB 物理 record: rec_t

offsets 数组由rec_get_offsets(), 数组大小由 n_fields + 1 + REC_OFFS_HEADER_SIZE 决定.

  • offsets[0] = n_alloc /* n_alloc 是数组元素个数. */
  • offsets[1] = n_fields /* n_fields 是 record 列数. */
  • offsets[2] = extra size
  • offsets[3.. 3 + n_fields] /* 记录每个 field 的结束偏移. */

rec_t可以直接通过cmp_dtuple_rec_with_match_low()与dtuple_t比较:

rec_t可以通过 offsets 数组分别获取对应的 filed 字段, 再与((dfield_t *)tuple->fields + n)直接进行比较.

B-tree 游标: btr_pcur_t

btr_pcur_t是在 search 或者 modify 过程中用来定位的游标, 其中记录定位信息, 可以直接通过store_position()来保存，通过restore_position()可以恢复至上一次保存 record 位置信息.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct btr_pcur_t {
  /** ... */

  /* 保存 pcur 记录的信息. */
  void store_position(mtr_t *mtr);

  /* 恢复出来上一次 pcur 保存的位置. */
  bool restore_position(ulint latch_mode, mtr_t *mtr, const char *file,
                        ulint line);

  /** pcur 定位的元信息: index, block, n_fileds ... */
  btr_cur_t m_btr_cur;

  /** true if old_rec is stored */
  bool m_old_stored{false};

  /* 保存当前 pcur 指向的 record. */
  rec_t *m_old_rec{nullptr};

  /* 记录 m_old_rec 的 filed 数量. */
  ulint m_old_n_fields{0};

  /* 记录数据 page 的 modify clock. */
  uint64_t m_modify_clock{0};

  /** ... */
}

store_position()保存位置信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void btr_pcur_t::store_position(mtr_t *mtr) {
  ut_ad(m_pos_state == BTR_PCUR_IS_POSITIONED);
  ut_ad(m_latch_mode != BTR_NO_LATCHES);

  auto block = get_block();
  auto index = btr_cur_get_index(get_btr_cur());

  auto page_cursor = get_page_cur();

  /* pcur 指向的 record. */
  auto rec = page_cur_get_rec(page_cursor);
  /* record 所在的 page. */
  auto page = page_align(rec);
  /* record 在 page 上的 offset. */
  auto offs = page_offset(rec);

  /* ... */

  if (page_rec_is_supremum_low(offs)) {
    /* pcur 指向的是一个 supremum record, 则保存前一个 record. */
    rec = page_rec_get_prev(rec);

    m_rel_pos = BTR_PCUR_AFTER;

  } else if (page_rec_is_infimum_low(offs)) {
    /* pcur 指向的是一个 infimum record, 则保存后一个 record. */
    rec = page_rec_get_next(rec);

    m_rel_pos = BTR_PCUR_BEFORE;
  } else {
    /* pcur 指向的是一个 user record, 直接保存这个 record. */
    m_rel_pos = BTR_PCUR_ON;
  }

  m_old_stored = true;

  /* 保存当前指向的 record 至 m_old_rec. */
  m_old_rec = dict_index_copy_rec_order_prefix(index, rec, &m_old_n_fields,
                                               &m_old_rec_buf, &m_buf_size);

  m_block_when_stored.store(block);

  /* Function try to check if block is S/X latch. */
  /* 记录 modify clock. */
  m_modify_clock = buf_block_get_modify_clock(block);
}

  • 如果 pcur 指向一个 supremum record, 保存 supremum record 前的一个 record, m_rel_pos 为 BTR_PCUR_AFTER.

  • 如果 pcur 指向一个 infimum record, 保存 infimum record 后的一个 record, m_rel_pos 为 BTR_PCUR_BEFORE.

  • 如果 pcur 指向一个 user record, 保存 user record, m_rel_pos 为 BTR_PCUR_ON.

restore_position()先尝试乐观加锁，即直接判断m_modify_clock是否变化，假如 b+ tree 发生了 SMO, 需要进行悲观加锁的方式，即通过btr_cur_search_to_nth_level()重新 search 加锁:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
bool btr_pcur_t::restore_position(ulint latch_mode, mtr_t *mtr,
                                  const char *file, ulint line) {
  dtuple_t *tuple;
  page_cur_mode_t mode;

  ut_ad(mtr->is_active());
  ut_ad(m_old_stored);
  ut_ad(is_positioned());

  auto index = btr_cur_get_index(get_btr_cur());

  /* ... */

  ut_a(m_old_rec != nullptr);
  ut_a(m_old_n_fields > 0);

  /* Optimistic latching involves S/X latch not required for
  intrinsic table instead we would prefer to search fresh. */
  if ((latch_mode == BTR_SEARCH_LEAF || latch_mode == BTR_MODIFY_LEAF ||
       latch_mode == BTR_SEARCH_PREV || latch_mode == BTR_MODIFY_PREV) &&
      !m_btr_cur.index->table->is_intrinsic()) {
    /* Try optimistic restoration. */
    /* 乐观恢复. */
    if (m_block_when_stored.run_with_hint([&](buf_block_t *hint) {
          return hint != nullptr && btr_cur_optimistic_latch_leaves(
                                        hint, m_modify_clock, &latch_mode,
                                        &m_btr_cur, file, line, mtr);
        })) {
      m_pos_state = BTR_PCUR_IS_POSITIONED;

      m_latch_mode = latch_mode;

      buf_block_dbg_add_level(get_block(), dict_index_is_ibuf(index)
                                               ? SYNC_IBUF_TREE_NODE
                                               : SYNC_TREE_NODE);

      if (m_rel_pos == BTR_PCUR_ON) {
#ifdef UNIV_DEBUG
        /* ... */
#endif /* UNIV_DEBUG */
        return (true);
      }

      /* This is the same record as stored,
      may need to be adjusted for BTR_PCUR_BEFORE/AFTER,
      depending on search mode and direction. */
      if (is_on_user_rec()) {
        m_pos_state = BTR_PCUR_IS_POSITIONED_OPTIMISTIC;
      }
      return (false);
    }
  }

  /* If optimistic restoration did not succeed, open the cursor anew */

  auto heap = mem_heap_create(256);

  tuple = dict_index_build_data_tuple(index, m_old_rec, m_old_n_fields, heap);

  /* Save the old search mode of the cursor */
  auto old_mode = m_search_mode;

  /*  根据 store_position() 时记录的 m_rel_pos 采用不同的 search mode. */
  switch (m_rel_pos) {
    case BTR_PCUR_ON:
      mode = PAGE_CUR_LE;
      break;
    case BTR_PCUR_AFTER:
      mode = PAGE_CUR_G;
      break;
    case BTR_PCUR_BEFORE:
      mode = PAGE_CUR_L;
      break;
    default:
      ut_error;
  }

  /* 乐观恢复 pcur 失败，就要通过 btr_cur_search_to_nth_level 来重新定位 pcur. */
  open_no_init(index, tuple, mode, latch_mode, 0, mtr, file, line);

  /* Restore the old search mode */
  m_search_mode = old_mode;

  ut_ad(m_rel_pos == BTR_PCUR_ON || m_rel_pos == BTR_PCUR_BEFORE ||
        m_rel_pos == BTR_PCUR_AFTER);

  if (m_rel_pos == BTR_PCUR_ON && is_on_user_rec() &&
      !cmp_dtuple_rec(
          tuple, get_rec(), index,
          rec_get_offsets(get_rec(), index, nullptr, ULINT_UNDEFINED, &heap))) {
    /* We have to store the NEW value for the modify clock,
    since the cursor can now be on a different page!
    But we can retain the value of old_rec */
    auto block = get_block();
    m_block_when_stored.store(block);
    m_modify_clock = buf_block_get_modify_clock(block);

    m_old_stored = true;

    mem_heap_free(heap);

    return (true);
  }

  mem_heap_free(heap);

  /* We have to store new position information, modify_clock etc.,
  to the cursor because it can now be on a different page, the record
  under it may have been removed, etc. */

  store_position(mtr);

  return (false);
}

  1. 对于 BTR_SEARCH_LEAF,BTR_MODIFY_LEAF,BTR_SEARCH_PREV,BTR_MODIFY_PREV 四种 latch mode, 可以尝试乐观 restore_position().

  2. 针对悲观 restore_position 的情况:

    • 如果 store_position() 时记录的 m_rel_pos 为 BTR_PCUR_ON, 则 store_position() 时为一个 user record, 采用 PAGE_CUR_LE 的 search mode, 恢复至最后一个小于等于 user record(old) 的 record.
    • 如果 store_position() 时记录的 m_rel_pos 为 BTR_PCUR_AFTER, 则 store_position() 时为一个 supremum record, 采用 PAGE_CUR_G 的 search mode, store_position() 时 pcur 保存的是 supremum record 前的 record(old), 所以恢复至大于 record(old) 的 record. (所以可能定位在大于 record(old) 的下一个 user record, 也可能是 store_position() 当时定位的 supremum record).
    • 如果 store_position() 时记录的 m_rel_pos 为 BTR_PCUR_BEFORE, 则 store_position() 时为一个 infimum record, 采用 PAGE_CUR_L 的 search mode, store_position() 时 pcur 保存的是 infimum record 后的 record(old), 所以恢复至小于 record(old) 的 record. (所以可能定位在小于 record(old) 的上一个 user record, 也可能是 store_position() 当时定位的 infimum record).

store_position()会记录buf_block_t, 在乐观恢复中直接通过尝试对buf_block_t加锁，当前的 Buffer Pool 支持动态 resize, 这部分的内存可能会被释放, 所以 InnoDB 会首先判断这个buf_block_t指针是否存在于 Buffer Pool 的 chunk 中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Block_hint::buffer_fix_block_if_still_valid() {
  if (m_block != nullptr) {
    const buf_pool_t *const pool = buf_pool_get(m_page_id);

    rw_lock_t *latch = buf_page_hash_lock_get(pool, m_page_id);
    rw_lock_s_lock(latch);

    /* If not own buf_pool_mutex, page_hash can be changed. */
    latch = buf_page_hash_lock_s_confirm(latch, pool, m_page_id);
    if (buf_is_block_in_instance(pool, m_block) &&
        m_page_id == m_block->page.id &&
        buf_block_get_state(m_block) == BUF_BLOCK_FILE_PAGE) {
      buf_block_buf_fix_inc(m_block, __FILE__, __LINE__);
    } else {
      clear();
    }

    rw_lock_s_unlock(latch);
  }
}

游标 cursor 的搜索模式

  • PAGE_CUR_G: > 查询，查询第一个大于 dtuple 的 rec_t.

  • PAGE_CUR_GE: >=，> 查询，查询第一个大于等于 dtuple 的 rec_t.

    1. 如果搜索一个存在的 user record, 使用 PAGE_CUR_GE 可能定位在这个 user record 的 previous page 的 supremum record.

  • PAGE_CUR_L: < 查询，查询最后一个小于 dtuple 的 rec_t.

  • PAGE_CUR_LE: <= 查询，查询最后一个小于等于 dtuple 的 rec_t.

    1. 如果搜索一个不存在的 user record, 使用 PAGE_CUR_LE 返回最后一个小于 dtuple 的 record.