Innodb 中的 Btree 实现 insert 篇

数据运维 2023-10-27 宇宙之一粟 手机阅读

6 Insert 路径解析

介绍完 Innodb 中 Btree 组织形式、搜索和并发控制策略，我们此时来看 Innodb 中 btree 是如何插入一条数据的。Innodb 在插入时需要对主键索引和二级索引分开考虑，先插入主键索引，再插入二级索引。

整个插入流程函数在 row_ins 中，插入前会先判断主键索引是否 unique（即是否定义主键），不是则会先分配 row id 来唯一标识一条 record。

无论主键索引还是二级索引，都需要先构建插入的完整行记录的内存版本（row，dtuple type），再基于 row 和各个索引（dict_index_t）的列信息构建真正需要插入索引中存储的版本（entry，dtuple type），进行 cursor 搜索定位到最后一个小于等于该 dtuple 的 rec_t 后，从 page 内部申请空间插入 entry 的内容。

6.1 主键索引的 insert 路径

主键索引的插入流程在 row_ins_clust_index_entry 函数中，先进行加锁范围更小的乐观插入流程，如果插入失败（page 空间不足），会进行悲观插入流程，加锁范围更大，并触发结点分裂流程，这也和 cursor 的乐观悲观搜索相对应。

控制乐观和悲观插入流程在 row_ins_clust_index_entry_low 中，根据 latch_mode 进行判断，每次都开启一个新的 mtr 流程，我们先看乐观插入:

  • 先进行乐观 cursor 搜索 (BTR_MODIFY_LEAF)，定位到 leaf page 的 rec_t 中。
  • duplicate check: 检查定位的 rec_t 是否和要插入的 entry 相等，存在重复，会将可能相等的 record 都加上事务锁（普通 insert 加 S lock，insert on duplicate key update 则加 X lock，gap mode 取决于事务隔离级别），保证不被其他事务修改。如果 rec_t 不是 delete mark，向上层返回 duplicate key 错误，如果是 delete mark，将插入流程转为 update-in-place 覆盖写入（row_ins_clust_index_entry_by_modify）。
  • 否则进入乐观插入（btr_cur_optimistic_insert），首先会计算插入 entry 空间，先判断 page 中 free list 空间是否足够，free list 空间不够，再判断 page 中未分配的堆的空间，如果还是不够，会判断 reorganize page 后的空间（整理 page 内部的空间碎片），如果存在空闲空间，将 entry 内容 copy 到申请的 rec_t 中，并更新 rec_t 和 page 的元信息，否则会进行悲观插入。
  • 真正插入 entry 前，会检查事务锁和记录 undo (btr_cur_ins_lock_and_undo)，检查事务锁 (lock_rec_insert_check_and_lock) 会判断 cursor 定位的下一个 rec_t 上当前有没有锁，有的话加上带有 gap 的插入意向的 X 锁（LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION ）的显示锁，来等待其他 gap 锁释放，确保要插入的区间没有其他事务访问。同时每一条 Insert 的 rec_t 上都默认有一个隐式锁，它是通过 trx_id 和当前活跃事务数组的 id 来检测的，这么做减少了 lock_sys 的操作，提升性能[6]。为了保证事务回滚，插入 entry 前会记录一条 insert 类型的 undo（trx_undo_report_row_operation），将 entry 的 key fields 写入 undo page 中，便于回滚时找到 record 的位置，并根据 undo page 的 id 和 offset 构建出回滚指针存入插入的 rec_t 中[7]。
  • 在写入 entry 之后，会向 mtr 的 log buf 记录 redo log (page_cur_insert_rec_write_log)，用于 WAL 故障恢复，通常一条 insert 的 redo log 会记录 page 和 index 信息，以及和 cursor 定位的 rec_t 相比的差异部分（btree的有序特性，相邻的 record 相同部分较多，减少存储的 redo log 大小）：

(Page ID, offset) + (len of each field) + (extra info) + (bytes which differs from cursor record)