这里主要是针对LRU算法的几种拓展优化思路记录,学习。

 

LRU算法,最近最少使用页面置换算法:

如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。

 

这里提供四种LRU拓展算法。

  • LRU-Middle,指的是MySQL数据库用到的中点插入策略。
  • LRU+FIFO,当数据第一次访问时进入FIFO队列,二次命中再放入LRU链表中。
  • LRU-K,这里K代表最近使用过的次数。
  • Multi-Queue,根据访问频率将数据划分为多个队列,不同的队列具有不同的访问优先级

 

LRU-Middle

这个算法的思想来自于《深入浅出MySQL》,里面提到了InnoDB和MyISAM引擎的中点插入策略。

这里以InnoDB引擎为例,简单理解算法思想。

InnoDB也实现了自己的缓存,称为Buffer Pool,我们将它分为 sublist_of_new_block(young区域)和sublist_of_old_block(old区域)

当然了这两个区域其实还是在LRU List里面,只是young在表头,old在表尾。

插入的时候,插入到old的头部(相当于表的中间位置),删除则从old表尾删除。

二次访问,则会将old区域的数据提升到young区域中。

 

最简单的一句话就是:插入在表中,二次访问提升,删除从表尾。

解决的问题就是,当数据访问次数极少时,插入到表中会比在表头更快淘汰。

 

LRU+FIFO

这个方案解决的想法跟LRU-Middle类似,它有两个缓存队列,一个是FIFO队列,一个是LRU队列。

当数据第一次访问时,放入到FIFO队列中,当二次命中则移到LRU队列中。

两个队列按照自己的逻辑运行即可。

 

新的数据插入在FIFO,如果没有二次访问,则最终会被淘汰。

如果被二次访问,则移动到LRU头部,淘汰LRU末尾的数据。

 

LRU-K

这里K代表最近使用次数,所以LRU可以被理解为LRU-1,表示最近使用过1次,就放入缓存。

而LRU-K则是将最近使用过一次的标准提升为最近使用过K次。

这个算法可以解决LRU缓存污染的问题。

缓存污染是指操作系统将不常用的数据从内存移到缓存,降低了缓存效率的现象。

 

LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史(后面称为历史访问列表)。

当数据第一次访问时,加入到历史访问列表中,如果它没有达到K次访问,则按照FIFO、LRU之类的规则淘汰。

只有当数据的访问次数达到K次的时候,才将它从历史访问列表中移到缓存队列中,并缓存数据(注意在历史访问列表中的数据是不被缓存的)。

 

当需要淘汰数据时,我思考了两种淘汰方案:

  1. 淘汰倒数第K次访问时间点距离当前时间最大的数据。
  2. 淘汰上次访问时间点距离当前时间最大的数据。

 

从淘汰上讲,方案1符合了LFU算法思想,一段时间内命中次数多。

从实现上讲,方案2更符合LRU设计思想,删除最近没有访问的数据。

从编码上讲,方案2更省内存,毕竟我不想去存储最近K次的访问时间,更想只存储一个时间点。

 

举个例子,A和B的访问时间是:

  • A:1-3-5-7-9
  • B:0-2-4-8-10

如果按照倒数K次的话,假设这里K = 3,那么应该淘汰B,因为B倒数第3次访问时间点4比A在时间点5要早,A在更短的时间内命中了K次。

如果按照上次访问时间,那么应该淘汰A,因为B的最后一次访问时间点比A更晚,更符合最近访问过的数据。

 

根据LRU算法设计,就应该选用方案2。

提一句LFU算法:最近最不常用页面置换算法,也就是淘汰一定时期内被访问次数最少的页,符合方案1。

 

关于K的取值,在实际应用中,LRU-2是综合最优的选择。

 

Multi-Queue(MQ)

MQ算法将数据划分为多个队列,不同队列具有不同的访问优先级。

其核心思想:优先缓存访问次数多的数据

举个例子🌰:

如果在低优先级队列中一个数据访问达到一定次数,需要提升优先级,将数据从当前优先级队列移动到上一级优先级队列中。

如果在高优先级队列中一个数据长时间没有被访问,当新数据进来,那么长时间未被访问的数据就移到低一级优先级的队列中。

需要淘汰数据时,从最低一级的队列按照LRU规则淘汰。

当数据被淘汰时,将数据从缓存中删除,将数据的索引放入历史访问队列中,如果重新访问数据,则再次计算优先级,移到目标队列头部。

 

MQ算法需要维护多个队列以及多个页面的数据,成本较大,复杂度也比LRU高。

 

 

LFU算法思想

我们先看一个数据访问例子:横轴是时间点,纵轴是不同的数据访问ABCD。

如果采用LRU算法,缓存大小是2,那么我们依据时间线会发现缓存内容如下:

我们可以看到开头的10个时间点,有6次未命中记录。

 

我们回顾淘汰的本质,就是想保留最可能再次访问的数据。

LRU是认为,最近被访问的数据,将来最有可能被访问。

LFU的思想则是:最频繁被访问的数据,将来最有可能被访问。

 

那么根据LFU算法,我们得出的时间点是这样:

这里缓存淘汰优先按次数排序,次数一致则按最后一次访问时间决定。

 

LFU算法存在的问题:

  1. LFU算法要求严格按照计数器进行排序,新增节点或者更新节点时效率是O(N)。
  2. 简单计数并不完美,访问模式可能频繁变化。一段时间内频繁访问的数据,可能之后很少用到。

问题的解决思路:

  1. 第一个问题可以维护待淘汰的pool,这样相对整体来说更新的效率会变高。
  2. 记录最后访问的时间,随着时间推移,降低计数器,这样就减小它的优先级。

 

LRU算法拓展 与 LFU算法思想
Tagged on:     
0 0 vote
Article Rating
订阅
提醒
0 评论
Inline Feedbacks
View all comments