一文读懂常见的缓存策略

缓存策略介绍

缓存是一种用于临时存储数据的技术，旨在提高数据访问速度和性能。通过将常用的数据存储在缓存中，可以减少对原始数据存储位置的访问次数，从而加快数据的读取速度。缓存通常用于加速计算机系统、网络和Web应用程序的性能。

常见的缓存策略包括：

1. 「FIFO（First In, First Out）」：先进先出，最先进入缓存的数据最先被淘汰。
2. 「LRU（Least Recently Used）」：最近最少使用，根据数据最近被访问的时间来淘汰缓存中的数据。
3. 「LFU（Least Frequently Used）」：最不经常使用，根据数据被访问的频率来淘汰缓存中的数据。
4. 「随机替换」：随机选择要淘汰的数据。

FIFO缓存策略

FIFO（First In, First Out）是一种缓存替换策略，它按照数据进入缓存的顺序来进行替换。当缓存已满并且需要替换新的数据时，FIFO策略会选择最早进入缓存的数据进行替换。

在FIFO策略中，新数据被加入到缓存的末尾，而替换时会选择缓存中最早进入的数据进行替换。这种策略简单直观，但可能会导致缓存中的热数据被频繁替换，影响缓存的命中率。

数学公式表示FIFO缓存替换策略如下：

假设缓存大小为N，缓存中已有n个数据，新数据为x，则替换时选择的数据为缓存中最早进入的数据，即第一个进入缓存的数据。

FIFO缓存策略实现(JAVA)

FIFO缓存适用于以下使用场景：

• 数据访问模式呈现出明显的时间局部性
• 缓存数据量较小，且缓存空间有限
• 对于缓存命中率要求不是特别高的场景

在Java中，可以使用LinkedHashMap来实现FIFO缓存策略。LinkedHashMap继承自HashMap，它保留了插入顺序，因此非常适合用来实现FIFO缓存。

import java.util.LinkedHashMap;
import java.util.Map;

public class FIFOCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;

    public FIFOCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void mAIn(String[] args) {
        FIFOCache<String, Integer> cache = new FIFOCache<>(3);
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        System.out.println(cache); // 输出：{A=1, B=2, C=3}
        cache.put("D", 4);
        System.out.println(cache); // 输出：{B=2, C=3, D=4}
    }
}

在上面的示例中，我们创建了一个FIFOCache类，继承自LinkedHashMap，并重写了removeEldestEntry方法来控制缓存的大小和淘汰策略。

LRU缓存策略

LRU（Least Recently Used）缓存策略是一种常见的缓存淘汰策略，它根据数据的访问时间来淘汰最近最少使用的数据。当缓存空间不足时，会淘汰最近最少被访问的数据，以便为新数据腾出空间。

LRU缓存策略通常通过双向链表和哈希表来实现。双向链表用于记录数据的访问顺序，哈希表用于快速查找数据在链表中的位置。当数据被访问时，如果数据已经在缓存中，则将其移动到链表头部；如果数据不在缓存中，则将其添加到链表头部，并在哈希表中记录其位置。当需要淘汰数据时，可以直接从链表尾部淘汰最近最少被访问的数据。

LRU缓存策略的优点是能够有效地利用缓存空间，将最常用的数据保留在缓存中，提高访问速度。但是实现起来相对复杂，需要维护链表和哈希表的一致性，并且在高并发场景下可能存在性能瓶颈。

数学公式表示LRU缓存策略的淘汰规则可以用如下的方式表示：

设  为缓存的大小， 表示第  个数据被访问的时间，则淘汰规则可以表示为：

淘汰规则：

LRU缓存策略实现(Java)

LRU缓存适用于需要频繁访问数据的场景，例如：

• 数据库查询结果的缓存
• 网络请求的结果缓存
• 页面内容的缓存

以下是一个简单的Java使用LinkedHashMap来实现LRU缓存：

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_ENTRIES;

    public LRUCache(int maxEntries) {
        super(maxEntries, 0.75f, true);
        MAX_ENTRIES = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_ENTRIES;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");
        System.out.println(cache); // 输出: {1=One, 2=Two, 3=Three}
        cache.put(4, "Four");
        System.out.println(cache); // 输出: {2=Two, 3=Three, 4=Four}
    }
}

在这个示例中，LRUCache继承自LinkedHashMap，并重写了removeEldestEntry方法来控制缓存的大小。当缓存超过指定大小时，最近最少使用的条目将被移除。

LFU缓存策略

