MySQL内核:innodb动态数组内部实现

2016-02-19 19:51 13 1 收藏

下面,图老师小编带您去了解一下MySQL内核:innodb动态数组内部实现,生活就是不断的发现新事物,get新技能~

【 tulaoshi.com - 编程语言 】

  动态数组涉及的文件是innodb存储引擎的三个文件:dyn0dyn.h、dyn0dyn.ic以及dyn0dyn.c。

(本文来源于图老师网站,更多请访问http://www.tulaoshi.com/bianchengyuyan/)

  这是一个基本的组件功能,是作为一个动态的虚拟线性数组。数组的基本元素是byte。动态数组dyn主要用来存放mtr的锁定信息以及log。Dyn在实现上,如果block需要分裂节点,则会使用一个内存堆。每个blok块存储数据的数据字段的长度是固定的(默认值是512),但是不一定会完全用完。假设需要存储的数据项的尺寸大于数据块时,该数据项被分拆,这种情况主要用于log的缓冲。

  2. 数据结构

  typedef struct dyn_block_struct  dyn_block_t;
typedef dyn_block_t     dyn_array_t;
#defineDYN_ARRAY_DATA_SIZE  512
  struct dyn_block_struct{
mem_heap_t*  heap;
ulint    used;
byte    data[DYN_ARRAY_DATA_SIZE];
UT_LIST_BASE_NODE_T(dyn_block_t)  base;
UT_LIST_NODE_T(dyn_block_t)     list;
#ifdef UNIV_DEBUG
ulint    buf_end;
ulint    magic_n;
#endif
};
  //下面两个是公共宏定义,见ut0lst.h
#define UT_LIST_BASE_NODE_T(TYPE)
struct {
ulintcount;/* count of nodes in list */
TYPE *start;/* pointer to list start, NULL if empty */
TYPE *end;/* pointer to list end, NULL if empty */
}
  #define UT_LIST_NODE_T(TYPE)
struct {
TYPE *prev;/* pointer to the previous node,
 NULL if start of list */
TYPE *next;/* pointer to next node, NULL if end of list */
}

  字段解释:

  1) heap

  从字面上理解,heap是内存堆的意思。从上面的结构体中,我们可以看出,dyn_array_t就是dyn_block_struct。这个结构体里面的字段date用来存放数据,used显示已经使用的字节数量,假设这时候还要存储一个大小为长度为x的数据,这时候data里面已经存储不了,所以就需要再分配一个新的block节点。那么分配结构所需要的内存从哪里来了,就从第一个节点里面的heap里面分配。

  这里面,我们还需要主意一点。虽然数据结构用的是同一个dyn_block_struct,但是我们称第一个节点为arr,表明这个是动态数据的头节点。其它的节点,我们称为block节点。

  我们这里面先来看看,刚开始创立dyn的函数是怎么实现的:

  UNIV_INLINE
dyn_array_t*
dyn_array_create(
/*=============*/
  /* out: initialized dyn array */
dyn_array_t*arr)/* in: pointer to a memory buffer of
  size sizeof(dyn_array_t) */
{
ut_ad(arr);
ut_ad(DYN_ARRAY_DATA_SIZE DYN_BLOCK_FULL_FLAG);
  arr-heap = NULL;
arr-used = 0;
  #ifdef UNIV_DEBUG
arr-buf_end = 0;
arr-magic_n = DYN_BLOCK_MAGIC_N;
#endif
return(arr);
}

  其中的ud_ad是属于红判断,相当于assert。这个我们暂时不表。这个函数是在mtr创建的时候来调用的,在调用的时候已经分配了arr指针。

  在dyn_array_create函数中,系统将heap字段设置为NULL,Used设置为0。Buf_end和magic_n是调试的时候使用的,每个结构体定义都会唯一的对应一个magic_n值。这样在调试的时候,就可以快速进行问题的跟踪。

  下面一个问题是,既然heap在起初的设置为NULL,那么什么时候分配给它值?是第一次分配block成员的时候?还是每次分配block成员的时候?

  我们这里暂不分析如何插入,我们先看看,当dyn数组已经数据不够用的时候,我们怎么给这个arr增加一个新的block。代码如下:

  dyn_block_t*
