文章

Android 磁盘最近最少缓存实现 - DiskLruCache 源码分析

 DiskLruCache 是一个 Android 端使用广泛的磁盘 LRU (最近最少使用)缓存算法的实现库,甚至在 AOSP 中都有使用。

基础使用

为了对整体架构有个印象,方便找分析入口,先看看基本的使用。

实例化:

val cache = DiskLruCache.open(cacheFile, version, valueCount, maxSize)

写入:

val editor = cache.edit(key.md5())
val os = editor.newOutputStream(0)

读取:

val snapshot = cache.get(key.md5())
val is = snapshot?.getInputStream(0)

关于它的具体使用可以看这篇文章

整体来看并不复杂,实际上代码量也确实不多。通过读取时的 snapshot 封装猜测后续修改不会影响已经读取到的值。

日志文件

DiskLruCache 的一个显著特征就是在缓存目录有一个 journal 文件,用于记录所有操作日志,大概长这个样子:

libcore.io.DiskLruCache
1
19
1

DIRTY c915a1313f3e413252fae2957469dcd2
CLEAN c915a1313f3e413252fae2957469dcd2 50196
READ c915a1313f3e413252fae2957469dcd2
DIRTY 8b33d00d5f9d443095e20829a1367e05
CLEAN 8b33d00d5f9d443095e20829a1367e05 159594

前五行是元数据:

  1. 一个魔法数,固定字符串,用于标识这是一个 DiskLruCache 的日志文件。
  2. DiskLruCache 版本号,从发布以来就没变过,预留一下便于后续格式更新。
  3. 开发者声明的应用版本号。
  4. 每个 key 对应几个 value,一般都是1。一个 key 支持写入多个值,每个值都是一个文件,文件名是 key.index
  5. 一个空行

每次初始化时都要校验这些元数据。

之后是真正的日志数据,每一行是一个记录,拥有 state, key, option 字段,用空格分隔,其中 option 字段根据 state 的不同是可选的。

  • DIRTY: 表示一项数据正在被写入(创建或更新)。后面必须跟着一个 CLEANREMOVE。否则这个项目将被视为临时文件,需要清除。
  • CLEAN: 表示一项数据被成功写入。后面跟着一个数据大小 (Byte),如果一个 key 对应多个数据,则跟着多个大小。
  • REMOVE: 表示一项数据已经被删除。
  • READ: 表示对应项被读取了一次。其实这个不能算是状态,就是一个操作记录。

实例化

open()

那就直接从使用的入口开始分析吧。

  /**
   * 在指定位置打开一个 cache 实例,如果日志文件不存在就创建一个。
   *
   * @param directory 一个可写的目录
   * @param valueCount 每个缓存项的数据个数
   * @param maxSize 可占用的最大空间
   * @throws IOException if reading or writing the cache directory fails
   */
  public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize)
      throws IOException {
    // 检查参数
    if (maxSize <= 0) {
      throw new IllegalArgumentException("maxSize <= 0");
    }
    if (valueCount <= 0) {
      throw new IllegalArgumentException("valueCount <= 0");
    }

    // 检查备份日志文件
    File backupFile = new File(directory, JOURNAL_FILE_BACKUP);
    if (backupFile.exists()) {
      File journalFile = new File(directory, JOURNAL_FILE);
      // 如果日志存在就删除备份
      if (journalFile.exists()) {
        backupFile.delete();
      } else {
        renameTo(backupFile, journalFile, false);
      }
    }

    // 日志文件存在则继续处理
    DiskLruCache cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
    if (cache.journalFile.exists()) {
      try {
        cache.readJournal();
        cache.processJournal();
        cache.journalWriter = new BufferedWriter(
            new OutputStreamWriter(new FileOutputStream(cache.journalFile, true), Util.US_ASCII));
        return cache;
      } catch (IOException journalIsCorrupt) {
        System.out
            .println("DiskLruCache "
                + directory
                + " is corrupt: "
                + journalIsCorrupt.getMessage()
                + ", removing");
        cache.delete();
      }
    }

    // 否则执行初始化
    directory.mkdirs();
    cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
    cache.rebuildJournal();
    return cache;
  }

open 函数没什么好讲的,重点都注释了。一波预处理后判断日志文件是否存在,不存在就执行初始化创建一个,存在就读取并处理。

初始化

