关于java:Redis-为何使用近似-LRU-算法淘汰数据而不是真实-LRU

在《Redis 数据缓存满了怎么办？》咱们晓得 Redis 缓存满了之后能通过淘汰策略删除数据腾出空间给新数据。

淘汰策略如下所示：

设置过期工夫的 key

volatile-ttl、volatile-random、volatile-lru、volatile-lfu 这四种策略淘汰的数据范畴是设置了过期工夫的数据。

所有的 key

allkeys-lru、allkeys-random、allkeys-lfu 这三种淘汰策略无论这些键值对是否设置了过期工夫，当内存不足都会进行淘汰。

这就意味着，即便它的过期工夫还没到，也会被删除。当然，如果曾经过了过期工夫，即便没有被淘汰策略选中，也会被删除。

volatile-ttl 和 volatile-randon 很简略，重点在于 volatile-lru 和 volatile-lfu，他们波及到 LRU 算法 和 LFU 算法。

明天码哥带大家一起搞定 Redis 的 LRU 算法…

近似 LRU 算法

什么是 LRU 算法呢？

LRU 算法的全程是 Least Rencently Used，顾名思义就是依照最近最久未应用的算法进行数据淘汰。

核心思想「如果该数据最近被拜访，那么未来被发放稳的几率也更高」。

咱们把所有的数据组织成一个链表：

• MRU：示意链表的表头，代表着最近最常被拜访的数据；
• LRU：示意链表的表尾，代表最近最不常应用的数据。

能够发现，LRU 更新和插入新数据都产生在链表首，删除数据都产生在链表尾。

被拜访的数据会被挪动到 MRU 端，被拜访的数据之前的数据则相应往后挪动一位。

应用单链表能够么？

如果选用单链表，删除这个结点，须要 O(n) 遍历一遍找到前驱结点。所以选用双向链表，在删除的时候也能 O(1) 实现。

Redis 应用该 LRU 算法治理所有的缓存数据么？

不是的，因为 LRU 算法须要用链表治理所有的数据，会造成大量额定的空间耗费。

除此之外，大量的节点被拜访就会带来频繁的链表节点挪动操作，从而升高了 Redis 性能。

所以 Redis 对该算法做了简化，Redis LRU 算法并不是真正的 LRU，Redis 通过 对大量的 key 采样，并淘汰采样的数据中最久没被拜访过的 key。

这就意味着 Redis 无奈淘汰数据库最久拜访的数据。

Redis LRU 算法有一个重要的点在于能够更改样本数量来调整算法的精度，使其近似靠近实在的 LRU 算法，同时又防止了内存的耗费，因为每次只须要采样大量样本，而不是全副数据。

配置如下：

maxmemory-samples 50

运行原理

大家还记得么，数据结构 redisObject 中有一个 lru 字段，用于记录每个数据最近一次被拜访的工夫戳。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    /* LRU time (relative to global lru_clock) or
     * LFU data (least significant 8 bits frequency
     * and most significant 16 bits access time).
     */
    unsigned lru:LRU_BITS; 
    int refcount;
    void *ptr;
} robj;

Redis 在淘汰数据时，第一次随机选出 N 个数据放到 候选汇合，将 lru 字段值最小的数据淘汰。

当 再次 须要淘汰数据时，会从新筛选数据放入第一次创立的候选汇合，不过有一个筛选规范：进入该汇合的数据的 lru 的值必须小于候选汇合中最小的 lru 值。

如果新数据进入候选汇合的个数达到了 maxmemory-samples 设定的值，那就把候选汇合中 lru 最小的数据淘汰。

这样就大大减少链表节点数量，同时不必每次拜访数据都挪动链表节点，大大晋升了性能。

Java 实现 LRU Cahce

LinkedHashMap 实现

齐全利用 Java 的 LinkedHashMap 实现，能够采纳组合或者继承的形式实现，「码哥」应用组合的模式实现。

public class LRUCache<K, V> {
    private Map<K, V> map;
    private final int cacheSize;

    public LRUCache(int initialCapacity) {map = new LinkedHashMap<K, V>(initialCapacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > cacheSize;
            }
        };
        this.cacheSize = initialCapacity;
    }
}

重点在于 LinkedHashMap的第三个构造函数上，要把这个结构参数 accessOrder 设为 true，代表 LinkedHashMap 外部维持拜访程序。

另外，还须要重写removeEldestEntry()，这个函数如果返回true，代表把最久未被拜访的节点移除，从而实现淘汰数据。

本人实现

其中代码是从 LeetCode 146. LRU Cache 上摘下来的。代码外面有正文。

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 在链头放最久未被应用的元素，链尾放刚刚增加或拜访的元素
 */
class LRUCache {
    class Node {
        int key, value;
        Node pre, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
            pre = this;
            next = this;
        }
    }

    private final int capacity;// LRU Cache 的容量
    private Node dummy;// dummy 节点是一个冗余节点，dummy 的 next 是链表的第一个节点，dummy 的 pre 是链表的最初一个节点
    private Map<Integer, Node> cache;// 保留 key-Node 对，Node 是双向链表节点

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy = new Node(0, 0);
        cache = new ConcurrentHashMap<>();}

    public int get(int key) {Node node = cache.get(key);
        if (node == null) return -1;
        remove(node);
        add(node);
        return node.value;
    }

    public void put(int key, int value) {Node node = cache.get(key);
        if (node == null) {if (cache.size() >= capacity) {cache.remove(dummy.next.key);
                remove(dummy.next);
            }
            node = new Node(key, value);
            cache.put(key, node);
            add(node);
        } else {cache.remove(node.key);
            remove(node);
            node = new Node(key, value);
            cache.put(key, node);
            add(node);
        }
    }

    /**
     * 在链表尾部增加新节点
     *
     * @param node 新节点
     */
    private void add(Node node) {
        dummy.pre.next = node;
        node.pre = dummy.pre;
        node.next = dummy;
        dummy.pre = node;
    }

    /**
     * 从双向链表中删除该节点
     *
     * @param node 要删除的节点
     */
    private void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}

不要悭吝赞美，当他人做的不错，就给予他正反馈。少关注用「赞美」投票的事件，而应该去关注用「交易」投票的事件。

判断一个人是否牛逼，不是看网上有多少人夸赞他，而是要看有多少人违心跟他产生交易或赞叹、领取、下单。

因为赞美太便宜，而违心与他产生交易的才是真正的信赖和反对。

码哥到当初曾经写了近 23+ 篇 Redis 文章，赠送了很多书籍，收到过许多赞美和 大量赞叹，感激已经赞叹过我的读者，谢谢。

我是「码哥」，大家能够叫我靓仔，好文请点赞，对于 LFU 算法，咱们下一篇见。

历史好文

• Redis 内存满了怎么办？
• Redis 的过期数据会被立马删除么？
• Redis 缓存击穿（生效）、缓存穿透、缓存雪崩怎么解决？

参考文献

https://redis.io/docs/manual/…

http://antirez.com/news/109

https://time.geekbang.org/col…

https://halfrost.com/lru_lfu_…

https://blog.csdn.net/csdlwzy…