LRU算法与Caffeine、Redis中的缓存淘汰策略

AI文本 OCR识别最佳实践

AI Gamma一键生成PPT工具直达链接

玩转cloud Studio 在线编码神器

玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间

资源分享

代码语言：javascript复制

「java、python面试题」来自UC网盘app分享，打开手机app，额外获得1T空间
https://drive.uc.cn/s/2aeb6c2dcedd4
AIGC资料包
https://drive.uc.cn/s/6077fc42116d4
https://pan.xunlei.com/s/VN_qC7kwpKFgKLto4KgP4Do_A1?pwd=7kbv#
https://yv4kfv1n3j.feishu.cn/docx/MRyxdaqz8ow5RjxyL1ucrvOYnnH

引言

在现代计算机系统中，缓存是提高系统性能的关键技术之一。为了避免频繁的IO操作，常见的做法是将数据存储在内存中的缓存中，以便快速访问。然而，由于内存资源有限，缓存的大小是有限的，因此需要一种策略来淘汰缓存中的数据，以便为新的数据腾出空间。本文将介绍一种常用的缓存淘汰策略——最近最少使用（Least Recently Used，LRU）算法，并且比较它与Caffeine和Redis中的缓存淘汰策略。

LRU算法

LRU算法是一种基于访问时间的缓存淘汰策略。其核心思想是根据数据的访问顺序来判断数据的热度，将最近最少使用的数据淘汰出缓存。具体实现上，可以使用一个双向链表和一个哈希表来实现LRU缓存。

双向链表用于记录数据的访问顺序，新访问的数据插入链表头部，而最少访问的数据则位于链表尾部。哈希表用于快速查找数据是否在缓存中，并且能够在O(1)的时间复杂度内找到对应的链表节点。

下面是一个示例的LRU缓存的代码实现：

代码语言：java复制

class LRUCache {
    private int capacity;
    private Map<Integer, Node> map;
    private Node head;
    private Node tail;

    class Node {
        int key;
        int value;
        Node prev;
        Node next;
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node();
            node.key = key;
            node.value = value;
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node removed = removeTail();
                map.remove(removed.key);
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
}

上述代码中，LRUCache类是LRU缓存的实现。其中，map用于快速查找节点，head和tail是链表的头尾节点。LRUCache类提供了get和put方法用于获取缓存数据和插入缓存数据。

Caffeine缓存淘汰策略

Caffeine是一种Java缓存库，提供了多种缓存淘汰策略。除了LRU算法外，Caffeine还支持LFU（Least Frequently Used，最不经常使用）和基于时间的淘汰策略。下面是一个示例展示了如何使用Caffeine库来创建一个LRU缓存：

代码语言：java复制

LoadingCache<String, String> cache = Caffeine.newBuilder()
.cacheLoader(key -> fetchDataFromDB(key))
.maximumSize(1000)
.expireAfterWrite(10, TimeUnit.MINUTES)
.removalListener((key, value, cause) -> System.out.println("Key "   key   " was removed from cache"))
.build();

String data = cache.get("key");

上述代码中，使用Caffeine的newBuilder方法创建一个缓存，设置了最大缓存大小为1000条记录，并且设置了数据在写入后的10分钟内过期。在缓存中找不到数据时，会调用fetchDataFromDB方法从数据库中获取数据，并将数据放入缓存中。

Redis缓存淘汰策略

Redis是一种内存数据库，也提供了多种缓存淘汰策略。与Caffeine类似，Redis也支持LRU、LFU和基于时间的淘汰策略。

在Redis中，可以使用maxmemory-policy配置项来设置缓存淘汰策略。下面是一个示例展示了如何使用Redis的LRU淘汰策略：

代码语言：txt复制

CONFIG SET maxmemory-policy volatile-lru

上述命令将缓存的淘汰策略设置为volatile-lru，即LRU淘汰策略。当缓存空间达到上限时，Redis会根据数据的访问时间来选择最近最少使用的数据进行淘汰。

总结

本文介绍了LRU算法及其在Caffeine和Redis中的应用。LRU算法是一种常用的缓存淘汰策略，通过记录数据的访问顺序来判断数据的热度，从而决定数据的淘汰顺序。Caffeine和Redis都提供了LRU淘汰策略，并且还支持其他的淘汰策略，以满足不同场景下的需求。

通过本文的介绍，读者可以了解到LRU算法的原理及其在实际应用中的实现方式。同时，也能够了解到Caffeine和Redis这两个常用的缓存库是如何使用LRU淘汰策略来提高缓存性能的。希望本文对读者在面试和实际项目中的应用有所帮助。

参考文献：

Caffeine: a high performance Java caching library
Redis Documentation

redis redis-cluster java

0 人点赞