DiskLruCache 源码分析

本文分析 OkHttp 源码中的 DiskLruCache。

DiskLruCache 在很多系统中承担了缓存系统的作用。作为一个组件,根据 key 向外部提供缓存的增、删、改、查的能力,同时按照 LRU 算法淘汰缓存,以保证整个缓存占用的空间不会过大。

下面我们会从 DiskLruCache 的几个部分开展分析。

创建缓存系统

要创建一个基于磁盘的缓存系统,我们需要几部分信息:

  1. 文件在文件系统的位置
  2. 文件占用大小限制
  3. 版本号及其他一些信息
return new DiskLruCache(fileSystem, directory, appVersion, valueCount, maxSize, executor);

在此实现中,我们使用 FileSystem 抽象对文件系统的操作。

uml of FileSystem.java

对 OkHttp 的维护者来说,并非在一开始就有抽象文件系统的概念,在这个 提交 里面可以看到,在引入文件系统这个抽象概念的同时,删除了Util.java 工具类中的部分内容,并且还引入了一个用于测试的 InMemoryFileSystem

github_commit_filesystem

想要减少 IO 操作的重复代码,简单地使用静态工具类就能实现,为什么要使用抽象?抽象在这里的作用不仅仅是减少重复代码,一个更重要的原因是解耦,方便日后的拓展和测试。例如上述提交中的 InMemoryFileSystem 类,将内存作为磁盘提供服务,方便测试。又例如,我们可以在磁盘系统与使用者中间添加文件加密的功能。

如何表示磁盘中的缓存

我们以文件的方式保存用户的缓存,为了不超过大小的限制,就需要记录文件的大小。用户还需要对缓存进行增、删、改和查,还要能够在写入过程中放弃写入,所以,我们采用 dirtyFile + cleanFile 的方式,用户先在 dirtyFile 中写入数据,在用户确认写入完毕之后,我们才使用 dirtyFile 覆盖 cleanFile,并更新缓存大小。

上述这些属性属于同一个缓存,表示缓存对象的方方面面,因此将这些数据封装成一个 Entry 类。

uml of entry

我们将所有的缓存在内存中的表示成一个列表,通过 LRU 算法,不断淘汰相对来说较少使用的缓存。在 DiskLruCache 中,我们使用 LinkedHashMap 来组织这个索引列表,它也支持 LRU 算法移除最少使用的 Entry,满足我们的需求。

写入

我们打算向用户提供一个输出流,并且保证几点:

  1. 同一时间只有一个输出流
  2. 记录用户的操作
  3. 用户中途放弃写入之后删除 dirtyFile

因此将这些行为封装到 Editor 类:

uml of editor

当用户调用了 edit() 方法后,我们在代表该缓存的 entry 之上新建返回一个 Editor,并且在 entry 中保存此 editor 的引用。之后就可以根据 entry 中是否存在 editor 的引用,判断该缓存是否正在被编辑。在用户确认写入完毕之后,删除此引用。

if (entry != null && entry.currentEditor != null) {
    return null; // Another edit is in progress.
}

用户使用 editor 获得一个在 dirtyFile 之上的输出流,往这个流写入数据,调用 editor.commit() 确认写入完成,我们用 dirtyFile 覆盖 cleanFile,然后更新总缓存大小。由于总缓存大小有可能比原来的更大了,所以我们需要判断大小情况,根据需要执行清理任务。

用户中途放弃写入时调用 editor.abort(),我们简单地将 dirtyFile 删除即可。

读取

同样地,我们以输入流的方式向用户提供缓存读取的能力。除了流,我们还会提供文件的大小等信息,不过,我们不能直接将 Entry 对象提供给用户,用户不需要也不应该知道具体的实现,所以我们将这些数据封装成 Snapshot 提供给用户。

uml of snapshot

日志文件

我们会在内存中维持缓存在内存中的索引,表现为一系列的 entry 对象组成的列表(上文提到的 LinkedHashMap)。冷启动时,我们根据日志文件重新生成索引,当缓存有修改时,同时更新索引和日志。所以日志文件相当重要,稍有不慎便会造成野缓存的产生,磁盘空间得不到释放。

上文说到,我们使用 dirtyFile + cleanFile 的方式编辑缓存,所以: 1. 对于一次编辑,首先会有一行 DIRTY 日志 2. 用户确认写入完毕之后,使用 dirtyFile 覆盖 cleanFile,然后产生一行 CLEAN 日志 3. 读取缓存时产生一行 READ 日志 4. 移除缓存时产生一行 REMOVE 日志

除了在操作缓存时会写入日志行,在日志文件行数过多时,需要执行清理任务缩小日志文件的体积。这时候,我们根据内存中的缓存索引重建日志文件。