dyn_array_add_block(
/*================*/
  /* out: created block */
dyn_array_t*arr)/* in: dyn array */
{
mem_heap_t*heap;
dyn_block_t*block;
  ut_ad(arr);
ut_ad(arr-magic_n == DYN_BLOCK_MAGIC_N);
  if (arr-heap == NULL) {
 UT_LIST_INIT(arr-base);
 UT_LIST_ADD_FIRST(list, arr-base, arr);
  arr-heap = mem_heap_create(sizeof(dyn_block_t));
}
  block = dyn_array_get_last_block(arr);
block-used = block-used | DYN_BLOCK_FULL_FLAG;
  heap = arr-heap;
  block = mem_heap_alloc(heap, sizeof(dyn_block_t));
  block-used = 0;
  UT_LIST_ADD_LAST(list, arr-base, block);
  return(block);
}

  代码中,我们可以看出,第一次增加block的时候,因为“arr-heap == NULL”条件为真,就会创建一个heap堆,在以后的再增加block时,就会使用的该堆直接分配。所以,我们可以得知,对于dyn动态数组,只有首节点的heap才是有效的。

  好,那我们通过图形来看下,增加新节点之后的图形变化。

  图1表示的是只有一个节点时的情况,当节点分裂时的变化,见图2。

  通过图2,并集合前面的代码,我们可以发现,从第一个节点,变为两个节点的时候,首节点先把自己挂到base链表中,并分配一个新的节点,挂在base的最后一个节点。链表中的节点通过list进行互连。同样,如果还需要再增加一个节点,那么就在base链表的结尾再增加一个。因为是新增节点,所以设置该节点的used值为0。

  我们在关注一下这一行代码:

  block-used = block-used | DYN_BLOCK_FULL_FLAG;

  从这一行代码,我们可以猜想一下该行代码的含义:

  a) FULL表明该节点已经完全使用完,不可以再使用其中的空间。所以,链表只有最后一个节点才是可以使用的。每增加一个节点,总要设置前面一个节点的DYN_BLOCK_FULL_FLAG。

  b) 每个块,data数组的预设值是DYN_ARRAY_DATA_SIZE(值为512),

  #define DYN_BLOCK_FULL_FLAG 0x1000000UL

  所以,use的值小于等于512,那么该节点为尾节点。因为非尾节点的值肯定大于512,它与DYN_BLOCK_FULL_FLAG进行了或操作。

  2)used

  used表示data[DYN_ARRAY_DATA_SIZE]字段中已经使用的字节的数量,假设需要申请len字节的长度,在使用之前需要判断的是,尾 block中的可用空间是否够用。也就是判断判断下used+len是否满足used+len= DYN_ARRAY_DATA_SIZE,如果满足就可以放进该block,并将已使用的字节数used加上len。

  如果,该block空间不够,那么就会申请一个新的block,这里我们就可以明白了,为什么需要满足len的长度小于等于DYN_ARRAY_DATA_SIZE。

  好,我们下面先看下分配空间的函数。

  /*************************************************************************
Makes room on top of a dyn array and returns a pointer to the added element.
The caller must copy the element to the pointer returned. */
UNIV_INLINE
void*
dyn_array_push(
/*===========*/
  /* out: pointer to the element */
dyn_array_t*arr,/* in: dynamic array */
ulint size)/* in: size in bytes of the element */
{
dyn_block_t*block;
ulint used;
  ut_ad(arr);
ut_ad(arr-magic_n == DYN_BLOCK_MAGIC_N);
ut_ad(size = DYN_ARRAY_DATA_SIZE);
ut_ad(size);
block = arr;
used = block-used;
  if (used + size DYN_ARRAY_DATA_SIZE) {
 /* Get the last array block */
 
 block = dyn_array_get_last_block(arr);
 used = block-used;
  if (used + size DYN_ARRAY_DATA_SIZE) {
 block = dyn_array_add_block(arr);
 used = block-used;
 }
}
  block-used = used + size;
ut_ad(block-used = DYN_ARRAY_DATA_SIZE);
  return((block-data) + used);
}

  在这里面,我们要关注一下:

  block=arr;
  used=block-used;

  首先得到arr的首节点,在前面的内容中,我们描述过,在只有一个节点的时候(参考图1),arr本身就是block,如果是多个节点,这个代码相当于获得的是链表的首节点。

  那么如果是只有一个节点,那么很容易理解。假设链表是多个节点,这里面的used肯定是大于DYN_ARRAY_DATA_SIZE。因为每次生成一个block,就会调用dyn_array_add_block函数,在该函数中,会将前一个block的used进行置位操作。

  block-used = block-used | DYN_BLOCK_FULL_FLAG;

  所以,当arr存在多个block的时候,首节点的条件“used + size DYN_ARRAY_DATA_SIZE”必为真。这时候,我们就去获取尾节点。

  block = dyn_array_get_last_block(arr);
