前言
之前介绍的月报 http://mysql.taobao.org/monthly/2017/05/01/ 中, 详细介绍了 InnoDB Buffer Pool 的实现细节, Buffer Pool 主要就是用来存储数据页的, 是数据页在内存中的动态存储方式, 而本文介绍一下数据页在磁盘上的静态存储方式以及相关的操作. 由于数据页的结构涉及 InnoDB 非常底层的代码, 因此各个版本的 MySQL 都可以参考. 相关代码主要集中在 page 目录下.
基础知识
数据库采用数据页的形式组织数据. MySQL 默认的非压缩数据页为 16KB. 在 ibd 中间中, 0-16KB 偏移量即为 0 号数据页, 16KB-32KB 的为 1 号数据页, 依次类推. 数据页的头尾除了一些元信息外, 还有 Checksum 校验值, 这些校验值在写入磁盘前计算得到, 当从磁盘中读取时, 重新计算校验值并与数据页中存储的对比, 如果发现不同, 则会导致 MySQL crash. 遇到这种情况, 往往需要从备份集中恢复数据, 如果备份不可用, 只能使用
innodb_force_recovery
强行启动, 然后尽可能多的导出数据. 这篇月报 http://mysql.taobao.org/monthly/2017/11/01/ 中介绍了一种从物理文件中恢复数据的方法, 在走投无路的情况下可以使用.
数据页格式
严格来讲, InnoDB 的数据页有很多种, 比如, 索引页, Undo 页, Inode 页, 系统页, BloB 页等, 一共有 10 多种. 本文主要介绍最常见的索引页. 下文中, 没有特殊说明, 数据页都指索引页.
数据页包括七个部分, 数据页文件头, 数据页头, 最大最小记录, 用户记录, 空闲空间, 数据目录, 数据页尾部.
简单的来说, 数据页分两部分, 一部分存储数据记录, 按照记录的大小通过记录的指针连接起来. 另外一部分存储数据页的目录, 用来加速查找. 注意这个目录是稀疏的, 即不是所有的记录在目录都有索引, 平均是每隔六个记录才有一个目录. 数据记录部分是从低地址向高地址空间增长的, 而数据目录部分则相反. 这种数据结构可以保证比较高的插入删除和查找效率. 具体方法详见核心函数小节.
这篇月报 http://mysql.taobao.org/monthly/2017/11/01/ 的最后有一张图, 详细展示了数据页的结构, 读者可以先自行了解一下, 接下来, 本文解释一下各个部分的内容.
数据页文件头(Fil Header)
这个部分主要用来存储表空间相关的信息. 主要在 fil0fil.h 这个文件中.
FIL_PAGE_SPACE_OR_CHKSUM:
这个占用四字节, 主要用来存储数据页的 checksum. 注意, 计算校验值的时候, 并不是整个数据页都计算, 有几个地方是不计算进去的(
buf_calc_page_crc32
和
buf_calc_page_new_checksum
), 例如头尾存 checksum 的地方, 存 space_id 的地方(历史原因导致).Checksum 的计算方式详见
数据页 Corruption
这一小节.
FIL_PAGE_OFFSET: 这个就是对应数据页的 page number, 每个表空间从 0 开始, 即这个值乘以数据页的大小就可以得到数据页在文件中的起始偏移量. fio_io 函数读取以及写入数据页的时候依赖这个规则.
FIL_PAGE_PREV,FIL_PAGE_NEXT:
这两个是指针, 分别指向前一个数据页和后一个数据页. 注意, 这里的前后是指按照用户记录排序的先后顺序, 也是逻辑顺序. 因为在 InnoDB 数据页不断的分配和释放中, 会导致逻辑上连续的数据页在物理上不连续. 所以需要指针链接. 前后两个指针共同构建了一个双向链表.
FIL_PAGE_LSN: 当前数据页最新被修改的 lsn. 这个字段非常重要, InnoDB redolog 幂等的特性就依赖此字段. 在奔溃恢复应用日志阶段, 如果发现 redolog 的 lsn 小于等于这个值, 就不需要再次应用 redolog 了.
FIL_PAGE_TYPE: 当前页面是哪种类型的数据页. 包括, 索引页, Undo 页, Inode 页, 系统页, BloB 页等十几种.
FIL_PAGE_FILE_FLUSH_LSN:
ibdata 文件第一个数据页才有意义, 记录 ibdata 成功刷到磁盘的 lsn.
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID:
现在的版本就是用来存 spaceid 的.
数据页头(Page Header)
从存储的信息来看, 这部分才是存的数据页相关的元信息. 定义在 page0page.h 中.
PAGE_N_DIR_SLOTS: 这个表示数据页中数据目录的个数. 一个新建的空数据页, 就有 2 个目录, 分别指向最大记录和最小记录. 在一个非空的数据页中, 第一个目录永远指向最小记录, 最后一个目录永远指向最大记录. 当增加目录的时候, 会递增这个值.
PAGE_HEAP_TOP: 这个指向数据页中的空闲空间的起始地址. 大于这个地址的且小于数据目录的空间都是未分配的, 可以被后续使用. 但是由于空闲记录链表 (PAGE_FREE) 的存在, 小于这个地址的也可能被重用.
PAGE_N_HEAP: 目前已经被使用空间中的记录数量, 包括正常的记录和已经被删除 (放入 PAGE_FREE 中) 的记录. 从代码逻辑看, 这个值是不会减少的, 每次都空闲空间记录的时候就会增加. 在创建新的空页时候, 默认被置为 2, 即最大和最小记录. 此外, 最高位被用来标记这个数据页是否存了新格式的记录(compact 和 redundant).
PAGE_FREE: 删除记录的链表, 记录被删除, 会放到这个链表头上, 如果这个页上有记录要插入, 可以先从这里分配空间, 如果空间不够, 才从空闲地址 (PAGE_HEAP_TOP) 分配. 注意放到这个链表里面的, 都是被 purge 线程彻底删除的记录, delete-marked 的记录不在这里.
PAGE_GARBAGE: 所有已经被删除的记录占用空间的大小. 主要是为了方便计算空闲的空间.
PAGE_LAST_INSERT: 指向最近一个被插入的记录的. 主要用来加速后续插入操作.
PAGE_DIRECTION: 最后一个记录插入的方向, 目前就两个方向, 从左边插入和从右边插入. 也是用来加速后续插入操作.
PAGE_N_DIRECTION: 同一个方法插入的记录数. 主要用来加速后续插入操作.
PAGE_N_RECS: 当前数据页中用户的记录, 不包括最大和最小记录. 与 PAGE_N_HEAP 不同, 如果记录被标记为 delete-marked, 这个值就会递减.
PAGE_MAX_TRX_ID: 修改此数据页的当前最大事务 id.
PAGE_LEVEL: 这个页是否是 B 树中的叶子节点. 如果是 0, 就是叶子节点.
PAGE_INDEX_ID: 索引页的索引 id.
PAGE_BTR_SEG_LEAF,PAGE_BTR_SEG_TOP:
分别是叶子节点和非叶子节点的段头页地址.
最大最小记录(Infimum and Supremum Records)
最大记录是这个数据页中逻辑上最大的记录, 所有用户的记录都小于它. 最小记录是数据页上最小的记录, 所有用户记录都大于它. 他们在数据页被创建的时候创建, 而且不能被删除. 引入他们主要是方便页内操作.
用户记录(User Records)
用户所有插入的记录都存放在这里, 默认情况下记录跟记录之间没有间隙, 但是如果重用了已删除记录的空间, 就会导致空间碎片. 每个记录都有指向下一个记录的指针, 但是没有指向上一个记录的指针. 记录按照主键顺序排序. 即, 用户可以从数据页最小记录开始遍历, 直到最大的记录, 这包括了所有正常的记录和所有被 delete-marked 记录, 但是不会访问到被删除的记录(PAGE_FREE).
空闲空间(Free Space)
从 PAGE_HEAP_TOP 开始, 到最后一个数据目录, 这之间的空间就是空闲空间, 都被重置为 0, 当用户需要插入记录时候, 首先在被删除的记录的空间中查找, 如果没有找到合适的空间, 就从这里分配. 空间分配给记录后, 需要递增 PAGE_N_RECS 和 PAGE_N_HEAP.
数据目录(Page Directory)
用户的记录是从低地址向高地址扩展, 而数据目录则相反. 在数据页被初始化的时候, 就会数据页最后 (当然在 checksum 之前) 创建两个数据目录, 分别指向最大和最小记录. 之后插入新的数据的时候, 需要维护这个目录, 例如必要的时候增加目录的个数. 每个数据目录占用两个字节, 存储对应记录的页内偏移量. 假设目录 N, 这个目录 N 管理目录 N-1(不包括)和目录 N 之间的记录, 我们称目录 N own 这些记录. 在目录 N 指向的记录中, 会有字段记录 own 记录的数量. 由此可见, 目录 own 的记录不能太多, 因为太多的话, 即意味着目录太过稀疏, 不能很好的提高查询效率, 但同时也不能 own 太少, 这会导致目录数量变多, 占用过多的空间. 在 InnoDB 的实现中, 目录 own 的记录数量在 4-8 之间, 包括 4 和 8, 平均是 6 个记录. 如果超过这个数量, 就需要重新均衡目录的数量. 目录的增加和删除可能需要进行内存拷贝, 但是由于目录占用的总体空间很小, 开销可以忽略不计.
数据页尾部(Fil Trailer)
这个部分处于数据页最后的位置, 只有 8 个字节. 低地址的四个字节存储 checksum 的值, 高地址的四个字节存储 FIL_PAGE_LSN 的低位四字节. 注意这里的 checksum 的值不一定与 FIL_PAGE_SPACE_OR_CHKSUM 的相同, 这个依赖不同的 checksum 计算方法.
核心函数
本节详细剖析一下数据页相关的几个核心函数.
插入记录
核心入口函数在
page_cur_insert_rec_low
. 核心步骤如下:
获取记录的长度. 函数传入参数就有已经组合好的完整记录, 所以只需要从记录的元数据中获取即可.
首先从 PAGE_FREE 链表中尝试获取足够的空间. 仅仅比较链表头的一个记录, 如果这个记录的空间大于需要插入的记录的空间, 则复用这块空间(包括 heap_no), 否则就从 PAGE_HEAP_TOP 分配空间. 如果这两个地方都没有, 则返回空. 这里注意一下, 由于只判断 Free 链表的第一个头元素, 所以算法对空间的利用率不是很高, 估计也是为了操作方便. 假设, 某个数据页首先删除了几条大的记录, 但是最后一条删除的是比较小的记录 A, 那么后续插入的记录大小只有比记录 A 还小, 才能把 Free 链表利用起来. 举个例子, 假设先后删除记录的大小为 4K, 3K, 5K, 2K, 那么只有当插入的记录小于 2K 时候, 这些被删除的空间才会被利用起来, 假设新插入的记录是 0.5K, 那么 Free 链表头的 2K, 可以被重用, 但是只是用了前面的 0.5K, 剩下的 1.5K 依然会被浪费, 下次插入只能利用 5K 记录所占的空间, 并不会把剩下的 1.5K 也利用起来. 这些特性, 从底层解释了, 为什么 InnoDB 那么容易产生碎片, 经常需要进行空间整理.
如果 Free 链表不够, 就从 PAGE_HEAP_TOP 分配, 如果分配成功, 需要递增 PAGE_N_HEAP.
如果这个数据页有足够的空间, 则拷贝记录到指定的空间.
修改新插入记录前驱上的 next 指针, 同时修改这条新插入记录的指针 next 指针. 这两步主要是保证记录上链表的连续性.
递增 PAGE_N_RECS. 设置 heap_no. 设置 owned 值为 0.
更新 PAGE_LAST_INSERT,PAGE_DIRECTION,PAGE_N_DIRECTION, 设置这些参数后, 可以一定程度上提高连续插入的性能, 因为插入前需要先定位插入的位置, 有了这些信息可以加快查找. 详见查找记录代码分析.
修改数据目录. 因为增加了一条新的记录, 可能有些目录 own 的记录数量超过了最大值(目前是 8 条), 需要重新整理一下这个数据页的目录(
page_dir_split_slot
). 算法比较简单, 就是找到中间节点, 然后用这个中间节点重新构建一个新的目录, 为了给这个新的目录腾空间, 需要把后续的所有目录都平移, 这个涉及一次 momove 操作(
page_dir_split_slot
和 page_dir_add_slot).
写 redolog 日志, 持久化操作.
如果有 blob 字段, 则处理独立的 off-page.
删除记录
注意这里的删除操作是指真正的删除物理记录, 而不是标记记录为 delete-mark. 核心函数入口函数在
page_cur_delete_rec
. 步骤如下:
如果需要删除的记录是这个数据页的最后一个记录, 那么直接把这个数据页重新初始化成空页 (page_create_empty) 即可.
如果不是最后一条, 就走正常路径. 首先记录 redolog 日志.
重置 PAGE_LAST_INSERT 和递增 block 的 modify clock. 后者主要是为了让乐观的查询失效.
找到需要删除记录的前驱和后继记录, 然后修改指针, 使前驱直接指向后继. 这样记录的链表上就没有这条记录了.
如果一个目录指向这条被删除的记录, 那么让这个目录指向删除记录的前驱, 同时减少这个目录 own 的记录数.
如果这个记录有 blob 的 off-page, 则删除.
把记录放到 PAGE_FREE 链表头部, 然后递增 PAGE_GARBAGE 的大小, 减小 PAGE_N_RECS 用户记录的值.
由于第五步中递减了 own 值, 可能导致 own 的记录数小于最小值(目前是 4 条). 所以需要重新均衡目录, 可能需要删除某些目录(
page_dir_balance_slot
). 具体算法也比较简单, 首先判断是否可以从周围的目录中挪一条记录过来, 如果可以直接调整一下前后目录的指针即可. 这种简单的调整要求被挪出记录的目录 own 的记录数量足够多, 如果也没有足够的记录, 就需要删除其中一个目录, 然后把后面的目录都向前平移(
- page_dir_delete_slot
- ).
查找记录 / 定位位置
在 InnoDB 中, 需要查找某条件记录, 需要调用函数 page_cur_search_with_match, 但如果需要定位某个位置, 例如大于某条记录的第一条记录, 也需要使用同一个函数. 定位的位置有 PAGE_CUR_G,PAGE_CUR_GE,PAGE_CUR_L,PAGE_CUR_LE 四种, 分别表示大于, 大于等于, 小于, 小于等于四种位置.
由于数据页目录的存在, 查找和定位就相对简单, 先用二分查找, 定位周边的两个目录, 然后再用线性查找的方式定位最终的记录或者位置.
此外, 由于每次插入前, 都需要调用这个函数确定插入位置, 为了提高效率, InnoDB 针对按照主键顺序插入的场景做了一个小小的优化. 因为如果按照主键顺序插入的话, 能保证每次都插入在这个数据页的最后, 所以只需要直接把位置直接定位在数据页的最后 (PAGE_LAST_INSERT) 就可以了. 至于怎么判断当前是否按照主键顺序插入, 就依赖 PAGE_N_DIRECTION,PAGE_LAST_INSERT,PAGE_DIRECTION 这几个信息了, 目前的代码中要求满足 5 个条件:
当前的数据页是叶子节点
位置查询模式为 PAGE_CUR_LE
相同方向的插入已经大于 3 了(
- page_header_get_field(page, PAGE_N_DIRECTION)> 3
- )
最后插入的记录的偏移量为空(
- page_header_get_ptr(page, PAGE_LAST_INSERT) != 0
- )
从右边插入的(
- page_header_get_field(page, PAGE_DIRECTION) == PAGE_RIGHT
- )
其他函数
除了插入删除查找外, 还有一些函数也比较重要, 例如:
page_create, 创建新的空页的时候, 都需要调用这个函数来初始化元信息.
page_move_rec_list_end
, 当数据页需要重组时候, 需要把数据从一个数据页拷贝到另外一个, 这个时候就需要用到. 类似的还有函数
page_move_rec_list_start
, 两个函数的拷贝方式不同, 一个是从头开始拷贝到指定的记录, 另外一个是从指定记录开始拷贝到数据页最后.
page_validate, 这种函数主要是 debug 模式下校验数据页是否损坏的检验函数, 不做什么实际工作, 但是这些函数非常时候初学者阅读, 能快读的理解数据页的结构.
page_cur_open_on_rnd_user_rec
, 这函数是把位置放到一个随机的记录上, 当 change buffer 的 B 树满的时候, 目前的逻辑是随机选一条记录, 进行合并.
数据页 Corruption
数据页的 checksum 值的计算方法依赖参数
innodb_checksum_algorithm
. 目前提供三种计算 checksum 的方法, 第一种是 crc 校验(
buf_calc_page_crc32
), 这种是一种比较新的计算方法, 但是可以使用 cpu 硬件指令来加速. 第二种是 innodb 校验, 是 innodb 自己开发的一种计算方法, 但是有新老两种变体, 两种变体计算结果不同, 为了兼容老的变体, 需要在代码中兼容. 第三种是 none 模式, 这种计算方式不计算每个数据页的校验值, 而是使用一个指定的值填充 checksum 字段, 这种方式速度很快, 但也保证不了数据的正确性. 在
innodb_checksum_algorithm
中, 除了 innodb,crc32,none 三种选项之外, 还有 strict 带头的选项. strict 的选项表示, 在读取的时候必须是指定的校验方式的校验值才通过, 其他的都不行, 例如, 指定了 strict_crc32, 那么在数据页被读取计算 checksum 时候, 对应的校验值必须也是 crc32 的才可通过, 但是如果指定 crc32, 如果存储的是 innodb 或者 none 的结果, 也是可以通过校验的. 之所以提供了这种选项, 就是为了兼容老版本的 mysql 以及防止校验算法被修改而导致的数据不可用. 这里提醒一下, 使用 strict 模式由于计算量比较小, 因此效率相对较高.
接下里, 分析一下 checksum 写入和读取校验的代码细节.
在一个数据页即将被刷入磁盘的时候, 会调用函数
buf_flush_init_for_writing
进行相关元信息的修改. 这里主要包括 newest_len 和 checksum. 函数中首先往 FIL_PAGE_LSN 和
UNIV_PAGE_SIZE - FIL_PAGE_END_LSN_OLD_CHKSUM
分别写入 8 个字节的 newest_lsn, 接着计算 checksum, 填入
FIL_PAGE_SPACE_OR_CHKSUM
, 同时覆盖
UNIV_PAGE_SIZE - FIL_PAGE_END_LSN_OLD_CHKSUM
起始的四个字节. 我们会发现, 如果算法是 crc32 或者 none, 那么前后两个 checksum 存储的内容相同, 如果是 innodb, 则后面的 checksum 会存老版的值.
在一个数据页从磁盘读取的时候, IO 线程会回调
buf_page_io_complete
函数, 如果是读取操作, 这个函数中会调用函数
buf_page_is_corrupted
校验数据页的正确性.
buf_page_is_corrupted
首先会校验头尾的 newest_lsn 的低四字节是否相同(FIL_PAGE_LSN+4 和
UNIV_PAGE_SIZE- FIL_PAGE_END_LSN_OLD_CHKSUM
+4), 如果不相同, 直接认为数据页损坏了. 接下里会把完整的 8 字节 lsn 读取出来, 跟系统当前的 lsn 对比, 如果比当前的大, 也认为数据页坏了. 接下里, 会把首尾的 checksum 都读取出来, 如果发现都为 0, 则进一步判断是否是空页, 如果是空页, 则认为这个数据页正常(可能是 extend 文件出来的空页). 接下来, 计算数据页内容的校验值, 与存储在数据页首尾的值进行比较. 在 strict 算法下, 必须完全一致才认为数据页完整, 在非 strict 模式下, 只要有一种值匹配即可了. 如果校验值通过, 则认为数据页完好. 如果数据页损坏, 则会调用函数 buf_page_print 输出数据页的信息至错误日志, 这也是我们常常看到的数据页错误日志. 这个函数会把数据页所有内容, space_id,page_no, 头尾 lsn, 头尾 checksum 以及各种算法计算的 checksum 都打印出来, 此外, 还会依据 FIL_PAGE_TYPE 推测可能的数据页种类, 方便排查问题.
总结
总体来说, InnoDB 数据页的结构设计折中了插入, 删除以及查找的效率, 是一种值得学习的数据结构. 此外, 了解其的结构和原理, 当数据页发生损坏的时候, 能不慌不忙, 尽最大的努力找出残存的数据, 这也是一个优秀 DBA 不可缺少的素质.
来源: https://www.cnblogs.com/coderyuhui/p/8884717.html