准备

MySQL版本: 8.0

从用户的角度看 InnoDB 根据不同的功能将文件分为 Redo Log 文件(ib_logfile)，Undo Log 文件(undo_xxx)，系统表文件(ibdata)，临时表文件(ibtmp)，数据文件(.ibd)等等。当 MySQL 运行时，InnoDB 引擎内部同样需要在内存中维护这些文件，方便管理和读取，所以我们从内存中的文件管理和文件的物理结构两个方向来分析.

内存文件管理

在 InnoDB 中，表空间是基本的数据单元，比如系统表属于系统表空间(System tablespace)，Undo Log 属于(Undo Tablespaces). 由表空间来管理其文件和元信息.

Fil_system

在 InnoDB 的内存中维护了一个Fil_system的数据结构来缓存整个文件管理. Fil_system分为64个shard. 而每个shard管理多个Tablespace, 层级关系为: Fil_system->shard->Tablespace

innodb_fil_system

层级关系为: Fil_system -> shard -> tablespace

64个shard中，第1个即索引为0的shard属于系统表空间，最后一个shard即索引为63的shard为Redo Log的Tablespace, 而58-61是属于Undo Log的shard:

1
2
3
4
5
6
7
8
9
10
11
/** Maximum number of shards supported. */
static const size_t MAX_SHARDS = 64;

/** The redo log is in its own shard. */
static const size_t REDO_SHARD = MAX_SHARDS - 1;	/* Redo Log 的 shard */

/** Number of undo shards to reserve. */
static const size_t UNDO_SHARDS = 4;			/* 分配 4 个 shard 给 Undo Log */

/** The UNDO logs have their own shards (4). */
static const size_t UNDO_SHARDS_START = REDO_SHARD - (UNDO_SHARDS + 1);

在shard中的每一个Tablespace都有唯一的ID，通过shard_by_id()函数寻找所属的shard：

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
Fil_shard *shard_by_id(space_id_t space_id) const
      MY_ATTRIBUTE((warn_unused_result)) {
#ifndef UNIV_HOTBACKUP
    if (space_id == dict_sys_t::s_log_space_first_id) {
      /* 假如 Tablespace ID 为 dict_sys_t::s_log_space_first_id, 即返回 m_shards[63]. */
      return (m_shards[REDO_SHARD]);

    } else if (fsp_is_undo_tablespace(space_id)) {
      /* 假如 Tablespace ID 为
         dict_sys_t::s_min_undo_space_id 与
      	 dict_sys_t::s_max_undo_space_id 之间则返回 m_shards[UNDO_SHARDS_START + limit]. */
      const size_t limit = space_id % UNDO_SHARDS;

      return (m_shards[UNDO_SHARDS_START + limit]);
    }

    ut_ad(m_shards.size() == MAX_SHARDS);

    /* 其余的 Tablespace 根据 ID 求模获取对应的 shard */
    return (m_shards[space_id % UNDO_SHARDS_START]);
#else  /* !UNIV_HOTBACKUP */
    ut_ad(m_shards.size() == 1);

    return (m_shards[0]);
#endif /* !UNIV_HOTBACKUP */
  }

每一个Tablespce都对应一个或多个物理文件fil_node_t。

文件管理的数据结构

InnoDB将文件分为Log文件(Redo Log、Undo Log)、系统表空间文件ibdata、临时表空间文件、用户表空间。其中数据文件(.ibd)都由Pages->Extents-> Segments-> Tablespaces多级组成。Tablespace是由多个Segment组成，而每个Segment又由多个Extent组成，每个Extent由多个Page组成，Extent中Page的数量由其Page的大小决定, 对应关系如下:

1
2
3
4
5
6
7
8
9
/** File space extent size in pages
page size | file space extent size
----------+-----------------------
   4 KiB  | 256 pages = 1 MiB
   8 KiB  | 128 pages = 1 MiB
  16 KiB  |  64 pages = 1 MiB
  32 KiB  |  64 pages = 2 MiB
  64 KiB  |  64 pages = 4 MiB
*/

