LoopJump's Blog

InnoDB源码解析-存储管理层次

2022-06-03

InnoDB的存储层次

总的数据粒度：Row - Page - Extent - Segment - Tablespace。

!http://loopjump.com/wp-content/uploads/2020/06/image-20200623151536735-1024x756.png

数据格式

Row

行内容主要就是各列的值，外加一些flag信息。

!http://loopjump.com/wp-content/uploads/2020/06/1648964879799-1024x273.jpg

Page

Page(页面)是固定大小的物理存储块。Page有多种用途，既可以存放一组行记录，也可以存放存储管理元数据。

具体地，page类型相关的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/** File page types (values of FIL_PAGE_TYPE) @{ */
#define FIL_PAGE_INDEX    17855 /*!< B-tree node */
#define FIL_PAGE_RTREE    17854 /*!< B-tree node */
#define FIL_PAGE_UNDO_LOG 2 /*!< Undo log page */
#define FIL_PAGE_INODE    3 /*!< Index node */
#define FIL_PAGE_IBUF_FREE_LIST 4 /*!< Insert buffer free list */
/* File page types introduced in MySQL/InnoDB 5.1.7 */
#define FIL_PAGE_TYPE_ALLOCATED 0 /*!< Freshly allocated page */
#define FIL_PAGE_IBUF_BITMAP  5 /*!< Insert buffer bitmap */
#define FIL_PAGE_TYPE_SYS 6 /*!< System page */
#define FIL_PAGE_TYPE_TRX_SYS 7 /*!< Transaction system data */
#define FIL_PAGE_TYPE_FSP_HDR 8 /*!< File space header */
#define FIL_PAGE_TYPE_XDES  9 /*!< Extent descriptor page */
#define FIL_PAGE_TYPE_BLOB  10  /*!< Uncompressed BLOB page */
#define FIL_PAGE_TYPE_ZBLOB 11  /*!< First compressed BLOB page */
#define FIL_PAGE_TYPE_ZBLOB2  12  /*!< Subsequent compressed BLOB page */
#define FIL_PAGE_TYPE_UNKNOWN 13  /*!< In old tablespaces, garbage in FIL_PAGE_TYPE is replaced with this value when flushing pages. */
#define FIL_PAGE_COMPRESSED 14  /*!< Compressed page */
#define FIL_PAGE_ENCRYPTED  15  /*!< Encrypted page */
#define FIL_PAGE_COMPRESSED_AND_ENCRYPTED 16  /*!< Compressed and Encrypted page */
#define FIL_PAGE_ENCRYPTED_RTREE 17 /*!< Encrypted R-tree page */

一个FIL_PAGE_INDEX页面包含7部分：

!http://loopjump.com/wp-content/uploads/2020/06/WX20220403-135236@2x-1024x479.png

Fil Header

Fil Header总计占38字节，代码参见 include/fil0fil.h

!http://loopjump.com/wp-content/uploads/2020/06/WX20220403-135428@2x-1024x455.png

Page Header

代码参见 include/page0page.h

!http://loopjump.com/wp-content/uploads/2020/06/WX20220403-135728@2x-1024x543.png

Extent

代码见 include/fsp0fsp.h “EXTENT DESCRIPTOR”一节

引入Extent的主要目的是批量分配一段连续的page，提升分配效率和数据局部性。

Extent Descriptor是描述Extent属性的元数据信息，占用40字节，主要包括：

!http://loopjump.com/wp-content/uploads/2020/06/WX20220403-135856@2x-1024x304.png

Extent Descriptor本身也要存放到页面上，这个页面叫XDES Page（类型为FIL_PAGE_TYPE_XDES），一个Extent Descriptor也称为Extent Entry。

XDES Page的格式：

!http://loopjump.com/wp-content/uploads/2020/06/xdes-280x300.jpg

Segment

Segment是Page和Extent的资源集合，Segment可以管理extent和一些零散的page（最多32个）。

InnoDB中的索引对应两个segment：一个管理叶子节点，一个管理非叶子节点。

代码中，一个segment用inode entry这个数据结构来描述，参见include/fsp0fsp.h中FILE SEGMENT INODE部分。

