[MySQL 源码] Innodb Pessimistic Insert流程

简单跟了下插入导致索引分裂的流程

//////////////////////////////////

入口函数：row_ins_index_entry

实际上悲观插入和乐观插入是根据row_ins_index_entry_low的第一个参数来判断的

调用两次row_ins_index_entry_low

第一次参数为btr_modify_leaf，表示只修改叶子节点，如果失败了

第二次参数为btr_modify_tree，表示需要修改b-tree，这时候会选择调用函数：

btr_cur_pessimistic_insert:

2.检查锁，如果是聚集索引，还要记录undo，并记录回滚段指针，对于非聚集索引，要在page上记录最大事务id

之前已经分析过，这里不赘述。

    err = btr_cur_ins_lock_and_undo(flags, cursor, entry,

                    thr, mtr, &dummy_inh);

3.扩展文件，为ibd预留足够的文件空间

n_extents = cursor->tree_height / 16 + 3;

success = fsp_reserve_free_extents(&n_reserved, index->space,

                           n_extents, fsp_normal, mtr);

4.检查当前记录是否需要进行外部存储(page_zip_rec_needs_ext)，如果需要的话，则需要对记录进行处理

在函数dtuple_convert_big_rec中，会去循环查找，能最大减少rec的外部存储列

但固定长度列、空列、外部存储列或则长度小于40字节的列不做考虑

另外，在是用dynamic和compressed格式时，任何最大长度小于256字节的非blob列都是本地存储；而对于redundant和compact类型而言，最大不超过788字节时都会本地存储。

big_rec_vec = dtuple_convert_big_rec(index, entry, &n_ext);

返回值类型为big_rec_struct，用于存储溢出数据。

如果找不到满足要求的最大列，返回null。

如果找到了，则替换原记录上的外部指针，并存储实际数据。

如果依然不满足页内存储，则继续寻找该记录上更多的列来进行外部存储。

5.开始进行索引分裂：

a.如果当前记录的cursor在根page上，则分裂节点，提升btree高度，然后再插入记录

*rec = btr_root_raise_and_insert(cursor, entry, n_ext, mgr);

1)首先为b-tree分配一个新page，并进行初始化前后page指针     level = btr_page_get_level(root, mtr);     new_block = btr_page_alloc(index, 0, fsp_no_dir, level, mtr);     new_page = buf_block_get_frame(new_block);     new_page_zip = buf_block_get_page_zip(new_block);     btr_page_create(new_block, new_page_zip, index, level, mgr);     btr_page_set_next(new_page, new_page_zip, fil_null, mtr);     btr_page_set_prev(new_page, new_page_zip, fil_null, mtr); 2)将root节点的记录一个个拷贝到new_page中         /* copy the page byte for byte. */         page_zip_copy_recs(new_page_zip, new_page,                    root_page_zip, root, index, mgr);     //拷贝记录         /* update the lock table and possible hash index. */         lock_move_rec_list_end(new_block, root_block,  //page间迁移记录锁                        page_get_infimum_rec(root));         btr_search_move_or_delete_hash_entries(new_block, root_block, index);  //更新ahi 例外还需要将root页上supremum记录上的锁迁移到新block的supremum记录上，这在做悲观更新时会发生锁托管到系统记录上 lock_update_root_raise(new_block, root_block); 3).构建node ptr 读取新page上的第一个用户记录，创建节点指针(节点键值+page no)     rec = page_rec_get_next(page_get_infimum_rec(new_page));     new_page_no = buf_block_get_page_no(new_block);     node_ptr = dict_index_build_node_ptr(index, rec, new_page_no, heap,                          level); 设置node_ptr的flag为rec_info_min_rec_flag，表面这是该层的最小记录 dtuple_set_info_bits(node_ptr,                  dtuple_get_info_bits(node_ptr)                  | rec_info_min_rec_flag); 4)清空重置root节点，并将node ptr写入root节点 btr_page_empty(root_block, root_page_zip, index, level + 1, mgr);  //清空root page btr_page_set_next(root, root_page_zip, fil_null, mgr);    //设置page的前后page为null btr_page_set_prev(root, root_page_zip, fil_null, mtr);     page_cursor = btr_cur_get_page_cur(cursor);                    page_cur_set_before_first(root_block, page_cursor);      node_ptr_rec = page_cur_tuple_insert(page_cursor, node_ptr,  //将node ptr插入到root page中                          index, 0, mtr); 5).重置记录cursor page_cur_search(new_block, index, tuple,             page_cur_le, page_cursor); 并对新page进行split btr_page_split_and_insert(cursor, tuple, n_ext, mtr) 也就是下面普通的page分裂流程

