LRU 是 Least Recently Used 的缩写，指的是最近最少使用算法，通常用于缓存管理中，它可以帮助缓存系统更有效地利用有限的缓存空间。对于数据库等应用而言，为了保证更快的查询效率，通常会将使用过的数据放在内存中进行加速读取，这就需要对于内存中的数据施加以合适的缓存策略，而在Innodb引擎中使用的LRU却在我们常见的LRU算法上添加了一定的特殊性。

一、Innodb引擎架构

InnoDB存储引擎使用内存缓冲池来弥补硬盘和CPU之间的速度差异。类似于操作系统将硬盘文件缓存到内核缓冲区一样，InnoDB为硬盘中的数据和索引建立了用户空间的内存缓冲池。这样，当数据库需要读取数据时，首先会查看内存缓冲池中是否存在该数据，如果存在，则直接返回，如果不存在，则从硬盘中读取。

对于数据页的修改，InnoDB首先在内存缓冲池中进行修改，然后在合适的时机将这些修改持久化到硬盘，这通常由Checkpoint技术来决定。

尽管Linux操作系统中已经有内核缓冲区来提高I/O效率，为什么InnoDB还要建立自己的缓冲池呢？这是因为内核缓冲区主要关注硬件相关细节，比如页对齐和数据边界，而InnoDB的缓冲池则更专注于应用层，不需要关心硬件细节，并且可以由应用程序进行更灵活的控制。

下图是Innodb引擎的架构图：

从上图中可见，数据页和索引页占据了缓冲区的绝大部分空间。

二、Innodb缓冲池LRU算法

LRU 算法的核心思想是基于数据的访问模式。当需要淘汰数据时，选择最近最少被使用的数据进行淘汰。LRU 算法通常通过维护一个数据访问历史记录或者使用特定的数据结构来实现。一种常见的实现方式是使用双向链表和哈希表。哈希表用于快速查找数据是否在缓存中，而双向链表用于记录数据的访问顺序。当数据被访问时，它会被移动到链表的头部，表示最近被使用；当需要淘汰数据时，可以选择链表尾部的数据，因为那些数据是最近最少被使用的。

但是，InnoDB对LRU算法进行了改进，最近访问到的数据并不直接放到LRU列表的首部，而是放到LRU列表的midpoint位置。在默认配置下，midpoint位于LRU列表的5/8处。

InnoDB中的LRU列表被分为两部分：midpoint之前的部分被称为new列表（或者在Java中的GC术语中称为新生代），而midpoint之后的部分被称为old列表（或者称为老年代）。

当new列表中的数据被访问时，它会被直接放置于LRU列表的首部。新的页面进入LRU列表时，会被放置于midpoint位置，使其成为old列表的一部分。

对于old列表中的数据访问，需要进行判断。如果数据在old列表中存在的时间超过1秒，它将被移至列表的首部。如果存在时间小于1秒，它将保持当前位置。这个时间判断由'innodb_old_blocks_time'参数决定，默认为1000毫秒（即1秒）。

此设计的原因在于，采用朴素的LRU算法可能导致某些索引或表扫描操作将所有的索引页和数据页都置换出去，而这些数据通常只是一次性使用的。采用midpoint实现后，即使出现大范围的表扫描和索引扫描,也至少能够保证5/8的数据都是热点数据。

这种特有的LRU算法流程如下：

1. 将3/8的空间用作旧的子链表，而链表的中点连接了新的子链表的尾部和旧的子链表的头部。
2. 当InnoDB将一个数据页读入缓冲池时，它会被插入到旧的子链表的中点（即链表的头部）类似的查询操作或预读操作也会触发数据页的读入。
3. 访问旧的子链表中的数据页会使其变得“年轻”，因为它们会被移向缓冲池的头部（即新的子链表的头部）。如果一个数据页是因为需要而被读入缓冲池，那么它会立即被标记为最近访问，从而变得“年轻”。但如果一个数据页是因为预读而被读入缓冲池，它并不会立即被标记为最近访问（有可能在被驱逐前根本就不会被读取）。
4. 随着数据库操作的进行，未被访问的数据页会逐渐变老并移向链表的尾部。同时，新旧子链表中的数据页都会变老。最终，长时间未被使用的数据页会被驱逐出缓冲池。默认情况下，查询读取的数据页会被立即移到新的子链表，使其能够长时间留在缓冲池中。然而，表扫描和后台预读操作可能会导致被访问过的数据页被推到旧的子链表，从而被驱逐。

如果需要提高次LRU算法的效率，可以通过执行"show engine innodb status\G;"命令，查看InnoDB缓冲池的各种指标，包括当前缓冲池的大小以及一个关键的性能指标——内存命中率。

在线上服务中，为了确保响应时间，缓冲池的内存命中率通常应该保持在95%以上。如果某个MySQL实例的命中率低于这个值，就需要检查缓冲池总大小的设置，并且查看是否频繁进行了大范围数据扫描，导致LRU列表被污染。

除了增加缓冲池的大小以提高效率外，当持续存在热点数据的问题时，如果预计未来的热点数据超过了缓冲池的63%，也可以调整中点（midpoint）的值，以减少热点数据被淘汰的概率。

innodb_old_blocks_pct默认值为37%, 即3/8