[数据结构与算法]浅谈Innodb存储结构(Buffer Pool、Double Write Buffer、Change Buffer、Redo log、Undo Log、自适应索引.......)

前情提要：

? ?

innodb引擎对于磁盘读写的最小单位为页，每页为16kb（但是文件系统的一页为4kb，所以innodb引擎需要写4次文件系统，这4次操作不是原子性的）

一、全局结构图

二、内存部分

（1）Buffer Pool

（1）引入原因

? ? ? ? ? 对于Innodb来说，咱们建的表以及里面存储的记录等其他的一些信息都是持久化存储在磁盘上面的，也就是说在读写的的过程中肯定是绕不过对磁盘的读写的，不同表中的记录可能又不是存储在同一块区域的，如果我们要对分布在多个磁盘区域的记录进行更新和查询时，就属于是随机读写，磁盘的随机读写消耗相对来说还是挺大的，Innodb在设计的时候就考虑到了，所以他在内存中构建了一个缓冲区（Buffer Pool）来缓解随机读写磁盘的压力。改动的时候先按页为单位(16KB)将数据加载到内存中，比如你要查询的记录在页号为50的数据页中，为了避免后续操作可能会用到该数据页附近的数据页，Innodb直接通过预读，将页号为50的数据页周围的数据页通过异步的方式加载到buffer pool中。后续直接在内存中进行读取或者写入操作，等到必要的时候再刷入磁盘即可。

注：innodb引入了buffer pool之外还搞了很多对磁盘I/O的优化，预读就是其中的一个

??变种LRU链表

引入原因：
?

? ? ? 当请求变多了之后，加载到buffer pool的数据页肯定是越来越多的，innodb就提供了一种淘汰算法来淘汰数据页，被淘汰的数据页会被刷入磁盘中。这种算法和传统的LRU很像
?

传统LRU算法原理：
?

? ? ? ? 假如链表固定长度为3，并且链表中的元素是唯一的，当链表元素个数达到3时（3->2->1），此时第四个元素插入，如果链表中已经存在该元素，则把链表中的该元素放在链表头部（1插入3->2->1，变成1->3->2）,如果链表中不存在该元素，则最后一个元素被剔除链表，新元素插入头部（4插入3->2->1，变成4->3->2，1被剔除）
?

如果将传统LRU算法引入到Innodb里面会产生什么问题呢？

??预读失效：

????????由于预读会提前把页放入了缓冲池，但最终这些预读页都没有被操作就被淘汰了，称为预读失效。

??缓冲池污染：

????????由于预读需要加载很多数据页到链表中，而这些新进来的那些预读页可能根本用不上，并且链表中经常访问的热数据页直接就被这些无用的预读页替换掉了。
?

??解决办法：

????????将LRU链表分为两段，一段为年轻代，一段为老年代，并且在老年代设置时间窗口，我们之后就称之为变种LRU算法（其实redis也采用了自己设计的LRU算法来淘汰key，感兴趣的可以去了解一下）

变种LRU算法原理：

将LRU链表按比例分为2个部分，假设按热点数据页也就是真正被访问的数据页占70%，预读页占30%，以这个比例来将链表分为2个部分。

脏数据如何被淘汰？

这个等我们讲完下面的redo log再一起说

参考链接：https://blog.csdn.net/shenjian58/article/details/93268633

??Change Buffer
?

更新数据时，我们能想到的操作一般是这样的：

??涉及的数据页已经被加载到Buffer Pool中：
?

? ? （1）则直接在Buffer Pool中更新（内存操作）

? ? （2）先记录redo log在内存中，事务提交后刷入磁盘（一次内存写入+一次磁盘顺序写入，写入磁盘的这次操作是顺序写入，后面会说）

??涉及的数据页没有被加载到Buffer Pool中：
?

? ? （1）去磁盘中把该数据页和预读页加载到Buffer Pool中

? ? （2）然后在Buffer Pool中进行更新操作，

? ? （3）记录redo log（一次内存写入+一次磁盘顺序写入）

这样看起来是没什么问题，你仔细想想如果我们更新了之后并没有那么及时去访问这个数据页中的数据(写多读少的场景)，那么我们是不是可以先记录一下这次修改操作，等到要访问这个数据页的时候，再将这次修改操作和数据页合并，这个合并操作我们称之为merge。由此引出了Change Buffer（之前叫Insert Buffer），Change Buffer主要是为了减少写操作的磁盘IO