Inode entry信息包括：

!http://loopjump.com/wp-content/uploads/2020/06/1648966943828-1024x514.jpg

Segment元数据存放到类型为FIL_PAGE_INODE的页面上，页面内数据组织大致如下：

!http://loopjump.com/wp-content/uploads/2020/06/image-20200628111646218-276x300.png

FSEG_INODE_PAGE_NODE：该字段用于串inode page链表。

表空间 TableSpace

共享表空间和独立表空间

如果innodb_file_per_table配置为ON，则每个表都有自己的frm和ibd文件，也就是独立表空间。

共享表空间的优点：表空间自动管理，可以分成多个文件上存储。

共享表空间的缺点：不同表混合存储，删除操作可能导致大量空隙。

独立表空间的优点：存储方式清晰，故障恢复相对独立；跨库移动单表容易实现；空间回收更容易；删除操作更容易处理。

独立表空间的缺点：文件数量多，单表大小受限于操作系统单个文件大小。

FSP Header

源码参见 include/fsp0fsp.h 中 ‘SPACED HEADER’ 部分。

表空间第一个Page是FSP Header，其类型是FIL_PAGE_TYPE_FSP_HDR。它是表空间的root page，创建表空间时初始化（fsp_header_init）。

!http://loopjump.com/wp-content/uploads/2020/06/WX20220403-142425@2x-1024x588.png

数据组织大图

源码

Tablespace

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
DataFile主要描述tablespace的磁盘文件的信息。

class DataFile
{
  char* m_name;
  char* m_filepath;
  char* m_filename;
  os_file_create_t m_open_flags;
  ulint m_size;
  ulint m_order; // ordinal position of this datafile in the tablespace
  device_t m_type;
  ulint m_space_id;
  ulint m_flags;
  bool m_exists; // true if file already existed on startup
  byte* m_first_page_buf; // Buffer to hold first page
  byte* m_first_page; // Pointer to the first page held in the buffer above
  struct stat m_file_info;
  pfs_os_file_t m_handle;
};

class Tablespace
{
  std::vector<DataFile> m_files;
  char *m_name;
  ulint m_space_id;
  char *m_path;
  ulint m_flags;
};

dberr_t Tablespace::open_or_create(bool is_temp)
|-- file_space_t *space = NULL;
|-- ut_ad(!m_files.empty());
|-- for (auto it : m_files)
|---|-- if (it->m_exists)
|---|---|-- it->open_or_create();
|---|---|---|-- m_handle = os_file_create(innodb_data_file_key, m_filepath);
|---|-- it->close();
|---|-- if (it == m_files.begin())
|---|---|-- flags = fsp_flags_set_page_size(0, univ_page_size); // 将page_size设置到fsp的flag
|---|---|-- space = fil_space_create(m_name, m_space_id, flags, is_temp);
|---|-- fil_node_create(it->m_filepath, it->m_size, space);

fil_space_create(name, space_id, flags)
|-- mutex_enter(fil_system->mutex);
|-- space = fil_space_get_name(name); // 查fil_system->name_hash
|-- assert(space == nullptr); // assert not exist
|-- space = fil_space_get_by_id(id); // 查fil_system->spaces
|-- assert(space == nullptr); // assert not exist
|-- space = (fil_space_t*)malloc();
|-- space->id = id;
|-- space->name = name;
|-- UT_LIST_INIT(space->chain, &file_node_t::chain); // 初始化space->chain
|-- HASH_INSERT(fil_space_t, hash, fil_system->space, id, space);
|-- HASH_INSERT(fil_space_t, name_hash, fil_space->name_hash, name, space);
|-- mutex_exit(fil_system->mutex);

创建filespace

