cache通常用来缓存热点数据，用于加速访问等； 业务这边有一些防重放的需求，简单学习一些cache淘汰策略的需求

• 1. lru
  • 1.1 lru原理
  • 1.2 lru c++ 实现
• 2. lru-k
  • 2.1 lru-k原理
  • 2.2 lru-k c++实现
• 3. lru & innodb

1. lru

1.1 lru原理

lru(least recentl used)最近最久未使用，将最近最久没有使用的数据淘汰。这种cache算法基于这样一种思路：最近访问过的数据，在接下来也有可能会被访问；

从实现来看：将所有数据放入链表，有访问过的数据，放入链表的头部，当链表的容量超过限制的时候，淘汰链表尾部的数据；

1.2 lru c++ 实现

通常在c++实现中，使用std::list 和unordered_map

参考例子：https://github.com/illx10000/relax/blob/master/leetcode-cn/0146.cpp

2. lru-k

当有周期性的批量存取消息在lru 缓存中，cache会被污染，命中率下降，因此引入LRU-K的方式应对缓存污染

2.1 lru-k原理

LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

2.2 lru-k c++实现

通常lru-k实现，会有两条队列，高优先级队列和低优先级队列，大概的思路是冷热分离，如果冷数据访问次数够多，也就变为热数据了；

3. lru & innodb

在《MySQL技术内幕：InnoDB存储引擎（第2版）》 书中介绍到innodb使用了LRUCache管理，但是在LRU列表中就如了Midpoint位置，每次新读入的页，不是直接放入LRU的首部，而是放在列表的5/8地方；

innodb将数据分为old列表和new列表，Midpoint到首部的数据是热数据，MidPoint到数据队尾的数据是冷数据，

================================================================

以下内容来自于：https://blog.51cto.com/14227759/2384690?source=dra

================================================================

一般生产的机器，内存比较大。我们会把innodb_old_blocks_pct值调低，防止热数据被刷出内存。

数据何时在old区，何时进入young区？

好，数据页第一次被加载进BufferPool时在old区头部。

当这个数据页在old区，再次被访问到，会做如下判断

如果这个数据页在LRU链表中old区存在的时间超过了1秒，就把它移动到young区

这个存在时间由innodb_old_blocks_time控制