==作者：YB-Chi==
[toc]
LRU
volatile-lru和allkeys-lru策略都用到了LRU算法。LRU算法的全称是Least Recently Used，从名字上就可以看出，这是按照最近最少使用的原则来筛选数据，最不常用的数据会被筛选出来，而最近频繁使用的数据会留在缓存中。
那具体是怎么筛选的呢？LRU会把所有的数据组织成一个链表，链表的头和尾分别表示MRU端和LRU端，分别代表最近最常使用的数据和最近最不常用的数据 。
如果有一个新数据15要被写入缓存，但此时已经没有缓存空间了，也就是链表没有空余位置了，那么，LRU算法做两件事：
- 数据15是刚被访问的，所以它会被放到MRU端；
- 算法把LRU端的数据5从缓存中删除，相应的链表中就没有数据5的记录了。
其实，LRU算法背后的想法非常朴素：它认为刚刚被访问的数据，肯定还会被再次访问，所以就把它放在MRU端；长久不访问的数据，肯定就不会再被访问了，所以就让它逐渐后移到LRU端，在缓存满时，就优先删除它。
不过，LRU算法在实际实现时，需要用链表管理所有的缓存数据，这会带来额外的空间开销。而且，当有数据被访问时，需要在链表上把该数据移动到MRU端，如果有大量数据被访问，就会带来很多链表移动操作，会很耗时，进而会降低Redis缓存性能。
所以，在Redis中，LRU算法被做了简化，以减轻数据淘汰对缓存性能的影响。具体来说，Redis默认会记录每个数据的最近一次访问的时间戳（由键值对数据结构RedisObject中的lru字段记录）。然后，Redis在决定淘汰的数据时，第一次会随机选出N个数据，把它们作为一个候选集合。接下来，Redis会比较这N个数据的lru字段，把lru字段值最小的数据从缓存中淘汰出去。
Redis提供了一个配置参数maxmemory-samples，这个参数就是Redis选出的数据个数N。例如，我们执行如下命令，可以让Redis选出100个数据作为候选数据集：
1 | CONFIG SET maxmemory-samples 100 |
当需要再次淘汰数据时，Redis需要挑选数据进入第一次淘汰时创建的候选集合。这儿的挑选标准是：能进入候选集合的数据的lru字段值必须小于候选集合中最小的lru值。当有新数据进入候选数据集后，如果候选数据集中的数据个数达到了maxmemory-samples，Redis就把候选数据集中lru字段值最小的数据淘汰出去。
LFU
LFU缓存策略是在LRU策略基础上，为每个数据增加了一个计数器，来统计这个数据的访问次数。当使用LFU策略筛选淘汰数据时，首先会根据数据的访问次数进行筛选，把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同，LFU策略再比较这两个数据的访问时效性，把距离上一次访问时间更久的数据淘汰出缓存。
重点放在缓存污染里介绍
摘选自:极客时间-Redis核心技术与实战