在上一篇《[innodb源码分析之重做日志结构](http://blog.csdn.net/yuanrxdu/article/details/42430187)》中我们知道redo log的基本结构和日志写入步骤，那么redo log是怎么进行数据恢复的呢？在什么时候进行redo log的日志推演呢？redo log的推演只有在数据库异常或者关闭后，数据库重新启动时会进行日志推演，将数据库状态恢复到关闭前的状态。那么这个过程是怎么进行的呢？以下我们逐步来解析。 ## 1.recv_sys_t结构 innodb在MySQL启动的时候，会对重做日志文件进行日志重做，重做日志是通过一个recv_sys_t的结构来进行数据恢 复和控制的。它的结构如下： ~~~ struct recv_sys_struct { mutex_t mutex; /*保护锁*/ ibool apply_log_recs; /*正在应用log record到page中*/ ibool apply_batch_on; /*批量应用log record标志*/ dulint lsn; ulint last_log_buf_size; byte* last_block; /*恢复时最后的块内存缓冲区*/ byte* last_block_buf_start; /*最后块内存缓冲区的起始位置，因为last_block是512地址对齐的，需要这个变量记录free的地址位置*/ byte* buf; /*从日志块中读取的重做日志信息数据*/ ulint len; /*buf有效的日志数据长度*/ dulint parse_start_lsn; /*开始parse的lsn*/ dulint scanned_lsn; /*已经扫描过的lsn序号*/ ulint scanned_checkpoint_no; /*恢复日志的checkpoint 序号*/ ulint recovered_offset; /*恢复位置的偏移量*/ dulint recovered_lsn; /*恢复的lsn位置*/ dulint limit_lsn; /*日志恢复最大的lsn,暂时在日志重做的过程没有使用*/ ibool found_corrupt_log; /*是否开启日志恢复诊断*/ log_group_t* archive_group; mem_heap_t* heap; /*recv sys的内存分配堆,用来管理恢复过程的内存占用*/ hash_table_t* addr_hash; /*recv_addr的hash表，以space id和page no为KEY*/ ulint n_addrs; /*addr_hash中包含recv_addr的个数*/ }; ~~~ 在这个结构中，比较复杂的是addr_hash这个哈希表，这个哈希表是用sapce_id和page_no作为hash key,里面存储有恢复时对应的记录内容。恢复日志在从日志文件中读出后，进行解析成若干个recv_t并存储在哈希表当中。在一个读取解析周期过后，日志恢复会对hash表中的recv_t中的数据写入到ibuf和page中。这里为什么要使用hash表呢？个人觉得是为了同一个page的数据批量进行恢复的缘故，这样可以page减少随机插入和修改。 以下是和这个过程相关的几个数据结构: ~~~ /*对应页的数据恢复操作集合*/ struct recv_addr_struct { ulint state; /*状态，RECV_NOT_PROCESSED、RECV_BEING_PROCESSED、RECV_PROCESSED*/ ulint space; /*space的ID*/ ulint page_no; /*页序号*/ UT_LIST_BASE_NODE_T(recv_t) rec_list; hash_node_t addr_hash; }; /*当前的记录操作*/ struct recv_struct { byte type; /*log类型*/ ulint len; /*当前记录数据长度*/ recv_data_t* data; /*当前的记录数据list*/ dulint start_lsn; /*mtr起始lsn*/ dulint end_lsn; /*mtr结尾lns*/ UT_LIST_NODE_T(recv_t) rec_list; }; /*具体的数据体*/ struct recv_data_struct { recv_data_t* next; /*下一个recv_data_t,next的地址后面接了一大块内存，用于存储rec body*/ }; ~~~ 他们的内存关系结构图如下：  ## 2.重做日志推演过程的LSN关系 除了这个恢复的哈希表以外，recv_sys_t中的各种LSN也是和日志恢复有非常紧密的关系。以下是各种lsn的解释：   parse_start_lsn    本次日志重做恢复起始的lsn，如果是从checkpoint处开始恢复，等于checkpoint_lsn。   scanned_lsn        在恢复过程，将恢复日志从log_sys->buf解析块后存入recv_sys->buf的日志lsn.   recovered_lsn      已经将数据恢复到page中或者已经将日志操作存储addr_hash当中的日志lsn;   在日志开始恢复时：    parse_start_lsn = scanned_lsn = recovered_lsn = 检查点的lsn。  在日志完成恢复时:      parse_start_lsn =  检查点的lsn      scanned_lsn = recovered_lsn = log_sys->lsn。 在日志推演过程中lsn大小关系如下：  ## 3.日志恢复的主要接口和流程 恢复日志主要的接口函数:  recv_recovery_from_checkpoint_start    从重做日志组内的最近的checkpoint开始恢复数据   recv_recovery_from_checkpoint_finish  结束从重做日志组内的checkpoint的数据恢复操作   recv_recovery_from_archive_start           从归档日志文件中进行数据恢复   recv_recovery_from_archive_finish         结束从归档日志中的数据恢复操作   recv_reset_logs                                          截取重做日志最后一段作为新的重做日志的起始位置，可能会丢失数据。 **重做日志恢复数据的流程(checkpoint方式)**  1.当MySQL启动的时候，先会从数据库文件中读取出上次保存最大的LSN。   2.然后调用recv_recovery_from_checkpoint_start，并将最大的LSN作为参数传入函数当中。   3.函数会先最近建立checkpoint的日志组，并读取出对应的checkpoint信息   4.通过checkpoint lsn和传入的最大LSN进行比较，如果相等，不进行日志恢复数据，如果不相等，进行日志恢复。   5.在启动恢复之前，先会同步各个日志组的archive归档状态   6.在开始恢复时，先会从日志文件中读取2M的日志数据到log_sys->buf，然后对这2M的数据进行scan,校验其合法性，而后将去掉block header的日志放入recv_sys->buf当中，这个过程称为scan,会改变scanned lsn.   7.在对2M的日志数据scan后，innodb会对日志进行mtr操作解析，并执行相关的mtr函数。如果mtr合法，会将对应的记录数据按space page_no作为KEY存入recv_sys->addr_hash当中。   8.当对scan的日志数据进行mtr解析后，innodb对会调用recv_apply_hashed_log_recs对整个recv_sys->addr_hash进行扫描，并按照日志相对应的操作进行对应page的数据恢复。这个过程会改变recovered_lsn。   9.如果完成第8步后，会再次从日志组文件中读取2M数据，跳到步骤6继续相对应的处理，直到日志文件没有需要恢复的日志数据。   10.innodb在恢复完成日志文件中的数据后，会调用recv_recovery_from_checkpoint_finish结束日志恢复操作，主要是释放一些开辟的内存。并进行事务和binlog的处理。 上面过程的示意图如下： 

在innodb的引擎实现中，为了实现事务的持久性，构建了重做日志系统。重做日志由两部分组成：内存日志缓冲区(redo log buffer)和重做日志文件。这样设计的目的显而易见，日志缓冲区是为了加快写日志的速度，而重做日志文件为日志数据提供持久化的作用。在innodb的重做日志系统中，为了更好实现日志的易恢复性、安全性和持久化性，引入了以下几个概念：LSN、log block、日志文件组、checkpoint和归档日志。以下我们分别一一来进行分析。 ## 1.LSN 在innodb中的重做日志系统中，定义一个LSN序号，其代表的意思是日志序号。LSN在引擎中定义的是一个dulint_t类型值，相当于uint64_t,关于dulint_t的定义如下： ~~~ typedef struct dulint_struct { ulint high; /* most significant 32 bits */ ulint low; /* least significant 32 bits */ }dulint_t; ~~~ LSN真正的含义是储存引擎向重做日志系统写入的日志量（字节数），这个日志量包括写入的日志字节 + block_header_size + block_tailer_size。LSN的初始化值是：LOG_START_LSN（相当于8192），在调用日志写入函数LSN就一直随着写入的日志长度增加，具体看: ~~~ void log_write_low(byte* str, ulint str_len) { log_t* log = log_sys; . . . part_loop: /*计算part length*/ data_len = log->buf_free % OS_FILE_LOG_BLOCK_SIZE + str_len; . . . /*将日志内容拷贝到log buffer*/ ut_memcpy(log->buf + log->buf_free, str, len); str_len -= len; str = str + len; . . . if(data_len = OS_FILE_LOG_BLOCK_SIZE - LOG_BLOCK_TRL_SIZE){ /*完成一个block的写入*/ . . . len += LOG_BLOCK_HDR_SIZE + LOG_BLOCK_TRL_SIZE; log->lsn = ut_dulint_add(log->lsn, len); . . . } else /*更改lsn*/ log->lsn = ut_dulint_add(log->lsn, len); . . . } ~~~ LSN是不会减小的，它是日志位置的唯一标记。在重做日志写入、checkpoint构建和PAGE头里面都有LSN。 **关于日志写入:** 例如当前重做日志的LSN = 2048,这时候innodb调用log_write_low写入一个长度为700的日志，2048刚好是4个block长度，那么需要存储700长度的日志，需要量个BLOCK(单个block只能存496个字节)。那么很容易得出新的LSN = 2048 + 700 + 2 * LOG_BLOCK_HDR_SIZE(12) + LOG_BLOCK_TRL_SIZE(4) = 2776。 **关于checkpoint和日志恢复：** 在page的fil_header中的LSN是表示最后刷新是的LSN, 假如数据库中存在PAGE1 LSN  = 1024，PAGE2 LSN = 2048， 系统重启时，检测到最后的checkpoint LSN = 1024，那么系统在检测到PAGE1不会对PAGE1进行恢复重做，当系统检测到PAGE2的时候，会将PAGE2进行重做。一次类推，小于checkpoint LSN的页不用重做，大于LSN checkpoint的PAGE就要进行重做。 ## 2.Log Block innodb在日志系统里面定义了log block的概念，其实log block就是一个512字节的数据块，这个数据块包括块头、日志信息和块的checksum.其结构如下：  Block no的最高位是描述block是否flush磁盘的标识位.通过lsn可以blockno,具体的计算过程是lsn是多少个512的整数倍，也就是no = lsn / 512 + 1;为什么要加1呢，因为所处no的块算成clac_lsn一定会小于传入的lsn.所以要+1。其实就是block的数组索引值。checksum是通过从块头开始到块的末尾前4个字节为止，做了一次数字叠加，代码如下： ~~~ sum = 1; sh = 0; for(i = 0; i < OS_FILE_LOG_BLOCK_SIZE - LOG_BLOCK_TRL_SIZE, i ++){ sum = sum & 0x7FFFFFFF; sum += (((ulint)(*(block + i))) << sh) + (ulint)(*(block + i)); sh ++; if(sh > 24) sh = 0; } ~~~ 在日志恢复的时候，innodb会对加载的block进行checksum校验，以免在恢复过程中数据产生错误。事务的日志写入是基于块的，如果事务的日志大小小于496字节，那么会合其他的事务日志合并在一个块中，如果事务日志的大小大于496字节，那么会以496为长度进行分离存储。例如：T1 = 700字节大小，T2 = 100字节大小存储结构如下：  ## 3.重做日志结构和关系图 innodb在重做日志实现当中，设计了3个层模块，即redo log buffer、group files和archive files。这三个层模块的描述如下： redo log buffer       重做日志的日志内存缓冲区，新写入的日志都是先写入到这个地方.redo log buffer中数据同步到磁盘上，必须进行刷盘操作。 group files      重做日志文件组，一般由3个同样大小的文件组成。3个文件的写入是依次循环的，每个日志文件写满后，即写下一个，日志文件如果都写满时，会覆盖第一次重新写。重做日志组在innodb的设计上支持多个。 archive files         归档日志文件，是对重做日志文件做增量备份，它是不会覆盖以前的日志信息。 **以下是它们关系示意图:**  ### 3.1重做日志组 重做日志组可以支持多个，这样做的目的应该是为了防止一个日志组损坏后，可以从其他并行的日志组里面进行数据恢复。在MySQL-5.6的将日志组的个数设置为1，不允许多个group存在。网易姜承尧的解释是innodb的作者认为通过外层存储硬件来保证日志组的完整性比较好，例如raid磁盘。重做日志组的主要功能是实现对组内文件的写入管理、组内的checkpoint建立和checkpiont信息的保存、归档日志状态管理（只有第一个group才做archive操作）.以下是对日志组的定义: ~~~ typedef struct log_group_struct { ulint id; /*log group id*/ ulint n_files; /*group包含的日志文件个数*/ ulint file_size; /*日志文件大小，包括文件头*/ ulint space_id; /*group对应的fil_space的id*/ ulint state; /*log group状态，LOG_GROUP_OK、LOG_GROUP_CORRUPTED*/ dulint lsn; /*log group的lsn*/ dulint lsn_offset; /*当前lsn相对组内文件起始位置的偏移量 */ ulint n_pending_writes; /*本group 正在执行fil_flush的个数*/ byte**file_header_bufs; /*文件头缓冲区*/ byte**archive_file_header_bufs;/*归档文件头信息的缓冲区*/ ulint archive_space_id; /*归档重做日志ID*/ ulint archived_file_no; /*归档的日志文件编号*/ ulint archived_offset; /*已经完成归档的偏移量*/ ulint next_archived_file_no; /*下一个归档的文件编号*/ ulint next_archived_offset; /*下一个归档的偏移量*/ dulint scanned_lsn; byte* checkpoint_buf; /*本log group保存checkpoint信息的缓冲区*/ UT_LIST_NODE_T(log_group_t) log_groups; }log_group_t; ~~~ 上面结构定义中的spaceid是对应fil0fil中的fil_space_t结构，一个fil_space_t结构可以管理多个文件fil_node_t，关于fil_node_t参见[这里](http://blog.csdn.net/yuanrxdu/article/details/41418421)。 ### 3.1.1LSN与组内偏移  在log_goup_t组内日志模块当中，其中比较重要的是关于LSN与组内偏移之间的换算关系。在组创建时，会对lsn和对应lsn_offset做设置，假如 初始化为 group lsn = 1024,  group lsn_offset = 2048，group由3个10240大小的文件组成，LOG_FILE_HDR_SIZE = 2048, 我们需要知道buf lsn = 11240对应的组内offset的偏移是多少，根据log_group_calc_lsn_offset函数可以得出如下公式：   group_size = 3 * 11240;  相对组起始位置的LSN偏移 = (buf_ls - group_ls)  + log_group_calc_size_offset(lsn_offset ) = (11240 - 1024) - 0 = 10216;  lsn_offset = log_group_calc_lsn_offset(相对组起始位置的LSN偏移 % group_size) = 10216 + 2 * LOG_FILE_HDR_SIZE = 14312; 这个偏移一定是加上了文件头长度的。 ### 3.1.2 file_header_bufs file_header_bufs是一个buffer缓冲区数组，数组长度和组内文件数是一致的，每个buf长度是2048。其信息结构如下：  log_group_id      对应log_group_t结构中的id file_start_lsn    当前文件其实位置数据对应的LSN值 File_no           当前的文件编号,一般在archive file头中体现 Hot backup str    一个空字符串,如果是hot_backup,会填上文件后缀ibackup。 File_end_ls       文件结尾数据对应的LSN值，一般在archive file文件中体现。 ### 3.2 checkpoint checkpoint是日志的检查点，其作用就是在数据库异常后，redo log是从这个点的信息获取到LSN,并对检查点以后的日志和PAGE做重做恢复。那么检查点是怎么生成的呢？当日志缓冲区写入的日志LSN距离上一次生成检查点的LSN达到一定差距的时候，就会开始创建检查点，创建检查点首先会将内存中的表的脏数据写入到硬盘，让后再将redo log buffer中小于本次检查点的LSN的日志也写入硬盘。在log_group_t中的checkpoint_buf，以下是它对应字段的解释: LOG_CHECKPOINT_NO            checkpoint序号， LOG_CHECKPOINT_LSN           本次checkpoint起始的LSN LOG_CHECKPOINT_OFFSET        本次checkpoint相对group file的起始偏移量 LOG_CHECKPOINT_LOG_BUF_SIZE  redo log buffer的大小，默认2M LOG_CHECKPOINT_ARCHIVED_LSN  当前日志归档的LSN LOG_CHECKPOINT_GROUP_ARRAY   每个log group归档时的文件序号和偏移量,是一个数组 ### 3.3 log_t 重做日志的写入、数据刷盘、建立checkpoint和归档操作都是通过全局唯一的,log_sys进行控制的，这是个非常庞大而又复杂的结构，定义如下： ~~~ typedef struct log_struct { byte pad[64]; /*使得log_struct对象可以放在通用的cache line中的数据，这个和CPU L1 Cache和数据竞争有和 直接关系*/ dulint lsn; /*log的序列号,实际上是一个日志文件偏移量*/ ulint buf_free; /*buf可以写的位置*/ mutex_t mutex; /*log保护的mutex*/ byte* buf; /*log缓冲区*/ ulint buf_size; /*log缓冲区长度*/ ulint max_buf_free; /*在log buffer刷盘后，推荐buf_free的最大值，超过这个值会被强制刷盘*/ ulint old_buf_free; /*上次写时buf_free的值,用于调试*/ dulint old_lsn; /*上次写时的lsn,用于调试*/ ibool check_flush_or_checkpoint; /*需要日志写盘或者是需要刷新一个log checkpoint的标识*/ ulint buf_next_to_write; /*下一次开始写入磁盘的buf偏移位置*/ dulint written_to_some_lsn; /*第一个group刷完成是的lsn*/ dulint written_to_all_lsn; /*已经记录在日志文件中的lsn*/ dulint flush_lsn; /*flush的lsn*/ ulint flush_end_offset; /*最后一次log file刷盘时的buf_free，也就是最后一次flush的末尾偏移量*/ ulint n_pending_writes; /*正在调用fil_flush的个数*/ os_event_t no_flush_event; /*所有fil_flush完成后才会触发这个信号,等待所有的goups刷盘完成*/ ibool one_flushed; /*一个log group被刷盘后这个值会设置成TRUE*/ os_event_t one_flushed_event; /*只要有一个group flush完成就会触发这个信号*/ ulint n_log_ios; /*log系统的io操作次数*/ ulint n_log_ios_old; /*上一次统计时的io操作次数*/ time_t last_printout_time; ulint max_modified_age_async; /*异步日志文件刷盘的阈值*/ ulint max_modified_age_sync; /*同步日志文件刷盘的阈值*/ ulint adm_checkpoint_interval; ulint max_checkpoint_age_async; /*异步建立checkpoint的阈值*/ ulint max_checkpoint_age; /*强制建立checkpoint的阈值*/ dulint next_checkpoint_no; dulint last_checkpoint_lsn; dulint next_checkpoint_lsn; ulint n_pending_checkpoint_writes; rw_lock_t checkpoint_lock; /*checkpoint的rw_lock_t,在checkpoint的时候，是独占这个latch*/ byte* checkpoint_buf; /*checkpoint信息存储的buf*/ ulint archiving_state; dulint archived_lsn; dulint max_archived_lsn_age_async; dulint max_archived_lsn_age; dulint next_archived_lsn; ulint archiving_phase; ulint n_pending_archive_ios; rw_lock_t archive_lock; ulint archive_buf_size; byte* archive_buf; os_event_t archiving_on; ibool online_backup_state; /*是否在backup*/ dulint online_backup_lsn; /*backup时的lsn*/ UT_LIST_BASE_NODE_T(log_group_t) log_groups; }log_t; ~~~ ### 3.3.1各种LSN之间的关系和分析 从上面的结构定义可以看出有很多LSN相关的定义，那么这些LSN直接的关系是怎么样的呢？理解这些LSN之间的关系对理解整个重做日志系统的运作机理会有极大的信心。以下各种LSN的解释： lsn                        当前log系统最后写入日志时的LSN flush_lsn                  redolog buffer最后一次数据刷盘数据末尾的LSN，作为下次刷盘的起始LSN written_to_some_lsn       单个日志组最后一次日志刷盘时的起始LSN written_to_all_lsn         所有日志组最后一次日志刷盘是的起始LSN last_checkpoint_lsn        最后一次建立checkpoint日志数据起始的LSN next_checkpoint_lsn        下一次建立checkpoint的日志    数据起始的LSN,用log_buf_pool_get_oldest_modification获得的 archived_lsn               最后一次归档日志数据起始的LSN next_archived_lsn          下一次归档日志数据的其实LSN   **关系图如下：**  ### 3.3.2偏移量的分析 log_t有各种偏移量，例如：max_buf_free、buf_free、flush_end_offset、buf_next_to_write等。偏移和LSN不一样，偏移量是相对redo log buf其实位置的绝对偏移量，LSN是整个日志系统的序号。 max_buf_free        写入日志是不能超过的偏移位置，如果超过，将强制redo log buf写入磁盘 buf_free            当前日志可以写的偏移位置  buf_next_to_write   下一次redo log buf数据写盘的数据起始偏移,在所有刷盘IO完成后，其值和 flush_end_offset是一致的。 flush_end_offset    本次刷盘的数据末尾的偏移量，相当于刷盘时的buf_free,当flush_end_offset 超过max_buf_free的一半时会将未写入的数据移到                       redobuffer的最前面，这时buf_free和buf_next_to_write都将做调整 大小关系图如下：  ### 3.4内存结构关系图  ## 4.日志写入和日志保护机制 innodb有四种日志刷盘行为,分别是异步redo log buffer刷盘、同步redo log buffer刷盘、异步建立checkpoint刷盘和同步建立checkpoint刷盘。在innodb中，刷盘行为是非常耗磁盘IO的，innodb对刷盘做了一套非常完善的策略。 ### 4.1重做日志刷盘选项 在innodb引擎中有个全局变量srv_flush_log_at_trx_commit,这个全局变量是控制flushdisk的策略，也就是确定调不调用fsync这个函数，什么时候掉这个函数。这个变量有3个值。这三个值的解释如下： 0     每隔1秒由MasterThread控制重做日志模块调用log_flush_to_disk来刷盘，好处是提高了效率，坏处是1秒内如果数据库崩溃，日志和数据会丢失。 1     每次写入重做日志后，都调用fsync来进行日志写入磁盘。好处是每次日志都写入了磁盘，数据可靠性大大提高，坏处是每次调用fsync会产生大量的磁盘IO，影响数据库性能。 2     每次写入重做日志后，都将日志写入日志文件的page cache。这种情况如果物理机崩溃后，所有的日志都将丢失。 ### 4.2日志刷盘保护 由于重做日志是一个组内多文件重复写的一个过程，那么意味日志如果不及时写盘和创建checkpoint，就有可能会产生日志覆盖，这是一个我们不愿意看到的。在innodb定义了一个日志保护机制，在存储引擎会定时调用log_check_margins日志函数来检查保护机制。简单介绍如下： 引入三个变量 buf_age、checkpoint_age和日志空间大小.                 buf_age = lsn -oldest_lsn;          checkpoint_age =lsn - last_checkpoint_lsn;         日志空间大小 = 重做日志组能存储日志的字节数（通过log_group_get_capacity获得）； 当buf_age >=日志空间大小的7/8时，重做日志系统会将red log buffer进行异步数据刷盘，这个时候因为是异步的，不会造成数据操作阻塞。 当buf_age >=日志空间大小的15/16时,重做日志系统会将redlog buffer进行同步数据刷盘，这个时候会调用fsync函数，数据库的操作会进行阻塞。       当 checkpoint_age >=日志空间大小的31/32时,日志系统将进行异步创建checkpoint，数据库的操作不会阻塞。 当 checkpoint_age == 日志空间大小时，日志系统将进行同步创建checkpoint,大量的表空间脏页和log文件脏页同步刷入磁盘，会产生大量的磁盘IO操作。数据库操作会堵塞。整个数据库事务会挂起。 ## 5.总结       Innodb的重做日志系统是相当完备的，它为数据的持久化做了很多细微的考虑,它效率直接影响MySQL的写效率，所以我们深入理解了它便以我们去优化它，尤其是在大量数据刷盘的时候。假设数据库的受理的事务速度大于磁盘IO的刷入速度，一定会出现同步建立checkpoint操作，这样数据库是堵塞的，整个数据库都在都在进行脏页刷盘。避免这样的问题发生就是增加IO能力，用多磁盘分散IO压力。也可以考虑SSD这读写速度很高的存储介质来做优化。

在[表空间结构](http://blog.csdn.net/yuanrxdu/article/details/41925279)分析当中，我们知道innodb的最小物理存储分配单位是page页，在MySQL-3.23版本的源码中，页只有两种页，一种是index page，一种是undo page。其类型值定义在fil0fil.h当中。               FIL_PAGE_INDEX                         数据索引页，在表空间的inode page和xdes page都是属于这类。               FIL_PAGE_UNDO_LOG                事务回滚日志页。 在这里我们主要分析的是 index page，undo log page在事务部分来介绍。不管是index page还是undo log page都是由三部分组成，page_header、page_body、page_trailer三部分组成。针对index page来分析者三部分结构。  ## 1.page header page header是page的头信息，占用38个字节，分别存储以下信息:   FIL_PAGE_SPACE            4字节                        page所属的表空间的space id   FIL_PAGE_OFFSET           4字节                        page no，一般是在表空间的物理偏移量   FIL_PAGE_PREV              4 字节                       前一页的page no (B+tree的叶子节点是通过链表串起来的，有前后关系)   FIL_PAGE_NEXT              4字节                        后一页的page no   FIL_PAGE_LSN                 8字节                        更改记录时最大的redo log lsn，一般用在redo log恢复时使用   FIL_PAGE_TYPE               2字节                        page的类型   FIL_PAGE_FILE_FLUSH_LSN 8字节                    space文件最后被flush是的redo log lsn,这个值只会在space的第一个页中被设置   FIL_PAGE_ARCH_LOG_NO 4字节                      最后被归档的archive log file 序号，这个值只会在space的第一个页中被设置 ## 2.page trailer page trailer是在文件末尾的最后8个字节， 低位4个字节是用来表示page页中数据的checksum,高位4位是用来存储FIL_PAGE_LSN的部分信息，关于checksum的计算是通过buf_calc_page_checksum这个函数来结算得到的，基本是通过对page中数据作为参数用ut_fold_binary来快速计算得到。在后续的版本中，page checksum是可以选择其他算法来做计算。这两个字在页保存到物理磁盘的时会进行更行，在页从物理磁盘读取出来的时候会被校验。宗旨就是保证页的完整性。 ## 3.page body index page body是由5部分组成，分别是body header、recorders、free recorders、free heap和page directory 组成。body header的结构定义如下： ~~~ #define PAGE_N_DIR_SLOTS 0 /*page directory拥有的slot个数*/ #define PAGE_HEAP_TOP 2 /*heap中空闲位置的偏移量*/ #define PAGE_N_HEAP 4 /*heap中的记录数,所有分配出去的记录数，free rec + PAGE_N_RECS + 2*/ #define PAGE_FREE 6 /*指向page中空闲空间的偏移量*/ #define PAGE_GARBAGE 8 /*已删除的记录字节数,用于重分配*/ #define PAGE_LAST_INSERT 10 /*最后插入记录的位置*/ #define PAGE_DIRECTION 12 /*记录的操作方向,PAGE_LEFT PAGE_RIGHT PAGE_SAME_REC PAGE_SAME_PAGE PAGE_NO_DIRECTION*/ #define PAGE_N_DIRECTION 14 /*同一方向连续插入的记录数*/ #define PAGE_N_RECS 16 /*页中存在的记录数，不包括infimum和supremum*/ #define PAGE_MAX_TRX_ID 18 /*修改当前页最大的事务ID*/ #define PAGE_HEADER_PRIV_END 26 #define PAGE_LEVEL 28 /*当前页在索引树的层位置*/ #define PAGE_BTR_SEG_LEAF 36 /*B+树叶子节点所在段的segment header信息*/ define PAGE_BTR_SEG_TOP (36 + FSEG_HEADER_SIZE) /*B+树非叶子节点所在段的segment header信息*/ ~~~ innodb在把真个页可以用的空间当着一个heap,当需要插入记录的时候，首先会在PAGE FREE中找是否有合适的记录 可以用，如果没有，就会在PAGE_HEAP_TOP的偏移上分配一个指定大小的rec_t的记录块，并将记录案主键值插入到 recorders当中。那么recorders是通过什么样的方式组织的呢? ### 3.1记录的组织方式 在index page body中，rec（记录）组织方式采用的是单向链表的方式来组织的，最前面一个记录和最后面一个记录是innodb定义的虚拟记录，叫做infimum和supremum。这两个记录的物理物质是在body header后面紧接着的连个记录。 其偏移如下： ~~~ #define PAGE_DATA (PAGE_HEADER + 36 + 2 * FSEG_HEADER_SIZE) #define PAGE_INFIMUM (PAGE_DATA + 1 + REC_N_EXTRA_BYTES) /*本page中索引最小的记录位置*/ #define PAGE_SUPREMUM (PAGE_DATA + 2 + 2 * REC_N_EXTRA_BYTES + 8) /*本page中索引最大的记录位置*/ ~~~ 这两条记录在index page创建的时候就会被创建，参见page_create函数，其他的记录是插入在其之间，入下示意图：  ### 3.2body free list 除了有效记录以外，page中还有一类是之间使用过但被删除的记录，这类记录不会直接回收到heap中（因为rec是逻辑 顺序关系进行组织的，无法直接回收到heap中），innodb采用了page free recorders列表来组织和管理，通过 body header中的PAGE_FREE来进行定位，PAGE_FREE指向第一个被删除的rec记录的页内偏移量。 示意图如下：  body header除了用PAGE_FREE来管理释放的记录外，还使用了PAGE_GARBAGE来管理其空间大小，这个值表示所有删除的记录占用空间字节总和，以便删除的记录可以重复被使用，提高空间的使用率。 除了recorders和free recorders外，还有一个连续的空间，这个空间是用来做记录分配的，只有当free recorders中没有合适的记录空间的时候，才会在这个连续空间上分配记录。这个空间的地址偏移是在PAGE_HEAP_TOP中的。 ### 3.3directory slots innodb为了快速查找记录，在body的后面定义了一个称之为directory的目录槽（slots）,每个槽位占用两个字节，采用的是逆序存储，也就是说mifimum的槽位总是在body最后2个字节上，其他的一次类推。每个槽位可以存储多个纪录。以下是各种slot的记录数描述范围（n_owned）：

Infimum slot owned	只有一条记录
supremum slot owned	1到8条记录
普通slot owned	4到8条记录

如果普通slot在插入新的一条记录时，普通slot或者supremum管理的记录数是8，这个时候会对supremum进行split，产生一个slots，所以它的范围是从4开始。以下是directory的一个关系示意图:  从上可以看出，slot指向的rec中的owned代表的是向前有多少个rec属于这个slot管辖，中间被管辖的rec的owned = 0。通过directory的二分查找只能查到对应记录所属的slot，还需要通过owned内部的二分查找才能精确定位到对应的记录。这种设计的做法可以减小directory对page空间的占用，又能有很好查找的效率。关于slot相关的函数说明：   page_dir_split_slot                        slot分裂函数，当一个slot管辖的范围内插入新的记录后超出其最大管理的记                                                          录数，就会对其进行平均范围分裂。   page_dir_balance_slot                  slot均衡函数，当一个slot管辖的范围内有记录删除后，其管理的记录数小于                                                          它最小范围，就会和邻近的slot做均衡。 不管是均衡还是分裂，都是最大范围提高directory存储空间效率和记录查找效率。 ### 3.4index page结构关系图  ## 4页的操作 innodb的index page对记录的操作主要有3种：查找记录、插入记录、删除记录。关于page的操作实现在page0cur.* 当中，在这些操作的中，innodb定义了一个page_cur_t，也就是page的游标，它是个逻辑概念的游标，只在内存中 有效。这个page cur是指向当前操作的记录。定义如下： ~~~ typedef struct page_cur_struct { byte* rec; /*游标记录的指针*/ }page_cur_t; ~~~ 因为所有的page操作必须将page从物理磁盘读入到内存中进行逻辑页的构建，再使用page_cur来进行查找、插入、删除操作。 ### 4.1查询操作 我们知道在innodb的B+Tree索引搜索中，只能找到对应记录所在的index page，那么找到page后，会在页中进行记录查找，这个页内查找过程如下：   1.先通过key在page的directory slots中进行二分查找，找到key对应的slot   2.因为slot是管理多个记录（普通的slot owned = [4,8]),所以会再根据KEY在对应的slot管理的记录中一次二分查找，直到找到记录为止。 页内查找的实现在page0cur.c的page_cur_search_with_match函数当中，这个函数除了返回查找的记录以外，还会记录二分查找过程中匹配的字节数和经过的跳数。值得注意的是这个函数支持四种模式的查找，分别定义如下： ~~~ #define PAGE_CUR_G 1 /*大于查询*/ #define PAGE_CUR_GE 2 /*大于等于查询*/ #define PAGE_CUR_L 3 /*小于查询*/ #define PAGE_CUR_LE 4 /*小于等于查询*/ ~~~ ### 4.2插入操作 在记录插入之前，会通过要插入记录KEY找到要插入的位置，查找的模式是PAGE_CUR_LE，具体步骤如下： 1.通过记录的key和记录查找函数查找要插入的位置(操作page cur指向插入记录的前一个记录）       2.修改前后记录的关联关系和插入记录的关联关系       3.修改page游标方向计数器、page last insert       4.修改所在的slot的owned数值，如果超出范围，进行split slot       5.因为插入记录是对页进行修改，所以记录插入记录的mtr log。以便异常时对页的恢复。 插入记录的mtr log构造比较复杂，以下是它的结构示意图：  这里要解释的是mismach_index这个变量，innodb为了节省存储空间，前后两条记录会做相同比较，这个变量就是插入的记录和其前面的记录从开始位置相同字节数，这样rec data是存储了与之前记录不同的数据。 一条记录的插入示意图：  整记录插入过程在page0cur.c中的page_cur_insert_rec_low函数中实现的。 ### 4.3删除操作 记录删除也是首先会通过删除记录的key或者记录地址来确定操作page cur.操作步骤如下：   1.通过记录信息确定page cur   2.添加一条删除记录的mtr log   3.将记录前后对应关联关系进行删除和更改   4.设置page last insert和其他的头信息（n _rec）   5.将记录插入到body header free列表的起始位置，并修改PAGE_GARBAGE   6.设置所在slot的owned,如果小于管辖范围的最小值，进行slot的均衡化。 删除的mtr log格式如下：  删除记录示意图：  ## 5.小结 innodb的index page结构是一个高效利用空间的存储结构，不仅考虑到查询的速度，也考虑了合理的利用存储空 间的存储效率。innodb在这两者之间找到了比较好的平衡点。页除了提供基本的插入删除查询操作外，还提供批量 拷贝记录、批量删除记录等功能。当这些都是基于基本的插入删除操作之上的。批量操作函数如下：

page_copy_rec_list_end	将page中的rec之后的记录全部复制到new page,包括rec
page_copy_rec_list_start	将page中在rec之前的记录全部拷贝到new page当中,不包括rec
page_delete_rec_list_end	将page中的rec之后的记录全部删除,包括rec
page_delete_rec_list_start	将page中在rec之前的记录全部删除,不包括rec
page_move_rec_list_end	将page中rec之后的记录全部move到new page中，包括rec，这些记录在page是被删除的
page_move_rec_list_start	将page中rec之前的记录全部move到new page中，不包括rec，这些记录在page是被删除的

innodb提供这些函数主要是方便上层调用。通过分析page的结构可以很好的理解innodb的记录组织方式，也有利于去理解B+Tree的索引方式。索引页相关参考：[http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/](http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/)

innodb在实现表空间（table space）基于文件IO之上构建的一层逻辑存储空间管理，table space采用逻辑分层的结构：space、segment inode、extent和page.在实现层的逻辑使用了磁盘链表这种结构来管理逻辑关系。我们先来介绍磁盘链表。 ## 1.磁盘链表 磁盘链表的实现fut0lst.*文件当中， innodb为了管理表空间和索引模块，定义了一个基于磁盘的链表，主要是用来保存磁盘数据结构之间的关系。这个链表不是基于内存指针的，而是基于page no和boffset来做位置绑定的。在innodb中定义了一个fil_addr_t的结构来做描述： ~~~ typedef struct fil_addr_struct { ulint page; /*page在space中的编号*/ ulint boffset; /*page中的字节偏移量，在内存中使用2字节表示*/ }fil_addr_t; ~~~ fil_addr_t可以通过fut_get_ptr函数来获得对应node的内存位置(flst_node_t) flst_node_t可以通过buf_ptr_get_fsp_addr来确定fil_addr_t。 flst_node_t中存有12个字节的内容，前6个字节（page:4 boffset:2）表示相对自己前一个node的fil_addr_t信息，后6个字节表示相对自己后1个node的fil_addr_t。除了flst_node_t以外，磁盘链表还有一个头信息flst_base_node_t，头信息是一个节点个数FLST_LEN（4字节） + FLST_FIRST (6字节)+ FLST_LAST（6字节）. ### 1.1磁盘链表的结构关系  ## 2.space结构分析 在innodb的表空间中，所有的数据都是以page为单位来存储的，在space(表空间)中有两种 page: FSP_HDR/XDES Page、fseg inodes Page。每个page是以默认16KB的大小存储的， innodb在分配page的时候总以一个extent为单位一次性分配64个page。 ### 2.1 FSP HDR/XDES Page ### 2.1.1XDES结构分析（extent） 这个类型的page主要存储两类信息，前面112个字节存储的是File Space header信息，后面剩余的空间存储多个extent描述信息（XDES ），具体存储结构图如下：  只有space的第一个page会保存FSP header,其他的页是用0填充的。 每个XDES Page最大包含256个XDES descritptors Entry，每个XDES descritptors Entry对应的是一个extent。XDES descritptors Entry的结构描述如下：  File Segment ID                 是当前extent所属segment的ID   XDES list                         是磁盘双向链表的一个节点，分别指向前一个XDES entry的page位置和后一个                                             XDES entry的page位置   state                                 extent的状态, XDES_FREE、XDES_FREE_FRAG、XDES_FULL_FRAG、                                             XDES_FSEG,在为XDES_FSEG的时候，表示这个extent已经隶属于一个                                             Segment,extent在创建的时候会指定成XDES_FSEG状态。一个extent在刚                                             分配时的状态XDES_FREE.  bitmap                              当前extent的所有page的状态索引，一个page占用2 bit,第一个bit表示是否被使用                                            状态，第二个位表示是否并 清空状态，清空状态暂时好像没有用 到，都是TRUE。 ### 2.1.2 FSP Header            space id                    当前表空间的ID           size                    当前space最大可容纳的page数,文件扩大时才会改变这个值           limit                   当前space已经分配初始化的page数,包括空闲的和已经使用的           flag                    未起作用           frage used         FSP_FREE_FRAG列表中已经被使用的page数           free list              space中可用的extent对象列表，extent里面没有一个page被使用           frag free list      有可用碎叶page的extent列表，exntent里面有部分page被使用           frag full list       没有有可用page的extent列表，exntent里面全部page被使用           segment id        下一个可利用的segment id           full inode list     space当前完全占满的segment inode页列表           free inode list     space当前完全占满的segment inode页列表 ### 2.2 Fseg inode Page 这个页类型是存储fseg inode用的页，每个inode 占用192个字节，一个page存储有85个inode对象,结构如下：  在FIL Header后面紧接了12个字节，这个12个字节其实就是full inode list或则free inode list中的列表所以，分别表示前后的fil_addr_t。每个inode信息占用192个字节，里面分别管理对应的extent和fragment page。inode 结构如下：    fseg id                                    segment ID           not full used                          FSEG_NOT_FULL列表中的page数           FSEG_FREE                         inode中空闲的extent列表           FSEG_NOT_FULL               extent有部分page被占用，有部分page空闲的extent列表           FSEG_FULL                          完全占满的extent的列表           FSEG_MAGIC_N                  校验魔法字           fragment array                       一个长度为32的零散page索引存储的数组，如果这个数据满了.主要的作用是                                                            节省空间，例如在表刚建立时，不会分配一个完整的extent给表用，只会分配                                                            6个PAGE页，这时候就需要用fragment array来管理。 ## 3.space结构图 ### 3.1space框架关系图  ### 3.2模块关系示意图  ## 4.space的inode、extent和page分配流程 innodb的space中，inode、extent和page之间的关系是环环相扣的，inode对应的是segment，extent对应的是区，page是页，也是表空间的最小分配单位。一个page在MySQL中默认是16KB大小，一个extent管理64个page,大小为1M，而inode可以管理很多extent加32个frag page（碎页）。frag page是为了节省空间而定义的。在了解了以上基本的概念后，我们开始分析inode的分配、extent的分配和page的分配过程。 ### 4.1 inode的分配流程 通过inode page的介绍我们可以知道，inode信息一定是存储在inode page中的，在分配inode的时候，一定是从inode page中获取空闲的inode。如果没有inode page可以使用，会先去在space的free list得到一个inode page（在函数fsp_alloc_seg_inode_page），然后再在这个inode page获得空闲的inode。在这个过程中会涉及到两个磁盘链表：FSP_SEG_INODES_FREE和FSP_SEG_INODES_FULL，这两个队列是管理inode page的，如果没有空闲inode的inode page是放在FSP_SEG_INODES_FULL中的，如果还有空闲inode的inode page是放在FSP_SEG_INODES_FREE中。一个inode页包含85个inode信息。以下是inode 分配示意图：    第1步：在FSP_SEG_INODES_FREE为空时，向space默认的头页中获取一个inode page，对应函数fsp_alloc_seg_inode_page   第2步：在申请inode时，如果FSP_SEG_INODES_FREE有可以的inode page,从inode page或的一个inode，对应函数fsp_alloc_seg_inode   第3步：如果在申请inode后，inode所处的inode page已经没有空闲的inode了，会将这个inode page放入FSP_SEG_INODE_FULL,并将其从FSP_SEG_INODES_FREE中删除。   第4步：如果inode管理的所有的页都是空闲，那么这个inode状态会被置为空闲状态，这个时候会将这个inode page从FSP_SEG_INODE_FULL移 到FSP_SEG_INODES_FREE中;这个过程只有在segment删除的时候才会调用。对应的函数fsp_free_seg_inode ### 4.2extent的分配流程 extent的分配方式有两种，一种是通过inode进行申请分配，一种是通过fragment碎片方式申请分配。inode分配方式是当inode中没有空闲可用的extent的时候，会向space free list中申请1个或者5个extent进行管理，如果当inode管理的extent数量小于40时，每次只会申请1个extent,如果超过这个大小，就会一次申请5个extent，这个过程会涉及到inode的FSEG_FREE、FSEG_NOT_FULL和FSEG_FULL三个磁盘链表。第二种申请方式是分配frag page时，是直接对extent进行申请，这其中会涉及到FSP_FREE_FRAG和FSP_FULL_FRAG这两个磁盘链表。以下是分配示意图：  上图中，1~7是属于inode申请分配流程， 8~12是属于frag page的申请extent方式   1: 当inode的free list为空，如果需要使用申请使用新的extent，innodb会从space free list获得空闲的extent加入到inode free list当中。   2: 当inode  free list中有extent,如果申请使用新的extent，只只需要从inode free list中拿取，并将extent移到inode not full当中。   3:只是通过inode方式申请页的一个操作，这个时候extent有足够多的空闲page.   4: 当extent中没有空闲的page时，会将这个extent从inode not full中转移到inode full当中。   5: 当一个page释放时，这个page所处的extent是一个完全占用的且被inode管理的extent,那么page释放后，就会将这个extent从inode full移到inode not full   6:当一个page释放时，这个page所处的extent有且只有这一个page被占用，那么page释放后,这个extent就会归还给inode list.并且会直接进行 7将extent归还给space free list. ** 8~12和以上步骤类似** ### 4.3page的分配流程 page的申请分配是基于inode 申请和extent申请的基础上，页的申请有外部通过inode方式申请，也有通过fragment page方式申请。fragment方式申请相对比较简单，就不在表述，源码中很清晰。inode方式分配是比较复杂的，其主要实现是在fseg_alloc_free_page_low和fseg_free_page_low这两个函数。在fseg_alloc_free_page_low函数中实现了7种情况获得inode中的page.   1. 指定的inode的hint位置的页是空闲状态，直接返回对应的page   2.descr是空闲状态，但segment inode中的空闲page数量 < 1/8,且碎片页被全部用完,为其分配一个extent,并获得hint对应的page   3.如果descr不是空闲状态，且segment inode中的空闲page数量 < 1/8,在inode当中获得一个空闲的extent，并且将这个extent descr对应的页返回。   4.descr是XDES_FSEG状态，且这个extent中还有空闲page,从其中获取一个page.   5.除了以上情况外，如果descr不是空闲的，但是inode还有其他的空闲extent,从其他的extent获得一个空闲。   6.如果其他的extent没有空闲页，但是fragment array还有空闲的碎片page，从空闲的碎片page中获得一个空闲页。   7.如果连碎页也没有，直接申请分配一个新的extent，并在其中获取一个空闲的page. ## 5.综述 table space的实现在fsp0fsp.*文件当中，也依赖于page0page.*  fil0fil.* 等文件。innodb在存储上，定义了最小的存储单位就是page，space在设计这些层关系，都是为了更为高效和合理的管理page。space可以和其他表存在同一个数据库文件中，也可以一张表一个文件存储。这取决于MySQL的配置。分析space的结构和工作原理有利于我们理解innodb的存储方式，其后面理解索引、锁和事务提供有力的基础。上面也说到最小的存储单位是page，我将在下一章节中单独来介绍数据page的存储方式和其工作原理。

  日志是innodb一个非常重要的模块，在innodb中有两类日志：redo log和undo log。其中redolog日志是用来做数据异常恢复和数据库重启时页数据同步恢复的，redo log是建立在在mini transaction基础上。数据库在执行事务时，通过minitransaction产生redo log来保证事务的持久性。 ## 1.mini transaction三个协议        mini-transcation是用来实现innodb的物理逻辑日志的写入和页恢复的，通过mini-transcation来保证并发事务操作和数据库异常是页的一致性。为了得到页的一致性，mini-transaction遵循以下三个协议:        1. The FIX Rules      2. Write-Ahead Log      3. Force-log-at-commit ### 1.1The FIX Rules    The FIX Rules规定如下：              修改一个页需要获得该页的x-latch             访问一个页是需要获得该页的s-latch或者x-latch             持有该页的latch直到修改或者访问该页的操作完成 ### 1.2Write-Ahead Log       Write-Ahead Log的意思就是如果一个页操作在写入到持久设备时，必须内存中相对应的日志写入到持久化设备中。每个页有一个LSN,每次页修改需要维护这个LSN,当一个页需要写入到持久化设备时，要求内存中小于该页LSN的日志先写入到持久化设备中。日志写完后，先Fixed这个页的latch，再将内存中的页刷盘。完成刷盘后，释放页latch。这里遵循The FIX Rules协议。 ### 1.3 Force-log-at-commit      一个事务可以同时修改了多个页，Write-AheadLog单个数据页的一致性，无法保证事务的持久性。Force -log-at-commit要求当一个事务提交时，其产生所有的mini-transaction日志必须刷到持久设备中。这样即使在页数据刷盘的时候宕机，也可以通过日志进行redo恢复。 ## 2 mini-transaction的日志实现       innodb是采用mini-transaction来构建操作的物理逻辑日志的，在事务执行的时候，会通过mtr来保证页的数据一致性和持久性。mini-transaction是通过一个mtr_t的结构来实现mini-transaction的三个协议。mtr_t的定义如下： ~~~ typedef struct mtr_struct { ulint state; /*mtr的状态，MTR_ACTIVE、MTR_COMMITING、MTR_COMMITTED*/ dyn_array_t memo; /*正在持有的latch列表*/ dyn_array_t log; /*mtr产生的日志数据*/ ibool modifications; /*是否修改了页*/ ulint n_log_recs; /*log操作页的个数*/ ulint log_mode; /*log操作模式，MTR_LOG_ALL、MTR_LOG_NONE、MTR_LOG_SHORT_INSERTS*/ dulint start_lsn; /*mtr起始的LSN*/ dulint end_lsn; /*mtr结束的LSN*/ ulint magic_n; /*魔法字*/ }mtr_t; ~~~ 其中成员memo是个latch持有状态的数组列表，采用的是dyn_array_t的动态内存结构来保存的，每个单元存储的是mtr_memo_slot_t这样的结构。定义如下：      ~~~ typedef struct mtr_memo_slot_struct { ulint type; /*latch的类型值*/ void* object; /*latch对象句柄，可以是rw_lock_t或者buf_block_t*/ }mtr_memo_slot_t; ~~~ latch类型如下：   MTR_MEMO_PAGE_S_FIX         /*rw_locks-latch*/   MTR_MEMO_PAGE_X_FIX         /*rw_lockx-latch*/   MTR_MEMO_BUF_FIX               /*buf_block_t*/   MTR_MEMO_S_LOCK               /*rw_lock s-latch*/   MTR_MEMO_X_LOCK               /*rw_lock x-latch*/ memo的latch管理接口   mtr_memo_push                                       获得一个latch，并将状态信息存入mtr memo当中   mtr_release_s_latch_at_savepoint      释放memo偏移savepoint的slot锁状态   mtr_memo_contains                          判断锁对象是否在memo当中   mtr_memo_slot_release                    释放slot锁的控制权   mtr_memo_pop_all                           释放所有memo中的锁的控制权 mt_t中的log成员是也是一个dyn_array_t动态结构的内存，用来保存mtr产生的日志信息。日志的写入是通过mtr0log.h来写入的。这里指的一提的是日志格式，日志格式是有日志头和日志体组成，日志头信息是由type、space和page no组成,由mlog_write_initial_log_record_fast函数写入到mtr_t的log中的。以下是一个比较具体的示意图:       log body的数据写入是通过mtr0log.h中的日志写入方法进行写入的。每写入一跳操作日志，n_log_recs会加1. 标识modifications是标识是否有page的数据改动，如果有，在mtr_commit调用时会先将mtr->log刷盘，然后释放mtr所有的所控制权。日志会一定会在mtr结束时刷盘，这符合Force-log-at-commit的规定。日志写入调用的是log_write_low这个函数。 ### 2.1 mtr_t的内存结构关系图  ## 3 总结 mini transaction是innodb对ACID中的持久性的最小保证单元，所有涉及到事务执行、页数据刷盘、redo log数据恢复等都需要进行mini transaction的构造和执行。几乎所有的模块都涉及到mini transaction,例如：btree、page、事务、inser tbuffer、redo-log等，d对mini transcaion的理解不能孤立的去看源代码，应该结合redo log、page相关的代码了解。它是理解innodb工作原理的基石。

innodb作为数据库引擎，自然少不了对文件的操作，在innodb中所有需要持久化的信息都需要文件操作，例如：表文件、重做日志文件、事务日志文件、备份归档文件等。innodb对文件IO操作可以是煞费苦心，其主要包括两方面，一个是对异步io的实现，一个是对文件操作管理和io调度的实现。在MySQL-5.6版本的innodb还加入了DIRECT IO实现。做了这么多无非是优化io操作的性能。在innodb的文件IO部分中，主要实现集中在os_file.*和fil0fil.*两个系列的文件当中，其中os_file*是实现基本的文件操作、异步IO和模拟异步IO。fil0fil.*是对文件io做系统的管理和space结构化。下面依次来介绍这两个方面的内容. ## 1.系统文件IO 在innodb中，文件的操作是比较关键的，innodb封装了基本的文件操作，例如：文件打开与关闭、文件读写以及文件属性访问等。这些是基本的文件操作函数封装。在linux文件的读写方面，默认是采用pread/pwrite函数进行读写操作，如果系统部支持这两个函数，innodb用lseek和read、write函数联合使用来达到效果. 以下是innodb文件操作函数:   os_file_create_simple                        创建或者打开一个文件   os_file_create                                     创建或者打开一个文件，如果操作失败会重试，直到成功   os_file_close                                       关闭打开的文件   os_file_get_size                                   获得文件的大小   os_file_set_size                                   设置文件的大小并以0填充文件内容   os_file_flush                                        将写的内容fsync到磁盘   os_file_read                                        从文件中读取数据   os_file_write                                       将数据写入文件 innodb除了实现以上基本的操作以外，还实现了文件的异步IO模型，在Windows下采用的IOCP模型来进行处理（具 体可以见网上的资料），在linux下是采用aio来实现的，有种情况，一种是通过系统本身的aio机制来实现，还有一种是 通过多线程信号模拟来实现aio.这里我们重点来介绍，为了实现aio,innodb定义了slot和slot array,具体数据结构如下： ~~~ typedef struct os_aio_slot_struct { ibool is_read; /*是否是读操作*/ ulint pos; /*slot array的索引位置*/ ibool reserved; /*这个slot是否被占用了*/ ulint len; /*读写的块长度*/ byte* buf; /*需要操作的数据缓冲区*/ ulint type; /*操作类型：OS_FILE_READ OS_FILE_WRITE*/ ulint offset; /*当前操作文件偏移位置，低32位*/ ulint offset_high; /*当前操作文件偏移位置，高32位*/ os_file_t file; /*文件句柄*/ char* name; /*文件名*/ ibool io_already_done; /*在模拟aio的模式下使用，TODO*/ void* message1; void* message2; #ifdef POSIX_ASYNC_IO struct aiocb control; /*posix 控制块*/ #endif }os_aio_slot_t; typedef struct os_aio_array_struct { os_mutex_t mutex; /*slots array的互斥锁*/ os_event_t not_full; /*可以插入数据的信号，一般在slot数据被aio操作后array_slot有空闲可利用的slot时发送*/ os_event_t is_empty; /*array 被清空的信号，一般在slot数据被aio操作后array_slot里面没有slot时发送这个信号*/ ulint n_slots; /*slots总体单元个数*/ ulint n_segments; /*segment个数，一般一个对应n个slot，n = n_slots/n_segments，一个segment作为aio一次的操作范围*/ ulint n_reserved; /*有效的slots个数*/ os_aio_slot_t* slots; /*slots数组*/ os_event_t* events; /*slots event array，暂时没弄明白做啥用的*/ }os_aio_array_t; ~~~ 内存结构关系图:  ## 2.文件管理的内存结构 在innodb中定义三种文件类型：表空间文件(ibdata*)、重做日志文件(ib_logfile*)和归档文件(ib_arch_log*)。一般innodb在运行的过程中，会同时打开很多个文件，这就要求对文件进行系统的管理和控制。在innodb中定义了一套基于fil_system_t、fil_space_t和fil_node_t的内存管理结构。每个文件对应的是一个fil_node_t,fil_node是存储的最小单元，多个同一模块的fil_node组成一个fil_space_t，所有的space组成一个fil_system_t，在innodb引擎里，只有一个fil_system_t对象。 fil_system_t管理着全局的文件操作资源，例如：文件打开的数量、打开文件的信号控制、fil_space_t的管理和索引等。以下是fil_system_t的结构定义： ~~~ typedef struct fil_system_struct { mutex_t mutex; /*file system的保护锁*/ hash_table_t* spaces; /*space的哈希表，用于快速检索space,一般是通过space id查找*/ ulint n_open_pending; /*当前有读写IO操作的fil_node个数*/ ulint max_n_open; /*最大允许打开的文件个数*/ os_event_t can_open; /*可以打开新的文件的信号*/ UT_LIST_BASE_NODE_T(fil_node_t) LRU; /*最近被打开操作过的文件,用于快速定位关闭的fil_node*/ UT_LIST_BASE_NODE_T(fil_node_t) space_list; /*file space的对象列表*/ }fil_system_t; ~~~ 值得注意的是space的哈希表和LRU,这里为什么会出现用hash table来索引space呢？因为在实际的数据库系统中，fil_space_t是会非常多的，用哈希表能快速定位到需要操作的fil_space_t。LRU是用于保存最近被打开和被操作过的fil_node,为了避免频发的关闭和打开文件，LRU保存一定数量（500）的最近打开过的文件，这样可以提高系统的效率。 fil_space_t是用于管理同一模块的file_node,上层模块操作文件不是以文件名来做操作关联的，而是用space_id， 也就是说，所有的文件操作是通过space为单位进行操作的。fil_space支持三种类型，分别是：       FIL_TABLESPACE                表空间space       FIL_LOG                                  重做日志space       FIL_ARCHI_LOG                   归档日志space fil_space_t的定义如下： ~~~ struct fil_space_struct { char* name; /*space名称*/ ulint id; /*space id*/ ulint purpose; /*space的类型，主要有space table, log file和arch file*/ ulint size; /*space包含的页个数*/ ulint n_reserved_extents; /*预留的页个数*/ hash_node_t hash; /*chain node的HASH表*/ rw_lock_t latch; /*space操作保护锁,用于多线程并发*/ ibuf_data_t* ibuf_data; /*space 对应的insert buffer*/ ulint magic_n; /*魔法校验字*/ UT_LIST_BASE_NODE_T(fil_node_t) chain; UT_LIST_NODE_T(fil_space_t) space_list; }; ~~~ fil_space通常是由一组文件组成，例如重做日志，一般是有3个文件组成一个group space用于重做日志记录。space通过成员latch可以支持多线程并发的。在innodb文件操作中，主要是通过space来做控制，以下是它的控制函数： fil_space_create                        创建一个fil_space fil_space_free                            销毁一个fil_space fil_space_truncate_start          从space中删除fil_node，删除的总数据长度为trunc_len fil_node_create                          创建一个fil_node并加入到对应的space当中 fil_space_get_size                    获得space的空间大小，以page为单位记 fil_io                                            指定space的io操作 fil_aio_wait                                aio异步方式的io操作等待,并根据完成状态更新space状态 fil_flush                                      指定space进行数据刷盘 fil_node_t是对单个文件进行管理，主要是管理文件的打开状态、文件句柄信息、文件的page数量和更新状态等。 其结构定义如下： ~~~ struct fil_node_struct { char* name; /*文件路径名*/ ibool open; /*文件是否被打开*/ os_file_t handle; /*文件句柄*/ ulint size; /*文件包含的页个数，一个页是16K*/ ulint n_pending; /*等待读写IO操作的个数*/ ibool is_modified; /*是否有脏也存在，flush是根据这个标志进行刷盘的*/ ulint magic_n; /*魔法校验字*/ UT_LIST_NODE_T(fil_node_t) chain; UT_LIST_NODE_T(fil_node_t) LRU; }; ~~~ 值得注意的是当外部调用了fil_flush时，判断一个fil_node是否需要刷盘的必要条件是：   文件必须是打开的                                    open = TRUE   文件存在内存和硬盘数据不一致            is_modified = TRUE 了解了他们三者的基本定义后，那他们之间的关系是怎么的？不用文字叙述，看下面的内存结构关系图：  在了解了他们之间的基本关系后，那么一个io操作是怎么进行的？在这个模型里，一个io操作提交和被运行是比较复杂的。具体流程如下：   1.外部模块提交一个fil_io, 先会进行基本的io操作类型的判断和文件打开方式的判断。   2.然后进行对正在进行io操作的计数做判断，如果正在进行的io数量 > 最大文件打开数量的四分之三，唤醒所有aio的操作线程进行io处理，并进行sleep等待。   3.如果正在进行的io数量 = 最大文件打开数量,唤醒所有的aio操作线程进行io处理，并等待fil_system_t的can_open信号。   4.如果不满足2和3，找到需要受理io操作的space和node,并打开node对应的文件，打开文件时会对打开文件数量限制做判断，如果当前打开文件操作io的数量 + LRU里已经打开文件的数量>= 最大文件打开数量时，会取出LRU中最后一个fil_node进行文件关闭。然后在对新的io操作的fil_node文件进行打开。   5.fil_node文件打开后，调用os_aio进行io操作提交，然后等待io操作完成   6. io操作完成后，将完成io操作的fil_node放入LRU的第一个位置，并更改对应的fil_system/fil_space/fil_node的状态，最后触发一个fil_system的can open信号。   7.监听can_open的线程收到这个信号后，会跳到第4步进行自己的io操作提交。 流程图如下：  ## 3总结 总体来说，innodb的文件IO涉及到知识面很多，可以能短时间无法完全理解透彻，一般在阅读源码的时候可以做一些基本的单元测试，这样有助于理解。弄清楚innodb的文件IO操作是非常有必要的，因为文件IO操作模块直接影响对innodb的日志系统的理解、表空间系统的理解。而且Innodb在文件IO模块的改进还是比较大的，尤其是引入Direct IO后。Direct IO很多数据库都在用这个技术，除了innodb,oracle和淘宝的oceanbase都使用了这个技术, 关于Direct IO网络上资料很多，可以自行结合MySQL-5.6的innodb来做研究。

innodb是一个多线程并发的存储引擎，内部的读写都是用多线程来实现的，所以innodb内部实现了一个比较高效的并发同步机制。innodb并没有直接使用系统提供的锁(latch)同步结构，而是对其进行自己的封装和实现优化，但是也兼容系统的锁。我们先看一段innodb内部的注释（MySQL-3.23）: Semaphore operations in operating systems are slow: Solaris on a 1993 Sparc takes 3 microseconds (us) for a lock-unlock pair and Windows NT on a 1995 Pentium takes 20 microseconds for a lock-unlock pair. Therefore, we have toimplement our own efficient spin lock mutex. Future operating systems mayprovide efficient spin locks, but we cannot count on that. 大概意思是说1995年的时候，一个Windows NT的 lock-unlock所需要耗费20us,即使是在Solaris 下也需要3us,这也就是他为什么要实现自定义latch的目的,在innodb中作者实现了系统latch的封装、自定义mutex和自定义rw_lock。下面我们来一一做分析。 ## 1 系统的mutex和event   在innodb引擎当中，封装了操作系统提供的基本mutex（互斥量）和event（信号量），在WINDOWS下的实现暂时不做记录，主要还是对支持POSIX系统来做介绍。在POSIX系统的实现是os_fast_mutex_t和os_event_t。os_fast_mutex_t相对简单，其实就是pthread_mutex。定义如下： ~~~ typedef pthread_mutex os_fast_mutex_t; ~~~ 而os_event_t相对复杂，它是通过os_fast_mutex_t和一个pthread_cond_t来实现的，定义如下： ~~~ typedef struct os_event_struct { os_fast_mutex_t os_mutex; ibool is_set; pthread_cond_t cond_var; }os_event_t; ~~~ 以下是os_event_t的两线程信号控制的例子流程：  对于系统的封装，最主要的就是os_event_t接口的封装，而在os_event_t的封装中，os_event_set、os_event_reset、os_event_wait这三 个方法是最关键的。 ## 2 CPU原子操作 在innodb的mutex(互斥量)的实现中，除了引用系统的os_mutex_t以外，还使用了原子操作来进行封装一个高效的mutex实现。在 系统支持原子操作的情况下，会采用自己封装的mutex来做互斥，如果不支持，就使用os_mutex_t。在gcc 4.1.2之前，编译器是 不提供原子操作的API的，所以在MySQL-.3.23的innodb中自己实现了一个类似__sync_lock_test_and_set的实现，代码是采用 了汇编实现： ~~~ asm volatile("movl $1, %%eax; xchgl (%%ecx), %%eax" : "=eax" (res), "=m" (*lw) : "ecx" (lw)); ~~~ 这段代码是什么意思呢?其实就是将lw的值设置成1,并且返回设置lw之前的值(res),这个过程都是CPU需要回写内存的，也就是CPU和内存是完全一致的。除了上面设置1以外，还有一个复位的实现，如下： ~~~ asm volatile("movl $0, %%eax; xchgl (%%ecx), %%eax" : "=m" (*lw) : "ecx" (lw) : "eax"); ~~~ 这两个函数交叉起来使用，就是gcc-4.1.2以后的__sync_lock_test_and_set的基本实现了。在MySQL-5.6的Innodb引擎当中，将以上汇编代码采用了__sync_lock_test_and_set代替，我们可以采用原子操作实现一个简单的mutex. ~~~ #define LOCK() while(__sync_lock_test_and_set(&lock, 1)){} #define UNLOCK() __sync_lock_release(&lock) ~~~ 以上就是一个基本的无锁结构的mutex，在linux下测试确实比pthread_mutex效率要高出不少。当然在innodb之中的mutex实现不会仅仅这么简单，需要考虑的因素还是比较多的，例如：同线程多次lock、lock自旋的周期、死锁检测等。 ## 3 mutex的实现 在innodb中，带有原子操作的mutex自定义互斥量是基础的并发和同步的机制，目的是为了减少CPU的上下文切换和提供高效率，一般mutex等待的时间不超过100微秒的条件下，这种mutex效率是非常高的。如果等待的时间长，建议选择os_mutex方式。虽然自定义mutex在自旋时间超过自旋阈值会进入信号等待状态，但是整个过程相对os_mutex来说，效率太低，这不是自定义mutex的目的。自定义mutex的定义如下： ~~~ struct mutex_struct { ulint lock_word; /*mutex原子控制变量*/ os_fast_mutex_t os_fast_mutex; /*在编译器或者系统部支持原子操作的时候采用的系统os_mutex来替代mutex*/ ulint waiters; /*是否有线程在等待锁*/ UT_LIST_NODE_T(mutex_t) list; /*mutex list node*/ os_thread_id_t thread_id; /*获得mutex的线程ID*/ char* file_name; /*mutex lock操作的文件/ ulint line; /*mutex lock操作的文件的行数*/ ulint level; /*锁层ID*/ char* cfile_name; /*mute创建的文件*/ ulint cline; /*mutex创建的文件行数*/ ulint magic_n; /*魔法字*/ }; ~~~ 在自定义mute_t的接口方法中，最核心的两个方法是:mutex_enter_func和mutex_exit方法   mutex_enter_func                    获得mutex锁，如果mutex被其他线程占用，先会自旋SYNC_SPIN_ROUNDS,然后                                                        再等待占用锁的线程的信号   mutex_exit                                 释放mutex锁，并向等待线程发送可以抢占mutex的信号量 ### 3.1 mutex_enter_func流程图：  以上流程主要是在mutex_spin_wait这个函数中实现的，从其代码中可以看出，这个函数是尽力让线程在自旋周期内获得锁，因为一旦进入cell_wait状态，至少的耗费1 ~ 2次系统调用，在cell_add的时候有可能触发os_mutex_t的锁等待和一定会event_wait等待。这比系统os_mutex效率会低得多。如果在调试状态下，获得锁的同时会向thread_levels的添加一条正在使用锁的信息，以便死锁检查和调试。 ### 3.2 mutex_exit流程图  ### 3.4 mutex_t的内存结构关系图  3.4mutex获得锁和释放锁的示意图  ## 4 rw_lock的实现 innodb为了提高读的性能，自定义了read write lock，也就是读写锁。其设计原则是：   1、同一时刻允许多个线程同时读取内存中的变量   2、同一时刻只允许一个线程更改内存中的变量   3、同一时刻当有线程在读取变量时不允许任何线程写存在   4、同一时刻当有线程在更改变量时不允许任何线程读，也不允许出自己以外的线程写（线程内可以递归占有锁）。   5、当有rw_lock处于线程读模式下是有线程写等待，这时候如果再有其他线程读请求锁的时，这个读请求将处于等待前面写完成。 从上面5点我们可以看出，rw_lock在被占用是会处于读状态和写状态，我们称之为S-latch(读共享)和X-latch（写独占），《MySQL技术内幕：innodb引擎》对S-latch和X_latch的描述如下： | S-latch | X-latch | |-----|-----| | S-latch | 兼容 | 不兼容 | | X-latch | 不兼容 | 不兼容 | innodb中的rw_lock是在建立在自定义mutex_t之上的，所有的控制是基于mutex和thread_cell的。 以下是rw_lock_t的结构定义： ~~~ struct rw_lock_struct { ulint reader_count; /*获得S-LATCH的读者个数,一旦不为0，表示是S-LATCH锁*/ ulint writer; /*获得X-LATCH的状态，主要有RW_LOCK_EX、RW_LOCK_WAIT_EX、 RW_LOCK_NOT_LOCKED， 处于RW_LOCK_EX表示是一个x-latch 锁,RW_LOCK_WAIT_EX的状态表示是一个S-LATCH锁*/ os_thread_id_t writer_thread; /*获得X-LATCH的线程ID或者第一个等待成为x-latch的线程ID*/ ulint writer_count; /*同一线程中X-latch lock次数*/ mutex_t mutex; /*保护rw_lock结构中数据的互斥量*/ ulint pass; /*默认为0，如果是非0，表示线程可以将latch控制权转移给其他线程， 在insert buffer有相关的调用*/ ulint waiters; /*有读或者写在等待获得latch*/ ibool writer_is_wait_ex; UT_LIST_NODE_T(rw_lock_t) list; UT_LIST_BASE_NODE_T(rw_lock_debug_t) debug_list; ulint level; /*level标示，用于检测死锁*/ /*用于调试的信息*/ char* cfile_name; /*rw_lock创建时的文件*/ ulint cline; /*rw_lock创建是的文件行位置*/ char* last_s_file_name; /*最后获得S-latch时的文件*/ char* last_x_file_name; /*最后获得X-latch时的文件*/ ulint last_s_line; /*最后获得S-latch时的文件行位置*/ ulint last_x_line; /*最后获得X-latch时的文件行位置*/ ulint magic_n; /*魔法字*/ }; ~~~ 在rw_lock_t获得锁和释放锁的主要接口是:rw_lock_s_lock_func、rw_lock_x_lock_func、rw_lock_s_unlock_func、rw_lock_x_unlock_func四个关键函数。 其中rw_lock_s_lock_func和rw_lock_x_lock_func中定义了自旋函数，这两个自旋函数的流程和mutex_t中的自旋函数实现流程是相似的，其目的是要在自旋期间就完成锁的获得。具体细节可以查看sync0rw.c中的rw_lock_s_lock_spin/rw_lock_x_lock_func的代码实现。从上面结构的定义和函数的实现可以知道rw_lock有四种状态： RW_LOCK_NOT_LOCKED                    空闲状态 RW_LOCK_SHARED                             处于多线程并发都状态 RW_LOCK_WAIT_EX                            等待从S-latch成为X-latch状态 RW_LOCK_EX                                       处于单线程写状态 以下是这四种状态迁移示意图：  通过上面的迁徙示意图我们可以很清楚的了解rw_lock的运作机理，除了状态处理以外，rw_lock还为debug提供了接口，我们可以通过内存关系图来了解他们的关系：  ## 5 死锁检测与调试 innodb除了实现自定义mutex_t和rw_lock_t以外，还对这两个类型的latch做了调试性死锁检测， 这大大简化了innodb的latch调试，latch的状态和信息在可以实时查看到，但这仅仅是在innodb的调试 版本中才能看到。与死锁检测相关的模块主要是mutex level、rw_lock level和sync_cell。latch level相关的定义： ~~~ /*sync_thread_t*/ struct sync_thread_struct { os_thread_id_t id; /*占用latch的thread的id*/ sync_level_t* levels; /*latch的信息，sync_level_t结构内容*/ }; /*sync_level_t*/ struct sync_level_struct { void* latch; /*latch句柄，是mute_t或者rw_lock_t的结构指针*/ ulint level; /*latch的level标识ID*/ }; ~~~ 在latch获得的时候，innodb会调用mutex_set_debug_info函数向sync_thread_t中加入一个latch被获得的状态信息，其实就是包括获得latch的线程id、获得latch的文件位置和latch的层标识（具体的细节可以查看mutex_enter_func和mutex_spin_wait）。只有占用了latch才会体现在sync_thread_t中，如果只是在等待获得latch是不会加入到sync_thread_t当中的。innodb可以通过sync_thread_levels_empty_gen函数来输出所有latch等待依赖的cell_t序列，追踪线程等待的位置。 ### 5.1sync_thread_t与sync_level_t的内存结构关系:  sync_thread_level_arrays的长度是OS_THREAD_MAX_N（linux下默认是10000），也就是和最大线程个数是一样的。 levels的长度是SYNC_THREAD_N_LEVELS（10000）。 ### 5.2死锁与死锁检测 什么是死锁，通过以下的例子我们可以做个简单的描述：   线程A                                        线程B   mutex1    enter                mutex2        enter   mutex2    enter                mutex1        enter   执行任务                           执行任务   mutex2    release             mutex1          release   mutex1    release            mutex2           release  上面两个线程同时运行的时候，可能产生死锁的情况，就是A线程获得了mutex1正在等待mutex2的锁，同时线程2获得了mutex2正在等待mutex1的锁。在这种情况下，线程1在等线程2，线程2在等线程就造成了死锁。 了解了死锁的概念后，我们就可以开始分析innodb中关于死锁检测的流程细节，innodb的检车死锁的实质就是判断 要进行锁的latch是否会产生所有线程的闭环，这个是通过sync_array_cell_t的内容来判断的。在开始等待cell信号的时候， 会判断将自己的状态信息放入sync_array_cell_t当中，在进入os event wait之前会调用sync_array_detect_deadlock来判 断是否死锁，如果死锁，会触发一个异常。死锁检测的关键在与sync_array_detect_deadlock函数。 以下是检测死锁的流程描述：   1、将进入等待的latch对应的cell作为参数传入到sync_array_detect_deadlock当中，其中start的参数和依赖的cell参 数填写的都是这个cell自己。   2、进入sync_array_detect_deadlock先判断依赖的cell是否正在等待latch,如果没有，表示没有死锁，直接返回. 如果有，先判断等待的锁被哪个线程占用，并获得占用线程的id,通过占用线程的id和全局的sync_array_t  等待cell数组状 态信息调用sync_array_deadlock_step来判断等待线程的锁依赖。   3、进入sync_array_deadlock_step先找到占用线程的对应cell,如果cell和最初的需要event wait的cell是同一 个cell,表示是一个闭环，将产生死锁。如果没有，继续将查询到的cell作为参数递归调用 sync_array_detect_deadlock执行第2步。这是个两函数交叉递归判断的过程。 在检测死锁过程latch句柄、thread id、cell句柄三者之间环环相扣和递归，通过latch的本身的状态来判断闭环死锁。在上面的第2步会根据latch是mutex和rw_lock的区别做区分判断，这是由于mutex和rw_lock的运作机制不同造成的。因为关系数据库的latch使用非常频繁和复杂，检查死锁对于锁的调试是非常有效的，尤其是配合thread_levels状态信息输出来做调试，对死锁排查是非常有意义的。 死锁示意图:  ## 6.总结 通过上面的分析可以知道innodb除了实现对操作系统提供的latch结构封装意外，还提供了原子操作级别的自定义latch，那么它为什么要实现自定义latch呢?我个人理解主要是减少操作系统上下文的切换，提高并发的效率。innodb中实现的自定义latch只适合短时间的锁等待（最好不超过50us）,如果是长时间锁等待，最好还是使用操作系统提供的，虽然自定义锁在等待一个自旋周期会进入操作系统的event_wait，但这无疑比系统的mutex lock耗费的资源多。最后我们还是看作者在代码中的总结： We conclude that the best choice is to set the spin time at 20 us. Then the system should work well on a multiprocessor. On a uniprocessor we have to make sure that thread swithches due to mutex collisions are not frequent, i.e., they do not happen every 100 us or so, because that wastes too much resources. If the thread switches are not frequent, the 20 us wasted in spin loop is not too much. 

在innodb中实现了自己的内存池系统和内存堆分配系统，在innodb的内存管理系统中，大致分为三个部分：基础的内存块分配管理、内存伙伴分配器和内存堆分配器。innodb定义和实现内存池的主要目的是提供内存的使用率和效率，防止内存碎片和内存分配跟踪和调试。我们先来看看他们的关系和结构。 以下是它的关系结构图：  上图中的： ut_mem_block块是基础内存管理 Buddy allocator是内存伙伴分配器  mem_heap是内存堆分配器 ## 1.基础内存管理 innodb中的内存分配和内存释放是通过统一的结构进行管理，具体的实现在ut0mem.h和ut0mem.c当中，其中最重要的就是对malloc和free的封装。通过一个链表结构体来管理已经分配的内存，结构体如下： ~~~ typedef ut_mem_block_struct { ulint size; /*这个被分配block的内存大小*/ ulint magic_n; /*节点魔法字，用于校验所用*/ UT_LIST_NODE_T(ut_mem_block_t) mem_block_list; /*block list node,指定prev node和next node*/ }; ~~~ 关于block的list定义是个全局的变量，UT_LIST_BASE_NODE_T(ut_mem_block_t) ut_mem_block_list;所有分配的block都会加入到这个list当中。在ut_malloc_low函数分配内存的时候会将分配的block加入到list当中，在ut_free的时候会所释放的内存所在的block从list当中删除。除了这两个函数以外，innodb还提供ut_free_all_mem函数来释放所有分配的block和统计分配内存的总数ut_total_allocated_memory功能。 基础内存管理的方法如下：       ut_malloc_low                    分配一个n长度的内存块，并将分配的块记录到ut_mem_block_list当中.       ut_malloc                            与ut_malloc_low功能相同，但是会用0初始化所分配的内存。       ut_free                                释放一个分配的内存块，并将其从ut_mem_block_list当中删除。       ut_free_all_mem                 释放ut_mem_block_list所有的内存块并清空ut_mem_block_list 以上函数是支持多线程并发操作的，也就是说是线程安全的。 innodb这样做的目的是保证所有malloc出去的内存都在 ut_mem_block_list当中，以便管理。   基础内存管理的结构如下：  ## 2.伙伴分配器 innodb的伙伴分配器是基于ut_malloc_low函数之上的内存管理器，在创建伙伴分配器时，innodb会一下用ut_malloc_low开辟一个很大的内存块，然后用伙伴分配来分配这个块的内存使用。innodb的伙伴分配器是基于2的基数为基础的管理方式，其buddy alloc pool的定义如下： ~~~ struct mem_pool_struct { byte* buf; /*整体内存的句柄*/ ulint size; /*整体内存大小*/ ulint reserved; /*当前分配出去的总内存大小*/ mutex mutex; /*多线程互斥量*/ UT_LIST_BASE_NODE_T(mem_area_t) free_list[64]; /*area_t链表数组,每个数组单元能管理2的i次方内存块列表，i是数组的下标*/ }； ~~~ ~~~ struct mem_area_struct { ulint size_and_free; /*area的内存大小（一定是2的次方），最后一个bit表示是否已经释放*/ UT_LIST_NODE_T(mem_area_t) free_list; /*area链表的上下area,因为buddy area是会分裂的，有可能多个*/ }; ~~~ mem_area_t是一个buddy的内存区域，也就是mem_area_struct。以下是一个32位机器管理1024字节内存块的buddy list分布：  每一个area是有mem_area_t头和可分配的内存（memory_buffer）确定的，memory_buffer的长度不小于mem_area_t头的长度，在32位机器上mem_area_t的头应该是16个字节（8字节对齐）。 ### 2.1mem_area_t的分裂 在内存分配的过程中，有可能会造成mem_area_t的分裂，还是以上面的例子来说，加入我们要分配一个200字节的内存，这时候伙伴分配器的分配流程是这样的：       1.找到一个离200+sizeof(mem_area_t)最近的2的i次方的数（256），确定i = 8，       2.在free_list[i]的列表中查找是否有空闲的node,如果有，将node职位no free.如果没有，对i + 1层执行查找是否有可用的内存，       3.在上面的例子中，i+1=9,free_list是空的，继续在i+2层找，一次类推，直到找到有node的层，也就是i = 10;       4.首先对10层进行分裂，分裂成两512大小的第9层节点，并从10删除area，在第9层加入2个512的node.       5.然后在对第9层的第一个节点进行分裂，分裂两个大小为256的第8层节点，并从第九层删除，在第8层加入2个节点。       6.将第一个256大小的area分配给对应的操作者，并置为no free标识。   以下是分配了一个200字节的内存池结构:  如果分配出去后的area_t会从free_list[i]链表中删除，也就是说在buddy上将是记录的。 ### 2.2mem_area_t的合并 如果200字节分配出去后，使用完毕会归还给buddy allocator,还是拿上面的例子来说，就会发生area合并的情况,步骤如下：   1.使用者归还伙伴分配的内存，首先会根据area_t的信息去找到自己的buddy,也就是第8层另外一个没有被分配的area.   2.找到buddy area后，判断buddy area是否是释放状态，如果是，触发合并，将自己和buddy area从第8层删除，合并成一个512大小的第9层area,   3.在重复1 ~ 2步，又会将自己和第九层另外一个buddy area合并成一个1024大小的第10层area. ### 2.3buddy allocator的接口函数:   mem_pool_create                构建一个buddy allocator   mem_area_alloc                   用buddy allocator分配一块内存   mem_area_free                    将一块内存归还给buddy allocator   mem_pool_get_reserved      获得buddy allocator已经使用的内存大小 ## 3内存分配堆(memory heap) innodb中的内存管理最终的体现形式是mem_heap_t内存分配与管理，所有关于内存分配的操作都会调用mem_heap的API方法，mem_heap_t的结构定义如下： ~~~ struct mem_block_info_struct { ulint magic_n; /*魔法字*/ char file_name[8]; /*分配内存的文件*/ ulint line; /*分配内存的文件所在行*/ ulint len; /*block的长度*/ ulint type; /*依赖的底层分配类型，有DYNAMIC、BUFFER、BTR_SEARCH三种类型*/ ibool init_block; /*是否是外部分配的内存块*/ ulint free; /*被占用的空间大小*/ ulint start; /*可分配内存的起始位置*/ byte* free_block; /*备用block,仅仅在BTR_SEARCH方式可用*/ UT_LIST_BASE_NODE_T(mem_block_t) base; UT_LIST_NODE_T(mem_block_t) list; }; ~~~ **备注：mem_block_info_struct/mem_block_info_t/mem_block_t/mem_heap_t是等价** mem_heap_t的内存结构如下：  关于mem_heap_t的几个要点：   1.一个mem_block_t最小空间不小于64字节，标准的大小是8KB,在非MEM_HEAP_BUFFER模式下分配的空间不大于page size - 200（page size一般为16KB）   2.mem_heap_t有三种类型，分别是DYNAMIC、BUFFER、BTR_SEARCH，在DYNAMIC模式下都是基于buddy allocator进行mem_block_t分配的，在BTR_SEARCH模式下，使用free_block来作为内存分配，在BUFFER模式下比较复杂，如果分配的内存大小< page size的一半时，使用buddy alloc,否则使用buf_frame的内存分配方式（这个是属于buf0buf.XX里面的方式，还未开始分析）。   3.mem_heap_t在分配新的mem_block_t的时候一定是分配一个heap最后节点大小的两倍，如果分配的大小超过MEM_MAX_ALLOC_IN_BUF（相当于一个page size）的时候，heap 类型判断，在不是DYNAMIC模式下，最大就是一个MEM_MAX_ALLOC_IN_BUF大小。如果其他模式下就是设置成MEM_BLOCK_STANDARD_SIZE标准大小，在这些限制外，如果需要分配的内存大于这些限制，以分配内存大小为准进行mem_block_t分配。分配好的mem_block_t总是加入到heap base list的最后，也就是heap堆栈的顶端。   4.mem_heap_t在释放mem_block_t时候总是从顶端开始释放，直到不能释放为止（mem_block_t没有被使用者归还）。在mem_block_t释放的时候也是需要参考DYNAMIC、BUFFER、BTR_SEARCH类型进行相对于的归还规则（和2要点是相对应的）。 **mem_heap_t函数方法说明:** mem_heap_create                                        用DYNAMIC模式创建一个mem_heap_t mem_heap_create_in_buffer                        用BUFFER模式创建一个mem_heap_t mem_heap_create_in_btr_search                 用BTR_SEARCH模式创建一个mem_heap_t mem_heap_free                                            释放mem_heap_t对象 mem_alloc                                                    创建在MEM_HEAP_DYNAMIC模式下，并分配一块指定大小的内存（在这种方式下mem_heap_t只会有一个mem_block_t） mem_free                                                      归还mem_heap_t分配的内存，并释放mem_heap_t mem_heap_alloc                                           在指定的mem_heap_t上分配一块内存 mem_heap_get_heap_top                            获得heap顶端块可使用内存的地址 mem_heap_empty                                        清空指定的mem_heap_t mem_heap_get_top                                     获得heap顶部的指定n大小的mem_block_t指针 mem_heap_free_top                                    释放heap顶部N大小的mem_block_t块 ## 4总结 innodb提供内存池和heap分配方式来统一管理内存，最主要的目的是提高内存的率。在MySQL-5.6的版本中，innodb提供两种选择，一种是使用innodb提供的内存池管理内存，还有一种是提供系统的malloc和free来作为内存管理。MySQL默认的是系统管理内存方式，一些有经验的DBA会使用系统的管理内存方式+TMalloc来做内存优化，借助TMalloc高效的内存管理方式实现MySQL的性能提升。

近一年来一直在分析关于数据库相关的源码，前段时间分析了levelDB的实现和BeansDB的实现，这两个数据库网络上分析的文章很多，也都比较分析的比较深，所以也就没有太多必要重复劳动。最近开始关注关系数据库和MYSQL，当然主要还是数据库存储引擎，首先我还是从innodb这个最流行的开源关系数据库引擎着手来逐步分析和理解。我一般分析源码的时候都是从基础的数据结构和算法逐步往上分析，遇到不明白的地方，自己按照源码重新输入一遍并做对应的单元测试，这样便于理解。对于Innodb这样的大项目，也应该如此，以后我会逐步将具体的细节和实现写到BLOG上。我分析Innodb是以MySQL-3.23为蓝本作为分析对象，然后再去比较5.6版本的改动来做分析的。这样做有个好处就是先理解相对基础的代码容易，在有了基本概念后再去理解最新的改动。以下是我对innodb基础的数据结构和算法的理解。 ## 1.vector innodb的vector是个动态数组的数据结构，和c++的STL用法相似，值得一提的是vector的内存分配可以通过函数指针来指定是从heap内存池堆上分配内存还是用OS自带的malloc来分配内存。内存分配器的结构为: ~~~ struct ib_alloc_t { ib_mem_alloc_t mem_malloc; //分配器的malloc函数指针 ib_mem_free_t mem_release; //分配器的free函数指针 ib_mem_resize_t mem_resize; //分配器的重新定义堆大小指针 void* arg; //堆句柄，如果是系统的malloc方式，这个值为NULL }; ~~~ vector内部集成了排序功能函数，其排序的算法是通过qsort（快速）来进行排序。 vector内存结构:   ## 2.内存list innodb的list数据结构是个标准的双向链表结构，ib_list_node_t当中有指向前一个node的prev和指向后一个 node的next，list的内存分配可以通过heap内存堆来分配，也可以通过系统的malloc来分配。就看是采用 ib_list_create_heap来创建list爱是永ib_list_create来创建list。但是内部的ib_list_node_t的内存分配是通过 heap来分配的。 ist的内存结构:  ## 3.FIFO-queue innodb的FIFO queue是个多线程的消息队列，可以有多个线程向queue中添加消息，可有多个线程同时读取queue中的消息并进行处理。queue的mutex是保证同时只有一个线程在操作（读或者写）queue的items链表,os_event是写线程完成后通知所有读线程可以进行queue的读事件，也就是说，只有向queue写完成一个消息，才会发送event信号给读线程。queue的消息缓冲区是采用ib_list_t来做存储的，一般写的时候写在list的最后，而读总是读取list的第一个。queue处理提供一直读取到消息为止的方法以外，也提供最长等待读取消息的方法，这样读取线程没有必要一直等待消息，可以在等待一段时间后去处理其他的任务。其C结构定义如下: ~~~ struct ib_wqueue_t { ib_mutex_t mutex; /*互斥量*/ ib_list_t* items; /*用list作为queue的载体*/ os_event_t event; /*信号量*/ }; ~~~ ## 4.哈希表 innodb中的哈希表的基本构造和传统的哈希表的构造是相似的，不同的就是innodb的哈希表采用的是自定义链式桶结构，而没有采用每个桶单元用传统的list来做碰撞管理。由于这个特性，innodb中的哈希表操作采用了一系列操作宏来做操作，这样做的目的是为了能泛型的对哈希表做操作，因为在innodb中，除了操作内存中的数据以外，还会操作隐射硬盘中的数据。以下是innodb的操作宏：       HASH_INSERT                                    插入操作       HASH_DELETE                                    删除操作       HASH_GET_FIRST                               获取指定HASH key对应cell的第一个数据单元       HASH_GET_NEXT                                获取cell_node对应的下一个单元       HASH_SEARCH                                   查找对应key的值       HASH_SEARCH_ALL                            遍历整个hash table并将每个数据单元为参数执行ASSERTION操作       HASH_DELETE_AND_COMPACT        删除操作并且优化和调整heap堆上的内存分配布局，使得heap效率更高       HASH_MIGRATE                                 将OLD_TABLE的数据单元合并到NEW_TABLE当中 这些宏在调用的时候都会指定数据的类型和Next函数名。 innodb的哈希表在多线程并发模式下也提供cell级粒度的锁，有mutex类型的锁，也有rw_lock类型的锁。在hash_create_sync_obj_func函数调用过程中，会创建一个n_sync_obj的锁数据单元，n_sync_obj必须是2的N次方。也就是说如果n_sync_obj = 8, 哈希表的n_cells = 19，那就至少两个cell公用一个锁。这是其他哈希表无法比拟的。 以下是hash table的结构定义： ~~~ struct hash_table_t { enum hash_table_sync_t type; /*hash table的同步类型*/ ulint n_cells; /*hash桶个数*/ hash_cell_t* array; /*hash桶数组*/ #ifndef UNIV_HOTBACKUP ulint n_sync_obj; union{ /*同步锁*/ ib_mutex_t* mutexes; rw_lock_t* rw_locks; }sync_obj; /*heaps的单元个数和n_sync_obj一样*/ mem_heap_t** heaps; #endif mem_heap_t* heap; ulint magic_n; /*校验魔法字*/ #endif }; ~~~ ## 5.小结 Innodb还有其他的一些数据结构，例如最小堆，这些都是通用的封装，也就不做过多的描述，在可以去看看innodb的源码相关就可以。innodb在定义数据结构的时候做了特殊的处理，例如对线程并发的控制，对内存分配的控制。这样做的目的是为了统一的管理。innodb的代码是C的，但支持C++。里面并没有使用STL这种传统的数据结构和算法，很大程度上是适合性的问题。据说MYSQL 5.7开始大量使用boost 和STL。个人感觉STL还勉强，使用boost有点步子迈大了的感觉。

> 原文出处：[innodb源码分析](http://blog.csdn.net/column/details/innodb-zerok.html) 作者：[yuanrxdu](http://blog.csdn.net/yuanrxdu) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # innodb源码分析 > 从源码深入分析innodb的内核实现、工作原理和存储结构,也是一次通向数据库内核的旅行，旅途会有各种未知的困难，但也会有美丽的风景和意想不到的收获。