Redis源码解析：缓存淘汰策略

Redis内存满了该怎么办？

Redis是一个内存数据库，当Redis使用的内存超过物理内存的限制后，内存数据会和磁盘产生频繁的交换，交换会导致Redis性能急剧下降。所以在生产环境中我们通过配置参数maxmemoey来限制使用的内存大小。

在redis.conf中和缓存淘汰策略相关的有如下2个配置

maxmemory: 设置Redis server可以使用的最大内存容量，一旦超过最大容量，会按照maxmemory-policy配置的策略进行内存淘汰操作

maxmemory-policy: 设置内存淘汰策略，主要有近似lru，近似lfu，ttl和随机淘汰这几种策略

当实际使用的内存超过maxmemoey后，Redis提供了如下几种可选策略。

noeviction：写请求返回错误

volatile-lru：使用lru算法删除设置了过期时间的键值对

volatile-lfu：使用lfu算法删除设置了过期时间的键值对

volatile-random：在设置了过期时间的键值对中随机进行删除

volatile-ttl：根据过期时间的先后进行删除，越早过期的越先被删除

allkeys-lru：在所有键值对中，使用lru算法进行删除

allkeys-lfu：在所有键值对中，使用lfu算法进行删除

allkeys-random：所有键值对中随机删除

我们来详细了解一下lru和lfu算法，这是2个常见的缓存淘汰算法。因为计算机缓存的容量是有限的，所以我们要删除那些没用的数据，而这两种算法的区别就是判定没用的纬度不一样。

LRU算法

lru（Least recently used，最近最少使用）算法，即最近访问的数据，后续很大概率还会被访问到，即是有用的。而长时间未被访问的数据，应该被淘汰

lru算法中数据会被放到一个链表中，链表的头节点为最近被访问的数据，链表的尾节点为长时间没有被访问的数据

lru算法的核心实现就是哈希表加双向链表。链表可以用来维护访问元素的顺序，而hash表可以帮我们在O(1)时间复杂度下访问到元素。

至于为什么是双向链表呢？主要是要删除元素，所以要获取前继节点。数据结构图示如下

使用双向链表+HashMap

举个例子演示一下LRU算法是如何工作的

LRUCache cache = new LRUCache(2);
// 左边是队头，右边是队尾

cache.put(1, 1);
// cache = [(1, 1)]

cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
// 一直往队头放

cache.get(1);
// cache = [(1, 1), (2, 2)]
// 元素被访问了，放到队头

cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 缓存容量满了，删除最久未使用的元素
// 然后把新元素放入队头

我们首先先定义链表的节点

public class ListNode<K, V> {
    K key;
    V value;
    ListNode pre;
    ListNode next;

    public ListNode() {}

    public ListNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

接着定义双向链表，可以看到head和tail节点并不是链表中实际的头节点和尾节点，而是假头和假尾，之所以定义假头和假尾，主要是为了简化删除节点操作，不然当删除头节点和尾节点的时候需要特判

另外需要注意的是我们这个实现是访问最频繁的数据放在队尾

public class DoubleList {

    ListNode head;
    ListNode tail;

    public DoubleList() {
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.pre = head;
    }

    public void remove(ListNode node) {
    }

    public void addLast(ListNode node) {
    }

    public ListNode removeFirst() {
    }
}

增加了假头和假尾节点后，链表的删除和增加对于你来说应该不难了吧！

// DoubleList
public void remove(ListNode node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
}

// 将节点加到链表尾部
public void addLast(ListNode node) {
    tail.pre.next = node;
    node.next = tail;
    node.pre = tail.pre;
    tail.pre = node;
}

// 删除链表的头节点
public ListNode removeFirst() {
    ListNode removeNode = head.next;
    remove(removeNode);
    return removeNode;
}

封装一个缓存类，实现为双向链表和HashMap

public class LRUCache {

    int capacity;
    DoubleList doubleList;
    Map<Integer, ListNode> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        doubleList = new DoubleList();
    }

    public int get(int key) {
    }

    public void put(int key, int value) {
    }
}

我们来实现get和put方法，因为对LRUCache的操作会涉及到对两种具体数据结构的操作。因此我们再抽象一层，对数据结构操作的逻辑封装成方法，这样不会乱，并且代码更清晰

