Redis之淘汰策略

2021-09-24 01:30:43

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列表放入淘汰池，等待下次循环。

码农公寓