初始化主要是调用 rebuildJournal().

  /**
   * 创建一个新日志,并覆盖已有的。
   */
  private synchronized void rebuildJournal() throws IOException {
    if (journalWriter != null) {
      journalWriter.close();
    }

    Writer writer = new BufferedWriter(
        new OutputStreamWriter(new FileOutputStream(journalFileTmp), Util.US_ASCII));
    try {
      // 写入元数据
      writer.write(MAGIC);
      writer.write("\n");
      writer.write(VERSION_1);
      writer.write("\n");
      writer.write(Integer.toString(appVersion));
      writer.write("\n");
      writer.write(Integer.toString(valueCount));
      writer.write("\n");
      writer.write("\n");

      // 将已有的数据项写入日志
      for (Entry entry : lruEntries.values()) {
        if (entry.currentEditor != null) {
          writer.write(DIRTY + ' ' + entry.key + '\n');
        } else {
          writer.write(CLEAN + ' ' + entry.key + entry.getLengths() + '\n');
        }
      }
    } finally {
      writer.close();
    }

    // 覆盖已有的
    if (journalFile.exists()) {
      renameTo(journalFile, journalFileBackup, true);
    }
    renameTo(journalFileTmp, journalFile, false);
    journalFileBackup.delete();

    journalWriter = new BufferedWriter(
        new OutputStreamWriter(new FileOutputStream(journalFile, true), Util.US_ASCII));
  }

初始化也不复杂,主体就是写入头信息和已有的缓存数据。未在编辑的直接标注 CLEAN 也就是准备就绪可以读取,正在编辑的则标注 DIRTY 等待后续操作。

稍微注意下替换过程,写入的是一个临时文件,将现有文件备份,最后才是用临时文件覆盖。这样如果出现异常还可以恢复。

读取处理日志

如日志文件存在首先进行读取,调用 readJournal() 函数。

private void readJournal() throws IOException {
    StrictLineReader reader = new StrictLineReader(new FileInputStream(journalFile), Util.US_ASCII);
    try {
      // 校验文件头
      String magic = reader.readLine();
      String version = reader.readLine();
      String appVersionString = reader.readLine();
      String valueCountString = reader.readLine();
      String blank = reader.readLine();
      if (!MAGIC.equals(magic)
          || !VERSION_1.equals(version)
          || !Integer.toString(appVersion).equals(appVersionString)
          || !Integer.toString(valueCount).equals(valueCountString)
          || !"".equals(blank)) {
        throw new IOException("unexpected journal header: [" + magic + ", " + version + ", "
            + valueCountString + ", " + blank + "]");
      }

      // 读取并顺便计算下日志记录数
      int lineCount = 0;
      while (true) {
        try {
          readJournalLine(reader.readLine());
          lineCount++;
        } catch (EOFException endOfJournal) {
          break;
        }
      }
      redundantOpCount = lineCount - lruEntries.size();
    } finally {
      Util.closeQuietly(reader);
    }
  }

读取的时候计算了一下日志的行数,减去真正有效的数据项,剩下的就是多余日志行数。后面会用来维护日志文件以免越来越臃肿。

具体日志解析在 readJournalLine() 函数里。

  private void readJournalLine(String line) throws IOException {
    int firstSpace = line.indexOf(' ');
    if (firstSpace == -1) {
      throw new IOException("unexpected journal line: " + line);
    }

    int keyBegin = firstSpace + 1;
    int secondSpace = line.indexOf(' ', keyBegin);
    final String key;
    if (secondSpace == -1) {
      // 找不到第二个空格,即:只有 state 和 key 两个字段
      key = line.substring(keyBegin);
      if (firstSpace == REMOVE.length() && line.startsWith(REMOVE)) {
        // REMOVE:删除对应的数据
        lruEntries.remove(key);
        return;
      }
    } else {
      key = line.substring(keyBegin, secondSpace);
    }

    Entry entry = lruEntries.get(key);
    if (entry == null) {
      // 如果没有加入到 lruEntries 就加进去
      entry = new Entry(key);
      lruEntries.put(key, entry);
    }

    if (secondSpace != -1 && firstSpace == CLEAN.length() && line.startsWith(CLEAN)) {
      // 设置 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);
    }
  }

还算是比较清晰。首先判断的是 REMOVE 记录,操作也很粗暴,直接从 lruEntries 里删除掉。接下来既然没有 REMOVE 那么就是存在的数据,应当加入集合,所以判断没有加入的话就加进去。最后根据读取到的值设置一下数据项的状态就好了。

不难看出解析之后最后集合中存在的元素需要满足 ①拥有至少一个非 REMOVE 状态的记录。 ②之后没有 REMOVE 记录。注意此时 DIRTY 也在集合中。

一个比较有意思的是对 state 字段的判断,利用 startsWithlength 完成,相对于先 substring 再比较效率稍微高一点。

到这里读取就结束了,下面进行处理。


