DiskLruCache源码分析

一个在文件系统上使用确定数量空间的缓存,每个cache entry包含一个字符串key和一个固定数字值。每个key必须匹配正则表达式[a-z0-9_-]{1,64}. 值表示为字节序列,可以通过流或者文件访问。每个值的长度在0Integer.MAX_VALUE之间。

缓存将数据存储在文件系统的一个文件夹中。缓存对这个文件夹必须是独占的,缓存可以删除或者覆盖文件夹中的文件。多个进程在同一时间使用同一个缓存会导致错误。

缓存限制了存储到文件系统的字节数量。当存储的字节数超出了上限,缓存会在后台删除一些entries直到符合上限。这个上限并不严格:在等待文件被删除的过程中,缓存可以暂时超限。这个上限并不包含文件系统开销或者缓存日志,所以对存储空间敏感的应用应该设置一个保守的上限。

这个类会对一些I/O错误容错。如果文件丢失,对应的entries会从缓存中丢掉。当在缓存中写入值的时候发生了错误,edit操作会没有任何提示失败。调用者需要处理其他问题,捕获IOException并正确处理。

既然是LRU Cache,那么怎么少得了LinkedHashMap这个数据结构呢?

1
2
private final LinkedHashMap<String, Entry> lruEntries =
new LinkedHashMap<String, Entry>(0, 0.75f, true);

LinkedHashMap设置accessOrder为true, 遍历的下一个元素就是Least Recently Used Element. 注意到Map里存放的Entry, 那么什么是Entry呢?

Entry

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private final class Entry {
private final String key;

/** Lengths of this entry's files. */
private final long[] lengths;

/** True if this entry has ever been published. */
private boolean readable;

/** The ongoing edit or null if this entry is not being edited. */
private Editor currentEditor;

/** The sequence number of the most recently committed edit to this entry. */
private long sequenceNumber;

private Entry(String key) {
this.key = key;
this.lengths = new long[valueCount];
}
...

public File getCleanFile(int i) {
return new File(directory, key + "." + i);
}

public File getDirtyFile(int i) {
return new File(directory, key + "." + i + ".tmp");
}
}

Entry对象一个key可以对应多个本地磁盘文件,采用key + “.” + i的形式保存要存储的文件,乍一想我好像并没有这样奇葩的需求啊,同一个文件我为什么要分开存储?找不到使用场景还真难以理解作者的设计意图。

OkHttp对磁盘缓存的用法彻底揭开了我的疑惑,对每一个response分两个文件存储,以.0和.1的结尾的文件名区分,分别存储响应的头部和实体部分,方便读取和处理(点击查看OkHttp缓存处理). getCleanFilegetDirtyFile表示以索引数字结尾的文件,也就是最后缓存写入的成员变量文件。

所以lengths成员变量表示一个key对应的多个文件的长度,readable成员变量表示文件是否可读,在完成一次成功的编辑(编辑代表磁盘存储操作)这个变量会被置为true, currentEditor成员变量表示当前entry是否正在被编辑,sequenceNumber成员变量表示最近一次编辑的序号。

DiskLruCache如何存储文件到磁盘

可以看下Universal Image Loader是如何往磁盘中存储图片的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean save(String imageUri, InputStream imageStream, IoUtils.CopyListener listener) throws IOException {
DiskLruCache.Editor editor = cache.edit(getKey(imageUri));
if (editor == null) {
return false;
}

OutputStream os = new BufferedOutputStream(editor.newOutputStream(0), bufferSize);
boolean copied = false;
try {
copied = IoUtils.copyStream(imageStream, os, listener, bufferSize);
} finally {
IoUtils.closeSilently(os);
if (copied) {
editor.commit();
} else {
editor.abort();
}
}
return copied;
}

首先根据图片的uri生成一个合法的key, 调用edit方法获取一个DiskLruCache.Editor对象,通过editor获取一个输出流,读取输入流中的字节数据写入到输出流,最后调用commit方法完成日志相关的操作。可以看出,Editor负责的是准备和善后工作,工具类IoUtils真正将数据写入到了缓存。

