【Android】LRU 缓存——内存缓存与磁盘缓存


缓存概述

在 Android 开发的过程中常常需要用到缓存的功能来减少应用对用户流量的消耗(如图片缓存,文章缓存等等)。而对于用户的手机而言,其内存/存储空间的大小一般都是有限的,在一些缓存量大或缓存十分频繁的情况下,如果我们不对缓存作出一些限制,很可能会导致用户对产品的反感。

因此为了提升用户的使用体验,开发者们提出了一种名为『缓存淘汰』的策略,它会在某种特定的情况下对部分缓存进行淘汰,从而保证缓存功能有效的同时不会对存储空间有太大的影响。

LRU策略

LRU 就是其中的一种缓存淘汰策略,它的全称是「Last Recently Used」,也就是最近最少使用策略。它的核心思想是:如果一个数据最近被访问,则将来它仍有可能被访问。因此,它会在达到某个阈值时,淘汰掉最近没有访问的数据,从而保证缓存的数据量不会过大。

这个思路非常简单,那么我们该如何实现它呢?

最常见的实现思路就是使用链表来实现,主要过程有以下几步:

  1. 每次有新数据加入,都在链表头部插入
  2. 如果缓存命中,将取走的数据移动至链表头部
  3. 链表满时将链表尾部数据丢弃

要实现上面三个步骤还是比较简单的,这里就不再赘述如何实现了

LruCache 原理剖析

其实 Android API 中已经包含了一个 Google 官方实现的 LRU 缓存容器 —— LruCache。相信接触过图片的缓存的读者对它都不会感觉到陌生,今天就让我们来简单看看它的源码,看看它是如何设计的

最大容量限制

首先看到它的构造函数

可以看到它是通过 LinkedHashMap 这一容器来实现的数据的存放。这里主要是一些值的初始化,其中我们可以注意看到 maxSize,它看上去是代表了 LruCache 中缓存数目的限制,其实它不止是这样,我们可以看到构造函数上方的注释:

注释中说,在没有重写其 sizeOf 方法的使用时,它的作用是限制缓存数目的限制,但如果我们重写了 sizeOf 方法,则它代表了对占据空间大小的限制。通过重写 sizeOf 方法,我们可以限制其存储数据占用的空间大小。

读取缓存

接下来我们看到其 get 方法:

其中代码中的 hitCount、missCount 等主要用于数据统计,我们先不用关注。首先,它通过 synchronized 对存在线程安全的代码块加了锁,保证了这里读取操作的线程安全。当无法读取到数据时, 它会调用 create 方法尝试创建数据。如果用户没有重写 create 方法进行数据的创建,则会返回 null,否则会将创建好的数据放入 Map 中。

将新数据放入 Map 后,会调用 trimToSize 方法进行空间的重整,从而使得缓存的大小不超过我们的 maxSize。

前面的过程看上去很完美,可以解决问题。但其实这样的实现还不够完美。因为在 create 的过程中,如果 create 是一个耗时操作,LruCache 有可能会被放入新的数据,这时还要把创建的新数据放入就不太合理了。

因此,它设计了一个兜底的策略。为了防止在 create 调用过程中放入 Map 中的缓存被创建的数据所替代,如果在放入 Map 时发现 key 对应的位置已经有数据,则不再需要放入该新 value,撤销上一步操作并返回之前 Map 插入的数据。

(不得不感叹 Google 的大神心思还是很细腻的)

写入缓存

我们看到其 put 方法:

put 方法相对比较简单,先将我们的数据放入 Map 中,然后如果之前 key 的位置有数据则将当前 size 再减去原 size 从而计算出放入后的 size。之后通过 trimToSize 方法进行空间重整

空间重整

我们接着看到 trimToSize 方法的实现:

可以看到,它不断地在通过 remove 方法对 Map 中前面的元素进行删除,直到 size 小于 maxSize 为止,从而实现了空间的重整。

LRU 实现

看到这里,如果你正在认真阅读这篇文章,应该会感到很困惑。为什么前面的代码中一点都没有体现 LRU 这一特点呢?LruCache 的 LRU 策略又是如何实现的呢?