读取完后 open() 会继续调用 processJournal() 函数。

  /**
   * 计算缓存大小并删除 Dirty 的数据项。
   */
  private void processJournal() throws IOException {
    deleteIfExists(journalFileTmp);
    for (Iterator<Entry> i = lruEntries.values().iterator(); i.hasNext(); ) {
      Entry entry = i.next();
      if (entry.currentEditor == null) {
        // 计算有效数据总大小
        for (int t = 0; t < valueCount; t++) {
          size += entry.lengths[t];
        }
      } else {
        // 清除无效数据
        entry.currentEditor = null;
        for (int t = 0; t < valueCount; t++) {
          deleteIfExists(entry.getCleanFile(t));
          deleteIfExists(entry.getDirtyFile(t));
        }
        i.remove();
      }
    }
  }

比解析日志简单一些,主要做了两件事:计算缓存大小、删除无效数据。

无效数据指的是单独出现了 DIRTY 但后面没有 REMOVECLEAN 与之对应的。这类项目在读取的时候我们把它加入了集合并设置为编辑模式,所以现在直接判断 currentEditor 就行了。

此时集合中只剩下有效的 CLEAN 项目,实例化完成。

写入缓存

我们通过拿到一个 DiskLruCache.Editor 打开一个输出流来进行写入操作,所以从 cache.edit() 开始分析。

  private synchronized Editor edit(String key, long expectedSequenceNumber) throws IOException {
    // 校验参数、状态
    checkNotClosed();
    validateKey(key);
    Entry entry = lruEntries.get(key);
    if (expectedSequenceNumber != ANY_SEQUENCE_NUMBER && (entry == null
        || entry.sequenceNumber != expectedSequenceNumber)) {
      return null; // Snapshot is stale.
    }

    // 没有就创建,正在编辑就返回 null
    if (entry == null) {
      entry = new Entry(key);
      lruEntries.put(key, entry);
    } else if (entry.currentEditor != null) {
      return null; // Another edit is in progress.
    }

    // 设置编辑状态
    Editor editor = new Editor(entry);
    entry.currentEditor = editor;

    // 写入日志并 flush 避免文件泄露(也就是写入了缓存但是日志中没有)
    journalWriter.write(DIRTY + ' ' + key + '\n');
    journalWriter.flush();
    return editor;
  }

也是非常常规易懂的操作。最后先调用一下 flush 写入磁盘,从实例化过程我们就能看出 DiskLruCache 完全靠日志来读取缓存数据,如果有数据写到了磁盘却没有在日志中体现,就永远不会被读取或被删除,造成文件泄露。

获取 editor 后可以通过 newOutputStream 拿到一个输出流用来写入。

    /**
     * 在给定 index 除打开一个输出流。如果写入磁盘时遇到了错误那么调用 commit 
     * 时编辑操作将终止并标记为失败。返回的输出流不会抛出 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);
      }
    }

getDirtyFile 返回的是一个名称为 {key}.{index}.tmp 的临时文件。把这个文件的输出流通过 FaultHidingOutputStream 封装最后返回。封装很简单就是对常见操作全部捕获了异常,内部设置一个 hasErrors 来记录。

写入完成后我们需要调用 comit 方法。

    /**
     * 提交此次编辑,数据项转为就绪状态。并解除锁定允许再次编辑。
     */
    public void commit() throws IOException {
      if (hasErrors) {
        completeEdit(this, false);
        remove(entry.key); // The previous entry is stale.
      } else {
        completeEdit(this, true);
      }
      committed = true;
    }

这里进行了一下错误判断。先 completeEdit 走完流程,如果有错那么直接删除掉。接下来看看是怎么完成编辑流程的。

  private synchronized void completeEdit(Editor editor, boolean success) throws IOException {
    Entry entry = editor.entry;
    // 校验状态
    if (entry.currentEditor != editor) {
      throw new IllegalStateException();
    }

    // 如果是首次创建,那么每个索引必须有值
    if (success && !entry.readable) {
      for (int i = 0; i < valueCount; i++) {
        if (!editor.written[i]) {
          editor.abort();
          throw new IllegalStateException("Newly created entry didn't create value for index " + i);
        }
        if (!entry.getDirtyFile(i).exists()) {
          editor.abort();
          return;
        }
      }
    }

    // 操作文件,成功就转为正式数据并更新一些参数,否则就删除文件
    for (int i = 0; i < valueCount; i++) {
      File dirty = entry.getDirtyFile(i);
      if (success) {
        if (dirty.exists()) {
          File clean = entry.getCleanFile(i);
          dirty.renameTo(clean);
          long oldLength = entry.lengths[i];
          long newLength = clean.length();
          entry.lengths[i] = newLength;
          size = size - oldLength + newLength;
        }
      } else {
        deleteIfExists(dirty);
      }
    }

    // 一些收尾工作,写入日志
    redundantOpCount++;
    entry.currentEditor = null;
    if (entry.readable | success) {
      entry.readable = true;
      journalWriter.write(CLEAN + ' ' + entry.key + entry.getLengths() + '\n');
      if (success) {
        entry.sequenceNumber = nextSequenceNumber++;
      }
    } else {
      lruEntries.remove(entry.key);
      journalWriter.write(REMOVE + ' ' + entry.key + '\n');
    }
    journalWriter.flush();

    // 超过限定大小要重构一下
    if (size > maxSize || journalRebuildRequired()) {
      executorService.submit(cleanupCallable);
    }
  }