LFU（Least Frequently Used）缓存策略是一种常见的缓存替换策略，它根据缓存中数据项被访问的频率来进行替换。具体来说，当缓存空间不足时，LFU算法会淘汰访问频率最低的数据项。

LFU缓存策略的实现通常需要维护一个访问频率的计数器，以及一个数据项和其对应访问频率的映射。当数据项被访问时，其对应的访问频率会增加，当需要替换数据项时，会选择访问频率最低的数据项进行淘汰。

在LFU缓存策略中，如果有多个数据项的访问频率相同，那么通常会选择最早被访问的数据项进行淘汰。

LFU缓存策略的优点是能够有效地淘汰访问频率低的数据项，但缺点是需要维护额外的访问频率计数器，增加了实现的复杂度。

在实际应用中，LFU缓存策略通常用于需要频繁访问的数据项，以便保持缓存中的数据项是最常被访问的。

LFU缓存策略实现(Java)

LFU缓存策略适用于需要根据数据访问频率来淘汰缓存的场景。在这种策略下，会优先淘汰访问频率最低的数据，以便为访问频率高的数据腾出空间，从而提高缓存命中率。

LFU缓存策略常用于以下场景：

• 需要根据数据访问频率来淘汰缓存的系统，如热点数据缓存、页面缓存等。
• 对于访问频率较低的数据，采用LFU策略可以有效释放缓存空间，提高系统整体性能。

在Java中，可以通过使用LinkedHashMap来实现LFU缓存策略。LinkedHashMap可以按照访问顺序或插入顺序来维护键值对，通过重写removeEldestEntry方法和自定义数据结构来实现LFU缓存策略。

以下是一个简单的Java实现LFU缓存策略的示例代码：

import java.util.*;

public class LFUCache<K, V> extends LinkedHashMap<K, V> {
    private Map<K, Integer> freqMap;

    public LFUCache(int capacity) {
        super(capacity, 0.75f, true);
        freqMap = new HashMap<>();
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity();
    }

    public V get(K key) {
        if (super.containsKey(key)) {
            freqMap.put(key, freqMap.get(key) + 1);
        }
        return super.get(key);
    }

    public void put(K key, V value) {
        if (!super.containsKey(key)) {
            freqMap.put(key, 1);
        }
        super.put(key, value);
    }

    public static void main(String[] args) {
        LFUCache<Integer, String> cache = new LFUCache<>(2);
        cache.put(1, "a");
        cache.put(2, "b");
        System.out.println(cache.get(1)); // 输出: a
        cache.put(3, "c");
        System.out.println(cache.get(2)); // 输出: null
    }
}

在上述示例中，通过继承LinkedHashMap并重写removeEldestEntry方法，以及使用freqMap来记录访问频率，实现了LFU缓存策略的简单Java实现。

随机替换缓存策略

随机替换缓存策略是指在需要替换缓存中的数据时，随机选择一个数据进行替换。这种策略不考虑数据的访问频率或者其他因素，只是简单地随机选择一个数据进行替换。

数学表示为：选择要替换的数据的概率是相等的，即每个数据被替换的概率都是1/n，其中n为缓存中数据的数量。

这种策略的优点是实现简单，但缺点是不能充分利用数据的访问模式，可能导致缓存命中率降低。

随机替换缓存策略实现(Java)

随机替换缓存策略是一种简单的缓存替换策略，它随机选择一个缓存条目进行替换，适用于对缓存命中率要求不高的场景。

• 测试环境：在测试环境中，可以使用随机替换缓存策略来模拟真实环境下的缓存替换情况，从而更好地评估系统的性能。
• 临时数据缓存：对于一些临时性数据的缓存，如广告内容、临时计算结果等，可以采用随机替换策略，因为对于这些数据的访问顺序并不具有规律性。

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class RandomReplacementCache<K, V> {
    private Map<K, V> cache;
    private Random random;

    public RandomReplacementCache() {
        this.cache = new HashMap<>();
        this.random = new Random();
    }

    public void put(K key, V value) {
        // 添加缓存条目
        cache.put(key, value);
    }

    public V get(K key) {
        // 获取缓存条目
        return cache.get(key);
    }

    public void evictRandom() {
        // 随机替换缓存条目
        if (!cache.isEmpty()) {
            int randomIndex = random.nextInt(cache.size());
            K keyToRemove = (K) cache.keySet().toArray()[randomIndex];
            cache.remove(keyToRemove);
        }
    }
}

在上面的示例中，我们使用了HashMap来实现缓存，通过Random类来实现随机替换缓存条目的功能。