用户新建表时，InnoDB会创建一个 “表名.ibd” 文件，并初始化filespace中的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
dict_build_tablespace_for_table(dict_table_t *table)
|-- bool needs_file_per_table = DICT_TF2_FLAG_IS_SET(table, DICT_TF2_USE_FILE_PER_TABLE);
|-- if (needs_file_per_table) // 每张表创建一个新的tablespace
|---|-- space_id = dict_hdr_get_new_id(table);
|---|-- table->space = space_id;
|---|-- ulint fsp_flags = dict_tf_to_fsp_flags(table->is_tmep, table->is_encrypted, table->has_data_dir);
|---|-- fil_make_filepath(fsp_flags, table->xx...dir, IBD); // 根据fsp_flags确定创建ibd filepath
|---|-- // 这里会创建一个single-table tablespace，初始化是4个page。
|---|-- // page 0: fsp header + extent descriptor;
|---|-- // page 1: ibuf bitmap page;
|---|-- // page 2: first inode page;
|---|-- // page 3: 表的聚簇索引的root
|---|-- fil_ibd_create(space, name, filepath, fsp_flags, FIL_IBD_FILE_INITIAL_SIZE);
|---|---|-- os_create_file(filepath, name);
|---|---|-- os_file_set_size(filepath, file, size * UNIV_PAGE_SIZE);
|---|---|-- page = (byte*)malloc_aligned(UNIV_PAGE_SIZE);
|---|---|-- fsp_header_init_fields(page, space_id, flags);
|---|---|---|-- mach_write_to_4(FSP_HEADER_OFFSET + FSP_SPACE_ID + page, space_id);
|---|---|---|-- mach_write_to_4(FSP_HEADER_OFFSET + FSP_SPACE_FLAGS + page, flags);
|---|---|-- mach_write_to_4(page + FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID, space_id); // mach_write屏蔽大小端
|---|---|-- buf_flush_init_for_writing(page);
|---|---|-- os_file_write(page); // 将page刷到
|---|-- mtr_start(&mtr);
|---|-- mtr.set_named_space(table->space);
|---|-- fsp_header_init(table->space, FIL_IBD_FILE_INITIAL_SIZE, &mtr);
|---|-- mtr_commit(&mtr);
|-- else // 已经初始化过，设定下table的space_id即可
|---|-- if (DICT_TF_HAS_SHARED_SPACE(table->flags))
|---|---|-- ut_ad(table->space == fil_space_get_by_id(table->tablespace()));
|---|-- else if (dict_table_is_temporary(table))
|---|---|-- table->space = srv_tmp_space.space_id();
|---|-- else
|---|---|-- ut_ad(table->space == srv_sys_space.space_id());

分配Segment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 入参page，如果指定了page(!=0)，表示要需要把inode entry的地址记录到page所指定的位置，
如果不指定page(=0)，表示创建一个**独立**的segment，需要将inode entry的地址记录在segment的某个page中；*/
fseg_create_general(space_id,
                    ulint page,
                    ulint byte_offset,
                    mtr_t *mtr)