public int get(int key) {
    ListNode listNode = map.get(key);
    if (listNode == null) {
        return -1;
    }
    // 将节点变成最新访问的节点
    // 涉及到2个操作，删除原来的节点，并添加新节点到链表尾部
    this.makeRecent(listNode);
    return listNode.value;
}

public void put(int key, int value) {
    ListNode listNode = map.get(key);

    if (listNode != null) {
        this.makeRecent(listNode);
        listNode.value = value;
        return;
    }

    if (map.size() == capacity) {
        // 删除最长事件没有访问的节点
        // 即删除链表的头节点和对应HashMap中的值
        removeOld();
    }

	// 增加最新访问的节点
	// 即将节点增加到链表尾部，并放到HashMap中
    addRecent(key, value);

}

上面抽象的方法我们再做具体实现

public void makeRecent(ListNode listNode) {
    doubleList.remove(listNode);
    doubleList.addLast(listNode);
}

public void addRecent(int key, int value) {
    ListNode listNode = new ListNode(key, value);
    doubleList.addLast(listNode);
    map.put(key, listNode);
}

public void removeOld() {
    ListNode listNode = doubleList.removeFirst();
    map.remove(listNode.key);
}

因为LinkedHashMap的底层实现就是哈希表加双向链表，所以你可以用LinkedHashMap替换HashMap和DoubleList来改写一下上面的类。

我来演示一下更骚的操作，只需要重写一下构造函数和removeEldestEntry方法即可。

