Redis第五讲 Redis内存淘汰策略之LRU与LFU算法详细介绍

前面介绍了Redis的一些内存淘汰策略，一般比较常用的两种淘汰策略为LRU,LFU，而且他们的算法考察的也比较多。

LRU(最近最久未使用)

标准LRU算法是这样的：它把数据存放在链表中按照“最近访问”的顺序排列，当某个key被访问时就将此key移动到链表的头部，保证了最近访问过的元素在链表的头部或前面。当链表满了之后，就将"最近最久未使用"的，即链表尾部的元素删除，再将新的元素添加至链表头部。其中LinkedHashMapt就可以通过访问的顺序来实现LRU算法。

一般的LRU的做法如下：
1、为每个节点设置一个prev前继节点指针和next后继节点指针，将所有节点通过这两个指针连接成一个链表，链表有着head和tail节点。
2、用一个哈希表将key和对应的节点存放起来，用来快速的找到key对应的节点
3、当通过key访问对应的节点的时候，通过哈希表查询key得到对应的节点。然后通过节点的的prev和next指针将节点从链表中移除，并将节点放到链表的头部中。
4、当新加入key和节点的时候，如果对应的链表已经满了，就将尾部的节点去除，然后将新节点加入到链表的头部。

从上述流程可以看出，基于链表和哈希表的LRU需要设置prev指针、next指针、以及hash表中的key和value的指针，这是一个很大的内存开销。

因为标准LRU算法需要消耗大量的内存，所以Redis采用了一种近似LRU的做法 给每个key增加一个大小为24bit的属性字段，代表最后一次被访问的时间戳。然后随机采样出5个key，淘汰掉最旧的key，直到Redis占用内存小于maxmemory为止。其中随机采