其实,它的 LRU 的实现依赖于了 LinkedHashMap 的实现。LinkedHashMap 的构造方法中有一个 accessOrder 参数,当它为 true 时,数据在被访问的时候会进行排序,将最近访问的结果放在集合的后面。有了这一特性,实现 LruCache 只需要在删除元素时从 Map 的前端删除即可实现。

LinkedHashMap

LinkedHashMap 是使用双向链表实现的一个 Map,我们看到它的 get 方法:

看得出来,在 accessOrder 为 true 时,它会调用 afterNodeAccess 方法将最近使用的数据移至链表的末尾,看到它的具体实现:

上面的代码很简单,其实就是通过链表操作来将该读取元素放置到链表尾部。

总结

LruCache 的源码还是十分简单的,它内部实现是使用的 LinkedHashMap。由于 LinkedHashMap 在 accessOrder 为 true 时,在访问数据时会将最近访问的数据放置到链表的结尾,利用这一特点 LruCache 就只需要实现对最大 size 的限制即可。当达到了其 maxSize,重整空间时只需要将 LinkedHashMap 头部的数据删除即可完成。

在上面的代码中我们还能看到,LruCache 的 put 过程都是先放入,再进行空间的重整。这样其实是有隐患的,因为它的 maxSize 并不是真正的最大容量,在 put 过程中其实内存的使用会超过这个 maxSize。因此为了保证程序正常运行,我们应当把 maxSize 设置为所剩内存稍小一些的值,才能避免 OOM 的发生。(虽然这种场景基本不太有可能会发生,但在这里还是提一下)

DiskLruCache 原理剖析

DiskLruCache 是一套能够在磁盘上实现 LRU 存储的开源库,由著名的 JakeWharton 大神开发,我们接下来研究一下它的源码。

初始化

它的构造函数为 private,我们需要通过 open 方法进行创建 DiskLruCache 对象。我们先看到 open 方法的实现

首先,可以发现它需要四个参数,我们先看看这四个参数

  • directory: 存储 DiskLruCache 的路径
  • appVersion: 应用的版本号,这里需要版本号因为应用升级缓存会被清除掉
  • valueCount: 表示一个 key 可以对应多少个文件,一般传入 1
  • maxSize: 缓存所能存储的最大字节数

之后,我们看到注释 1 处,它主要的目的是恢复之前的 backup 文件。如果指定目录下存在 backup 文件,且不存在 journal 文件,则将该 backup 文件改名为 journal 文件。

关于什么是 backup 文件,什么是 journal 文件,我们暂时先不关注,继续往下看应该能理解。

我们接着看到注释 2 处,这里创建了一个 DiskLruCache 对象,此时会为 journalFile、backupFile 等变量进行赋值。

之后在注释 3 处判断其对应的 journal 文件是否存在,若存在,则会调用 cache::readJournal 方法读取 journal 文件的内容,然后会调用 cache::processJournal 对 journal 文件作出一些处理。这两个方法我们后面再进行解析。

接着向下看到注释 4,此处会创建一个新的 DiskLruCache 对象,并且调用 cache::rebuildJournal 方法创建 journal 临时文件 journal.tmp 并写入之前读取到的数据(关于为什么会用到这个临时文件后面会做介绍),最后将这个新对象返回。

总结下来是这三步:

  1. 若存在 backup 文件,且不存在 journal 文件,将其恢复为 journal 文件
  2. 若存在 journal 文件,则尝试恢复 journal 文件内的信息到 DiskLruCache 对象
  3. 读取 journal 文件后,会调用 rebuildJournal 方法将读取并整理后的原 journal 文件内容写入到 journal 临时文件中。

读取 journal

下面我们接着看看 cache::readJournal 做了什么:

从上面的代码可以看到,这里是在用一个作者实现的 StrickLineReader 一行行读取 journal 文件的内容,并给对应数据赋值。在对 magic 字段等校验无误之后,就会开始循环调用 readJournalLine 方法对 journal 文件每一行分别读取。如果遇到了截断的行,则调用 rebuildJournal 在修改前先对 journal 文件进行重建。

journal 文件结构

看来 journal 文件是一种有着特殊规范的文件,我们可以看看 DiskLruCache 的文件头注释,里面有写清楚这个文件的格式及含义:

看得出,前五行是 journal 文件的文件头,它的主要用途是校验。其中的前面四行分别为 magic 字段(类似 class 文件的 magic number,用于校验文件类型)、DiskLruCache 版本、 App 版本、 以及 valueCount。

之后第六行开始就是对缓存的 entry 状态的记录,下面是 DIRTY 等关键词的解释:

  • DIRTY: 代表着有一个 entry 正在被写入。每当我们调用一次 edit 方法,都会向文件中写入一条 DIRTY,它往往都是紧跟着一次 CLEAN 或 REMOVE 操作(成功会跟上 CLEAN,失败会跟上 REMOVE),如果它后面没有匹配的 CLEAN 或 REMOVE,则说明这个文件不完整,应当被删除。
  • CLEAN: 代表着上一次写入操作成功执行,它后面紧跟着与它对应的每一个 Value 的长度(由于 valueCount 可能不止为 1,因此这里不止一个值)
  • READ: 每当对 LRU 的数据进行访问时,都会写入一条 READ 数据,说明有一次读取的记录
  • REMOVE: 代表了写入数据失败或手动调用了 remove 方法,也就是有一个 entry 被移除。

从上面的解释可以看出,journal 文件其实就是一个表示了 DiskLruCache 的 entry 操作记录的一个文件。

而这些关键词后面紧跟的,就是 entry 所对应的 key,看它的形式可以猜测是经过了某种加密。

读取 journal 内容

接下来我们看看 readJournalLine 方法:

我们先看到注释 1 处,这里是实际上就是通过空格的位置来分隔一行的字符串,同时读入了 entry 的 key。

之后从注释 2 处从 lruEntries 这个 Map 中获取 key 对应的 entry,获取不到则 new 并传入 Map。

注释 3 处开始判断操作符并对不同操作符进行了不同的处理:

  • 每当遇到 DIRTY,都会创建并设置一个 Editor对象。
  • 之后若遇到 CLEAN,则会读取它后面的 value 大小,传入 entry,并取消设置之前的 Editor 对象。
  • 若遇到了 REMOVE 或奇怪的参数,则抛出异常。
  • 遇到 READ 的情况下,什么都不会做。
读取 journal 后续处理

接着我们来看看 processJournal 方法,它主要是做一些读取后的后续处理:

我们在之前读 journal 文件的时候知道,如果 entry 已被成功写入,则 entry.currentEditor 应当为 null,因此其不为 null 则说明我们的写入未成功。

写入成功时,只需要根据成功的 value 大小从而统计总大小。

写入失败时,则会将该 entry 相关的文件进行删除,并且删除当前 entry。

journal 重建

初始化阶段,最终会调用 rebuildJournal 方法进行临时 journal 文件的重建 ,我们下面看看它的实现:

可以看出,这个方法的主要工作就是对 journal 文件的重建,将 lruEntities 中的数据重新写入创建的 journal 临时文件,从而去除一些无用的冗余条目。

数据写入&读取

写入数据我们需要通过 edit 方法,它有两个实现,最后都会调用到 edit(key, expectedSequenceNumber) 方法,其中 expectSequenceNumber 默认为 ANY_SEQUENCE_NUMBER。

首先在注释 1 处它通过 checkNotClosed 方法检查了 cache 文件是否关闭,之后通过 validate 方法对 key 通过正则表达式进行校验。

之后在注释 2 处它从 lruEntries 这个 Map 中获取了对应的 entry,同时对它的 currentEditor 进行了校验从而保证其并不是处于写入的状态(currentEditor 不为 null 说明正在进行写入)

这里的 lruEntries 也是一个 LinkedHashMap,可以猜测它也利用了 LinkedHashMap 的 accessOrder 特性。

之后在注释 3 处,创建了对应的 Editor 并返回,同时向 journal 文件中写入 DIRTY 表示该 entry 正在进行写入操作。

Editor

通过前面的代码可以猜测,真正的写入/读取操作是通过 Editor 来完成的,它主要的工作室是经过一系列处理后返回 I/O 的 Stream,提供给用户进行写入 / 读取上一次写入的数据。

写入 newOutputStream

我们首先看到 newOutputStream 方法:

可以通过此方法传入 index 获取到对应 value 的 OutputStream,从而对对应文件进行操作,可以看到它并不是直接创建了一个对目标文件写入的 OutputStream,而是创建了一个 key.$i.tmp 这一临时文件(Dirty 文件),之后所有的写入操作都是在这个临时文件中进行,不会影响到原本的缓存文件。最后,将其 OutputStream 包装为一个自定义的忽略错误的 OutputStream 后返回。

同时,在这里还做了一件事就是将 entry 的对应 value 标记为 written,也就是已进行了写入,方便后续判断。

读取 newInputStream

我们接着看看 newInputStream 方法:

可以通过此方法传入 index 获取对应 value 的 InputStream,可以从上面的代码中看出,它返回的是一个 Clean 文件,也就是写入成功后的文件。

DiskLruCache 采用的这种临时文件的设计保证了写入和读取之间相互隔离,所有的写入操作的记录都是记录在临时文件中,而读取则是读取写入成功后的缓存文件。

提交 commit

接着我们看看 commit 方法了解一下提交的流程:

有无 error 都会调用到 commitEdit 方法,当读取出现 error 时,传入的第二个 boolean 为 false 同时调用 remove 方法把 entry 删除。

commitEdit 方法比较长,我们慢慢分析:

在注释 1 处,如果之前的写入没有出现失败,但 entry 对应的 value 中有还没有进行过写入的,就会视为此次写入失败,调用 editor::abort 方法中止本次提交,并写入 REMOVE。

在注释 2 处,若之前的临时文件还存在,并且写入是成功的,则用这个临时文件替换掉旧的 journal 文件,并重新计算大小,否则会删除之前的临时文件。

在注释 3 处,若写入是成功的,则会写入 CLEAN 到 journal 文件,否则会写入 REMOVE 到 journal。

而在注释 4 处,如果当前的缓存大小超过了 maxSize,则会让 executorService 这个线程池执行 cleanupCallable 这一 Callable,我们猜测这个 Callable 就是用来重整空间的。

其中 editor::abort 实现比较简单,内部就是调用了commitEdit(this, false) 将状态切换为错误。

空间重整 cleanupCallable

DiskLruCache 的空间重整是一个异步的过程,它的代码如下:

首先它调用了 trimToSize 方法将缓存删除至缓存大小适当的状态,之后通过 journalRebuildRequired 方法判断该 journal 需要 rebuild 时,则调用 rebuildJournal 进行 rebuild。

我们先看看 trimToSize 方法:

可以看到,它在不断地删除 LinkedHashMap 头部的缓存,从而实现 LRU 的效果(和之前的 LruCache 的原理相同,这里不再赘述)

我们接着看看 journalRebuildRequired 方法:

通过上面的注释就可以看到,只有当冗余的数据量超过了 2000 条并且超过了 entry 的个数时,才需要进行 rebuildJournal 操作。

其实我们在记录 journal 文件的过程中,每次都会记录一条 DIRTY 伴随着一条 CLEAN 或 REMOVE,但操作完成后这些数据其实就不再那么重要了,因为我们只需要有 entry 条记录足够我们恢复原 entry map 的状态即可。而如果每次都将无用的记录删除肯定是一种效率的消耗,所以 DiskLruCache 的设计是在这种无用的冗余数据超过了 2000 条并且比我们 entry 的个数还要多时,就调用 rebuildJounal 进行 journal 的重建从而减小 journal 文件的体积。(想起了 MMKV 也有类似的做法)

总结

DiskLruCache 是一个采用 LinkedHashMap 实现的 LRU 磁盘缓存类,它使用 journal 这种特殊的文件记录用于记录每次对缓存的写入、读取、删除等操作的状态,而这些对 journal 文件及目标缓存文件的修改都是通过创建一个临时文件来进行的。这样可以保证写入进行的过程中的操作不会影响到已保存的文件,只有写入完成后才会将该文件替换为原来的文件。

这样设计的好处我认为有以下几点:

  • 保证了写入操作的原子性,对 entry 的一次写入操作,要么成功,要么失败。
  • 实现了写入和读取的分离,可以实现写入和读取同时进行,且互相不会冲突。

同时,DiskLruCache 在写入的过程中产生的 journal 文件中的许多数据其实是存在冗余的情况的,在读入 journal 文件及提交写入时都会对空间进行重整,在不影响缓存数据的前提下减小 journal 文件的大小。


Android Developer in GDUT