tablespace_layout

Page

每个Tablespace内部都是由Page组成，每个Page都具有相同的大小，默认的UNIV_PAGE_SIZE是16KB，即每个Extent的大小为1M, Page的大小可以由参数--innodb-page-size配置。下图是Page的布局图:

需要注意的是Extent是一个物理概念，对应的是物理文件上1MB空间大小，而Segment是一个逻辑概念，便于整个B tree索引的管理.

innodb_page_layout

  • FIL_PAGE_OFFSET就是Page的 Number 号, 第 0 页即为 0
  • FIL_PAGE_TYPE是Page的类型，比如Tablespace的第 0 页即为FIL_PAGE_TYPE_FSP_HDR类型
  • 在第0页中FIL_PAGE_PREV的值被替换为FIL_PAGE_SRV_VERSION即MySQL的版本, 比如80013
  • 在第0页中FIL_PAGE_NEXT的值被替换为FIL_PAGE_SPACE_VERSION即Tablespace的ID, 比如临时表就是0xFFFFFFFD
  • FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID为Page所在的Tablespace的space_id

Tablespace

Tablespace由多个Page组成，为了管理这些Page也需要一些Page存放元信息，所以Page 0、Page 1、Page 2和Page 3包含了这些元信息数据:

We initially let it be 4 pages:

  • page 0 is the fsp header and an extent descriptor page,
  • page 1 is an ibuf bitmap page,
  • page 2 is the first inode page,
  • page 3 will contain the root of the clustered index of the
    first table we create here. */

我们这里介绍关于文件管理的Page 0和Page 2. Page 0作为Tablespace的Header其中保存关于Extent的信息，而Page 2作为管理Segment的元信息页面.

Page 0

Page 0包括Tablespace的头部、Extents和Segments的链表管理，下图的Page 0的布局，其中蓝色的字段表示文件链表:

innodb_space_page_0

图中蓝色字段表示数据类型为文件链表

  • FSP_SPACE_ID表示该Tablespace的ID
  • FSP_SIZE表示目前Tablespace有多少个Page
  • FSP_FREE_LIMIT表示目前在空闲的Extent上最小的尚未被初始化的Page的Page Number
  • FSP_SPACE_FLAGS表示Tablespace的标志位
  • FSP_FRAG_N_USED表示FSP_FREE_FRAG中已经使用的Page数量
  • FSP_FREE表示所有的Page均为空闲的Extent
  • FSP_FREE_FRAG表示Extent中尚有Page未被使用
  • FSP_FULL_FRAG表示Extent的所有的Page均已被使用
  • FSP_SEG_ID表示下一个未被使用的Segment ID
  • FSP_SEG_INODES_FULL表示Segment Page的所有的Inode均已被使用
  • FSP_SEG_INODES_FREE表示Segment Page存在空闲的Inode

Extent Descriptor

Page 0中的字段XDES Entry即为Extent的描述符, FSP_HEADER后面紧跟256个EXTENT DESCRIPTOR用于记录Extent的描述页，大小为 40 Bytes. 其中的状态标志有6种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
enum xdes_state_t {

  /** extent descriptor is not initialized */
  XDES_NOT_INITED = 0,

  /** extent is in free list of space */
  XDES_FREE = 1,

  /** extent is in free fragment list of space */
  XDES_FREE_FRAG = 2,

  /** extent is in full fragment list of space */
  XDES_FULL_FRAG = 3,

  /** extent belongs to a segment */
  XDES_FSEG = 4,

  /** fragment extent leased to segment */
  XDES_FSEG_FRAG = 5
};

其中字段XDES_BITMAP为16Bytes即 16 * 8bits，其中一个Page占用两个bit用来表示Page是否被占用。

