A-A+

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

2022年02月04日数据库暂无评论阅读 726 次

InnoDB的存储层次

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

数据格式

Row

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

Page

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

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

/** 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部分：

Fil Header

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

Page Header

代码参见 include/page0page.h

Extent

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

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

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

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

XDES Page的格式：

Segment

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

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

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

Inode entry信息包括：

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

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）。

数据组织大图

源码

Tablespace

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中的内容。

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

/* 入参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

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

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

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、使逻辑相邻的数据，在物理上也尽可能相邻。