b.如果当前记录cursor不在根节点page上，走一般的索引分裂逻辑

*rec = btr_page_split_and_insert(cursor, entry, n_ext, mtr);

该函数会先进行page分裂，然后插入记录。

1)选择作为分裂中间点的记录； 先介绍涉及到的几个宏 #define fsp_up      ((byte)111) /*!< alphabetically upwards */ #define fsp_down    ((byte)112) /*!< alphabetically downwards */ #define fsp_no_dir  ((byte)113) /*!< no order */ 这几个宏决定记录插入新分裂页的顺序，是按照字母上升顺序，还是下降顺序。 分三种情况来决定分裂记录和方向 <1>.已经做过一次split，但记录依然无法插入成功，则继续进行分裂  direction = fsp_up;  hint_page_no = page_no + 1;  split_rec = btr_page_get_split_rec(cursor, tuple, n_ext); //查找一个分裂记录  if (univ_unlikely(split_rec == null)) {             insert_left = btr_page_tuple_smaller(                 cursor, tuple, offsets, n_uniq, &heap); <2>.如果函数btr_page_get_split_rec_to_right返回true，则: direction = fsp_up; int_page_no = page_no + 1; 函数btr_page_get_split_rec_to_righ流程如下： 首先判断本次插入记录是否在上次插入记录的右边，如果是的话，则认为这是顺序的插入，然后执行如下： –>获取当前插入记录的下一个记录，如果是supremum record,则split_rec=null， –>再次获得下下条记录，也就是说，会向后看两条记录，这两条记录有一条为supremum record，split_rec都会被设置为null, 否则设置split_rec为第二个记录。 这样做的目的是，如果从插入点开始有超过两个用户记录，我们在该page上保留一个记录，这样随后的序列插入可以利用自适应哈希，因为他们可以简单的通过查看这个page上的记录，来检查正确的查找位置(翻译自注释，待证实)，split_rec为null表示从新插入的记录开始分裂. –>返回true 如果是随机插入的话，返回false <3>如果函数btr_page_get_split_rec_to_left返回true，则        direction = fsp_down;         hint_page_no = page_no – 1;         ut_ad(split_rec); 这种情况下split_rec不可为空 函数btr_page_get_split_rec_to_left流程如下 首先判断，如果上次插入的记录在当前插入记录的右边，则继续下面的流程，否则返回false      –>如果插入的记录不是当前page上的第一个记录，也就是不在infimum记录的下一个，设置split_rec为当前插入点 –>否则，设置split_rec为当前记录插入点的下一个 <4>如果上述都不满足         direction = fsp_up;         hint_page_no = page_no + 1;         如果page上记录不止1个，则从中间开始分裂         split_rec = page_get_middle_rec(page);         如果当前插入记录比该page上记录要小(btr_page_tuple_smaller),则         split_rec = page_rec_get_next(                 page_get_infimum_rec(page));         否则,split_rec为null         也就是说，当这个page上只有一个记录时，我们不能从中间做分裂，而是需要决定新节点是插入到左边还是右边节点。 综上，只有当上次插入的记录在当前插入点的右边时，才会设置direction = fsp_up，其他情况都是fsp_down 2)为索引分配一个新page     new_block = btr_page_alloc(cursor->index, hint_page_no, direction,                    btr_page_get_level(page, mtr), mtr);     btr_page_create(new_block, new_page_zip, cursor->index,             btr_page_get_level(page, mtr), mtr); 3)计算上半部分的page的第一个记录，以及在原始page上的第一个记录 <1> split_rec 不为空 first_rec = move_limit = split_rec; offsets = rec_get_offsets(split_rec, cursor->index, offsets,                          n_uniq, &heap); insert_left = cmp_dtuple_rec(tuple, split_rec, offsets) < 0; insert_left表示当前记录是插入到split_rec的左边还是右边。 <2>insert_left为true //只有在n_iterations>0时才会发生         first_rec = page_rec_get_next(page_get_infimum_rec(page));           move_limit = page_rec_get_next(btr_cur_get_rec(cursor)); <3>其他（split_rec为空）         buf = mem_alloc(rec_get_converted_size(cursor->index,                                tuple, n_ext));         first_rec = rec_convert_dtuple_to_rec(buf, cursor->index,                               tuple, n_ext);         first_rec为插入的记录         move_limit为当前插入记录的下一条 4)修改b树结构 <1>将新page attach到btree上对应的层次上，并向上层节点插入node指针，更新当前层次的节点链表指针    btr_attach_half_pages(cursor->index, block,                   first_rec, new_block, direction, mtr); <2>判断新记录是否能够满足插入。 –>split_rec不为空： insert_will_fit = !new_page_zip             && btr_page_insert_fits(cursor, split_rec,                         offsets, tuple, n_ext, heap); 对于压缩表，new_page_zip不为空，也就是说insert_wil_fit总是为false。 –>split_rec为空，表示分裂记录就是当前插入记录         insert_will_fit = !new_page_zip             && btr_page_insert_fits(cursor, null,                         null, tuple, n_ext, heap); 同样的insert_will_fit对于压缩表而言，总是为false。这意味着在索引分裂的过程中，会一直持有索引上的排他锁 这也会导致压缩表的分裂开销非常大。 <3>判断是否释放索引上的排他锁     if (insert_will_fit && page_is_leaf(page)) {         mtr_memo_release(mtr, dict_index_get_lock(cursor->index),                  mtr_memo_x_lock);     } 5)开始做记录迁移，根据direction的不同，走不同的分支，流程大同小异，这里我们主要看一下fsp_up <1>看该函数的返回值： page_move_rec_list_end(new_block, block, move_limit,                          cursor->index, mtr) 将block上从move_limit(包含该记录)开始记录拷贝到new_block中。      –>page_copy_rec_list_end(new_block, block,                           split_rec, index, mtr)          实际拷贝动作，在拷贝完成后，还会对新page做compress      如果返回false，表示压缩失败，直接返回false。不继续下面的流程     –>从block上删除转移的记录。     page_delete_rec_list_end(split_rec, block, index,                  new_n_recs – old_n_recs,                  new_data_size – old_data_size, mtr);     –>返回true 如果转移记录到新block,但新block压缩失败的话，还需要继续做处理： –>将原page中的记录拷贝到新page中。             page_zip_copy_recs(new_page_zip, new_page,                        page_zip, page, cursor->index, mtr); –>从新page上删除从move_limit开始的记录，不包括move_limit记录以及系统记录             page_delete_rec_list_start(move_limit – page                            + new_page, new_block,                            cursor->index, mtr); –>更新锁表和ahi             lock_move_rec_list_end(new_block, block, move_limit);             btr_search_move_or_delete_hash_entries(                 new_block, block, cursor->index); –>从源表上删除从move_limit（包括move_limit）开始的记录              page_delete_rec_list_end(move_limit, block,                          cursor->index,                          ulint_undefined,                          ulint_undefined, mtr); 最后更新记录锁         left_block = block;         right_block = new_block;         lock_update_split_right(right_block, left_block); 6)到了这一步，索引树的分裂和修改已经结束了，这时候可以把记录插入到其中，根据insert_left来选择插入到哪个block中 7)如果插入失败，则重新reorgnize page，n_iterations++;然后重头开始继续分裂。 8)对于二级索引，更新insert buffer.

6.更新adaptive hash index

btr_search_update_hash_on_insert(cursor);

7.更新记录锁信息

lock_update_insert(btr_cur_get_block(cursor), *rec);

8.如果之前分配了extend,则更新space->n_reserved_extents计数

    if (n_extents > 0) {

        fil_space_release_free_extents(index->space, n_reserved);