16、缓存策略：LRU与LFU缓存实现、预加载与预解码、内存缓存与磁盘缓存分级

缓存这东西，说白了就是用空间换时间。

我在做音视频播放器的时候，最头疼的就是用户快速滑动进度条。每次拖动都要重新解码，卡得让人抓狂。后来我意识到，没有缓存策略的播放器，就像没有油箱的车——跑不远。

这一章，我们来聊聊缓存那些事。我会把我在项目中踩过的坑、总结的经验，都摊开来讲。

16.1 为什么需要缓存？

音视频处理有个特点：数据量大，计算密集。一个1080p的视频帧，解码后可能占用几MB内存。如果每次播放都要重新解码，CPU直接拉满，手机发烫，用户骂娘。

缓存的核心目标就三个：

• 减少重复计算：已经解码的帧，别解第二遍
• 降低延迟：用户拖进度条时，能快速响应
• 节省带宽：网络数据别反复下载

16.2 LRU与LFU：两种经典的淘汰策略

缓存空间是有限的。内存就那么大，磁盘也不能无限写。所以我们需要一套规则，来决定「谁该被踢出去」。

16.2.1 LRU：最近最少使用

LRU 的思路很简单：如果数据最近被访问过，那么将来被访问的概率也高。说白了，就是「优先淘汰最久没被用过的」。

我习惯用 LinkedHashMap 来实现 LRU，Android 的 LruCache 底层就是这个。

public class LRUCache<K, V> {
    private final LinkedHashMap<K, V> map;
    private final int maxSize;

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

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }
}

注意那个 accessOrder = true 的参数。它决定了 LinkedHashMap 是按访问顺序排序，还是按插入顺序排序。我刚开始用的时候没注意这个，结果 LRU 变成了 FIFO，缓存命中率惨不忍睹。

16.2.2 LFU：最不经常使用

LFU 的思路不同：它统计每个数据的访问频率，优先淘汰访问次数最少的。

你想想看，有些数据虽然最近被访问过，但可能只是偶然。而有些数据虽然很久没被访问，但历史上被访问过很多次。LFU 更看重「历史贡献」。

public class LFUCache<K, V> {
    private final int capacity;
    private final Map<K, V> valueMap = new HashMap<>();
    private final Map<K, Integer> freqMap = new HashMap<>();
    private final TreeMap<Integer, LinkedHashSet<K>> freqList = new TreeMap<>();

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public V get(K key) {
        if (!valueMap.containsKey(key)) return null;
        increaseFreq(key);
        return valueMap.get(key);
    }

    public void put(K key, V value) {
        if (capacity == 0) return;
        if (valueMap.containsKey(key)) {
            valueMap.put(key, value);
            increaseFreq(key);
            return;
        }
        if (valueMap.size() >= capacity) {
            evict();
        }
        valueMap.put(key, value);
        freqMap.put(key, 1);
        freqList.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
    }

    private void increaseFreq(K key) {
        int freq = freqMap.get(key);
        freqMap.put(key, freq + 1);
        freqList.get(freq).remove(key);
        if (freqList.get(freq).isEmpty()) {
            freqList.remove(freq);
        }
        freqList.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    private void evict() {
        int lowestFreq = freqList.firstKey();
        K keyToEvict = freqList.get(lowestFreq).iterator().next();
        freqList.get(lowestFreq).remove(keyToEvict);
        if (freqList.get(lowestFreq).isEmpty()) {
            freqList.remove(lowestFreq);
        }
        valueMap.remove(keyToEvict);
        freqMap.remove(keyToEvict);
    }
}

16.2.3 LRU vs LFU：怎么选？

维度	LRU	LFU
淘汰依据	最近访问时间	历史访问频率
实现复杂度	低	高
内存开销	小	大（需要维护频率表）
适用场景	访问模式集中	访问模式分散但稳定
缓存污染风险	低	高

我个人习惯：音视频场景下，LRU 更实用。因为用户的操作往往是连续的，最近访问的数据大概率还会被再次访问。LFU 更适合「热点数据长期稳定」的场景，比如推荐系统的 Top-N 缓存。

16.3 预加载与预解码

缓存是被动策略——数据被访问了才缓存。但预加载是主动策略——我猜你会用，所以我提前准备好。

16.3.1 预加载：提前拉数据

播放器里最常见的预加载，就是「预下载下一段视频」。用户还在看第 5 秒，我已经在后台下载第 10 秒的数据了。

实现起来不复杂：

public class Preloader {
    private final ExecutorService executor = Executors.newSingleThreadExecutor();
    private final Map<String, byte[]> cache = new ConcurrentHashMap<>();

