过期删除策略

定时过期
每个设置过期时间的key都需要创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好；但是会占用大量的CPU资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。
惰性过期
只有当访问一个key时，才会判断该key是否已过期，过期则清除。该策略可以最大化地节省CPU资源，却对内存非常不友好。极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。
定期过期
每隔一定的时间，会扫描一定数量的数据库的expires字典中一定数量的key，并清除其中已过期的key。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果。
(expires字典会保存所有设置了过期时间的key的过期时间数据，其中，key是指向键空间中的某个键的指针，value是该键的毫秒精度的UNIX时间戳表示的过期时间。键空间是指该Redis集群中保存的所有键。)

内存淘汰策略
  1. noeviction：当内存使用超过配置的时候会返回错误，不会驱逐任何键
  2. allkeys-lru：加入键的时候，如果过限，首先通过LRU算法驱逐最久没有使用的键
  3. volatile-lru：加入键的时候如果过限，首先从设置了过期时间的键集合中驱逐最久没有使用的键
  4. allkeys-random：加入键的时候如果过限，从所有key随机删除
  5. volatile-random：加入键的时候如果过限，从过期键的集合中随机驱逐
  6. volatile-ttl：从配置了过期时间的键中驱逐马上就要过期的键
  7. volatile-lfu：从所有配置了过期时间的键中驱逐使用频率最少的键
  8. allkeys-lfu：从所有键中驱逐使用频率最少的键

Redis的内存淘汰策略的选取并不会影响过期的key的处理。内存淘汰策略用于处理内存不足时的需要申请额外空间的数据；过期策略用于处理过期的缓存数据。

Redis LRU

LRU(least recently used)是一种缓存置换算法。即在缓存有限的情况下，如果有新的数据需要加载进缓存，则需要将最不可能被继续访问的缓存剔除掉。
最早版本
随机从dict中取出五个key,淘汰一个lru字段值最小的。(随机选取的key是个可配置的参数maxmemory-samples,默认值为5).
3.0 版本
首先第一次随机选取的key都会放入一个pool中(pool的大小为16),pool中的key是按lru大小顺序排列的。接下来每次随机选取的keylru值必须小于pool中最小的lru才会继续放入，直到将pool放满。放满之后，每次如果有新的key需要放入，需要将pool中lru最大的一个key取出。

手写LRU

  1. hashmap + 双向链表

  2. 使用LinkedHashMap, jdk源码说明是很好lru实现类

    1. public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    2.  private final int CACHE_SIZE;
    4.  // 这里就是传递进来最多能缓存多少数据
    5.  public LRUCache(int cacheSize) {
    6. //  true指linkedhashmap将元素按访问顺序排序
    7.      super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
    8.      CACHE_SIZE = cacheSize;
    9.  }
    11.  @Override
    12.  protected boolean removeEldestEntry(Map.Entry eldest) {
    13. // 当KV数据量大于指定缓存个数时，就自动删除最老数据
    14.      return size() > CACHE_SIZE;
    15.  }
    16. }

    Redis LFU

    LFU(least frequently used)
    键值对的访问频率记录和更新