分析理解Redis内存淘汰策略相关知识 - 主机乐

Redis中有很多无效的缓存，这些缓存数据会降低数据IO的性能，因为不同的数据类型时间复杂度算法不同，数据越多可能会造成性能下降
随着系统的运行，redis的数据越来越多，会导致物理内存不足。通过使用虚拟内存（VM），将很少访问的数据交换到磁盘上，腾出内存空间的方法来解决物理内存不足的情况。虽然能够解决物理内存不足导致的问题，但是由于这部分数据是存储在磁盘上，如果在高并发场景中，频繁访问虚拟内存空间会严重降低系统性能。

所以遇到这类问题的时候，我们一般有几种方法。

对每个存储到redis中的key设置过期时间，这个根据实际业务场景来决定。否则，再大的内存都会随着系统运行被消耗完
增加内存
使用内存淘汰策略

二、设置内存

在实际生产环境中，服务器不仅仅只有Redis，为了避免Redis内存使用过多对其他程序造成影响，我们一般会设置最大内存。Redis默认的最大内存 maxmemory=0 ，表示不限制Redis内存的使用。我们可以修改 redis.conf 文件，设置Redis最大使用的内存。

双向链表的查找时间复杂度是O(n)，删除和插入是O(1)，借助HashMap结构，可以使得查找的时间复杂度变成O(1)。
Hash表用来查询在链表中的数据位置，链表负责数据的插入，当新数据插入到链表头部时有两种情况。

链表满了，把链表尾部的数据丢弃掉，新加入的缓存直接加入到链表头中。
当链表中的某个缓存被命中时，直接把数据移到链表头部，原本在头节点的缓存就向链表尾部移动。

这样，经过多次Cache操作之后，最近被命中的缓存，都会存在链表头部的方向，没有命中的，都会在链表尾部方向，当需要替换内容时，由于链表尾部是最少被命中的，我们只需要淘汰链表尾部的数据即可。
java代码实现简单的LRU算法

回收池满了，并且当前插入的key的空闲时间最小（也就是回收池中的所有key都比当前插入的key的空闲时间都要大），则不作任何操作。
回收池未满，并且插入的位置x没有键，则直接插入即可
回收池未满，且插入的位置x原本已经存在要淘汰的键，则把第x个以后的元素都往后挪一个位置，然后再执行插入操作。
回收池满了，将当前第x个以前的元素往前挪一个位置（实际就是淘汰了），然后执行插入操作。

这样做的目的是能够选出最真实的最少被访问的key，能够正确选择不常使用的key。因为在Redis3.0之前是随机选取样本，这样的方式很有可能不是真正意义上的最少访问的key。LRU算法有一个弊端，假如一个key值访问频率很低，但是最近一次被访问到了，那LRU会认为它是热点数据，不会被淘汰。同样，经常被访问的数据，最近一段时间没有被访问，这样会导致这些数据被淘汰掉，导致误判而淘汰掉热点数据，于是在Redis 4.0中，新加了一种LFU算法。

五、LFU

LFU（Least Frequently Used），表示最近最少使用，它和key的使用次数有关，其思想是：根据key最近被访问的频率进行淘汰，比较少访问的key优先淘汰，反之则保留。LFU的原理是使用计数器来对key进行排序，每次key被访问时，计数器会增大，当计数器越大，意味着当前key的访问越频繁，也就是意味着它是热点数据。它很好的解决了LRU算法的缺陷：一个很久没有被访问的key，偶尔被访问一次，导致被误认为是热点数据的问题。LFU的实现原理如下图所示，LFU维护了两个链表，横向组成的链表用来存储访问频率，每个访问频率的节点下存储另外一个具有相同访问频率的缓存数据。具体的工作原理是：