注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

网易杭研后台技术中心的博客

 
 
 
 
 

日志

 
 

InnoDB insert buffer实现详解  

来自raolh   2013-03-25 14:35:13|  分类: 默认分类 |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 InnoDB的inset buffer机制到了MySQL5.5的时候已经更名为change buffer,不但支持insert操作的buffer,还支持update,delete,purge等操作的buffer,这些增加的功能都是在insert buffer原理上面发展而来的。本文通过剖析insert操作的buffer过程来讲解整个的实现原理。

    insert buffer功能从mysql 3.23起被加入,出于简洁原则本文讲解insert buffer在3.23中的实现。

ibuf相关的页

    首先看看Insert buffer的页结构。在系统表空间中inser buffer相关的页:

System tablespace

MySQL insert buffer实现详解 - raolh - 枫叶的博客

系统表空间中的第2个页page1是Bitmap页,记录了一个区中所有页的空间占用情况,insert缓存状况等。第4个页page3是insert buffer的头部信息结构,记录了ibuf使用的段的信息。第5个页是ibuf的根节点页,因为ibuf本质上是一棵B+树。

Bitmap页中,只用4bits来记录一个页的信息,对于16KiB的页Bitmap的页结构如下:
MySQL insert buffer实现详解 - raolh - 枫叶的博客

记录一个页的信息的4bits的结构如下:
MySQL insert buffer实现详解 - raolh - 枫叶的博客

头两个bit用来记录页的空闲状态,由于只能表示0,1,2,3 所表示的空闲空间算法是:
if (bits == 3) { return(4 * UNIV_PAGE_SIZE /32); }
return(bits * UNIV_PAGE_SIZE / 32);

该算法表示的是空闲空间的下限值,目的是使缓存的insert操作不超过页的空闲空间。并且算法最大只能表示2k的空间,所以如果一个页缓存的Insert操作要超过2k,那么这个页将被读入到bp中。


第3个bit表示该页是否有Insert缓存在ibuf中,第4个bit表示该页是否是ibuf的页。


ibuf header页只记录了使用的段的管理信息inode,当ibuf从段中分配新的页时需要到这个页。


ibuf root页与一般Index root页的区别是:page header中没有记录段的信息,而是记录了一个free页链表的信息。ibuf分配新的空间时,先从段中分配空闲页并加入到free页链表中,再从free页链表中取出一个页使用。ibuf root页的结构如下:

MySQL insert buffer实现详解 - raolh - 枫叶的博客
 

ibuf的记录结构


ibuf中缓存的是二级索引页的记录,所以存放在ibuf中的记录包含了缓存记录的信息,格式如下:

MySQL insert buffer实现详解 - raolh - 枫叶的博客

ibuf中的记录比原记录多了两个字段:page_no,记录欲插入的二级index页的页号;fields_type,原记录各个字段的类型结构数组,增加该字段的目的是计算原记录字段为null时的字段长度。

ibuf的逻辑结构

管理ibuf的逻辑结构是:

struct ibuf_data_struct

{

ulint  space;                         //ibuf所属表空间的id,由于mysql 4.1之后只有系统表空间中有ibuf,所以该值为0

ulint  seg_size;                   //ibuf的段空间的大小,以页为单位,是ibuf的空间总大小。seg_size=size+free_list_len

ulint  size;                           //ibuf的大小,既ibuf整个B+树已经使用的页的个数

ibool  empty;                     //ibuf B+树中是否有记录

ulint  free_list_len;            //free页链表的长度,既空闲空间的大小

ulint  height;                        //B+树的高度

dict_index_t*  index;       /* insert buffer index */ 

UT_LIST_NODE_T(ibuf_data_tdata_list;

ulint  n_inserts;                    //insert的次数

ulint  n_merges;                 //merge的次数

ulint  n_merged_recs;       /* number of records merged */

};


ibuf的merge


 merge的过程是,当一个二级索引页被读入到BP中时,将ibuf中的记录插回到二级index页中。
MySQL insert buffer实现详解 - raolh - 枫叶的博客

由二级index页的page_no获得IBUF_BITMAP_BUFFERED位置信息的算法是:
Bitmap_page_no = page_no / 16k
Bitmap_page_bit_offset = 38*8 + (page_no % 16k)*4
可以使用index页的page_no直接在ibuf上查找,以获得该页的insert 记录。

实现merge功能的函数是 ibuf_merge_or_delete_for_page,该函数会在一个页被读入到BP后调用,此时的功能就是做merge。该函数还会在一个页被初始化的时候调用,此时的功能只从ibuf中删除相关的记录而不做插入记录的操作。

ibuf的contract

contract的过程是给ibuf瘦身,减小ibuf的大小。一次contract的过程是:
1,随机选择ibuf的一个叶子页first_page;
2,选举first_page相邻的若干个页;
3,将选举出来的页读到BP中。

InnoDB中定义了一次contract的页的个数是8,所以选举first_page相邻页的算法最多只会选举出8个页,且优先选举出first_page左边的页出来。过程如下:
MySQL insert buffer实现详解 - raolh - 枫叶的博客

有两个地方会调用contract过程,:1,向ibuf悲观插入一条记录时(既插入操作引起了页的分裂),此称为被动contract;2,在系统的主线程中每隔若干秒会做contract,次称为主动contract。
 
 ibuf的insert
   
ibuf的插入分乐观观插入和悲观插入,悲观插入会引起页的分裂,而乐观插入则不会。向ibuf中插入记录首先会进行乐观插入,失败后会进行悲观插入,乐观插入的过程如下:
MySQL insert buffer实现详解 - raolh - 枫叶的博客

悲观插入的过程如下:
MySQL insert buffer实现详解 - raolh - 枫叶的博客

实现ibuf插入过程的函数是ibuf_insert,它会在函数btr_cur_search_to_nth_level 调用,触发条件是:
      ... ...

if (page == NULL)

{

    if (  ibuf_should_try( … )  &&  ibuf_insert( … )  )

... ...

 既,当一个页在BP中没有找到时,会将insert缓存到ibuf中。ibuf_should_try的功能是判断该页是否是非唯一的二级index页,只有在这种情况下才会进行ibuf的Insert缓存。
  评论这张
 
阅读(1280)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017