阿里面试官问我: LRU 和 Innodb Buffer Pool 有什么关系?

你好,我是yes。

这个问题来自我的 VIP 读者,他在简历里写了熟悉 MySQL ,然后被问了 LRU 相关实现之后紧接着被问与 Innodb Buffer Pool 的联系,然后读者就蒙了。

所以 LRU 和 Innodb Buffer Pool 有什么联系吗?

确实有。

其实我之前的文章写到过这个,就在今年的三月份,不过是写 Kafka 的冷热分区时顺带提了一下 Innodb Buffer Pool。

今天咱们再来仔细盘一盘它们两者之间的联系,还是挺有启发的。

Buffer Pool

Buffer Pool 翻译过来就是缓冲池,缓冲什么呢?缓冲的就是数据库的数据。

数据库的数据都是要落盘存储的,但硬盘的访问速度又过于缓慢,所以需要把硬盘内部的数据加载到内存中,这样数据库直接从内存读取数据,减少磁盘的 I/O,速度就快了。

其实借助操作系统的 page cache 就能透明的实现这个功能,但是这不便于数据库自身对数据的管理,因为操作系统上还有很多其他程序也会使用 page cache。

所以 MySQL 就自己划了个池子来管理数据,即 Buffer Pool。

LRU

但是 Buffer Pool 是有限的,因为内存是有限的,一般而言内存不会比硬盘大吧?

所以想要把硬盘上的所有数据都加载到内存中是不实际的。当请求的数据不在内存的时候,不得不去硬盘拿,而这种时候查询速度就会变慢,用户在使用上的直接反应是:为什么这个破网站这么卡?

因此,我们要尽可能的避免这种情况的发生,也就是提高缓存的命中率。

如何提高呢?

当内存存储的数据满了的时候,把用户经常访问的数据保留着,淘汰一些不经常被访问的数据,腾出位置存放新访问的数据。

这样不就能提高缓存命中率了?

冷热数据就是有这样的特性,类比微博热搜,越热的数据,访问量就越大,越冷门的数据越没有人访问。

根据这个特性,LRU 就很合适,Least Recently Used,最近最少使用。根据这个算法就能选择最近最少使用的数据淘汰之~

第五层

如果就回答到上面那个程度,还不够,满足不了面试官对你的期望。

我们来想一下普通的 LRU 实现在 buffer 管理这个场景会有什么问题。

下图为先后访问数据 6 和数据 3 之后的情况。

阿里面试官问我: LRU 和 Innodb Buffer Pool 有什么关系?

可以看到,被访问的数据会被移到的头部,如果内存不足,会淘汰尾部的数据。

这种实现放在 Buffer Pool 中会有什么问题?

首先你需要了解一个原理:局部性原理

  • 时间局部性:如果一个数据现在被访问了,在近期可能还会被多次访问。
  • 空间局部性:如果一个数据被访问了,那么存储在它附近的数据,很有可能立马被访问。

在硬件、操作系统、应用程序有很多都根据局部性原理做了对应的实现,像磁盘就有预读功能来减少磁盘I/O。

对应到 Buffer Pool 中也实现了预读的功能。当顺序访问数据页面到达一定的数量或者一个 extent(页面管理的逻辑分区)中有很多页面被加载的时候,Innodb 都会预读页面加载到 Buffer Pool 中。

预读是好事,如果用朴素的 LRU 来实现数据的淘汰就有点问题。

因为预读的数据也会被移动到头部,这样头部原本的热数据就会更靠后了,面临着被淘汰的危机,如果预读的数据有用那没事,如果没用的话,这波就是好心做了坏事。

所以怎么办?

冷热分区,又称老年代和新生代(有 JVM 那味儿了)

Innodb 将缓冲池分为了新生代和老年代。默认头部的 63% 为新生代,尾部 37% 为老年代。

阿里面试官问我: LRU 和 Innodb Buffer Pool 有什么关系?

当第一次从磁盘加载数据到 Buffer Pool 时,会将数据放置在老年代的头部,而不是新生代的头部,这样即使有预读功能也不会把前面的热数据给顶一下。

然后下次访问这个数据的时候,会把数据从老年代移动带新生代的头部。

好像已经很完美了?我们再来看另一种情况全表扫描

全表扫描是我们在日常开发中需避免的一种查询,但是有时候就是有需求会全表扫描,或者不经意的错误使用导致全表扫描。

这时候会有很多冷数据被加载到 Buffer Pool 中,被放在老年代,紧接着肯定又会对全表扫描到的数据进行一波处理,那这样这些数据再次被访问,就会被放到新生代的头部,这样就会大量淘汰热区的数据。

一次全表扫描,就替换了很多热数据,降低了缓存的命中率,这波有点伤。

所以怎么办?

加个时间判断

因为全表扫描的数据,大部分紧接着就会被访问,然后之后就没用了,于是 Innodb 设置了一个时间窗口,默认是1s。

即在老年代数据被再次访问的时间与之前被访问的时间间隔超过1s,才会晋升到新生代,否则还是在老年代,这样就不会污染新生代的热数据。

这波有点秀吧。

所以 Innodb 针对数据库数据访问的特性,基于分区和时间窗口两个实现改进了 LRU 淘汰缓存页的机制,提高了缓存的命中率,提升了查询效率。

所以,面试官如果问你* LRU 与 Innodb Buffer Pool 之间有什么联系吗?*就用我上面这句话回答即可。

​紧接着等他深入询问,再把上面的缘由解释给他听,这波就OK了。

如果面试官问:还有吗?

那下面这个回答可以用上:有。

如果按照普通的 LRU 实现,新生代页面的访问会频繁把数据移动到头部,这个移动是有开销的,而且在很大程度上没有必要,你想想都是热数据自个儿在那移动来移动去的,是不是又是白给?

所以新生代又可以被分个区,新生代前面四分之一的数据访问不会被移动到头部,后面四分之三的数据范围才会被移动到头部(这个内容参考自《从根儿上理解MySQL》,我没看过源码不清楚 Innodb是否真的是这样实现)。

这波回答可以说差不多在第五层了。

不过关于 LRU 变型实现还有很多,比如和 CDN 相关的 TLRU,和 CPU cache 相关的 PLRU 等等,有兴趣的同学自行查询,这里就不做展开了。

最后

好了,至此想必你已经能说清 LRU 与 Innodb Buffer Pool 两者的关系啦。

上面说的冷热分区的比例是可以调整的,参数是:innodb_old_blocks_pct

还有我上面都是用数据作为单位来移动头部和尾部,这只是为了便于理解。其实 Buffer Pool 是基于页来管理数据的,等我下篇再来好好盘盘 Buffer Pool 吧。

上一篇:关于java文件下载文件名乱码问题解决方案


下一篇:【.net】在ASP.NET中,IE与Firefox下载文件名中带中文汉字的文件,文件名乱码的问题