[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:


1.首先做一次乐观插入(btr_cur_optimistic_insert),这实际上是重复的动作,会带来额外的开销,在后面的版本已经被移除了。http://bugs.mysql.com/bug.php?id=61456


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为当前记录插入点的下一个

–>返回TRUE


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

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

        move_limit = page_rec_get_next(btr_cur_get_rec(cursor));


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

    }

原创文章,转载请注明: 转载自Simple Life

本文链接地址: [MySQL 源码] Innodb Pessimistic Insert流程

Post Footer automatically generated by wp-posturl plugin for wordpress.


Comments

Leave a Reply

Your email address will not be published. Name and email are required


Current month ye@r day *