MySql教程

LRU算法在MySQL中的改进

本文主要是介绍LRU算法在MySQL中的改进,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

LRU算法在MySQL中的应用

Innodb改进了LRU算法,实质上将内存链表分成两段。 靠近头部的young和靠近末尾的old,取5/12段为分界。 新数据在一定时间内只能在old段的头部,当在old段保持了一定的时间后被再次访问才能升级到young。实质上是分了两段lru,这样做的好处是防止大表扫描时,内存数据被全量替换,导致内存命中率急剧下降而造成性能雪崩。

下图是一个 LRU 算法的基本模型。

image

InnoDB 管理 Buffer Pool 的 LRU 算法,是用链表来实现的。

  • 在状态 1 里,链表头部是 P1,表示 P1 是最近刚刚被访问过的数据页;假设内存里只能放下这么多数据页;
  • 这时候有一个读请求访问 P3,因此变成状态 2,P3 被移到最前面;
  • 状态 3 表示,这次访问的数据页是不存在于链表中的,所以需要在 Buffer Pool 中新申请一个数据页 Px,加到链表头部。但是由于内存已经满了,不能申请新的内存。于是,会清空链表末尾 Pm 这个数据页的内存,存入 Px 的内容,然后放到链表头部。
  • 从效果上看,就是最久没有被访问的数据页 Pm,被淘汰了。

这个算法乍一看上去没什么问题,但是如果考虑到要做一个全表扫描,会不会有问题呢?

假设按照这个算法,我们要扫描一个 200G 的表,而这个表是一个历史数据表,平时没有业务访问它。那么,按照这个算法扫描的话,就会把当前的 Buffer Pool 里的数据全部淘汰掉,存入扫描过程中访问到的数据页的内容。也就是说 Buffer Pool 里面主要放的是这个历史数据表的数据。对于一个正在做业务服务的库,这可不妙。你会看到,Buffer Pool 的内存命中率急剧下降,磁盘压力增加,SQL 语句响应变慢。

所以,InnoDB 不能直接使用这个 LRU 算法。实际上,InnoDB 对 LRU 算法做了改进。

image

改进的 LRU 算法在 InnoDB 实现上,按照 5:3 的比例把整个 LRU 链表分成了 young 区域和 old 区域

图中 LRU_old 指向的就是 old 区域的第一个位置,是整个链表的 5/8 处。也就是说,靠近链表头部的 5/8 是 young 区域,靠近链表尾部的 3/8 是 old 区域。

改进后的 LRU 算法执行流程变成了下面这样。

  • 状态 1,要访问数据页 P3,由于 P3 在 young 区域,因此和优化前的 LRU 算法一样,将其移到链表头部,变成状态 2。
  • 之后要访问一个新的不存在于当前链表的数据页,这时候依然是淘汰掉数据页 Pm,但是新插入的数据页 Px,是放在 LRU_old 处。
  • 处于 old 区域的数据页,每次被访问的时候都要做下面这个判断:
    • 若这个数据页在 LRU 链表中存在的时间超过了 1 秒,就把它移动到链表头部。
    • 如果这个数据页在 LRU 链表中存在的时间短于 1 秒,位置保持不变。1 秒这个时间,是由参数 innodb_old_blocks_time 控制的。其默认值是 1000,单位毫秒。

这个策略,就是为了处理类似全表扫描的操作量身定制的。还是以刚刚的扫描 200G 的历史数据表为例,我们看看改进后的 LRU 算法的操作逻辑:

  • 扫描过程中,需要新插入的数据页,都被放到 old 区域 ;
  • 一个数据页里面有多条记录,这个数据页会被多次访问到,但由于是顺序扫描,这个数据页第一次被访问和最后一次被访问的时间间隔不会超过 1 秒,因此还是会被保留在 old 区域;
  • 再继续扫描后续的数据,之前的这个数据页之后也不会再被访问到,于是始终没有机会移到链表头部(也就是 young 区域),很快就会被淘汰出去。

可以看到,这个策略最大的收益,就是在扫描这个大表的过程中,虽然也用到了 Buffer Pool,但是对 young 区域完全没有影响,从而保证了 Buffer Pool 响应正常业务的查询命中率。

这篇关于LRU算法在MySQL中的改进的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!