??引入Change Buffer后，涉及的数据页没有被加载到Buffer Pool中：
?

? ?? （1）先将修改操作记录在Change Buffer中

? ?? （2）记录redo log

产生merge的场景：

?????????? 读取Buffer Pool中不存在的数据页，但是Change Buffer中包含该数据页的修改记录

?????????? 后台线程，认为数据库空闲时

?????????? Buffer Pool不够用时

?????????? 数据库正常关闭时

?????????? redo log写满时

适合引入Change Buffer的场景：

?????????? 数据库大部分是非唯一索引

?????????? 业务是写多读少，或者不是写后立刻读取可以使用写缓冲，将原本每次写入都需要进行磁盘IO的SQL，优化定期批量写磁盘。例如，账单流水业务

不适合引入Change Buffer的场景：
?

?????????? 数据库大部分时唯一索引（如果修改的部分涉及到唯一索引，需要去磁盘中进行一些判断来保证索引的唯一性）

?????????? 写入一个数据后，会立刻读取它（读多写少的场景）

相关配置：

innodb_change_buffer_max_size：
?

? ? ? ? 介绍：配置写缓冲的大小，占整个缓冲池的比例，默认值是25%，最大值是50%。（写多读少的业务，才需要调大这个值，读多写少的业务，25%其实也多了）

innodb_change_buffering:
?

? ? ?? 介绍：配置哪些写操作启用写缓冲，可以设置成all/none/inserts/deletes等。（这个也好理解，就是见名知意，如果只配置成inserts，那就只对INSERT操作生效，以此类推）

Change Buffer不会产生数据丢失的原因：

?????????? 记录Change Buffer之前会记录redo log

?????????? 写缓冲不只是一个内存结构，它也会被定期刷盘到写缓冲系统表空间

参考链接：https://blog.csdn.net/shenjian58/article/details/93691224

??Double Write Buffer
?

引入原因

? ? ? ? ?Buffer Pool中的数据页肯定不可能一直放在内存中，当满足一些触发条件时，这些缓存页将会刷入磁盘中，例如正常关闭服务的时候，或者LRU链表淘汰数据页的时候。MySQL的Buffer Pool中一页的大小是16K，文件系统一页的大小是4K，也就是说，MySQL将Buffer Pool中一页数据刷入磁盘，要写4个文件系统里的页，但是这4步并不是原子性的，可能刷入其中2个就失败了，那这页数据不就不完整了？你可能想到，不是有redo log吗，直接从redo log恢复不就好了，非常遗憾，redo log中记录的是该页被修改的部分，并不是一整页数据页的副本，所以对于这种缺失页，redo log也无能为力，为此InnoDB引入了 双写缓存区（Double Write Buffer）。

Double Write Buffer怎么解决缺失页问题的

Buffer Pool中的数据页刷入磁盘时，不直接刷入磁盘：
?

（1）先将数据页memcopy进内存中的Double Write Buffer中

（2）内存中的Double Write Buffer将数据页刷到系统表空间中的Double Write Buffer磁盘区域

（3）内存中的Double Write Buffer将数据页刷到存储该页的通用表空间中，也就是其原来在磁盘中存储的位置

注：（2）（3）步是从内存"先"写入磁盘中的系统表空间中，"后"写入通用表空间中，由此得出"双写"，

? 假如（1）故障，那么此时磁盘中的通用表空间里面的数据页是完整的，直接用redo log恢复即可

? 假如（2）故障，此时磁盘中的通用表空间里面的数据页也是完整的，直接用redo log恢复即可

? 假如（3）故障，此时磁盘中的通用表空间里面的数据页不完整了，redo log无法直接恢复，但是步骤（2）已经完成，所以此时系统表空间中的Double Write Buffer中有完整的数据页，直接从系统表空间里面恢复即可。

相关命令

查看Double Write Buffer的使用情况：show global status like "%dblwr%"

总结：

（1）不是一个内存buffer，是一个内存/磁盘两层的结构，是InnoDB里On-Disk架构里很重要的一部分；

（2）是一个通过写两次，保证页完整性的机制；

（3）在异常崩溃时，如果不出现“页数据损坏”，能够通过redo恢复数据；