记录EXTENT DESCRIPTOR信息的Page所在的Extent会被直接插入FSP_FREE_FRAG，因为已经存在一个被使用了的Page。而一个EXTENT DESCRIPTOR的Page只记录了256个Extent，所以假如Page的大小是16KB即每隔256 * 64 = 16384 页 就需要申请一个带有EXTENT DESCRIPTOR的Page，后面新申请分配的Extent依然与其他的Extent文件链表连接。

1
bool init_xdes = (ut_2pow_remainder(i, page_size.physical()) == 0);

文件链表

例如FSP_FREE是一个文件链表，有一个BaseNode包含整个链表元素长度，并且指向第一个元素First和最后一个元素Last。 除了BaseNode多了一个4 bytes的长度标记，其他的元素都具有相同的数据结构，6 bytes分为两部分: 4 bytes的Page Number, 2 bytes的Page在整个Tablespace的偏移，其组织形式如下图：

file_list

Page 2

Tablespace的第三个Page是关于Segment信息的，类型为FIL_PAGE_INODE，其中一个Inode可以理解为管理一个Segment元信息单元:

innodb_space_page_2

在一个Inode即一个Segment中:

  • FSEG_ID表示Segment的ID
  • FSEG_NOT_FULL_N_USED表示Segment中被使用的Page数量
  • FSEG_FREE表示所有Page均为空闲的Extent
  • FSEG_NOT_FULL表示部分Page空闲的Extent
  • FSEG_FULL表示所有Page均被使用的Extent
  • FSEG_MAGIC_N表示一个magic numbe用于Debug
  • Slot表示一个Page

数据页(Index)

在InnoDB中，数据即索引，索引即数据，所以这里的数据页一般也指索引页，非压缩页的结构如下:

innodb_index_page

  • PAGE_N_DIR_SLOTS表示数据页中页目录的数量
  • PAGE_HEAP_TOP指向数据页中的空闲空间的起始地址
  • PAGE_N_HEAP表示目前存放的 Record 数量
  • PAGE_FREE表示删除的 Record 的链表
  • PAGE_GARBAGE表示被删除的 Record 所占的 Bytes 大小
  • PAGE_LAST_INSERT指向最近一次插入的 Record
  • PAGE_DIRECTION表示最后一个记录插入的方向
  • PAGE_N_DIRECTION表示连续同一个方向插入的 Record 数量
  • PAGE_N_RECS表示当前数据页中用户的 Record 数量
  • PAGE_MAX_TRX_ID表示当前数据页中最大的 Transaction ID
  • PAGE_LEVEL表示当前数据页在整个索引的 B+ 树中的层级
  • PAGE_INDEX_ID表示当前数据页所属的索引 ID
  • PAGE_BTR_SEG_LEAF表示 Leaf 节点对应的 Segment Header 信息
  • PAGE_BTR_SEG_TOP表示非 Leaf 节点对应的 Segment Header 信息
  • PAGE_OLD_INFIMUM表示当前数据页中最大的 Record
  • PAGE_OLD_SUPREMUM表示当前数据页中最小的 Record

Infimum Record和Supremum Record分别代表该数据页中逻辑最大和最小的值.

数据页的页目录

Page Directory(页目录)占用两个字节，存放了 Record 在 Page 的相对偏移 weizhi, 页目录是一个稀疏目录(Sparse Directory), 即一个页目录中有多个 Record, 上下限分别为 4 和 8.在整个数据页中，会存在多个 Record 作为 Slot，即管理一个页目录. 其中 Record 中的REC_NEW_N_OWNED字段记录该页目录的 Record 数量.