Editor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public final class Editor {
private final Entry entry;
private final boolean[] written;
private boolean hasErrors;
private boolean committed;
...
/**
* Returns a new unbuffered output stream to write the value at
* {@code index}. If the underlying output stream encounters errors
* when writing to the filesystem, this edit will be aborted when
* {@link #commit} is called. The returned output stream does not throw
* IOExceptions.
*/

public OutputStream newOutputStream(int index) throws IOException {
synchronized (DiskLruCache.this) {
if (entry.currentEditor != this) {
throw new IllegalStateException();
}
if (!entry.readable) {
written[index] = true;
}
File dirtyFile = entry.getDirtyFile(index);
FileOutputStream outputStream;
try {
outputStream = new FileOutputStream(dirtyFile);
} catch (FileNotFoundException e) {
// Attempt to recreate the cache directory.
directory.mkdirs();
try {
outputStream = new FileOutputStream(dirtyFile);
} catch (FileNotFoundException e2) {
// We are unable to recover. Silently eat the writes.
return NULL_OUTPUT_STREAM;
}
}
return new FaultHidingOutputStream(outputStream);
}
}
}

Editor负责编辑Entry对象的值,调用newOutputStream创建输出流时,将written成员变量置为true, 表示entry可写,在对输出流写入数据时发生错误时会将标记变量hasErrors置为true, 完成一次编辑操作将committed置为true.

创建输出流检查当前Editor是否正确,否则抛出异常,创建一个dirty文件,指定输出流写入的目标文件就是dirty文件,最后创建出一个隐藏错误的输出流,或者当创建输出流失败时返回一个do nothing的NULL_OUTPUT_STREAM.

DiskLruCache如何读取缓存

同样,先看Universal Image Loader是如何读缓存的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public File get(String imageUri) {
DiskLruCache.Snapshot snapshot = null;
try {
snapshot = cache.get(getKey(imageUri));
return snapshot == null ? null : snapshot.getFile(0);
} catch (IOException e) {
L.e(e);
return null;
} finally {
if (snapshot != null) {
snapshot.close();
}
}
}

调用DiskLruCache的get方法获取对应key的一个Snapshot(快照)对象,然后根据对应的index获取File对象。

Snapshot

1
2
3
4
5
6
7
8
9
/** A snapshot of the values for an entry. */
public final class Snapshot implements Closeable {
private final String key;
private final long sequenceNumber;
private File[] files;
private final InputStream[] ins;
private final long[] lengths;
...
}

Snapshot就是一个entry的值的快照,包含成员变量key, sequenceNumber, 缓存文件files及文件长度,缓存文件的输入流。通过get方法可以获取到对应key的一个Snapshot.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* Returns a snapshot of the entry named {@code key}, or null if it doesn't
* exist is not currently readable. If a value is returned, it is moved to
* the head of the LRU queue.
*/

public synchronized Snapshot get(String key) throws IOException {
checkNotClosed();
validateKey(key);
Entry entry = lruEntries.get(key);
if (entry == null) {
return null;
}

if (!entry.readable) {
return null;
}

// Open all streams eagerly to guarantee that we see a single published
// snapshot. If we opened streams lazily then the streams could come
// from different edits.
File[] files = new File[valueCount];
InputStream[] ins = new InputStream[valueCount];
try {
File file;
for (int i = 0; i < valueCount; i++) {
file = entry.getCleanFile(i);
files[i] = file;
ins[i] = new FileInputStream(file);
}
} catch (FileNotFoundException e) {
// A file must have been deleted manually!
for (int i = 0; i < valueCount; i++) {
if (ins[i] != null) {
Util.closeQuietly(ins[i]);
} else {
break;
}
}
return null;
}
...
return new Snapshot(key, entry.sequenceNumber, files, ins, entry.lengths);
}

首先做一般性检查(日志writer是否关闭,key是否合法),获取entry的clean文件,打开输入流,发布一个snapshot对象,调用getFile或者getInputStream可以获取到文件或者输入流对象。

DiskLruCache如何移除缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Drops the entry for {@code key} if it exists and can be removed. Entries
* actively being edited cannot be removed.
*
* @return true if an entry was removed.
*/

