Android 内存缓存框架 LruCache 的实现原理，手写试试？

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。

前言

大家好，我是小彭。

在之前的文章里，我们聊到了 LRU 缓存淘汰算法，并且分析 Java 标准库中支持 LUR 算法的数据结构 LinkedHashMap。当时，我们使用 LinkedHashMap 实现了简单的 LRU Demo。今天，我们来分析一个 LRU 的应用案例 —— Android 标准库的 LruCache 内存缓存。

小彭的 Android 交流群 02 群已经建立啦，扫描文末二维码进入~

思维导图：

1. 回顾 LRU 和 LinkedHashMap

在具体分析 LruCache 的源码之前，我们先回顾上一篇文章中讨论的 LRU 缓存策略以及 LinkedHashMap 实现原理。

LRU （Least Recently Used）最近最少策略是最常用的缓存淘汰策略。LRU 策略会记录各个数据块的访问 “时间戳” ，最近最久未使用的数据最先被淘汰。与其他几种策略相比，LRU 策略利用了 “局部性原理”，平均缓存命中率更高。

FIFO 与 LRU 策略

经过总结，我们可以定义一个缓存系统的基本操作：

• 操作 1 - 添加数据： 先查询数据是否存在，不存在则添加数据，存在则更新数据，并尝试淘汰数据；
• 操作 2 - 删除数据： 先查询数据是否存在，存在则删除数据；
• 操作 3 - 查询数据： 如果数据不存在则返回 null；
• 操作 4 - 淘汰数据： 添加数据时如果容量已满，则根据缓存淘汰策略一个数据。

我们发现，前 3 个操作都有 “查询” 操作，所以缓存系统的性能主要取决于查找数据和淘汰数据是否高效。为了实现高效的 LRU 缓存结构，我们会选择采用双向链表 + 散列表的数据结构，也叫 “哈希链表”，它能够将查询数据和淘汰数据的时间复杂度降低为 O(1)。

• 查询数据： 通过散列表定位数据，时间复杂度为 O(1)；
• 淘汰数据： 直接淘汰链表尾节点，时间复杂度为 O(1)。

在 Java 标准库中，已经提供了一个通用的哈希链表 —— LinkedHashMap。使用 LinkedHashMap 时，主要关注 2 个 API：

• accessOrder 标记位： LinkedHashMap 同时实现了 FIFO 和 LRU 两种淘汰策略，默认为 FIFO 排序，可以使用 accessOrder 标记位修改排序模式。
• removeEldestEntry() 接口： 每次添加数据时，LinkedHashMap 会回调 removeEldestEntry() 接口。开发者可以重写 removeEldestEntry() 接口决定是否移除最早的节点（在 FIFO 策略中是最早添加的节点，在 LRU 策略中是最久未访问的节点）。

LinkedHashMap 示意图

LinkedHashMap#put 示意图

2. 实现 LRU 内存缓存需要考虑什么问题？

在阅读 LruCache 源码之前，我们先尝试推导 LRU 内存缓存的实现思路，带着问题和结论去分析源码，也许收获会更多。

2.1 如何度量缓存单元的内存占用？

缓存系统应该实时记录当前的内存占用量，在添加数据时增加内存记录，在移除或替换数据时减少内存记录，这就涉及 “如何度量缓存单元的内存占用” 的问题。计数 or 计量，这是个问题。比如说：

• 举例 1： 实现图片内存缓存，如何度量一个图片资源的内存占用？
• 举例 2： 实现数据模型对象内存缓存，如何度量一个数据模型对象的内存占用？
• 举例 3： 实现资源内存预读，如何度量一个资源的内存占用？

我将这个问题总结为 2 种情况：

• 1、能力复用使用计数： 这类内存缓存场景主要是为了复用对象能力，对象本身持有的数据并不多，但是对象的结构却有可能非常复杂。而且，再加上引用复用的因素，很难统计对象实际的内存占用。因此，这类内存缓存场景应该使用计数，只统计缓存单元的个数，例如复用数据模型对象，资源预读等；

