前言
数据库系统与文件系统最大的区别在于数据库能保证操作的原子性，一个操作要么不做要么都做，即使在数据库宕机的情况下，也不会出现操作一半的情况，这个就需要数据库的日志和一套完善的崩溃恢复机制来保证。本文仔细剖析了InnoDB的崩溃恢复流程，代码基于5.6分支。
基础知识
lsn: 可以理解为数据库从创建以来产生的redo日志量，这个值越大，说明数据库的更新越多，也可以理解为更新的时刻。此外，每个数据页上也有一个lsn，表示最后被修改时的lsn，值越大表示越晚被修改。比如，数据页A的lsn为100，数据页B的lsn为200，checkpoint lsn为150，系统lsn为300，表示当前系统已经更新到300，小于150的数据页已经被刷到磁盘上，因此数据页A的最新数据一定在磁盘上，而数据页B则不一定，有可能还在内存中。
redo日志: 现代数据库都需要写redo日志，例如修改一条数据，首先写redo日志，然后再写数据。在写完redo日志后，就直接给客户端返回成功。这样虽然看过去多写了一次盘，但是由于把对磁盘的随机写入(写数据)转换成了顺序的写入(写redo日志)，性能有很大幅度的提高。当数据库挂了之后，通过扫描redo日志，就能找出那些没有刷盘的数据页(在崩溃之前可能数据页仅仅在内存中修改了，但是还没来得及写盘)，保证数据不丢。
undo日志: 数据库还提供类似撤销的功能，当你发现修改错一些数据时，可以使用rollback指令回滚之前的操作。这个功能需要undo日志来支持。此外，现代的关系型数据库为了提高并发(同一条记录，不同线程的读取不冲突，读写和写读不冲突，只有同时写才冲突)，都实现了类似MVCC的机制，在InnoDB中，这个也依赖undo日志。为了实现统一的管理，与redo日志不同，undo日志在Buffer Pool中有对应的数据页，与普通的数据页一起管理，依据LRU规则也会被淘汰出内存，后续再从磁盘读取。与普通的数据页一样，对undo页的修改，也需要先写redo日志。
检查点: 英文名为checkpoint。数据库为了提高性能，数据页在内存修改后并不是每次都会刷到磁盘上。checkpoint之前的数据页保证一定落盘了，这样之前的日志就没有用了(由于InnoDB redolog日志循环使用，这时这部分日志就可以被覆盖)，checkpoint之后的数据页有可能落盘，也有可能没有落盘，所以checkpoint之后的日志在崩溃恢复的时候还是需要被使用的。InnoDB会依据脏页的刷新情况，定期推进checkpoint，从而减少数据库崩溃恢复的时间。检查点的信息在第一个日志文件的头部。
崩溃恢复: 用户修改了数据，并且收到了成功的消息，然而对数据库来说，可能这个时候修改后的数据还没有落盘，如果这时候数据库挂了，重启后，数据库需要从日志中把这些修改后的数据给捞出来，重新写入磁盘，保证用户的数据不丢。这个从日志中捞数据的过程就是崩溃恢复的主要任务，也可以成为数据库前滚。当然，在崩溃恢复中还需要回滚没有提交的事务，提交没有提交成功的事务。由于回滚操作需要undo日志的支持，undo日志的完整性和可靠性需要redo日志来保证，所以崩溃恢复先做redo前滚，然后做undo回滚。
我们从源码角度仔细剖析一下数据库崩溃恢复过程。整个过程都在引擎初始化阶段完成(innobase_init)，其中最主要的函数是innobase_start_or_create_for_mysql，innodb通过这个函数完成创建和初始化，包括崩溃恢复。首先来介绍一下数据库的前滚。
redo日志前滚数据库
前滚数据库，主要分为两阶段，首先是日志扫描阶段，扫描阶段按照数据页的space_id和page_no分发redo日志到hash_table中，保证同一个数据页的日志被分发到同一个哈希桶中，且按照lsn大小从小到大排序。扫描完后，再遍历整个哈希表，依次应用每个数据页的日志，应用完后，在数据页的状态上至少恢复到了崩溃之前的状态。我们来详细分析一下代码。
首先，打开所有的ibdata文件(open_or_create_data_files)(ibdata可以有多个)，每个ibdata文件有个flush_lsn在头部，计算出这些文件中的max_flush_lsn和min_flush_lsn，因为ibdata也有可能有数据没写完整，需要恢复，后续(recv_recovery_from_checkpoint_start_func)通过比较checkpont_lsn和这两个值来确定是否需要对ibdata前滚。
接着，打开系统表空间和日志表空间的所有文件(fil_open_log_and_system_tablespace_files)，防止出现文件句柄不足，清空buffer pool(buf_pool_invalidate)。接下来就进入最最核心的函数:recv_recovery_from_checkpoint_start_func，注意，即使数据库是正常关闭的，也会进入。
虽然recv_recovery_from_checkpoint_start_func看过去很冗长，但是很多代码都是为了LOG_ARCHIVE特性而编写的，真正数据崩溃恢复的代码其实不多。
首先，初始化一些变量，查看srv_force_recovery这个变量，如果用户设置跳过前滚阶段，函数直接返回。
接着，初始化recv_sys结构，分配hash_table的大小，同时初始化flush list rbtree。recv_sys结构主要在崩溃恢复前滚阶段使用。hash_table就是之前说的用来存不同数据页日志的哈希表，哈希表的大小被初始化为buffer_size_in_bytes/512, 这个是哈希表最大的长度，超过就存不下了，幸运的是，需要恢复的数据页的个数不会超过这个值，因为buffer poll最多(数据库崩溃之前脏页的上线)只能存放buffer_size_in_bytes/16KB个数据页，即使考虑压缩页，最多也只有buffer_size_in_bytes/1KB个，此外关于这个哈希表内存分配的大小，可以参考bug#53122。flush list rbtree这个主要是为了加入插入脏页列表，InnoDB的flush list必须按照数据页的最老修改lsn(oldest_modifcation)从小到大排序，在数据库正常运行时，可以通过log_sys->mutex和log_sys->log_flush_order_mutex保证顺序，在崩溃恢复则没有这种保证，应用数据的时候，是从第一个元素开始遍历哈希表，不能保证数据页按照最老修改lsn(oldest_modifcation)从小到大排序，这样就需要线性遍历flush_list来寻找插入位置，效率太低，因此引入红黑树，加快查找插入的位置。
接着，从ib_logfile0的头中读取checkpoint信息，主要包括checkpoint_lsn和checkpoint_no。由于InnoDB日志是循环使用的，且最少要有2个，所以ib_logfile0一定存在，把checkpoint信息存在里面很安全，不用担心被删除。checkpoint信息其实会写在文件头的两个地方，两个checkpoint域轮流写。为什么要两个地方轮流写呢？假设只有一个checkpoint域，一直更新这个域，而checkpoint域有512字节(OS_FILE_LOG_BLOCK_SIZE)，如果刚好在写这个512字节的时候，数据库挂了，服务器也挂了(先不考虑硬件的原子写特性，早期的硬件没有这个特性)，这个512字节可能只写了一半，导致整个checkpoint域不可用。这样数据库将无法做崩溃恢复，从而无法启动。如果有两个checkpoint域，那么即使一个写坏了，还可以用另外一个尝试恢复，虽然有可能这个时候日志已经被覆盖，但是至少提高了恢复成功的概率。两个checkpoint域轮流写，也能减少磁盘扇区故障带来的影响。checkpoint_lsn之前的数据页都已经落盘，不需要前滚，之后的数据页可能还没落盘，需要重新恢复出来，即使已经落盘也没关系，因为redo日志时幂等的，应用一次和应用两次都一样(底层实现: 如果数据页上的lsn大于等于当前redo日志的lsn，就不应用，否则应用。checkpoint_no可以理解为checkpoint域写盘的次数，每次刷盘递增1，同时这个值取模2可以用来实现checkpoint_no域的轮流写。正常逻辑下，选取checkpoint_no值大的作为最终的checkpoint信息，用来做后续崩溃恢复扫描的起始点。
接着，使用checkpoint域的信息初始化recv_sys结构体的一些信息后，就进入日志解析的核心函数recv_group_scan_log_recs，这个函数后续我们再分析，主要作用就是解析redo日志，如果内存不够了，就直接调用应用(recv_apply_hashed_log_recs)日志，然后再接着解析。如果需要应用的日志很少，就仅仅解析分发日志，到recv_recovery_from_checkpoint_finish函数中在应用日志。
接着，依据当前刷盘的数据页状态做一次checkpoint，因为在recv_group_scan_log_recs里可能已经应用部分日志了。至此recv_recovery_from_checkpoint_start_func函数结束。
在recv_recovery_from_checkpoint_finish函数中，如果srv_force_recovery设置正确，就开始调用函数recv_apply_hashed_log_recs应用日志，然后等待刷脏的线程退出(线程是崩溃恢复时临时启动的)，最后释放recv_sys的相关资源以及hash_table占用的内存。
至此，数据库前滚结束。接下来，我们详细分析一下redo日志解析函数以及redo日志应用函数的实现细节。
redo日志解析函数
解析函数的最上层是recv_group_scan_log_recs，这个函数调用底层函数(log_group_read_log_seg)，按照RECV_SCAN_SIZE(64KB)大小分批读取。读取出来后，首先通过block_no和lsn之间的关系以及日志checksum判断是否读到了日志最后(所以可以看出，并没一个标记在日志头标记日志的有效位置，完全是按照上述两个条件判断是否到达了日志尾部)，如果读到最后则返回(之前说了，即使数据库是正常关闭的，也要走崩溃恢复逻辑，那么在这里就返回了，因为正常关闭的checkpoint值一定是指向日志最后)，否则则把日志去头掐尾放到一个recv_sys->buf中，日志头里面存了一些控制信息和checksum值，只是用来校验和定位，在真正的应用中没有用。在放到recv_sys->buf之前，需要检验一下recv_sys->buf有没有满(RECV_PARSING_BUF