public synchronized boolean remove(String key) throws IOException {
checkNotClosed();
validateKey(key);
Entry entry = lruEntries.get(key);
if (entry == null || entry.currentEditor != null) {
return false;
}

for (int i = 0; i < valueCount; i++) {
File file = entry.getCleanFile(i);
if (file.exists() && !file.delete()) {
throw new IOException("failed to delete " + file);
}
size -= entry.lengths[i];
fileCount--;
entry.lengths[i] = 0;
}

...
lruEntries.remove(key);
...
return true;
}

移除一条entry, 正在被编辑的entry不可移除,删除clean文件,更新缓存大小size和文件数目fileCount.

围绕着Cache对象,其实就三个操作edit(将文件存到磁盘),get(从磁盘读取缓存文件),remove(从磁盘移除缓存)。但是还不够,如何避免缓存错误?如何在程序重新启动时恢复缓存数据(包括LRU顺序)?

日志

DiskLruCache引入了日志journal解决了上述问题。

使用一个名字为”journal”的日志文件。日志文件看起来像这样
libcore.io.DiskLruCache
1
100
2

CLEAN 3400330d1dfc7f3f7f4b8d4d803dfcf6 832 21054
DIRTY 335c4c6028171cfddfbaae1a9c313c52
CLEAN 335c4c6028171cfddfbaae1a9c313c52 3934 2342
REMOVE 335c4c6028171cfddfbaae1a9c313c52
DIRTY 1ab96a171faeeee38496d8b330771a7a
CLEAN 1ab96a171faeeee38496d8b330771a7a 1600 234
READ 335c4c6028171cfddfbaae1a9c313c52
READ 3400330d1dfc7f3f7f4b8d4d803dfcf6

前五行组成了日志文件头,分别是字符串常量”libcore.io.DiskLruCache”, cache版本,应用程序版本,value数目和一个空行。

接下来的行是记录了缓存entry的状态。每行包含用空格分隔的值:状态,key, 可选的指定状态值。
o DIRTY 记录一条entry正被创建或更新。每一个成功的DIRTY操作应该跟随着CLEAN或REMOVE操作
否则需要删除临时文件
o CLEAN 记录一条entry被成功发布或者成功读取。CLEAN行跟随着每个值的长度大小。
o READ 记录LRU访问顺序
o REMOVE 记录被删除的entry

当发生cache操作的时候就会添加日志操作记录,时不时通过删除冗余行整理压缩日志。在压缩过程中会使用临时文件”journal.tmp”; 在打开cache的时候就会删除这个临时文件。

前面的分析过程都略过了日志文件的操作,下面来分析通过操作日志是如何解决上述问题的。

edit操作,最后会向日志写入一条DIRTY操作记录

journalWriter.append(DIRTY + ‘ ‘ + key + ‘\n’);

get操作,最后会向日志写入一条READ操作记录

journalWriter.append(READ + ‘ ‘ + key + ‘\n’);

remove操作,最后会向日志写入一条REMOVE操作记录

journalWriter.append(REMOVE + ‘ ‘ + key + ‘\n’);

同时在edit操作结束后,接下来的commit操作会添加CLEAN或REMOVE操作记录

journalWriter.append(CLEAN + ‘ ‘ + key + ‘\n’);

如果磁盘缓存文件大小超过上限或者文件数目超过上限,或者日志冗余行超过上限就会把清理文件和重建日志的任务cleanupCallable提交到线程池中执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if (size > maxSize || fileCount > maxFileCount || journalRebuildRequired()) {
executorService.submit(cleanupCallable);
}

...

private final Callable<Void> cleanupCallable = new Callable<Void>() {
public Void call() throws Exception {
synchronized (DiskLruCache.this) {
if (journalWriter == null) {
return null; // Closed.
}
trimToSize();
trimToFileCount();
if (journalRebuildRequired()) {
rebuildJournal();
redundantOpCount = 0;
}
}
return null;
}
};

以上这些对日志的操作避免了缓存错误。
调用open创建DiskLruCache,会逐行读取日志信息,将状态为CLEAN/DIRTY/READ的记录恢复为entry,添加到LinkedHashMap集合中。调用processJournal删除混乱的entry,DIRTY记录行后面不是跟着CLEAN或者REMOVE记录行的属于混乱的记录。这样就在内存中恢复了上次访问状态的视图。

参考资料

DiskLruCahe的实现