数据页 Record 的插入(page_cur_rec_insert)

  • 获取Record的长度
  • 从PAGE_FREE链表取下最近一个被删除的Record, 判断大小是否合适，假如待插入的Record超过了被删除的Record的大小, 则从Page的PAGE_HEAP_TOP指向的位置分配空间
  • 将待插入的Record拷贝至对应的存储位置
  • 更新Record的前序后置Record
  • 设置Record的REC_OLD_N_OWNED和REC_OLD_HEAP_NO标志位
  • 更新Page Header的PAGE_DIRECTION,PAGE_N_DIRECTION,PAGE_LAST_INSERT标志位
  • 更新数据页的页目录(Page Directory), 即对应的REC_NEW_N_OWNED自增1，假如超过了PAGE_DIR_SLOT_MAX_N_OWNED即8个Record, 数据目录需要分裂成两个
  • 写Redo Log持久化插入操作

数据页 Record 的删除

  • 写 Redo Log 持久化
  • 将待删除的 Record 从对应的前序后置 Record 链表中删除
  • 更新页目录 directory slot 对应的信息
  • 将待删除的 Record 插入PAGE_FREE链表
  • 假如 directory slot 中 Record 的数量小于PAGE_DIR_SLOT_MIN_N_OWNED, 则平衡 Page Directory

数据页 Record 的查找

  • 调用page_cur_search_with_match()对指定 Page 的 Page Directory (页目录)进行二分查找定位 Record 周边的两个 slot
  • 从low_rec开始线性迭代直到up_rec，查找符合条件的 Record.

物理文件管理

为了理解上半部分介绍的多种数据结构和不同Page的格式的真正用途，我们需要分析 InnoDB 是如何利用这些数据结构来完成文件的管理。

物理文件创建

创建Tablespace的同时通过os_file_create()创建物理文件, 一个Fil_shard管理多个 Tablespace, 一个 Tablesapce 根据类型不同会创建一个或者多个文件. 例如数据Tablespace仅有一个物理文件，而系统表有多个文件.

Tablespace 创建

  • 对于非临时表的数据Tablesapce，初始化大小为 FIL_IBD_FILE_INITIAL_SIZE(7) 个Page, 而对于临时Tablspace， 初始化大小为 FIL_IBT_FILE_INITIAL_SIZE(5) 个Page

  • fil_create_tablespace()初始化tablespace的相关元信息包括m_flags等等

  • 创建ibd文件并更新至内存文件管理Fil_system，初始化Page 0的FIL_Header

  • 初始化Page 0的FSP_Header 字段和EXTENT DESCRIPTOR文件链表，更新EXTENT DESCRIPTOR列表中的第一个Extent描述符

Tablespace的创建流程初始化Page 0，完成了Tablespace中前256个Extent Descriptor的初始化创建。在用户创建的Tablespace过程中，对于系统表的新建，会调用btr_create()从而引入Segment的创建. 对于用户普通表, 会根据是否在建表时指定Primary Key选择不同的策略来创建索引(btr_create())从而引入Segment的创建(create_clustered_index_when_no_primary()/create_index()).

