gpt4 book ai didi

Android内存缓存框架LruCache的实现原理,手写试试?

转载 作者:我是一只小鸟 更新时间:2022-12-03 22:36:09 26 4
gpt4 key购买 nike

本文已收录到 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 的像素数据内存占用.

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

度量策略 举例
计数 1、Message 消息对象池:最多缓存 50 个对象
2、OkHttp 连接池:默认最多缓存 5 个空闲连接
3、数据库连接池
计量 1、图片内存缓存
2、位图池内存缓存

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:

public API 描述
V get(K) 获取缓存数据
V put(K,V) 添加 / 更新缓存数据
V remove(K) 移除缓存数据
void evictAll() 淘汰所有缓存数据
void resize(int) 重新设置最大内存容量限制,并调用 trimToSize()
void trimToSize(int) 淘汰最早数据直到满足最大容量限制
Map<K, V> snapshot() 获取缓存内容的镜像 / 拷贝
protected API 描述
void entryRemoved() 数据移除回调(可用于回收资源)
V create() 创建数据(可用于创建缺省数据)
Int sizeOf() 测量数据单元内存

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 步,满足要求或者缓存为空,才会退出。

逻辑很好理解,不过还是拦不住一些小朋友出来举手提问了 🙋🏻‍♀️ :

  • 🙋🏻‍♀️疑问 1:为什么 LruCache 不支持 null 作为 Key 或 Value?

其实并没有一定不能为 null 的理由,我的理解是 Google 希望降低 LruCache 的理解成本。如果允许 Value 为 null,那么当 LruCache 需要计算 Value 的 size 时,Value 为 null 默认应该当作 0 还是当作 1呢?

再者,如果业务开发确实有 Key 或 Value 的需求,也可以选择重写 LruCache 的相关方法,或者直接自实现一个 LruCache,这都是可以接受的方案。例如,在 Android Glide 图片框架中的 LruCache 就是自实现的.

  • 🙋🏻‍♀️疑问 2:为什么 LruCache 淘汰数据没有重写 LinkedHashMap#removeEldestEntry() 接口?

这个问题其实跟上一节的 “淘汰一个最早的节点就足够吗?” 问题相同。由于只淘汰一个数据后,有可能还不满足最大容量限制的要求,所以 LruCache 直接放弃了 LinkedHashMap#removeEldestEntry() 接口,而是自己实现了 trimToSize() 淘汰方法.

LinkedHashMap#eldest() 是 Android SDK 添加的方法,在 OpenJDK 中没有这个方法,这个方法会返回 LinkedHashMap 双向链表的头节点。由于我们使用的是 LRU 排序模式,所以头节点自然是 LRU 策略要淘汰的最久未访问的节点.

在 trimToSize() 方法中,会循环调用 LinkedHashMap#eldest() 取最早的节点,移除节点后再减去节点占用的内存大小。所以 trimToSize() 将淘汰数据的逻辑放在 while(true) 循环中,直到满足要求或者缓存为空,才会退出.

添加数据示意图 。

LruCache.java 。

                        
                          public final V put(K key, V value) {
    // 疑问 1:不支持 null 作为 Key 或 Value
    if (key == null || value == null) {
        throw new NullPointerException("key == null || value == null");
    }

    // 被替换的数据
    V previous;
    synchronized (this) {
        // 1、统计添加计数
        putCount++;
        // 2、增加新 Value 内存占用
        size += safeSizeOf(key, value);
        // 3、设置数据
        previous = map.put(key, value);
        // 4、减去旧 Value 内存占用
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }
    // 5、数据移除回调(previous -> value)
    if (previous != null) {
        entryRemoved(false /*非淘汰*/, key, previous, value);
    }
    // 6、自动淘汰数据
    trimToSize(maxSize);
    return previous;
}

// -> 6、自动淘汰数据
public void trimToSize(int maxSize) {
    // 淘汰数据直到不超过最大容量限制
    while (true) {
        K key;
        V value;
        synchronized (this) {
            if (size < 0 || (map.isEmpty() && size != 0)) {
                throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
            }

            // 不超过最大容量限制,跳出
            if (size <= maxSize) {
                break;
            }

            // 6.1 取最早的数据
            Map.Entry<K, V> toEvict = map.eldest();
            // toEvict 为 null 说明没有更多数据
            if (toEvict == null) {
                break;
            }

            key = toEvict.getKey();
            value = toEvict.getValue();
            // 6.2 移除数据
            map.remove(key);
            // 6.3 减去旧 Value 内存占用
            size -= safeSizeOf(key, value);
            // 6.4 统计淘汰计数
            evictionCount++;
        }
        // 6.5 数据移除回调(value -> null)
        entryRemoved(true /*淘汰*/, key, value, null);
    }
}

                        
                      

Android LinkedHashMap.java 。

                        
                          // 提示:OpenJDK 中没有这个方法,是 Android SDK 添加的

public Map.Entry<K, V> eldest() {
    return head;
}

                        
                      

3.6 LruCache 的获取方法