used = block-used;
  if (used + size DYN_ARRAY_DATA_SIZE) {
 block = dyn_array_add_block(arr);
 used = block-used;
}

  尾节点的used肯定没有进行过置位操作。然后判断是否需要新增block节点。

  回过头来,函数dyn_array_push的返回值,是一个指针,指向新增加元素的指针,然后用户对该指针进行操作赋值。我们来看下,系统中的一个使用实例。

  /*******************************************************
Pushes an object to an mtr memo stack. */
UNIV_INLINE
void
mtr_memo_push(
/*==========*/
mtr_t*mtr,/* in: mtr */
void*object,/* in: object */
ulinttype)/* in: object type: MTR_MEMO_S_LOCK, ... */
{
dyn_array_t* memo;
mtr_memo_slot_t*slot;
  ut_ad(object);
ut_ad(type = MTR_MEMO_PAGE_S_FIX);
ut_ad(type = MTR_MEMO_X_LOCK);
ut_ad(mtr);
ut_ad(mtr-magic_n == MTR_MAGIC_N);
  memo = &(mtr-memo);
  //分配大小为sizeof(mtr_memo_slot_t)的动态数组空间
slot = dyn_array_push(memo, sizeof(mtr_memo_slot_t));
  slot-object = object; //对返回的指针进行操作
slot-type = type;   //对返回的指针进行操作
}

  通过上文的描述,我们可以使用dyn进行操作。分配一个元素,然后进行赋值。那么我们再思考下,有没有优化的可能?

(本文来源于图老师网站,更多请访问http://www.tulaoshi.com/bianchengyuyan/)

来源:http://www.tulaoshi.com/n/20160219/1622026.html

延伸阅读
最近,在项目开发过程中,碰到了数据库死锁问题,在解决问题的过程中,笔者对MySQL InnoDB引擎锁机制的理解逐步加深。 案例如下: 在使用Show innodb status检查引擎状态时,发现了死锁问题: *** (1) TRANSACTION: TRANSACTION 0 677833455, ACTIVE 0 sec, process no 11393, OS thread id 278546 starting index rea...
MySQL数据库分二种类型,一种是传统的数据表格式,一种是支持事务处理的数据表格式(InnoDB,BDB,其中以InnoDB为主),下面我介绍一下关于MySQL事务处理数据库的安装及使用方法你先要去下载一下Mysql max版的安装程序,下载地址:www.mysql.com 按常规的方法进行安装 安装完成后,启动mysqlinWinMySQLadmin 再退出 运行 mysqlinmydqld-nt --re...
功能描述:用指定分隔符切割输入的字符串,返回一维数组,每个数组元素为一个子串。 源代码: CREATE OR REPLACE TYPE ty_str_split IS TABLE OF VARCHAR2 (4000); CREATE OR REPLACE FUNCTION fn_split (p_str IN VARCHAR2, p_delimiter IN VARCHAR2)   RETURN ty_str_split IS   j INT := 0;   i INT := 1;   len INT...
标签: 服务器
Linux内核驱动fsync机制实现图解   在Linux内核中的IO模型基本分为4类: 1、同步阻塞I/O 2、同步非阻塞I/O 3、异步阻塞I/O 4、异步非阻塞I/O 同步:应用显式地通过函数访问数据,在此函数返回时就会得到结果(成功或失败)。 异步:应用会显示地通过函数提出访问或关注申请。数据到达时,硬件和驱动会通...
下面写一个给大家做参考啊 代码如下: create procedure sp_find(pfind varchar(500) BEGIN DECLAR msql varchar(2000); SET @MyQuery=Concat('select * from 表 where ',pfind); PREPARE msql from @MyQuery; EXECUTE msql; END 注意一点的就是MYSQL中有好多已经定义好的函数可以使用,比如上面的拼接函数Concat(),利用好这些函数会...

经验教程

44

收藏

38
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部