（4）在出现“页数据损坏”时，能够通过double write buffer恢复页数据；

参考链接：https://blog.csdn.net/liuxiao723846/article/details/103509226

??自适应索引
?

引入原因：

Innodb存储引擎会监控对表上二级索引的查找，如果发现某二级索引被频繁访问，二级索引成为热数据，建立哈希索引可以带来查询速度的提升，

注：书上也没详细说，了解一下就好，是否建立这个索引不是我们能控制的，是innodb自己去监控的，不过这个和Double Write Buffer以及Change Buffer统称为Innodb 三大特性。

??History List
?

引入原因：

每次更新、删除、插入的undo log都会先写入到History List中提供事务的MVCC机制，这里就不细说了，MVCC中每行数据的历史版本都存储在这个History List中，History List中的每个节点为undo page，undo page可以理解为装undo log的页，每个undo page中的undo log又通过链表连接。这样的话，活跃的事务如果要回滚则直接可以通过查询这个History List来找到要回退的undo log（活跃的事务指的是还未提交的事务，不活跃的事务也就是已经提交的事务）

History List中的undo log多久刷入磁盘—purge机制：

内存空间是有限的，肯定得有一定的规则来释放History List中已经“用不到”的undo log，什么叫做用不到呢？也就是当前活跃事务中，不用提供MVCC的undo log。Innodb提供了purge机制来将这些没用的undo log刷到undo log表空间中，其本质就是起一个异步线程来遍历History List，然后将没用的undo log刷入磁盘。

全局动态参数innodb_purge_batch_size用来设置每次purge操作需要清理的undo page数量。默认值为300 全局动态参数innodb_max_purge_lag用来控制history list的长度，若大于该参数时，其会延缓DML的操作 全局动态参数innodb_max_purge_lag_delay,用来控制DML操作每行数据的最大延缓时间，单位为毫秒。
?

History List中的undo log如何保证其不丢失：

从purge机制得知，undo log并不是实时刷入磁盘的，而且提供MVCC的undo log也是没有立即被刷到磁盘上的，那么如果宕机了，这些undo log不就丢失了？为此，innodb早就想到了，它在Buffer Pool中记录undo log之前会先将undo log按redo log的形式记录成redo log，并且事务的回退操作也会记录成redo log，然后随着redo log的刷盘策略刷入磁盘中。这样数据恢复的时候直接用redo log来恢复即可，先用redo log恢复，然后用记录了undo log回退操作的redo log回退。

undo log如何对事务进行回滚

在History List中找到需要回滚的undo log，然后恢复到这个undo log记录的值，并且将这个undo log记录为可删除状态，等到History List中的undo log刷盘的时候就会将这些被标记了可删除状态的undo log物理删除掉。

注：其实很有很多细节没讲，比如undo log的分类，undo page的重用，大佬们自行百度一下

（2）Log Buffer

??Redo Log Buffer
?

前面知识点的串联：

前面我们知道，当一个写操作来了之后，会在Buffer Pool中记录相应的undo log，Change Buffer以及修改缓存页，然后还要看是否需要在LRU链表中淘汰缓存页，需要淘汰的话就得先把淘汰页记录到Double Write Buffer中，然后通过purge线程双写到磁盘中的系统表空间里的Double Write Buffer区域以及通用表空间中，然后会用purge机制定期清理没有提供MVCC机制的Histoty中的undo log，Innodb会根据二级索引缓存页的访问频率等一些因素来决定是否在Buffer Pool中建立自适应索引来提高热点二级索引缓存页的查询效率，以上这些都是Buffer Pool中的工作，在内存中还有一个比较重要的区域，它不在Buffer Pool中而是在内存中另外分配了块空间，也就是Redo Log Buffer，其是用来记录redo log的。

什么是redo log？

一个事务会包含许多SQL，而一条SQL修改语句，会产生"很多组redo log"就，而这"一组redo log"称为mtr（Mini-Transaction）是写入的最小单元，比如update age = 5? from A where id > 10这条sql，如果A表中存在满足id > 10的多条记录，那修改一条记录就可以看成一条redo log，你修改肯定得把所有满足id > 10这个条件的记录都修改了才是原子性的，这就是一个mtr是一组redo log的由来，一个redo log记录的就是在磁盘的哪个位置，修改了什么东西。对应关系就是：

"一个事务"——>"多条sql语句"