在获取数据时,LruCache 增加了自动创建数据的功能,区分 2 种 情况:

  • 1、缓存命中: 直接返回缓存的数据;
  • 2、缓存未命中: 调用 LruCache#create 尝试创建数据,并将数据设置到缓存池中。这意味着 LruCache 不仅支持缓存数据,还支持创建数据。
                        
                          public final V get(K key) {
    // 不支持 null 作为 Key 或 Value
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized (this) {
        // 1. 尝试获取缓存的数据
        // mapValue:旧数据
        mapValue = map.get(key);
        if (mapValue != null) { // <标记点>
            // 1.1 缓存命中计数
            hitCount++;
            // 1.2 缓存命中,返回缓存数据
            return mapValue;
        }
        missCount++;
    }

    // 疑问 3:为什么 create(key) 要放在 synchronized 块外部?
    // 2. 尝试自动创建缓存数据(类似对象池)
    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }

    synchronized (this) {
        // 3.1 创建数据计数
        createCount++;
        // 3.2 设置创建的缓存数据
        // mapValue:旧数据
        mapValue = map.put(key, createdValue);

        // 疑问 4:在 <标记点> 判断 mapValue 为 null,这里再次 get 又有可能非 null,岂不是矛盾?
        if (mapValue != null) {
            // 3.3 如果 mapValue 旧数据不为 null,说明在调用 create() 的过程中,有其他线程创建并添加了数据
            // 那么放弃创建的数据,将 mapValue 重新设置回去。由于另一个线程在设置时已经累加 size 内存占用,所以这里不用重复累加
            map.put(key, mapValue);
        } else {
            // 3.4 如果 mapValue 旧数据为 null,那么累加 createdValue 的内存占用
            size += safeSizeOf(key, createdValue);
        }
    }

    // 4. 后处理
    if (mapValue != null) {
        // 4.1 数据移除回调(createdValue -> mapValue)
        entryRemoved(false /*非淘汰*/, key, createdValue, mapValue);
        return mapValue;
    } else {
        // 4.2 增加了 createdValue 后,需要缩容
        trimToSize(maxSize);
        return createdValue;
    }
}

protected V create(K key) {
    return null;
}

                        
                      

不出意外的话又有小朋友出来举手提问了 🙋🏻‍♀️ :

  • 🙋🏻‍♀️疑问 3:为什么 create(key) 要放在 synchronized 块外部?

这是为了降低锁的颗粒度.

由于 create(key) 创建数据的过程可能是耗时的,如果将 create(key) 放到 synchronized 同步块内部,那么在创建数据的过程中就会阻塞其他线程访问缓存的需求,会降低缓存系统的吞吐量.

  • 🙋🏻‍♀️疑问 4:在 <标记点> 判断 mapValue 为 null,这里再次 get 又有可能非 null,岂不是矛盾?

这个问题与上一个问题有关.

由于 create(key) 放在 synchronized 块外部,那么在执行 create(key) 的过程中,有可能其他线程已经创建并添加了目标数据,所以在 put(createdValue) 的时候就会出现 mapValue 不为 null 的情况.

此时,会存在两个 Value 的情况,应该选择哪一个 Value 呢?LruCache 认为其他线程添加的数据的优先级优于默认创建的缺省数据,所以在 3.3 分支放弃了缺省数据,重新将 mapValue 设置回去.

获取数据示意图 。

3.7 LruCache 的移除方法

LruCache 的移除方法是添加方法的逆运算,过程我概括为 3 步:

  • 1、移除节点(LinkedHashMap#remove);
  • 2、size 减去 Value 的内存占用;
  • 3、数据移除回调(LruCache#entryRemoved);
                        
                          public final V remove(K key) {
    // 不支持 null 作为 Key 或 Value
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V previous;
    synchronized (this) {
        // 1. 移除数据
        previous = map.remove(key);
        // 2. 减去移除 Value 内存占用
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }

    // 3. 数据移除回调(previous -> null)
    if (previous != null) {
        entryRemoved(false, key, previous, null);
    }

    return previous;
}

                        
                      

移除数据示意图 。

至此,LruCache 源码分析结束.


4. 总结

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

  • 2、LruCache 需要重写 sizeOf() 测量缓存单元的内存占用量,否则缓存单元的大小默认视为 1,相当于 maxSize 表示的是最大缓存数量; 。

  • 3、LruCache 放弃了 LinkedHashMap#removeEldestEntry() 接口,而是自己实现了 trimToSize() 淘汰方法; 。

今天,我们讨论了 LRU 缓存淘汰策略和一些内存缓存的设计问题,并且分析了 Android LruCache 源码。在我们熟悉的 Glide 图片框架中,也深入使用了 LRU 内存缓存策略,你能说出它的设计原理吗。这个问题我们在下一篇文章讨论,请关注.


参考资料

  • Android 开源框架源码鉴赏:LruCache 与 DiskLruCache —— 郭孝星 著
  • LruCache 在美团 DSP 系统中的应用演进 —— 王粲 崔涛 霜霜(美团技术团队)著
  • LruCache —— Android 官方文档

小彭的 Android 交流群 02 群

最后此篇关于Android内存缓存框架LruCache的实现原理,手写试试?的文章就讲到这里了,如果你想了解更多关于Android内存缓存框架LruCache的实现原理,手写试试?的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com