• 2、数据复用使用计量： 这类内存缓存场景主要是为了复用对象持有的数据，数据对内存的影响远远大于对象内存结构对内存的影响，是否度量除了数据外的部分内存对缓存几乎没有影响。因此， 这里内存缓存场景应该使用计量，不计算缓存单元的个数，而是计算缓存单元中主数据字段的内存占用量，例如图片的内存缓存就只记录 Bitmap 的像素数据内存占用。

还有一个问题，对象内存结构中的对象头和对齐空间需要计算在内吗？一般不考虑，因为在大部分业务开发场景中，相比于对象的实例数据，对象头和对齐空间的内存占用几乎可以忽略不计。

2.2 最大缓存容量应该设置多大？

网上很多资料都说使用最大可用堆内存的八分之一，这样笼统地设置方式显然并不合理。到底应该设置多大的空间没有绝对标准的做法，而是需要开发者根据具体的业务优先级、用户机型和系统实时的内存紧张程度做决定：

• 业务优先级： 如果是高优先级且使用频率很高的业务场景，那么最大缓存空间适当放大一些也是可以接受的，反之就要考虑适当缩小；

• 用户机型： 在最大可用堆内存较小的低端机型上，最大缓存空间应该适当缩小；

• 内存紧张程度： 在系统内存充足的时候，可以放大一些缓存空间获得更好的性能，当系统内存不足时再及时释放。

2.3 淘汰一个最早的节点就足够吗？

标准的 LRU 策略中，每次添加数据时最多只会淘汰一个数据，但在 LRU 内存缓存中，只淘汰一个数据单元往往并不够。例如在使用 “计量” 的内存图片缓存中，在加入一个大图片后，只淘汰一个图片数据有可能依然达不到最大缓存容量限制。

因此，在复用 LinkedHashMap 实现 LRU 内存缓存时，前文提到的 LinkedHashMap#removeEldestEntry() 淘汰判断接口可能就不够看了，因为它每次最多只能淘汰一个数据单元。这个问题，我们后文再看看 Android LruCache 是如何解决的。

2.4 策略灵活性

LruCache 的淘汰策略是在缓存容量满时淘汰，当缓存容量没有超过最大限制时就不会淘汰。除了这个策略之外，我们还可以增加一些辅助策略，例如在 Java 堆内存达到某个阈值后，对 LruCache 使用更加激进的清理策略。

在 Android Glide 图片框架中就有策略灵活性的体现：Glide 除了采用 LRU 策略淘汰最早的数据外，还会根据系统的内存紧张等级 onTrimMemory(level) 及时减少甚至清空 LruCache。

Glide · LruResourceCache.java

@Override
public void trimMemory(int level) {
    if (level >= android.content.ComponentCallbacks2.TRIM_MEMORY_BACKGROUND) {
        // Entering list of cached background apps
        // Evict our entire bitmap cache
        clearMemory();
    } else if (level >= android.content.ComponentCallbacks2.TRIM_MEMORY_UI_HIDDEN || level == android.content.ComponentCallbacks2.TRIM_MEMORY_RUNNING_CRITICAL) {
        // The app's UI is no longer visible, or app is in the foreground but system is running
        // critically low on memory
        // Evict oldest half of our bitmap cache
        trimToSize(getMaxSize() / 2);
    }
}

2.5 线程同步问题

一个缓存系统往往会在多线程环境中使用，而 LinkedHashMap 与 HashMap 都不考虑线程同步，也会存在线程安全问题。这个问题，我们后文再看看 Android LruCache 是如何解决的。

3. LruCache 源码分析

这一节，我们来分析 LruCache 中主要流程的源码。

3.1 LruCache 的 API

LruCache 是 Android 标准库提供的 LRU 内存缓存框架，基于 Java LinkedHashMap 实现，当缓存容量超过最大缓存容量限制时，会根据 LRU 策略淘汰最久未访问的缓存数据。