"一条sql语句"——>"多条mtr"

"一条mtr"——>"多个redo log"

"一个redo log" ——>"把表空间x、页号y、偏移量为z处的值更新为n"

redo log写入到redo log buffer的过程

为了解决数据随机读写磁盘速度过慢的问题而引入了 Buffer Pool 。同理，写入 redo log时也不能直接直接写到磁盘上，实际上在服务器启动时就向操作系统申请了一大片称之为 redo log buffer 的连续内存空间，翻译成中文就是 redo日志缓冲区 ，我们也可以简称为 log buffer 。这片内存空间被划分成若干个连续的redo log block，然后innodb维护了个全局偏移量，也就是buffer free，表示新的redo log要写入redo log buffer中哪块redo log block中的哪个位置，每个mtr的执行过程中，先将其对应的多个redo log写入到内存中的某个地方，然后当该mtr执行完成后再一次性写入到redo log buffer中。由于不一定只有一个事务在执行，所以redo log是并发写入到redo log buffer中的，每个事务对应的多个redo log不一定是连续的，可能是交错的。

redo log刷盘时机

（1）提交事务后就刷盘，刷入的位置由innodb_flush_log_at_trx_commit决定：
?

?????????? innodb_flush_log_at_trx_commit=0 ：

????????????????表示每次事务提交时都只是把 redo log 留在 redo log buffer 中 ，等待异步线程去刷盘;
?

?????????? innodb_flush_log_at_trx_commit=1:

????????????????表示每次事务提交时都将 redo log 直接持久化到磁盘；
?

?????????? innodb_flush_log_at_trx_commit=2:

????????????????表示每次事务提交时都只是把 redo log 写到 page cache，page cache是磁盘和内存之间的一块缓冲区，它并不是持久化的，随着系统异常关闭时其会丢失。

（2）定时处理：
?

????????innodb_flush_log_at_timeout配置定时刷盘，配置之后有线程会定时(默认每隔 1 秒)把redo log buffer中的数据刷盘，并且需要注意，配置这个项后，事务提交之后并不会马上触发刷盘，而是需要等这个线程去刷。

（3）根据空间处理：
?

????????redo log buffer 占用到了一定程度( innodb_log_buffer_size 设置的值一半)占，这个时候也会把redo log buffer中的数据刷盘。

redo log刷盘过程：
?

????????根据上面的刷盘机制，redo log buffer中的redo log最终会被刷入到磁盘中Innodb分配到的一块叫Redo Log File的区域，然后默认情况下，会用2个文件来装这些redo log，一开始会先从第一个文件(ib_logfile_1)开始写，写满了就换第二个文件(ib_logfile_2)来写，第二个文件写满了就清理一部分第一个文件的空间，然后继续写入第一个文件，这个清理的机制叫做checkpoint 。

checkpoint机制：

?? 为什么需要checkpoint：

Redo Log File中的空间并不是无限的，当2个ib_logfile记录满了之后，需要回到第一个ib_logfile开始记录，那么ib_logfile_1就需要腾出一部分空间来装这些新的redo log，那么哪些redo log可以被"腾出来"呢，在这之前我们需要知道redo log是为了保证buffer pool中的脏页的持久性而存在的，也就是说buffer pool的LRU链表中的数据页还没来得及被刷新到磁盘中时，机器就宕机了，那么这些数据页在buffer pool中被修改的部分就丢失了，此时就需要用redo log来恢复。此时回答之前的那个问题，什么样的redo log可以被腾出来呢，也就是Buffer Pool中已经被刷到磁盘的数据页对应的redo log可以被腾出来，因为这些数据页已经刷入磁盘了已经得到了持久化的保证，不需要再用redo log来恢复了。

上面可以总结为：当Redo Log File中的2个ib_logfile都写满后，innodb会判断此时这2个文件中哪些redolog对应的脏页已经被刷入到磁盘中了，然后就直接把这部分的redo log淘汰掉，腾出来的空间就可以留给新的redo log。如果空间需求比较大，则会从buffer pool中强制刷新一些脏页到磁盘中，然后将对应的redo log就可以被覆盖。

?? 什么时候会触发checkpoint：

（1）数据库正常关闭时，脏页是需要刷到磁盘的，全部刷入磁盘后，所有的redo log就可以被覆盖了，即innodb_fast_shutdown=0时需要执行sharp checkpoint