for (Entry entry : lruEntries.values()) {
    if (entry.currentEditor != null) {
        writer.writeUtf8(DIRTY).writeByte(' ');
        writer.writeUtf8(entry.key);
         writer.writeByte('\n');
    } else {
        writer.writeUtf8(CLEAN).writeByte(' ');
        writer.writeUtf8(entry.key);
        entry.writeLengths(writer);
         writer.writeByte('\n');
    }
}

在冷启动时需要恢复上次关闭缓存系统时的状态,根据日志文件重新生成缓存索引,不同的日志行有对应的行为:

if (secondSpace == -1) {
    key = line.substring(keyBegin);
    if (firstSpace == REMOVE.length() && line.startsWith(REMOVE)) {
        lruEntries.remove(key);
        return;
    }
} else {
    key = line.substring(keyBegin, secondSpace);
}
 
Entry entry = lruEntries.get(key);
if (entry == null) {
    entry = new Entry(key);
    lruEntries.put(key, entry);
}

if (secondSpace != -1 && firstSpace == CLEAN.length() && line.startsWith(CLEAN)) {
    String[] parts = line.substring(secondSpace + 1).split(" ");
    entry.readable = true;
    entry.currentEditor = null;
    entry.setLengths(parts);
} else if (secondSpace == -1 && firstSpace == DIRTY.length() && line.startsWith(DIRTY)) {
    entry.currentEditor = new Editor(entry);
} else if (secondSpace == -1 && firstSpace == READ.length() && line.startsWith(READ)) {
    // This work was already done by calling lruEntries.get().
} else {
    throw new IOException("unexpected journal line: " + line);
}

为了保证日志文件不出错,DiskLruCache 拥有三个跟日志有关的文件: 1. journalFile 2. journalFileTmp 3. journalFileBackup

当冷启动时,优先使用 journalFile 重建索引,如果 journalFile 不存在将重命名 journalFileBackupjournalFile 并使用。

if (fileSystem.exists(journalFileBackup)) {
    // If journal file also exists just delete backup file.
    if (fileSystem.exists(journalFile)) {
        fileSystem.delete(journalFileBackup);
    } else {
        fileSystem.rename(journalFileBackup, journalFile);
    }
}

当清理日志文件时,先将日志行写入 journalFileTmp,然后使用 journalFileTmp 覆盖 journalFile

if (fileSystem.exists(journalFile)) {
    fileSystem.rename(journalFile, journalFileBackup);
}
fileSystem.rename(journalFileTmp, journalFile);
fileSystem.delete(journalFileBackup);

清理

DiskLruCache 中的清理任务,包括两个方面的工作:

  1. 清理缓存文件
  2. 清理日志文件

一个通用的清理模型是:Executor + RunnableExecutor 是一个特定配置的线程池,可以看做一个运行 Runnable 逻辑的地方。我们在某些时机将 Runnable 提交到 Executor 执行,全部或者部分清理任务的执行时机包括:

  1. 调用 flush()close()
  2. 用户请求缓存 Snapshot 并且需要清理日志文件时
  3. 用户希望编辑缓存但是上次的清理任务失败时
  4. 修改了缓存大小限制时
  5. 用户确认缓存写入完毕时
  6. 移除缓存并且需要清理日志文件时

可以看到 DiskLruCache 有根据业务需求来确定执行的时机。不过总的来说,当缓存或者日志有修改后,甚至更严格地,有增量后,就应该启动清理任务。

内存索引的维护

日志文件确保了缓存不会成为野缓存,我们需要确保内存索引与日志文件一致:

  1. 当冷启动时我们从日志文件恢复索引,两者毫无疑问是一致的。
  2. 当清理日志文件时,根据内存索引生成日志文件,亦可保证一致。
  3. 当用户编辑缓存时,需要同时修改内存索引和日志文件,以确保一致。

总结

arch

至此,我们可以总结出 DiskLruCache 整体的架构图:

  1. 在底层,我们抽象了对文件系统的操作,方便日后的拓展和测试。
  2. 上一层,对于每一个缓存,我们封装成一个 Entry。每一个对于 Entry 列表的操作,都记录在 Journal 中,以便下次启动时根据 Journal 在内存中重新创建 Entry 列表。当 Entry 总大小或者 Journal 行数有可能超过最大值时,我们在 Executor 中运行清理任务。
  3. 用户的查询请求会得到一个 Snapshot 对象,编辑请求会得到一个 Editor 对象。
  4. 通过 Snapshot 对象(或 Editor 对象)获得 Source(或 Sink),查询(或编辑)缓存内容。