用一个表格整理 LruCache 的 API：

3.2 LruCache 的属性

LruCache 的属性比较简单，除了多个用于数据统计的属性外，核心属性只有 3 个：

• 1、size： 当前缓存占用；
• 2、maxSize： 最大缓存容量；
• 3、map： 复用 LinkedHashMap 的 LRU 控制能力。

LruCache.java

public class LruCache<K, V> {
    // LRU 控制
    private final LinkedHashMap<K, V> map;

    // 当前缓存占用
    private int size;
    // 最大缓存容量
    private int maxSize;

    // 以下属性用于数据统计

    // 设置数据次数
    private int putCount;
    // 创建数据次数
    private int createCount;
    // 淘汰数据次数
    private int evictionCount;
    // 缓存命中次数
    private int hitCount;
    // 缓存未命中数
    private int missCount;
}

3.3 LruCache 的构造方法

LruCache 只有 1 个构造方法。

由于缓存空间不可能设置无限大，所以开发者需要在构造方法中设置缓存的最大内存容量 maxSize。

LinkedHashMap 对象也会在 LruCache 的构造方法中创建，并且会设置 accessOrder 标记位为 true，表示使用 LRU 排序模式。

LruCache.java

// maxSize：缓存的最大内存容量
public LruCache(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    // 缓存的最大内存容量
    this.maxSize = maxSize;
    // 创建 LinkedHashMap 对象，并使用 LRU 排序模式
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true /*LRU 模式*/);
}

使用示例

private static final int CACHE_SIZE = 4 * 1024 * 1024; // 4Mib
LruCache bitmapCache = new LruCache(CACHE_SIZE);

3.4 测量数据单元的内存占用

开发者需要重写 LruCache#sizeOf() 测量缓存单元的内存占用量，否则缓存单元的大小默认视为 1，相当于 maxSize 表示的是最大缓存数量。

LruCache.java

// LruCache 内部使用
private int safeSizeOf(K key, V value) {
    // 如果开发者重写的 sizeOf 返回负数，则抛出异常
    int result = sizeOf(key, value);
    if (result < 0) {
        throw new IllegalStateException("Negative size: " + key + "=" + value);
    }
    return result;
}

// 测量缓存单元的内存占用
protected int sizeOf(K key, V value) {
    // 默认为 1
    return 1;
}

使用示例

private static final int CACHE_SIZE = 4 * 1024 * 1024; // 4Mib
LruCache bitmapCache = new LruCache(CACHE_SIZE){
    // 重写 sizeOf 方法，用于测量 Bitmap 的内存占用
    @Override
    protected int sizeOf(String key, Bitmap value) {
        return value.getByteCount();
    }
};

3.5 添加数据与淘汰数据

LruCache 添加数据的过程基本是复用 LinkedHashMap 的添加过程，我将过程概括为 6 步：

• 1、统计添加计数（putCount）；
• 2、size 增加新 Value 内存占用；
• 3、设置数据（LinkedHashMap#put）；
• 4、size 减去旧 Value 内存占用；
• 5、数据移除回调（LruCache#entryRemoved）;
• 6、自动淘汰数据：在每次添加数据后，如果当前缓存空间超过了最大缓存容量限制，则会自动触发 trimToSize() 淘汰一部分数据，直到满足限制。

淘汰数据的过程则是完全自定义，我将过程概括为 5 步：

• 1、取最找的数据（LinkedHashMap#eldest）；
• 2、移除数据（LinkedHashMap#remove）；
• 3、size 减去旧 Value 内存占用；
• 4、统计淘汰计数（evictionCount）；
• 5、数据移除回调（LruCache#entryRemoved）;
• 重复以上 5 步，满足要求或者缓存为空，才会退出。

逻辑很好理解，不过还是拦不住一些小朋友出来举手提问了