|-- buf_block_t *block = buf_page_get(page_id_t(space_id, page), page_size, RW_SX_LATH, mtr); // 指定了page，则取出。
|-- fseg_header_t *header = byte_offset + block->frame;
|-- type = FIL_PAGE_TYPE_TRX_SYS / FIL_PAGE_TYPE_SYS;
|-- space_header = fsp_get_space_header(space_id, page_size, mtr);
|---|-- block = buf_page_get(page_id_t(space_id, 0), page_size, RW_SX_LATCH, mtr);
|---|-- header = FSP_HEADER_OFFSET + block->frame;
|-- inode = fsp_alloc_seg_inode(space_header, mtr);
|-- seg_id = mach_read_from_8(space_header + FSP_SEG_ID);
|-- mlog_write_ull(inode + FSEG_ID, seg_id, mtr); // 将数据写到page，且log该变更到mtr
|-- mlog_write_ulint(inode + FSEG_NOT_FULL_N_USED, 0, MLOG_4BYTES, mtr);
|-- flst_init(inode + FSEG_FREE, mtr); // 初始化free list
|-- flst_init(inode + FSEG_NOT_FULL, mtr); // 初始化not_full list
|-- flst_init(inode + FSEG_FULL, mtr); // 初始化full list
|-- mlog_write_ulint(inode + FSEG_MAGIC_N, FSEG_MAGIC_N_VALUE, mtr);
|-- for (int i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) // 初始化该segment的FSEG_FRAG_ARR_N_SLOTS(=32)个独立page
|---|-- fseg_set_nth_frag_page_no(inode, i, FIL_NULL, mtr);
|-- if (page == 0) // 入参page=0，表示segment的位置写在自己的某个page上
|---|-- block = fseg_alloc_free_page_low(space_id, page_size, inode, mtr); // 分配一个page
|---|-- header = byte_offset + block->frame;
|---|-- mlog_write_ulint(block->frame + FIL_PAGE_TYPE, FIL_PAGE_TYPE_SYS, MLOG_2BYTES, mtr);
|-- mlog_write_ulint(header + FSEG_HDR_OFFSET, page_offset(inode), mtr);
|-- mlog_write_ulint(header + FSEG_HDR_PAGE_NO, page_get_page_no(page_align(inode), mtr);

分配Extent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fsp_alloc_free_extent(space_id, page_size, page_no_t hint, mtr_t *mtr)
|-- buf_block_t *desc_block = nullptr;
|-- fsp_header_t *header = fsp_get_space_header(space_id, page_size, mtr);
|-- xdes_t *descr = xdes_get_descriptor_with_space_hdr(header, space_id, mtr, &desc_block);
|-- fil_page_t *space = fil_space_get(space_id);
|-- fil_block_check_type(desc_block, FIL_PAGE_TYPE_XDES, mtr);
|-- if (descr && xdes_get_state(descr, mtr) == XDES_FREE)
|---|-- // ok, return this extent
|-- else
|---|-- first = fslt_get_first(header + FSP_FREE, mtr); // 取出FSP_FREE list第一个extent
|---|-- if (fil_addr_is_null(first)) // FSP_FREE没有空闲的extent
|---|---|-- fsp_fill_free_list(space, header, mtr); // 扩充空间******
|---|---|-- first = fslt_get_first(header + FSP_FREE, mtr); // 扩充完再取出FSP_FREE list第一个extent
|---|---|-- if (fil_addr_is_null(first)) // 扩展完还是没有空闲，返回失败
|---|---|-- desc = xdes_lst_get_desriptor(space_id, page_size, first, mtr); // 获取xdes的地址
|---|-- flst_remove(header + FSP_FREE, descr + XDES_FLST_NODE, mtr); // 更新FSP_FREE链表
|---|-- space->free_len--;
|-- return descr;

分配Page

page的分配分为两种途径： 1）从全局的fsp上分配一个page，直接从FSP_FREE_FRAG或者FSP_FREE链表中分配一个extent，然后从这个extent中分配一个page。具体使用的场景包括分配inode page和为segment中的frag array分配page。 2）从segment中分配一个page。这种分配方式包括1），当segment中的frag array被填满时，会首先将全局的fsp上的extent分配给segment，然后再从已经分配segment的extent中寻找满足的条件的并分配page。

其实分配方式2）是供外部使用(比如BTree)的，通过fseg_alloc_free_page_general(这个对外的接口调用。

从全局fsp上分配page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
buf_block_t *fsp_alloc_free_page(space_id, page_size, page_no_t hint, rwlatch, mtr)
|-- fsp_header_t *header = fsp_get_space_header(space_id);
|-- xdes_t *descr = xdes_get_descriptor_with_space_hdr(header, page_size, mtr); // hint对应的extent
|-- if (descr && xdes_get_state(descr) == XDES_FREE_FRAG)
|---|-- // ok, we can take this extent
|-- else // hint page对应的extent没有空闲，则从FSP_FREE_FRAG/FSP_FREE链表中寻找有空闲page的extent
|---|-- first = flst_get_first(header + FSP_FREE_FRAG, mtr);
|---|-- if (fil_addr_is_null(first)) // FSP_FREE_FRAG链上没有free extent
|---|---|-- descr = fsp_alloc_free_extent(space, page_size, hint, mtr);
|---|---|-- xdes_set_state(descr, XDES_FREE_FRAG, mtr);
|---|---|-- flst_add_last(header + FSP_FREE_FRAG, descr + XDES_FLST_NODE, mtr);
|---|-- else
|---|---|-- descr = xdes_lst_get_description(space, page_size, first, mtr);
|-- // 从descr中分配一个page
|-- free = xdes_find_bits(descr, XDES_FREE_BIT, mtr);
|-- page_no = xdes_get_offset(descr) + free;
|-- space_size = mach_read_from_4(header + FSP_SIZE);
|-- if (space_size <= page_no)
|---|-- fil_space_t *fspace = fil_space_get(space);
|---|-- if (!fsp_try_extend_data_file(space)) // no space to extend
|---|---|-- return nullptr;
|-- fsp_alloc_from_free_frag(header, descr, free, mtr); // 从descr中分配free位置的page
|-- buf_block_t *ret_page = fsp_page_create(page_id_t(space, page_no), page_size, rwlatch, mtr); // 初始化这个page
|-- return ret_page;

从segment上分配page

1
2
3
4
5
6
7
buf_block_t *fseg_alloc_free_page_general(fseg_header_t *seg_header, page_no_t hint, byte direction, mtr)
|-- spcace_id = page_get_space_id(seg_header); // 读取space_id
|-- space = mtr_x_lock_space(space_id, mtr); // 获取space对象
|-- fseg_inode_t *inode = fseg_inode_get(seg_header, space_id, page_size, mtr, &iblock); // 获取inode地址
|-- fil_block_check_type(iblock, FIL_PAGE_INODE, mtr); // assert page type
|-- block = fseg_alloc_free_page_low(space, page_size, inode, hint, direction, RW_X_LATCH, mtr); // 从seg中分配page

page分配策略

page的分配按照以下策略一次去尝试分配.

  • 情况1: 目标xdes(hint page所属的xdes)已经分配给当前segment，并且hint page处于空闲状态；
  • 情况2: 目标xdes是完全空闲状态，并且当前空间占用满足要求(已使用的page超过已经占用的page的7/8,并且已使用的page数大于segment的frag array size)。那么将目标xdes分配给当前segment(能进入这个分支暗含的条件目标xdes不属于当前segment)，并将hint page分配出来。
  • 情况3: 当direction不是FSP_NO_DIR(FSP_UP或FSP_DOWN, 这个条件用来限制是因为BTree分裂需要申请page，暂时先这样理解)，并且当前空间占用满足要求。那么从segment中分配一个free的extent(fseg_alloc_free_extent)，并分配extent中的第一个或者最后一个page，具体根据direction确定。
  • 情况4: 目标xdes已经属于给当前segment，并且处于未满的状态。那么从目标xdes中分配一个空闲的page
  • 情况5: 当前segment中有空闲的page。那么寻找一个空闲的page分配出去，寻找的顺序是首先查找FSEG_NOT_FULL链表，再查找FSEG_FREE链表。
  • 情况6: 当前使用的page数小于segment的frag array size。那么从table space中分配一个碎片page，并放在segment中相应的frag slot。
  • 情况7: 兜底的情况，分配一个extent(fseg_alloc_free_extent)。如果extent是free状态，那么分配其第一个page，如果extent是free frag状态，那么分配第一个空闲的page。

单独的去理解每一种情况并不能完整的理解整个分配策略，我们需要关注的是通过以上分配策略遵循那些原则，要达到那些效果？

原则 (优先级从高到低)： 1、优先填满segment的frag array。 2、尽量使用已经分配给segment的空间，并使空间使用趋近于已使用的空间超过已占用空间的7/8。 3、尽量分配hint page。

对照以上原则，我们对上述7种情况进行解读： 情况1暗含已经满足原则1(因为如果原则1没有满足，当前segment大概率不会有extent)，并且也满足原则2(从已经占用的空间上分配page)，当然很明显满足原则3。 情况2很明显是在瞒住原则1和原则2的前提下，去满足原则3。 情况3是在满足原则1和原则2，并且原则3已经确定无法满足的前提下，分配page …剩余几种情况供读者去理解，应该是很好对应的

效果 1、避免小表占用太多空间。 2、使实际占用空间接近实际需要的空间。 3、使逻辑相邻的数据，在物理上也尽可能相邻。

Tags: MySQL
← InnoDB源码解析-事务系统 InnoDB源码解析-基础数据结构 →

扫描二维码，分享此文章