一开始 if (success && !entry.readable) 判断是否成功且是新创建的,若是编辑已存在的文件那么 readable 应该是 true. 这里面要求每一个索引都必须有数据。

接着进行文件操作。如果成功就把临时文件重命名为正式缓存数据,然后更新一下数据项大小和总大小。如果失败调用 deleteIfExists,其实就是删除临时文件。

最后进行收尾工作,成功的话设置下 readable 表示此缓存已就绪,写入一个 CLEAN 日志。否则删除这一数据项并写入一个 REMOVE 日志。然后判断一下是否需要重构,得满足任意一个条件就行:① 缓存大小超过限制。②日志条目超过阈值并且大于现有的缓存项数。这是很好理解的,即便日志数很多,但如果缓存项也很多那么这些日志就是必要的,不能删除。

除了 commit 外还有一个 abort 函数用于放弃此次编辑:

    /**
     * Aborts this edit. This releases the edit lock so another edit may be
     * started on the same key.
     */
    public void abort() throws IOException {
      completeEdit(this, false);
    }

同样是调用 completeEdit 只不过直接指明编辑失败。

读取缓存

读取缓存是调用 cache.get(kay) 得到一个 Snapshot 对象,那就先来看看这个 get 方法:

/**
   * 根据 key 返回一个快照对象,如果 key 不存在或不可读则返回 null. 
   *  一旦成功返回那么此数据项将移动到 lru 队列最前端。
   */
  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;
    }

    // 直接打开输入流来达到“快照”的效果。
    // 如果返回文件那么有可能在读取前被更改。
    InputStream[] ins = new InputStream[valueCount];
    try {
      for (int i = 0; i < valueCount; i++) {
        ins[i] = new FileInputStream(entry.getCleanFile(i));
      }
    } catch (FileNotFoundException e) {
      // 文件被异常删除了
      for (int i = 0; i < valueCount; i++) {
        if (ins[i] != null) {
          Util.closeQuietly(ins[i]);
        } else {
          break;
        }
      }
      return null;
    }

    // 写入日志,根据需求重构
    redundantOpCount++;
    journalWriter.append(READ + ' ' + key + '\n');
    if (journalRebuildRequired()) {
      executorService.submit(cleanupCallable);
    }
    // 返回快照对象
    return new Snapshot(key, entry.sequenceNumber, ins, entry.lengths);
  }

读取相对来说简单多了,分为三步:检验、读取、写日志。和一开始的猜测一样,在读取过程中直接打开了一个输入流以免后续编辑的影响。

总结(LRU实现)

虽然已经分析完了主要方法,但似乎没有看到 LRU 的实现啊?其实核心的东西就是一个变量:

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

LinkedHashMap 底层实现是一个双向链表,因此可以维护顺序。构造函数第三个参数是 accessOrder 默认为 false,这里非常少见地设置为 true 了。效果就是每次取元素时,被取到的元素就会自动移动到尾部,从而实现了 LRU,即:越靠近尾部的元素就是近期被访问过的。因此当大小超出阈值时,只需要从头部开始依次删除。

举个栗子🌰:我们先依次插入 [1, 5] 这五个数据项,那么此时的链表就是:

1, 2, 3, 4, 5

接着依次读取了[1, 4, 1],链表变为:

2, 3, 4, 5, 1 →
2, 3, 5, 1, 4 →
2, 3, 5, 4, 1

此时插入一个比较大的数据项,总空间达到阈值,那么只需从 2 开始依次删除就行了。

最后来看一下负责维持空间大小的 trimToSize 函数:

  private void trimToSize() throws IOException {
    while (size > maxSize) {
      Map.Entry<String, Entry> toEvict = lruEntries.entrySet().iterator().next();
      remove(toEvict.getKey());
    }
  }

非常简短,与刚才分析的一样,从 lruEntries 头部开始依次删除,直到大小符合要求。

说到底 DiskLruCache 这个库并没有在 LRU 上下太大功夫,核心算法由 LinkedHashMap 实现了。而我们需要做的更多的是维护磁盘缓存的一致性,避免文件泄露。仔细思考下 journal 文件的定义还是有不少收获。之前习惯性地用成熟的数据存储格式,比如 json, xml,甚至使用 sqlite 数据库,毫无疑问数据库 和 xml 太重了在用在这里不合适。而 json 定义严格,容错率低,哪怕有一个标点错误都很难简单地恢复尽可能多的记录。DiskLruCache 仅仅使用5个状态关键字就轻松解决了这一问题,大道至简啊。