Segment 创建

  • 首先通过fsp_reserve_free_extents()为不同类型的 Tablespace 预留空间.

  • 寻找空闲的Page作为Inode的Page，初始化Inode的文件链表

  • 选中一个空闲的Inode并对其进行初始化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    seg_id = mach_read_from_8(space_header + FSP_SEG_ID);

    // 更新 Tablespace 的 Header 中 FSP_SEG_ID
    mlog_write_ull(space_header + FSP_SEG_ID, seg_id + 1, mtr);

    // 更新 Inode 的所属的 FSEG_ID 和 FSEG_NOT_FULL_N_USED
    mlog_write_ull(inode + FSEG_ID, seg_id, mtr);
    mlog_write_ulint(inode + FSEG_NOT_FULL_N_USED, 0, MLOG_4BYTES, mtr);

    // 初始化文件链表 FSEG_FREE、FSEG_NOT_FULL 和 FSEG_FULL
    flst_init(inode + FSEG_FREE, mtr);
    flst_init(inode + FSEG_NOT_FULL, mtr);
    flst_init(inode + FSEG_FULL, mtr);

    mlog_write_ulint(inode + FSEG_MAGIC_N, FSEG_MAGIC_N_VALUE, MLOG_4BYTES, mtr);
    for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
      // 初始化 Inode 的32个 Slot
      fseg_set_nth_frag_page_no(inode, i, FIL_NULL, mtr);
    }

  • 从选中的Inode中选取一个Extent并从中获取空闲的Page

    • 在B+树索引中，叶子节点的Page分裂过程中，需要申请一个新的Page，而新申请的Page为了与被分裂的Page物理相邻，所以新申请的Page会被预设一个hint_page_no，根据分裂方向决定:

      • 假如分裂的方向为FSP_DOWN:

        1
        2
        direction = FSP_DOWN;
        hint_page_no = page_no - 1;	// page_no为被分裂的Page的ID

      • 假如分裂的方向为FSP_UP:

        1
        2
        direction = FSP_UP;
        hint_page_no = page_no + 1;	// page_no为被分裂的Page的ID

    • 假如hint页所在的Extent属于该Segment并且hint页属于空闲XDES_FREE_BIT状态，直接获取该hint页。

    • 假如hint所在的Extent属于XDES_FREE状态、而Segment中使用的Page数量已经超过分配的Page数量的87.5% 并且Segment中使用的Page数量也超过了32：

      • 尝试为Segment分配一个Extent，将其加入该Segment的FSEG_FREE链表，获取hint页

    • 假如申请的用户为B+树分裂，而Segment中使用的Page数量已经超过分配的Page数量的87.5% 并且Segment中使用的Page数量也超过了32：

      • 尝试为Segment分配一个Extent，将其加入该Segment的FSEG_FREE链表
      • 假如B+树分裂方向为FSP_DOWN，返回Extent的最后一个Page

    • 否则返回Extent中第一个空闲的Page

    • 假如hint所在的Extent存在空闲的Page，直接获取该Extent中的一个空闲Page

    • 假如Segment中已经分配的Page数量大于使用的Page数量：

      • 尝试迭代FSEG_NOT_FULL和FSEG_FREE链表，取得一个存在空闲Page的Extent然后获取一个空闲Page

    • 假如Segment使用的Page数量小于32(FSEG_FRAG_LIMIT)：

      • 尝试直接为Segment分配一个Page，插入Segment自带的Slot

    • 上述情况都不满足的情况下，我们需要为该Segment申请一个新的Extent，之后再获取空闲的Page

Extent 创建

为Segment分配Extent时:

  • 通过Tablespace的Header检查是否存在空闲的Extent，假如存在，即从FSP_FREE链表移除，之后返回空闲的Extent
  • 否则需要新建Extent，最多创建4个Extent，并且每隔FSP_EXTENT_SIZE个Page就需要一个创建Extent descriptor的Page。存在Extent descriptor的Page需要加入Tablespace的FSP_FREE_FRAG链表，完全空闲的Extent加入FSP_FREE链表
  • Extent申请分配完成后，从FSP_FREE链表中移除一个Extent分配给Segment并插入FSEG_FREE链表。

参数解释

innodb_file_per_table

在MySQL5.6以上的版本新增了一个参数innodb_file_per_table, 默认创建的Table存储在系统表System Tablespace, 打开这个参数允许用户为每一个table创建单独的Tablespace:

1
2
mysql> SET GLOBAL innodb_file_per_table=1;
mysql> CREATE TABLE t2 (c1 INT PRIMARY KEY);

示例中的表t2会在所属的Database目录下拥有独立的表空间文件t2.ibd.

innodb_data_file_path

innodb_data_file_path配置系统表空间文件的名字，大小，属性等。例如:

1
2
[mysqld]
innodb_data_file_path=ibdata1:50M;ibdata2:12M:autoextend:max:500MB

示例配置两个系统表文件ibdata1和ibdata2, 大小分别是50M和12M, 其中ibdata2可以自动扩容，但大小限制为500M.