Author: 韩逸
之前介绍的月报中，详细介绍了InnoDB Buffer Pool的实现细节，Buffer Pool主要就是用来存储数据页的，是数据页在内存中的动态存储方式，而本文介绍一下数据页在磁盘上的静态存储方式以及相关的操作。由于数据页的结构涉及InnoDB非常底层的代码，因此各个版本的MySQL都可以参考。相关代码主要集中在page目录下。
数据库采用数据页的形式组织数据。MySQL默认的非压缩数据页为16KB。在ibd中间中，0-16KB偏移量即为0号数据页，16KB-32KB的为1号数据页，依次类推。数据页的头尾除了一些元信息外，还有Checksum校验值，这些校验值在写入磁盘前计算得到，当从磁盘中读取时，重新计算校验值并与数据页中存储的对比，如果发现不同，则会导致MySQL crash。遇到这种情况，往往需要从备份集中恢复数据，如果备份不可用，只能使用innodb_force_recovery强行启动，然后尽可能多的导出数据。这篇月报中介绍了一种从物理文件中恢复数据的方法，在走投无路的情况下可以使用。
严格来讲，InnoDB的数据页有很多种，比如，索引页，Undo页，Inode页，系统页，BloB页等，一共有10多种。本文主要介绍最常见的索引页。下文中，没有特殊说明，数据页都指索引页。
数据页包括七个部分，数据页文件头，数据页头，最大最小记录，用户记录，空闲空间，数据目录，数据页尾部。
简单的来说，数据页分两部分，一部分存储数据记录，按照记录的大小通过记录的指针连接起来。另外一部分存储数据页的目录，用来加速查找。注意这个目录是稀疏的，即不是所有的记录在目录都有索引，平均是每隔六个记录才有一个目录。数据记录部分是从低地址向高地址空间增长的，而数据目录部分则相反。这种数据结构可以保证比较高的插入删除和查找效率。具体方法详见核心函数小节。
这篇月报的最后有一张图，详细展示了数据页的结构，读者可以先自行了解一下，接下来，本文解释一下各个部分的内容。
这个部分主要用来存储表空间相关的信息。主要在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的。
从存储的信息来看，这部分才是存的数据页相关的元信息。定义在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: 分别是叶子节点和非叶子节点的段头页地址。
最大记录是这个数据页中逻辑上最大的记录，所有用户的记录都小于它。最小记录是数据页上最小的记录，所有用户记录都大于它。他们在数据页被创建的时候创建，而且不能被删除。引入他们主要是方便页内操作。
用户所有插入的记录都存放在这里，默认情况下记录跟记录之间没有间隙，但是如果重用了已删除记录的空间，就会导致空间碎片。每个记录都有指向下一个记录的指针，但是没有指向上一个记录的指针。记录按照主键顺序排序。即，用户可以从数据页最小记录开始遍历，直到最大的记录，这包括了所有正常的记录和所有被delete-marked记录，但是不会访问到被删除的记录(PAGE_FREE)。
从PAGE_HEAP_TOP开始，到最后一个数据目录，这之间的空间就是空闲空间，都被重置为0，当用户需要插入记录时候，首先在被删除的记录的空间中查找，如果没有找到合适的空间，就从这里分配。空间分配给记录后，需要递增PAGE_N_RECS和PAGE_N_HEAP。
用户的记录是从低地址向高地址扩展，而数据目录则相反。在数据页被初始化的时候，就会数据页最后(当然在checksum之前)创建两个数据目录，分别指向最大和最小记录。之后插入新的数据的时候，需要维护这个目录，例如必要的时候增加目录的个数。每个数据目录占用两个字节，存储对应记录的页内偏移量。假设目录N，这个目录N管理目录N-1(不包括)和目录N之间的记录，我们称目录N own 这些记录。在目录N指向的记录中，会有字段记录own记录的数量。由此可见，目录own的记录不能太多，因为太多的话，即意味着目录太过稀疏，不能很好的提高查询效率，但同时也不能own太少，这会导致目录数量变多，占用过多的空间。在InnoDB的实现中，目录own的记录数量在4-8之间，包括4和8，平均是6个记录。如果超过这个数量，就需要重新均衡目录的数量。目录的增加和删除可能需要进行内存拷贝，但是由于目录占用的总体空间很小，开销可以忽略不计。
这个部分处于数据页最后的位置，只有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那么容易产生碎片，经常需要进行空间整理。PAGE_HEAP_TOP分配，如果分配成功，需要递增PAGE_N_HEAP。PAGE_N_RECS。设置heap_no。设置owned值为0。PAGE_LAST_INSERT，PAGE_DIRECTION，PAGE_N_DIRECTION，设置这些参数后，可以一定程度上提高连续插入的性能，因为插入前需要先定位插入的位置，有了这些信息可以加快查找。详见查找记录代码分析。page_dir_split_slot)。算法比较简单，就是找到中间节点，然后用这个中间节点重新构建一个新的目录，为了给这个新的目录腾空间，需要把后续的所有目录都平移，这个涉及一次momove操作(page_dir_split_slot和page_dir_add_slot)。注意这里的删除操作是指真正的删除物理记录，而不是标记记录为delete-mark。核心函数入口函数在page_cur_delete_rec。步骤如下：
page_create_empty)即可。PAGE_LAST_INSERT和递增block的modify clock。后者主要是为了让乐观的查询失效。PAGE_FREE链表头部，然后递增PAGE_GARBAGE的大小，减小PAGE_N_RECS用户记录的值。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_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树满的时候，目前的逻辑是随机选一条记录，进行合并。
数据页的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不可缺少的素质。