（2）redo log快满的时候进行fuzzy checkpoint ，也就是我们前面说的情况

（3）master thread每隔1秒或10秒定期进行fuzzy checkpoint，他会刷一些脏页到磁盘中。

（4）innodb保证有足够多的空闲page，如果发现不足，需要移除LRU链表末尾的page，如果这些page是脏页，那么也需要fuzzy checkpoint

（5）innodb buffer pool中脏页比超过innodb_max_dirty_pages_pct时也会触发fuzzy checkpoint

??：以上也可以理解为，什么时候LRU链表中的脏页会被刷入磁盘中，这样就回答了之前LRU部分的问题(脏页什么时候刷入磁盘)

Redo Log和Binlog的两阶段提交：

我们需要明确一个事情，Mysql的server层提供的binlog是用来保证数据备份和主从同步使用的。也就是说如果数据库所在的机器哪天故障了，你可以拿到binlog去另外台机器进行回档，主从同步也是如此，‘从数据库’只需要解析‘主数据库’的binlog得到sql语句，然后执行后就可以得到主库的所有数据。

然后存储引擎层innodb提供的redo log就做不到这些，因为我们之前说过当空间不足时他是会被覆盖的。redo log只是innodb用来提供crash safe的，即如果Mysql 进程异常重启了，系统会自动去检查redo log，将之前buffer pool中因为进程异常导致的未写入到磁盘的数据从redo log恢复到磁盘去。

上面这段话我只是想说明，redo log和binlog是在做不同的事情，但是它俩都涉及到数据库数据的完整性，所以他两保证的数据进度必须一致。所以mysql采用了两阶段提交方式来保证这个要求。

假设redo log和binlog分别提交，可能会造成用日志恢复出来的数据和原来数据不一致的情况。

（1）假设先写redo log再写binlog，即redo log没有prepare阶段，写完直接置为commit状态，然后再写binlog。那么如果写完redo log后Mysql宕机了，重启后系统自动用redo log 恢复出来的数据就会比binlog记录的数据多出一些数据，这就会造成磁盘上数据库数据页和binlog的不一致，下次需要用到binlog恢复误删的数据时，就会发现恢复后的数据和原来的数据不一致。

（2）假设先写binlog再写redolog。如果写完redo log后Mysql宕机了，那么binlog上的记录就会比磁盘上数据页的记录多出一些数据出来，下次用binlog恢复数据，就会发现恢复后的数据和原来的数据不一致。

由此可见，redo log和binlog的两阶段提交是非常必要的。
?

Redo Log如何进行数据恢复

磁盘中的数据页会维护一个LSN（你可以理解为数据进度），然后Redo Log中也会维护一个LSN，如果磁盘中数据页的LSN小于Redo Log的LSN，则说明需要恢复数据，就把大于磁盘LSN的redo log对磁盘中的数据页进行恢复即可

WAL机制

Innodb提供了WAL机制（write ahead? log）来提高读写效率，简单来说就是把对数据修改的部分先放入内存中的Buffer Pool中，不急着马上刷入磁盘，因为磁盘io是比较慢的嘛，而且如果你修改了之后马上又要查询这个数据，那岂不是又增加了一次磁盘io。这些在内存中修改操作我们肯定得保证它的持久性，我们就采用'先'写入redo log的方式来保证数据持久性，然后等到后面需要的时候"再"将内存中的脏数据页刷入磁盘中。

三、磁盘部分

（1）表空间

?? 通用表空间

存数据页的磁盘区域

?? 系统表空间

double write buffer、change buffer、undo 回滚段....的磁盘区域

?? Undo表空间

存undo log的磁盘区域

（2）Redo Log File
?

这个区域是redo log的磁盘区域，内存中Redo Log Buffer的redo log会被刷入该区域，具体规则在前面的Redo Log Buffer已说，这里就不再赘述

参考资料：

? ? ? ? 《Mysql是如何运行的？从根儿上理解mysql》
????????《Mysql技术内幕：Innodb存储引擎》
? ? ? ? ? https://blog.csdn.net/shenjian58/article/details/93268633
? ? ? ? ? https://blog.csdn.net/shenjian58/article/details/93691224
? ? ? ? ? https://blog.csdn.net/liuxiao723846/article/details/103509226