使用LinkedHashMap实现LRU

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private int cacheSize;


    public LruCache(int cacheSize) {
        /**
         * initialCapacity: 初始容量大小
         * loadFactor: 负载因子
         * accessOrder: false基于插入排序（默认），true基于访问排序
         */
        super(cacheSize, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    /**
     * 当调用put或者putAll方法时会调用如下方法，是否删除最老的数据，默认为false
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}

注意这个缓存并不是线程安全的，可以调用Collections.synchronizedMap方法返回线程安全的map

LruCache<String, String> lruCache = new LruCache(3);
Map<String, String> safeMap = Collections.synchronizedMap(lruCache);

Collections.synchronizedMap实现线程安全的方式很简单，只是返回一个代理类。代理类对Map接口的所有方法加锁

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    return new SynchronizedMap<>(m);
}

都看到这了，你就顺便把LeetCode的这道算法题给AC了把

https://leetcode-cn.com/problems/lru-cache/

LFU算法

LRU算法有一个问题，当一个长时间不被访问的key，偶尔被访问一下后，可能会造成比这个key访问更频繁的key被淘汰。

即LRU算法对key的冷热程度的判断可能不准确。而LFU算法（Least Frequently Used，最不经常使用）则是按照访问频率来判断key的冷热程度的，每次删除的是访问频率最低的数据，当有多个key的访问频率一样时，则删除最旧的数据

首先还是来演示一下LFU算法是如何工作的

LFUCache cache = new LFUCache(2);

cache.put(1, 1);

cache.put(2, 2);

cache.get(1);
// 键 1 的访问频率增加1

cache.put(3, 3);
// 缓存容量满了，删除访问频率最低的键 2

cache.get(2);
// 键 2 已被删除，返回-1

我们应该如何组织数据呢？

当我们实现LRU算法的时候使用一个map加一个双向链表来实现的，那么实现LFU算法应该如何组织数据？

首先为了实现键值的对快速访问，用一个map来保存键值对

private HashMap<Integer, Integer> keyToVal;

另外还需要用一个map来保存键的访问频率

private HashMap<Integer, Integer> keyToFreq;

接下来就是最核心的部分，删除访问频率最低的数据。

为了能在O(1)时间复杂度内找到访问频率最低的数据，我们需要一个变量minFreq记录访问最低的频率
每个访问频率有可能对应多个键。当空间不够用时，我们要删除最早被访问的数据，所以需要如下数据结构，Map<频率, 有序集合>。每次内存不够用时，删除有序集合的第一个元素即可。并且这个有序集合要能快速删除某个key，因为某个key被访问后，需要从这个集合中删除，加入freq+1对应的集合中
有序集合很多，但是能满足快速删除某个key的只有set，但是set插入数据是无序的。幸亏Java有LinkedHashSet这个类，链表和集合的结合体，链表不能快速删除元素，但是能保证插入顺序。集合内部元素无序，但是能快速删除元素，完美

我们将LFUCache定义如下

public class LFUCache {

    Map<Integer, Integer> keyToVal;
    Map<Integer, Integer> keyToFreq;
    Map<Integer, LinkedHashSet<Integer>> freqTokeys;

    // 最小的频次
    int minFreq;
    int capacity;

    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqTokeys = new HashMap<>();
        this.capacity = capacity;
        this.minFreq = 0;
    }

    public int get(int key) {
    }

    public void put(int key, int value) {
    }
}

接着就是实现get和put方法，老规矩还是将复杂的操作抽象出来

public int get(int key) {
    Integer v = keyToVal.get(key);
    if (v == null) {
        return -1;
    }
    // 增加key对应的频率
    increaseFrey(key);
    return v;
}

public void put(int key, int value) {
    if (keyToVal.containsKey(key)) {
        // 重新设置值
        keyToVal.put(key, value);
        increaseFrey(key);
        return;
    }

    // 超出容量，删除频率最低的key
    if (keyToVal.size() == capacity) {
        // 删除访问频率最低的key
        removeMinFreqKey();
    }

    keyToVal.put(key, value);
    keyToFreq.put(key, 1);
    freqTokeys.putIfAbsent(1, new LinkedHashSet<>());
    freqTokeys.get(1).add(key);
    this.minFreq = 1;
}

最后实现抽象的方法

// 增加频率
private void increaseFrey(int key) {
    int freq = keyToFreq.get(key);
    keyToFreq.put(key, freq + 1);
    freqTokeys.get(freq).remove(key);
    freqTokeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
    freqTokeys.get(freq + 1).add(key);
    if (freqTokeys.get(freq).isEmpty()) {
        freqTokeys.remove(freq);
        // 最小频率的set为空，key被移动到minFreq+1对应的set了
        // 所以minFreq也要加1
        if (freq == this.minFreq) {
            this.minFreq++;
        }
    }
}

// 删除出现频率最低的key
private void removeMinFreqKey() {
    LinkedHashSet<Integer> keyList = freqTokeys.get(minFreq);
    Integer deleteKey = keyList.iterator().next();
    keyList.remove(deleteKey);
    if (keyList.isEmpty()) {
        // 这里删除元素后不需要重新设置minFreq
        // 因为put方法执行完会将minFreq设置为1
        freqTokeys.remove(keyList);
    }
    keyToVal.remove(deleteKey);
    keyToFreq.remove(deleteKey);
}

都看到这了，你就顺便把LeetCode的这道算法题给AC了把

https://leetcode-cn.com/problems/lfu-cache/

在Redis中的LRU和LFU算法并不是严格按照上面的思路来的，而是采用近似LRU和LFU算法，效果相差不大，有对算法的实现细节感兴趣的小伙伴可以看看其他文章，我就不多做介绍了

参考博客

lru算法和lfu算法
[1]https://my.oschina.net/lscherish/blog/4467394
海子大佬的页面置换算法
[2]https://www.cnblogs.com/dolphin0520/p/3749259.html
[3]leetcode lru算法
https://leetcode-cn.com/problems/lru-cache-lcci/
[4]leetcode lfu算法
https://leetcode-cn.com/problems/lfu-cache
[5]https://labuladong.gitee.io/algo/2/21/45/
lfu算法
[6]https://mp.weixin.qq.com/s/oXv03m1J8TwtHwMJEZ1ApQ
redis经典面试题
[7]https://stor.51cto.com/art/202103/651799.htm
redis中的lru
[1]https://segmentfault.com/a/1190000017555834

本文标题：Redis源码解析：缓存淘汰策略

本文链接：https://blog.quwenai.cn/post/8997.html

作者授权：除特别说明外，本文由 toobug 原创编译并授权 TOOBUG信息安全网刊载发布。

本文链接：https://blog.quwenai.cn/post/8997.html

分享到：

正文

Redis源码解析：缓存淘汰策略

Redis内存满了该怎么办？

LRU算法

使用双向链表+HashMap

使用LinkedHashMap实现LRU

LFU算法

我们应该如何组织数据呢？

参考博客

相关阅读

【JVM】类加载器（二）：Tomcat 打破双亲委派

MYSQL自增主键丢失问题

【Java杂记】GUI技术：Swing基本使用及JFormDesigner插件安装使用

【Spring】日志：使用 spring 时日志的多种选择

发表评论取消回复

还没有评论，来说两句吧...

目录[+]