lru

ru(least recently used)是一种缓存置换算法。即在缓存有限的情况下，如果有新的数据需要加载进缓存，则需要将最不可能被继续访问的缓存剔除掉。因为缓存是否可能被访问到没法做预测，所以基于如下假设实现该算法:

如果一个key经常被访问，那么该key的idle time应该是最小的。

(但这个假设也是基于概率，并不是充要条件,很明显,idle time最小的,甚至都不一定会被再次访问到)

这也就是lru的实现思路。首先实现一个双向链表,每次有一个key被访问之后，就把被访问的key放到链表的头部。当缓存不够时,直接从尾部逐个摘除。

在这种假设下的实现方法很明显会有一个问题，例如mysql中执行如下一条语句

select * from table_a;
如果table_a中有大量数据并且读取之后不会继续使用,则lru头部会被大量的table_a中的数据占据。这样会造成热点数据被逐出缓存从而导致大量的磁盘io

mysql innodb的buffer pool使用了一种改进的lru算法，大意是将lru链表分成两部分，一部分为newlist,一部分为oldlist,newlist是头部热点数据，oldlist是非热点数据,oldlist默认占整个list长度的3/8.当初次加载一个page的时候，会首先放入oldlist的头部，再次访问时才会移动到newlist.具体参考如下文章:

https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html

https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html

https://redis.io/topics/lru-cache

http://antirez.com/news/109