redis内存不足时的淘汰策略
一般情况下，当内存超出物理内存限制时，内存数据将与磁盘产生频繁交换(swap)，swap会导致redis性能急剧下降，对于访问量较大的情况下，swap的存取效率会让服务基本处于不可用的状态。
在生产环境中，一般不允许redis出现swap行为，redis提供了 maxmemory 设置其最多可占用的内存空间。
当redis使用的内存超出maxmemory时，此时已经没有多余可用的内存空间，新的数据将无法写入，redis提供了几种数据淘汰策略，用于清理数据，腾出空间以继续提供服务。
淘汰策略
- noeviction
不会继续服务写请求(del请求可以)，读请求可以继续进行，即可读不可写，该策略不会丢失数据，但是同样生产的写请求不可用也会让业务无法进行下去，这种策略是默认策略。
- volatile-lru
淘汰具有过期时间的key，最少使用的key优先淘汰，没有过期时间的key不会被淘汰，该策略可以保证持久化的数据不被丢失。
- volatile-ttl
与 2 类似，区别是比较过期时间ttl的值，值越小越优先淘汰。
- volatile-random
与 2、3 类似，区别是随机淘汰具备过期时间的key，不分使用频率和过期时间长短。
- allkeys-lru
与 2 类似，不过该淘汰策略范围是redis中的所有key，不区分是否有过期时间，但是区分使用频率。
- allkeys-random
与 5 类似，范围是所有的key，但是不区分使用频率。
volatile开头的只会淘汰带有过期时间的key，allkeys则是所有的key，如果redis只是作为缓存使用，可以使用allkeys，如果有些数据是务必持久化的，则使用volatile。
LRU算法
LRU 即 Least Recently Used (最近最少使用) 算法，常用于操作系统的页面置换，以及一些常见框架的缓存数据淘汰，原理是空间不够时，选择一些最近没有使用过的数据进行淘汰。
实现LRU算法，需要一个key/value字典，以及一个链表，链表中的元素按照一定的顺序进行排列，当字典中的某个元素被访问时，其在链表中的位置将移动到表头，当空间满时，淘汰掉链表尾部的元素，所以链表的排序方式就是最近被访问的时间顺序。
LinkedHashMap
Java中的LinkedHashMap可以帮我们实现一个LRU功能, 如下方demo，LinkedHashMap构造函数第三个值意思是根据插入顺序排序还是根据访问顺序排序，
removeEldestEntry方法默认返回false，当返回true时，将移除最久没有使用的节点，因此当容量到达缓存限制时，进行移除节点操作。
public static void main(String[] args) {
// 最多缓存数量
int cacheSize = 3;
// 负载因子
float loadFactor = 0.75f;
// 最大容量 = （缓存大小 / 负载因子）+ 1，保证不会触发自动扩容
int capacity = (int) (cacheSize / loadFactor) + 1;
LinkedHashMap<String, String> cache = new LinkedHashMap<String, String>(capacity, loadFactor, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > cacheSize;
}
};
cache.put("1", "1");
cache.put("2", "2");
cache.put("3", "3");
System.out.println(cache);
cache.put("4", "4");
System.out.println(cache);
}
LinkedHashMap实现思路大致是：
- 用链表存储数据
- 一个节点被访问后，将其置于链表尾
- 链表头结点就是最近最久未使用的节点，直接移除即可
近似LRU算法
Redis使用近似LRU算法，因为LRU算法还需要一个链表按照访问时间顺序保存节点，这将占用大量的额外内存，
近似LRU算法是Redis在现有的数据结构基础上使用随机采样法来淘汰元素，可以达到与LRU算法非常近似的效果，Redis给每个key增加了一个额外的小字段，长度为24个bit，用于保存最后一次访问的时间戳。
随机采样
近似LRU算法触发是在Redis执行写操作时，发现内存超出 maxmemory 的值了，就会执行一次该算法，通过随机采样出 maxmemory_samples (默认值为5) 个key，然后淘汰掉最旧的一个key，如果淘汰后内存还是超出maxmemory，那就继续随机采样淘汰，直到低于maxmemory。
采样的数据根据 maxmemory-policy 的设置决定，如果是allkeys，在所有的字典key中进行采样，如果是volatile，则在具有过期时间key的字典中采样，采样的数量根据 maxmemory_samples 配置得来，采样数量越大，近似LRU算法的效果越接近严格LRU算法，
同时在Redis3.0中，还增加了一个淘汰池数组，大小是 maxmemory_samples，在每一次淘汰循环中，新的采样出来的key会和淘汰池中的key进行融合，淘汰掉最旧的一个key，然后将剩余最旧的key列表放入淘汰池，等待下次循环。