    public void preload(String url) {
        executor.submit(() -> {
            if (cache.containsKey(url)) return;
            byte[] data = download(url); // 网络请求
            cache.put(url, data);
        });
    }

    public byte[] get(String url) {
        return cache.remove(url); // 取走即删除，避免内存泄漏
    }
}

16.3.2 预解码：提前算好帧

预加载只是把原始数据拉到内存。但解码才是真正的性能杀手。所以更激进的做法是——预解码。

比如用户正在看第 100 帧，我提前把第 101-110 帧都解码好，放到缓存里。这样用户拖动到附近时，直接拿解码后的数据，零延迟。

public class PreDecoder {
    private final MediaCodec decoder;
    private final ArrayBlockingQueue<VideoFrame> decodedFrames = new ArrayBlockingQueue<>(30);

    public void startPreDecode() {
        new Thread(() -> {
            while (!Thread.interrupted()) {
                // 从解码器取出已解码帧
                MediaCodec.BufferInfo info = new MediaCodec.BufferInfo();
                int outputIndex = decoder.dequeueOutputBuffer(info, 0);
                if (outputIndex >= 0) {
                    ByteBuffer buffer = decoder.getOutputBuffer(outputIndex);
                    VideoFrame frame = new VideoFrame(buffer, info);
                    decodedFrames.offer(frame); // 放入缓存队列
                    decoder.releaseOutputBuffer(outputIndex, false);
                }
            }
        }).start();
    }

    public VideoFrame getNextFrame() throws InterruptedException {
        return decodedFrames.take();
    }
}

16.4 内存缓存与磁盘缓存分级

单一缓存是不够的。我习惯把缓存分成两级：

• L1：内存缓存——快，但容量小
• L2：磁盘缓存——慢，但容量大

访问流程是这样的：

1. 先查 L1，命中直接返回
2. L1 没命中，查 L2，命中后回填到 L1
3. L2 也没命中，从网络/解码器获取，然后同时写入 L1 和 L2

public class TieredCache {
    private final LruCache<String, Bitmap> memoryCache; // L1
    private final DiskLruCache diskCache;               // L2

    public TieredCache(Context context) {
        int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
        int cacheSize = maxMemory / 8; // 分配 1/8 内存给缓存
        memoryCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap bitmap) {
                return bitmap.getByteCount() / 1024;
            }
        };
        diskCache = DiskLruCache.open(context.getCacheDir(), 1, 1, 50 * 1024 * 1024);
    }

    public Bitmap get(String key) {
        Bitmap bitmap = memoryCache.get(key);
        if (bitmap != null) return bitmap;

        // 从磁盘读取
        byte[] data = diskCache.get(key);
        if (data != null) {
            bitmap = BitmapFactory.decodeByteArray(data, 0, data.length);
            memoryCache.put(key, bitmap); // 回填到 L1
            return bitmap;
        }
        return null;
    }

    public void put(String key, Bitmap bitmap) {
        memoryCache.put(key, bitmap);
        // 异步写入磁盘
        new Thread(() -> {
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            bitmap.compress(Bitmap.CompressFormat.JPEG, 80, bos);
            diskCache.put(key, bos.toByteArray());
        }).start();
    }
}

16.5 整体架构图

下面这张图，是我在项目中实际使用的缓存架构。你可以看到数据从网络到显示，经过了哪些缓存层。

16.6 一些实战建议

最后，分享几个我在项目中总结的经验：

• 缓存大小要动态调整：不要写死 50MB。根据设备内存、屏幕分辨率、当前播放的视频码率来动态计算。低端机少给点，高端机多给点。
• 注意内存碎片：频繁分配和释放 Bitmap 会导致内存碎片。我习惯用 BitmapPool 复用 Bitmap，而不是每次都新建。
• 磁盘缓存要限制写入频率：频繁写磁盘会耗电、伤闪存。我一般会做一个「延迟写入」的机制——数据先放内存，等积累到一定量或者空闲时再批量写入。
• 缓存命中率要打日志：上线后通过日志分析缓存命中率，如果低于 60%，说明策略有问题，需要调整。