2. InnoDB 存储引擎-InnoDB体系架构、InnoDB的关键特性、Master Thread、insert buffer、两次写、自适应哈希索引、异步IO，
2.1 InnoDB存储引擎概述
InnoDB存储引擎是第一个完整支持ACID事务的MySQL存储引擎，其特点是行锁设计、支持MVCC、支持外键、提供一致性非锁定读，同时被设计用来最有效的利用内存和CPU。
2.2 InnoDB存储引擎版本
从MySQL5.1 版本时，MySQL数据库允许存储引擎开发商以动态方式加载引擎，这样存储引擎的更新可以不受MySQL数据库版本的限制。
2.3 InnoDB体系架构
InnoDB存储引擎有多个内存块，可以认为这些内存块组成了一个大的内存池，负责如下工作：
- 维护所有进程、线程需要访问的多个内部数据结构
- 缓存磁盘上的数据，方便快速的读取，同时在对磁盘文件的数据修改之前在这里缓存。
- 重做日志缓冲（redo log）
- ……
后台线程的主要作用是负责刷新内存池中的数据，保证缓冲池中的内存缓存的是最新的数据，此外将已修改的数据文件刷新到磁盘文件。同时，保证在数据库发生异常的情况下，InnODB能恢复到正常状态。
2.3.1 后台线程
InnoDB是多线程的模型 ，不同线程负责不同的任务
2.3.1.1 Master Thread
负责将缓冲池中的数据异步刷新到磁盘，保证数据的一致性，其中包括脏页的刷新、合并插入缓冲、UNDO页的回收等
2.3.1.2 IO Thread
InnoDB 大量使用 AIO（Async IO）来处理写 IO 请求，这样可以提高数据库的性能。IO Thread主要负责这些IO请求的回调处理。
2.3.1.3 Purge Thread（清除线程）
事务被提交后，其使用的undo log 可能不再需要，因此需要 Purge Thread 回收应使用并分配的undo页。在 InnoDB 1.1 之前，该操作在Master Thread 中，1.1 之后，独立到单独的线程中，提高CPU的利用率以及提升INnoDB的性能。InnoDB 1.2 开始，InnoDB 支持多个 Purge Thread，进一步加快了undo页的回收，同时由于 Purge Thread 需要离散的读取undo页，这样可以进一步利用磁盘随机读取性能。
2.3.1.4 Page Cleaner Thread
该线程是在InnoDB 1.2.x版本引入的，作用是将之前版本中脏页的刷新操作都放入单独的线程中完成，目的是减轻原 Master Thread 的工作以及对用户查询线程的阻塞，进一步提高InnoDB的性能。
2.3.2 内存
1. 缓冲池
InnoDB 存储引擎是基于磁盘存储的，并将其中的记录按照页的方式进行管理，因此可将其视为基于磁盘的数据库系统。在数据库系统中，由于 CPU 与 磁盘之间的鸿沟，通常使用缓冲池技术来提高数据库的整体性能。
简单来说，缓冲池就是一块内存区域，通过内存来弥补磁盘速度较慢对数据库性能的影响。
读取操作，首先将从磁盘读取到的页存放到缓冲池中，下次读取相同的页时，首先判断该页是否在缓冲池中，若在，称该页在缓冲池中被命中，直接读取缓冲池的该页，否则，读取磁盘。
修改操作，先修改缓冲池中的页，然后以一定的频率刷新到磁盘。而页的刷新操作不是每次修改时触发，而是通过 CheckPoint 的机制刷新回磁盘。
从 InnoDB 1.0.x版本开始，允许有多个缓冲池实例。每个页根据哈希值平均分配到不同缓冲池实例中。这样做的好处是减少数据库内部的资源竞争，增加系统的并发处理能力。
2. LRU List、Free List和 Flush List
从上一节得知，缓冲池是一个很大的内存区域，其中存放各种类型的页。那么InnoDB是怎么管理这么大的内存区域呢？
通常来说，数据库中的缓冲池是通过 LRU 算法管理的。即最频繁最近使用的页在 LRU 列表的前端，而最少使用的页在 LRU 列表的尾端。当缓冲池中不能存放新读取到的页时，将释放LRU列表尾端的页。
InnoDB 对传统的LRU算法做了一些优化。在 LRU 列表中加入了 midpoint 位置，新读取的页，虽然是最近访问的页，但并不是直接放入到 LRU 列表的首部，而是放入到 LRU列表的midpoint位置，默认情况下是在 LRU列表长度的 5/8 处。这个算法在InnoDB存储引擎下称为 midpoint insertion strategy。
在 InnoDB中，把midpoint 之后的列表称为 old 列表，之前的称为 new 列表，即最为活跃的热点数据。
为什么不采用朴素的LRU算法呢？
因为某些SQL 操作（比如索引或数据的扫描操作）需要访问表中的许多页，甚至是全部的页，而这些页仅在这次查询操作中需要，并不是活跃数据。如果将其放入列表首部，那么可能将真正的热点数据从 LRU 列表移除，而在下次读取该页时，InnoDB再次访问磁盘。
LRU 列表用于管理已经读取的页。但数据库刚刚启动时，LRU列表是空的，这时，页都在Free 列表中，当需要从缓冲池中分页时，先从Free List 中查找是否有可用的空闲页，若有，将该页从 Free List中删除，放入 LRU 列表中。否则，根据LRU，淘汰LRU末尾的页，将该内存空间分配给新的页。
在 LRU 列表中的页被修改后，称为脏页，即缓冲池中的页和磁盘的页数据产生了不一致。这时，数据库会通过 Checkpoint机制将脏页刷新回磁盘，而 Flush 列表中的页即为脏页列表。需要注意的是，脏页既存在于 LRU 列表中，也存在于 Flush 列表。LRU 列表用来管理缓冲池中页的可用性，Flush用来管理将页刷新回磁盘，二者不影响。
3. 重做日志缓冲
InnoDB 的内存区域除了缓冲池，还有重做日志缓冲。InnoDB首先将重做日志先放入到这个缓冲区，然后按照一定的频率将其刷新到磁盘上的重做日志文件。默认大小为 8 MB.以下三种情况，会对重做日志进行刷新。
- Master Thread 每秒对重做日志缓冲刷新
- 每个事务提交时，对重做日志缓冲刷新
- 当重做日志缓冲池剩余空间小于 1/2 时
4. 额外的内存池
在 InnoDB 中，对内存的管理是通过一种称为 内存堆 的方式进行的，在对一些数据结构本身的内存进行分配时，需要从额外的内存池中进行申请，当该区域的内存不足时，会从缓冲池中进行申请。因此，在申请了很大的InnoDB 缓冲池时，应考虑相应的增加这个值。
2.4 Checkpoint 技术
为了避免发生数据丢失的问题，当前事务数据库普遍采用了 Write Ahead Log 策略，即当事务提交时，先写重做日志，再修改页。当由于宕机导致数据丢失时，通过重做日志完成数据的恢复，也是事务持久性的要求。
Checkpoint 技术目的是解决一下几个问题：
- 缩短数据库的恢复时间
- 缓冲池不够用时，将脏页刷新回磁盘
- 重做日志不可用时，刷新脏页
当数据库发生宕机时，数据库不需要重做所有的日志，因为 checkpoint 之前的页都已经刷新回磁盘，只需要对checkpoint之后的页进行恢复，大大缩短了恢复时间。
此外，当缓冲池不够用时，根据 LRU 算法会移除最近最少使用的页，若此页是脏页，那么需要强制执行 checkpoint，将脏页刷回磁盘。
重做日志出现不可用是因为当前事务数据库对重做日志的设计都是循环使用的，这从成本及管理上是比较困难的。重做日志可以被重用的部分是这些日志已经不再需要，即当数据库发生宕机时，不需要恢复这部分的日志，因此这部分可以被覆盖重用。若此时重做日志还需要使用，那么必须强制产生 checkpoint，将缓冲池中的页刷新到当前重做日志的位置。
checkpoint的目的是将缓冲池中的脏页刷回到磁盘，不同之处在于刷新多少到磁盘，每次从哪里读取脏页，什么时间触发checkpoint。InnoDB 中有两种 checkpoint：
Sharp Checkpoint 发生在数据库关闭时将所有的脏页刷新回磁盘，这是默认的工作方式。但如果数据库运行时也使用 Sharp Checkpoint，那么数据库的可用性会受到很大影响。因此，InnoDB内部使用 Fuzzy Checkpoint进行页的刷新，即只刷新一部分脏页，而不是刷新所有的脏页回磁盘。
InnoDB发生 Fuzzy Checkpoint 的情况分为以下几种：
Master Thread差不多以每秒或每十秒的速度从缓冲池中的脏页列表中刷新一定比例的页回磁盘，这个过程是异步的，不阻塞用户查询线程。
FLUSH_LRU_LIST Checkpoint 是因为InnoDB存储引擎需要保证 LRU 列表有差不多100个空闲页可使用。InnoDB1.1.x 版本之前，需要检查LRU列表是否有足够的可用空间操作发生在用户查询线程中，会阻塞用户查询操作。如果空闲页小于100，那么将LRU列表尾部的页移除，如果这些页中有脏页，那么需要 Checkpoint，而这些页来自 LRU列表，因此称为 FLUSH_LRU_LIST Checkpoint；在 MySQL 5.6之后，也就是 InnoDB 1.2.x 版本后，这个检查被放在了单独的 Page Cleaner线程中进行。
Async/Sync Flush Checkpoint 指的是重做日志不可用的情况，而此时脏页是从脏页列表中选取的，若将已经写入到重做日志的LSN记为 redo_lsn，将已经刷回磁盘最新页的lsn记为 Checkpoint_lsn，则可定义 Checkpoint_age = redo_lsn - checkpoint_lsn。之后会详细说明该部分，总之，Async/Sync Checkpoint 是为了保证重做日志的循环使用的可用性。从 InnoDB 1.2.x 开始，该部分的刷新操作同样放到了单独的 Page Cleaner Thread 中。
Dirty Page too much，导致InnoDB 存储引擎强制 Checkpoint，目的是为了保证缓冲池有足够可用的页，默认为 75%
2.5 Master Thread 工作方式
2.5.1 InnoDB 1.0.x版本之前的 Master Thread
Master Thread 有最高的线程优先级，内部有多个循环（loop）组成：主循环、后台循环、刷新循环（flush loop）、暂停循环（suspend loop）。Master Thread会根据数据库运行的状态在多个循环之前进行切换。
主循环（loop）
主循环中包含大多数的操作，其中有两大部分的操作——每秒的操作和每十秒的操作。loop 循环是通过 Thread sleep 来实现的，意味着时间不精确，在负载大的情况下，可能会有延迟。
每秒的操作包括：
每十秒的操作包括：
后台循环（background loop）
若当前没有用户活动（数据库空闲或关闭）时，切换到该循环。后台循环会执行以下操作：
刷新循环（flush loop）
若刷新循环中没有什么事情可做，则切换到 suspend loop中，将Master Thread 挂起，等待事件发生。若用户启用了InnoDB存储引擎，但却没有使用任何InnoDB 存储引擎的表，那么Master Thread总是处于挂起的状态。
2.5.2 InnoDB 1.2.x版本之前的 Master Thread
从上一节发现，InnoDB对IO是有限制的，在缓冲池向磁盘刷新时都做了一定的硬编码。在技术飞速发展的今天，当固态硬盘出现时，这种规定很大程度上限制了 InnoDB存储引擎对磁盘IO的性能，尤其是写入性能。
从上一节来看，无论何时，InnoDB最大知会刷新100个脏页到磁盘，合并20个插入缓冲。如果是在写密集的应用中，每秒可能会产生大于100个脏页，如果是产生大于20个插入缓冲的情况，Master Thread 似乎会忙不过来，即使磁盘可以在1秒内处理多余100个页的写入和20个插入缓冲的合并，但由于 hard coding，Master Thread 只能写100个脏页和20个合并缓冲。同时，当宕机发生要恢复时，由于很多数据还没有刷新回磁盘，会导致恢复时间过长，尤其是 insert buffer.
因此，InnoDB plugin（1.0.x）开始提供了参数 InnoDB_io_capacity，用来表示磁盘IO的吞吐量，默认200。若用户使用了SSD类的磁盘，存储设备拥有更高的IO速度时，可将 InnoDB_io_capacity 调高，直到符合磁盘IO的吞吐量。
除此之外，InnoDB 1.0.x还对其他的参数进行了调整，用以提高数据库系统的性能。
2.5.3 InnoDB 1.2.x版本的 Master Thread
对刷新脏页的操作，从 Master Thread 线程分离一个单独的Page Cleaner Thread，从而减轻 Master Thread 的工作，进一步提高系统的并发性。
2.6 InnoDB的关键特性
InnoDB的关键特性包括：
- 插入缓冲
- 两次写（double write）
- 自适应哈希索引（Adaptive Hash Index，AHI）
- 异步IO
- 刷新邻接页（Flush Neighbor Page）
2.6.1 插入缓冲
1. Insert buffer
InnoDB 缓冲池中有 insert buffer的信息，但 insert buffer 和数据页一样，是物理页的一个组成部分。
由于每张表不可能只有一个聚集索引，更多情况下，一张表有多个非聚集（且不唯一）的辅助索引。这种情况下，在进行插入操作时，数据页的存放还是按照主键进行顺序存放，但对于非聚集的索引叶子节点的插入不再是顺序的，这时需要离散的访问辅助索引页，由于随机读取的存在导致了插入操作的性能下降。这是由于B+树的特性决定了非聚集索引插入的离散性。
InnoDB存储引擎开创性的设计了Insert Buffer，对于非聚集索引的插入或更新操作，不是每一次直接插入到索引页中，而是先判断插入的索引页是否在缓冲池中，若在，则直接插入。若不在，则先放到一个insert buffer 对象中，好似欺骗，数据库这个非聚集索引已经插入到叶子节点，而实际没有，只是存放在另一个位置，然后以一定的频率和情况进行insert buffer 和辅助索引页子节点的merge操作，这时通常能将多个插入合并到一个操作中（因为在同一个索引页中），这大大提高了对于非聚集索引插入的性能。
然而insert buffer 需要同时满足两个条件
- 索引必须是辅助索引
- 索引不是唯一的：因为在插入缓冲时，数据库并不去查找索引页来判断插入记录的唯一性。如果去查找的话，又会涉及到离散读的情况，insert buffer失去意义
正如前面所说的，目前 insert buffer 存在一个问题：在写密集的情况下，插入缓冲会占用过多的缓冲池内存，默认最大可以占用1/2 的缓冲池内存。该值可修改
2.Change buffer
InnoDB 从 1.0.x 版本开始引入了 change buffer，可以将其视为 insert buffer 的升级。从这个版本开始，InnoDB存储引擎可以对DML操作-insert、delete、update都进行缓冲，他们分别是 insert buffer、delete buffer、purge buffer。
同样，change buffer 适用的对象是非唯一的辅助索引。
对一条记录的update操作可能分为两个步骤：
delete buffer 对应 update 操作的第一个过程，将记录标记为删除。purge buffer 对应update 的第二个过程，即真正的删除。同时 InnoDB提供了参数用来开启各种buffer 的选项。changes 标识insert 和 delete，all标识所有，none标识都不启用，该参数默认为all
3. insert buffer 的内部实现
insert buffer的数据结构是一棵B+树。之前的版本每个表都有一个B+树，现有版本中，全局只有一个 Insert buffer B+树，负责所有表的辅助索引进行 insert buffer。而这棵树存放在共享表空间中，默认也就是ibdata1。因此，试图通过独立表空间ibd文件恢复表中数据时，往往会导致 check table失败。因为表的辅助索引的数据可能还在 insert buffer 中，也就是共享表空间里，所以通过ibd文件进行恢复后，还需要进行 repair table 操作来重建表上所有的辅助索引。
insert buffer是一棵B+树，因此其也由叶子节点和非叶子节点组成，非叶子节点存放的是 search key（键值），其构造如图所示：
search key 一共有9个字节，其中space标识待插入记录所在的表空间id，在 InnoDB存储引擎中，每个表都有一个 space id，通过space id 可知是哪张表。space占用四个字节，marker一个字节，用来兼容老版本的insert buffer。offset 标识页所在的偏移量，占用四个字节。
当一个辅助索引要插入到页（space，offset）时，如果这个页不再缓冲池中，那么InnoDB会先根据上述负责构造一个 search key，接下来查询 insert buffer这棵B+ 树，然后再将这条记录插入到树中的叶子节点。
对于插入到insert buffer B+树叶子节点的记录，并不是将待插入的记录直接插入，而是根据如下的规则进程构造：
space、marker、offset和之前非叶子节点的含义相同，一共占用九个字节，metadata占用4个字节，用来排序每个记录进入insert buffer的顺序，通过这个顺序回放才能得到记录的正确值。
从 insert buffer叶子节点的第五列开始，就是实际插入记录的各个字段了。因此，insert buffer B+树的叶子节点记录需要额外13字节的开销。
因为启用 insert buffer索引后，辅助索引页（space，page no）中的记录可能被插入到insert buffer B+树中，所以为了保证每次merge insert buffer 页必须成功，还需要有一个特殊的页来标记每个辅助索引页（space，page_no）的可用空间，这个页的类型为 insert buffer bitmap。
4. Merge Insert Buffer
insert buffer 中的记录何时合并到真正的辅助索引页呢？概括的说，Merge insert buffer操作可能发生在以下几种情况下：
- 辅助索引页被读取到缓冲池时
- insert buffer bitmap页追踪到该辅助索引页无可用空间时
- Master Thread
第一种情况是当辅助索引页被读取到缓冲池时，例如这时正在执行 select 操作，需要检查insert buffer bitmap页，然后确认该辅助索引页是否有记录在insert bufferB+ 树中，若有，则将insert buffer B+树中该页的记录插入到该辅助索引页中。可以看到对该页多次的记录操作通过一次操作合并到了原有的辅助索引页中，性能得到很大提高
insert buffer bitmap页用来追踪每个辅助索引页的可用空间，并至少有1/32页的空间。如果小于 1/32，则会强制执行一个合并操作，即强制读取辅助索引页，将insert buffer B+树中该页的记录及待插入的记录插入到辅助索引页中。
最后是Master Thread中每秒或每十秒会进行一次 merge 操作，不同的是每次merge操作的页的数量不同
那么，InnoDB又是根据怎样的算法来得知需要合并的辅助索引页呢？在insert buffer B+树中，辅助索引页根据（space，offset）都已排好序，故可以根据（space,offset）的排序顺序进行页的选择。然而，对于insert buffer 页的选择，InnoDB并非采用该方式。它随机的选择 insert buffer B+ 树中的一个页，读取该页中的space及之后所需要数量的页。该算法在复杂情况下，有更好的公平性。同时，若merge时，要进行merge的表已经被删除，此时可以直接丢弃已经被 insert/change buffer 的数据记录。
2.6.2 两次写
两次写可提高InnoDB存储引擎数据页的可靠性。当数据库发生宕机时，可能InnoDB正在写入某个页到表中，而这个页只写了一部分，之后就发生了宕机，这种情况被称为部分写失效（partial page write）。有经验的DBA也许会想，如果发生写失效，可以通过重做日志进行恢复。但需要知道的是，重做日志中记录的是对页的物理操作，如偏移量800写’qqq‘记录。如果这个页本身发生了损坏，再对其进行重做是没有意义的。
这就是说，在应用重做日志前，用户需要一个页的副本，当写入失效发生时，先通过页的副本来还原该页，再进行重做，这就是 double write。
以上是doublewrite的架构图，doublewrite有两部分构成，一部分是内存中的 doublewrite buffer，大小为 2MB，另一部分是物理磁盘上共享表空间中连续的128个页，即两个区（extent），大小同样为 2MB。在对缓冲池的脏页进行刷新时，并不直接写磁盘，而是会通过 memcpy 函数将脏页先复制到内存的 doublewrite buffer，然后通过 doublewrite buffer 再分两次，每次 1MB 顺序写入共享表空间的物理磁盘上，然后马上调用fsync函数，同步磁盘，避免缓冲写带来的问题。
在以上的过程中，因为doublewrite是连续的，因此这个过程是顺序写，开销不是很大，完成doublewrite页的写入后，再将doublewrite buffer 中的页写入各个表空间文件中，此时的写是离散的。
2.6.3 自适应哈希索引
InnoDB 会监控对表上各个索引页的查询，如果观察到建立哈希索引可以带来速度提升，则建立哈希索引，称之为自适应哈希索引。
AHI有一个要求，对这个页的连续访问模式必须是一样的，例如对（a,b）这样的联合索引，其访问模式可以是以下情况：
- where a= xxx
- where a= xxx and b = xxx
访问模式一样意味着查询条件一样，若交替进行以上两种查询，那么InnoDB不会建立哈希索引。
AHI还有两个要求：
- 以该模式访问了100次
- 页通过该模式访问了N次，其中N= 页中记录 /16
2.6.4 异步IO
为了提高磁盘性能，当前数据库系统都采用异步IO的方式来处理磁盘操作，InnoDB也是如此。
用户可以在发出一个IO请求后，立即发出另一个，当全部IO请求发送完毕后，等待所有IO操作的完成，这就是AIO。
AIO的另一个优势就是可以进行IO merge，也就是将多个IO合并为1个IO，这样可以提高IOPS的性能。
2.6.5 刷新邻接页
InnoDB还提供了Flush Neighbor Page（刷新邻接页）的特性。其工作原理为：当刷新一个脏页时，InnoDB存储引擎会检测该页所在区（extent）的所有页。如果是脏页，那么一起进行刷新。这样做的好处，是通过AIO可以将多个IO合并为一个IO操作，故该工作机制在传统机械磁盘下有明显优势。但考虑到以下问题：
- 是不是可能将不怎么脏的页进行了写入，而该页之后又很快变成脏页。
- 固态硬盘有较高的IOPS，是否需要这个特性
InnoDB 从 1.2.x开始提供了参数用来控制是否启用该特性。