緩存概述
在 Android 開發(fā)的過程中常常需要用到緩存的功能來減少應用對用戶流量的消耗（如圖片緩存，文章緩存等等）。而對于用戶的手機而言，其內(nèi)存/存儲空間的大小一般都是有限的，在一些緩存量大或緩存十分頻繁的情況下，如果我們不對緩存作出一些限制，很可能會導致用戶對產(chǎn)品的反感。
因此為了提升用戶的使用體驗，開發(fā)者們提出了一種名為『緩存淘汰』的策略，它會在某種特定的情況下對部分緩存進行淘汰，從而保證緩存功能有效的同時不會對存儲空間有太大的影響。
LRU策略
LRU 就是其中的一種緩存淘汰策略，它的全稱是「Last Recently Used」，也就是最近最少使用策略。它的核心思想是：如果一個數(shù)據(jù)最近被訪問，則將來它仍有可能被訪問。因此，它會在達到某個閾值時，淘汰掉最近沒有訪問的數(shù)據(jù)，從而保證緩存的數(shù)據(jù)量不會過大。
這個思路非常簡單，那么我們該如何實現(xiàn)它呢？
最常見的實現(xiàn)思路就是使用鏈表來實現(xiàn)，主要過程有以下幾步：
- 每次有新數(shù)據(jù)加入，都在鏈表頭部插入
- 如果緩存命中，將取走的數(shù)據(jù)移動至鏈表頭部
- 鏈表滿時將鏈表尾部數(shù)據(jù)丟棄
要實現(xiàn)上面三個步驟還是比較簡單的，這里就不再贅述如何實現(xiàn)了
LruCache 原理剖析
其實 Android API 中已經(jīng)包含了一個 Google 官方實現(xiàn)的 LRU 緩存容器 —— LruCache。相信接觸過圖片的緩存的讀者對它都不會感覺到陌生，今天就讓我們來簡單看看它的源碼，看看它是如何設計的
最大容量限制
首先看到它的構造函數(shù)
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
可以看到它是通過 LinkedHashMap 這一容器來實現(xiàn)的數(shù)據(jù)的存放。這里主要是一些值的初始化，其中我們可以注意看到 maxSize，它看上去是代表了 LruCache 中緩存數(shù)目的限制，其實它不止是這樣，我們可以看到構造函數(shù)上方的注釋:
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
注釋中說，在沒有重寫其 sizeOf 方法的使用時，它的作用是限制緩存數(shù)目的限制，但如果我們重寫了 sizeOf 方法，則它代表了對占據(jù)空間大小的限制。通過重寫 sizeOf 方法，我們可以限制其存儲數(shù)據(jù)占用的空間大小。
讀取緩存
接下來我們看到其 get 方法：
/**
* Returns the value for {@code key} if it exists in the cache or can be
* created by {@code #create}. If a value was returned, it is moved to the
* head of the queue. This returns null if a value is not cached and cannot
* be created.
*/
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
其中代碼中的 hitCount、missCount 等主要用于數(shù)據(jù)統(tǒng)計，我們先不用關注。首先，它通過 synchronized 對存在線程安全的代碼塊加了鎖，保證了這里讀取操作的線程安全。當無法讀取到數(shù)據(jù)時， 它會調(diào)用 create 方法嘗試創(chuàng)建數(shù)據(jù)。如果用戶沒有重寫 create 方法進行數(shù)據(jù)的創(chuàng)建，則會返回 null，否則會將創(chuàng)建好的數(shù)據(jù)放入 Map 中。
將新數(shù)據(jù)放入 Map 后，會調(diào)用 trimToSize 方法進行空間的重整，從而使得緩存的大小不超過我們的 maxSize。
前面的過程看上去很完美，可以解決問題。但其實這樣的實現(xiàn)還不夠完美。因為在 create 的過程中，如果 create 是一個耗時操作，LruCache 有可能會被放入新的數(shù)據(jù)，這時還要把創(chuàng)建的新數(shù)據(jù)放入就不太合理了。
因此，它設計了一個兜底的策略。為了防止在 create 調(diào)用過程中放入 Map 中的緩存被創(chuàng)建的數(shù)據(jù)所替代，如果在放入 Map 時發(fā)現(xiàn) key 對應的位置已經(jīng)有數(shù)據(jù)，則不再需要放入該新 value，撤銷上一步操作并返回之前 Map 插入的數(shù)據(jù)。
（不得不感嘆 Google 的大神心思還是很細膩的）
寫入緩存
我們看到其 put 方法：
/**
* Caches {@code value} for {@code key}. The value is moved to the head of
* the queue.
*
* @return the previous value mapped by {@code key}.
*/
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
put 方法相對比較簡單，先將我們的數(shù)據(jù)放入 Map 中，然后如果之前 key 的位置有數(shù)據(jù)則將當前 size 再減去原 size 從而計算出放入后的 size。之后通過 trimToSize 方法進行空間重整
空間重整
我們接著看到 trimToSize 方法的實現(xiàn)：
/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
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 || map.isEmpty()) {
break;
}
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
可以看到，它不斷地在通過 remove 方法對 Map 中前面的元素進行刪除，直到 size 小于 maxSize 為止，從而實現(xiàn)了空間的重整。
LRU 實現(xiàn)
看到這里，如果你正在認真閱讀這篇文章，應該會感到很困惑。為什么前面的代碼中一點都沒有體現(xiàn) LRU 這一特點呢？LruCache 的 LRU 策略又是如何實現(xiàn)的呢？
其實，它的 LRU 的實現(xiàn)依賴于了 LinkedHashMap 的實現(xiàn)。LinkedHashMap 的構造方法中有一個 accessOrder 參數(shù)，當它為 true 時，數(shù)據(jù)在被訪問的時候會進行排序，將最近訪問的結果放在集合的后面。有了這一特性，實現(xiàn) LruCache 只需要在刪除元素時從 Map 的前端刪除即可實現(xiàn)。
LinkedHashMap
LinkedHashMap 是使用雙向鏈表實現(xiàn)的一個 Map，我們看到它的 get 方法：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
看得出來，在 accessOrder 為 true 時，它會調(diào)用 afterNodeAccess 方法將最近使用的數(shù)據(jù)移至鏈表的末尾，看到它的具體實現(xiàn)：
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
上面的代碼很簡單，其實就是通過鏈表操作來將該讀取元素放置到鏈表尾部。
總結
LruCache 的源碼還是十分簡單的，它內(nèi)部實現(xiàn)是使用的 LinkedHashMap。由于 LinkedHashMap 在 accessOrder 為 true 時，在訪問數(shù)據(jù)時會將最近訪問的數(shù)據(jù)放置到鏈表的結尾，利用這一特點 LruCache 就只需要實現(xiàn)對最大 size 的限制即可。當達到了其 maxSize，重整空間時只需要將 LinkedHashMap 頭部的數(shù)據(jù)刪除即可完成。
在上面的代碼中我們還能看到，LruCache 的 put 過程都是先放入，再進行空間的重整。這樣其實是有隱患的，因為它的 maxSize 并不是真正的最大容量，在 put 過程中其實內(nèi)存的使用會超過這個 maxSize。因此為了保證程序正常運行，我們應當把 maxSize 設置為所剩內(nèi)存稍小一些的值，才能避免 OOM 的發(fā)生。（雖然這種場景基本不太有可能會發(fā)生，但在這里還是提一下）
DiskLruCache 原理剖析
DiskLruCache 是一套能夠在磁盤上實現(xiàn) LRU 存儲的開源庫，由著名的 JakeWharton 大神開發(fā)，我們接下來研究一下它的源碼。
初始化
它的構造函數(shù)為 private，我們需要通過 open 方法進行創(chuàng)建 DiskLruCache 對象。我們先看到 open 方法的實現(xiàn)
/**
* Opens the cache in {@code directory}, creating a cache if none exists
* there.
*
* @param directory a writable directory
* @param valueCount the number of values per cache entry. Must be positive.
* @param maxSize the maximum number of bytes this cache should use to store
* @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");
}
// If a bkp file exists, use it instead.
// 1
File backupFile = new File(directory, JOURNAL_FILE_BACKUP);
if (backupFile.exists()) {
File journalFile = new File(directory, JOURNAL_FILE);
// If journal file also exists just delete backup file.
if (journalFile.exists()) {
backupFile.delete();
} else {
renameTo(backupFile, journalFile, false);
}
}
// Prefer to pick up where we left off.
// 2
DiskLruCache cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
// 3
if (cache.journalFile.exists()) {
try {
cache.readJournal();
cache.processJournal();
return cache;
} catch (IOException journalIsCorrupt) {
System.out
.println("DiskLruCache "
+ directory
+ " is corrupt: "
+ journalIsCorrupt.getMessage()
+ ", removing");
cache.delete();
}
}
// Create a new empty cache.
// 4
directory.mkdirs();
cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
cache.rebuildJournal();
return cache;
}
首先，可以發(fā)現(xiàn)它需要四個參數(shù)，我們先看看這四個參數(shù)
- directory: 存儲 DiskLruCache 的路徑
- appVersion: 應用的版本號，這里需要版本號因為應用升級緩存會被清除掉
- valueCount: 表示一個 key 可以對應多少個文件，一般傳入 1
- maxSize: 緩存所能存儲的最大字節(jié)數(shù)
之后，我們看到注釋 1 處，它主要的目的是恢復之前的 backup 文件。如果指定目錄下存在 backup 文件，且不存在 journal 文件，則將該 backup 文件改名為 journal 文件。
關于什么是 backup 文件，什么是 journal 文件，我們暫時先不關注，繼續(xù)往下看應該能理解。
我們接著看到注釋 2 處，這里創(chuàng)建了一個 DiskLruCache 對象，此時會為 journalFile、backupFile 等變量進行賦值。
之后在注釋 3 處判斷其對應的 journal 文件是否存在，若存在，則會調(diào)用 cache::readJournal 方法讀取 journal 文件的內(nèi)容，然后會調(diào)用 cache::processJournal 對 journal 文件作出一些處理。這兩個方法我們后面再進行解析。
接著向下看到注釋 4，此處會創(chuàng)建一個新的 DiskLruCache 對象，并且調(diào)用 cache::rebuildJournal 方法創(chuàng)建 journal 臨時文件 journal.tmp 并寫入之前讀取到的數(shù)據(jù)（關于為什么會用到這個臨時文件后面會做介紹），最后將這個新對象返回。
總結下來是這三步：
- 若存在 backup 文件，且不存在 journal 文件，將其恢復為 journal 文件
- 若存在 journal 文件，則嘗試恢復 journal 文件內(nèi)的信息到 DiskLruCache 對象
- 讀取 journal 文件后，會調(diào)用
rebuildJournal方法將讀取并整理后的原 journal 文件內(nèi)容寫入到 journal 臨時文件中。
讀取 journal
下面我們接著看看 cache::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();
// If we ended on a truncated line, rebuild the journal before appending to it.
if (reader.hasUnterminatedLine()) {
rebuildJournal();
} else {
journalWriter = new BufferedWriter(new OutputStreamWriter(
new FileOutputStream(journalFile, true), Util.US_ASCII));
}
} finally {
Util.closeQuietly(reader);
}
}
從上面的代碼可以看到，這里是在用一個作者實現(xiàn)的 StrickLineReader 一行行讀取 journal 文件的內(nèi)容，并給對應數(shù)據(jù)賦值。在對 magic 字段等校驗無誤之后，就會開始循環(huán)調(diào)用 readJournalLine 方法對 journal 文件每一行分別讀取。如果遇到了截斷的行，則調(diào)用 rebuildJournal 在修改前先對 journal 文件進行重建。
journal 文件結構
看來 journal 文件是一種有著特殊規(guī)范的文件，我們可以看看 DiskLruCache 的文件頭注釋，里面有寫清楚這個文件的格式及含義：
/*
* This cache uses a journal file named "journal". A typical journal file
* looks like this:
* 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
*
* The first five lines of the journal form its header. They are the
* constant string "libcore.io.DiskLruCache", the disk cache's version,
* the application's version, the value count, and a blank line.
*
* Each of the subsequent lines in the file is a record of the state of a
* cache entry. Each line contains space-separated values: a state, a key,
* and optional state-specific values.
* o DIRTY lines track that an entry is actively being created or updated.
* Every successful DIRTY action should be followed by a CLEAN or REMOVE
* action. DIRTY lines without a matching CLEAN or REMOVE indicate that
* temporary files may need to be deleted.
* o CLEAN lines track a cache entry that has been successfully published
* and may be read. A publish line is followed by the lengths of each of
* its values.
* o READ lines track accesses for LRU.
* o REMOVE lines track entries that have been deleted.
*
* The journal file is appended to as cache operations occur. The journal may
* occasionally be compacted by dropping redundant lines. A temporary file named
* "journal.tmp" will be used during compaction; that file should be deleted if
* it exists when the cache is opened.
*/
看得出，前五行是 journal 文件的文件頭，它的主要用途是校驗。其中的前面四行分別為 magic 字段（類似 class 文件的 magic number，用于校驗文件類型）、DiskLruCache 版本、 App 版本、 以及 valueCount。
之后第六行開始就是對緩存的 entry 狀態(tài)的記錄，下面是 DIRTY 等關鍵詞的解釋：
- DIRTY: 代表著有一個 entry 正在被寫入。每當我們調(diào)用一次 edit 方法，都會向文件中寫入一條 DIRTY，它往往都是緊跟著一次 CLEAN 或 REMOVE 操作（成功會跟上 CLEAN，失敗會跟上 REMOVE），如果它后面沒有匹配的 CLEAN 或 REMOVE，則說明這個文件不完整，應當被刪除。
- CLEAN: 代表著上一次寫入操作成功執(zhí)行，它后面緊跟著與它對應的每一個 Value 的長度（由于 valueCount 可能不止為 1，因此這里不止一個值）
- READ: 每當對 LRU 的數(shù)據(jù)進行訪問時，都會寫入一條 READ 數(shù)據(jù)，說明有一次讀取的記錄
- REMOVE: 代表了寫入數(shù)據(jù)失敗或手動調(diào)用了 remove 方法，也就是有一個 entry 被移除。
從上面的解釋可以看出，journal 文件其實就是一個表示了 DiskLruCache 的 entry 操作記錄的一個文件。
而這些關鍵詞后面緊跟的，就是 entry 所對應的 key，看它的形式可以猜測是經(jīng)過了某種加密。
讀取 journal 內(nèi)容
接下來我們看看 readJournalLine 方法：
private void readJournalLine(String line) throws IOException {
// 1
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) {
key = line.substring(keyBegin);
if (firstSpace == REMOVE.length() && line.startsWith(REMOVE)) {
lruEntries.remove(key);
return;
}
} else {
key = line.substring(keyBegin, secondSpace);
}
// 2
Entry entry = lruEntries.get(key);
if (entry == null) {
entry = new Entry(key);
lruEntries.put(key, entry);
}
// 3
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);
}
}
我們先看到注釋 1 處，這里是實際上就是通過空格的位置來分隔一行的字符串，同時讀入了 entry 的 key。
之后從注釋 2 處從 lruEntries 這個 Map 中獲取 key 對應的 entry，獲取不到則 new 并傳入 Map。
注釋 3 處開始判斷操作符并對不同操作符進行了不同的處理：
每當遇到 DIRTY，都會創(chuàng)建并設置一個 Editor對象。
之后若遇到 CLEAN，則會讀取它后面的 value 大小，傳入 entry，并取消設置之前的 Editor 對象。
若遇到了 REMOVE 或奇怪的參數(shù)，則拋出異常。
遇到 READ 的情況下，什么都不會做。
讀取 journal 后續(xù)處理
接著我們來看看 processJournal 方法，它主要是做一些讀取后的后續(xù)處理：
/**
* Computes the initial size and collects garbage as a part of opening the
* cache. Dirty entries are assumed to be inconsistent and will be deleted.
*/
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();
}
}
}
我們在之前讀 journal 文件的時候知道，如果 entry 已被成功寫入，則 entry.currentEditor 應當為 null，因此其不為 null 則說明我們的寫入未成功。
寫入成功時，只需要根據(jù)成功的 value 大小從而統(tǒng)計總大小。
寫入失敗時，則會將該 entry 相關的文件進行刪除，并且刪除當前 entry。
journal 重建
初始化階段，最終會調(diào)用 rebuildJournal 方法進行臨時 journal 文件的重建 ，我們下面看看它的實現(xiàn)：
/**
* Creates a new journal that omits redundant information. This replaces the
* current journal if it exists.
*/
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));
}
可以看出，這個方法的主要工作就是對 journal 文件的重建，將 lruEntities 中的數(shù)據(jù)重新寫入創(chuàng)建的 journal 臨時文件，從而去除一些無用的冗余條目。
數(shù)據(jù)寫入&讀取
寫入數(shù)據(jù)我們需要通過 edit 方法，它有兩個實現(xiàn)，最后都會調(diào)用到 edit(key, expectedSequenceNumber) 方法，其中 expectSequenceNumber 默認為 ANY_SEQUENCE_NUMBER。
/**
* Returns an editor for the entry named {@code key}, or null if another
* edit is in progress.
*/
private synchronized Editor edit(String key, long expectedSequenceNumber) throws IOException {
// 1
checkNotClosed();
validateKey(key);
// 2
Entry entry = lruEntries.get(key);
if (expectedSequenceNumber != ANY_SEQUENCE_NUMBER && (entry == null
|| entry.sequenceNumber != expectedSequenceNumber)) {
return null; // Snapshot is stale.
}
if (entry == null) {
entry = new Entry(key);
lruEntries.put(key, entry);
} else if (entry.currentEditor != null) {
return null; // Another edit is in progress.
}
// 3
Editor editor = new Editor(entry);
entry.currentEditor = editor;
// Flush the journal before creating files to prevent file leaks.
journalWriter.write(DIRTY + ' ' + key + '\n');
journalWriter.flush();
return editor;
}
首先在注釋 1 處它通過 checkNotClosed 方法檢查了 cache 文件是否關閉，之后通過 validate 方法對 key 通過正則表達式進行校驗。
之后在注釋 2 處它從 lruEntries 這個 Map 中獲取了對應的 entry，同時對它的 currentEditor 進行了校驗從而保證其并不是處于寫入的狀態(tài)（currentEditor 不為 null 說明正在進行寫入）
這里的 lruEntries 也是一個 LinkedHashMap，可以猜測它也利用了 LinkedHashMap 的 accessOrder 特性。
之后在注釋 3 處，創(chuàng)建了對應的 Editor 并返回，同時向 journal 文件中寫入 DIRTY 表示該 entry 正在進行寫入操作。
Editor
通過前面的代碼可以猜測，真正的寫入/讀取操作是通過 Editor 來完成的，它主要的工作室是經(jīng)過一系列處理后返回 I/O 的 Stream，提供給用戶進行寫入 / 讀取上一次寫入的數(shù)據(jù)。
寫入 newOutputStream
我們首先看到 newOutputStream 方法：
/**
* 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 {
if (index < 0 || index >= valueCount) {
throw new IllegalArgumentException("Expected index " + index + " to "
+ "be greater than 0 and less than the maximum value count "
+ "of " + valueCount);
}
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);
}
}
可以通過此方法傳入 index 獲取到對應 value 的 OutputStream，從而對對應文件進行操作，可以看到它并不是直接創(chuàng)建了一個對目標文件寫入的 OutputStream，而是創(chuàng)建了一個 key.$i.tmp 這一臨時文件（Dirty 文件），之后所有的寫入操作都是在這個臨時文件中進行，不會影響到原本的緩存文件。最后，將其 OutputStream 包裝為一個自定義的忽略錯誤的 OutputStream 后返回。
同時，在這里還做了一件事就是將 entry 的對應 value 標記為 written，也就是已進行了寫入，方便后續(xù)判斷。
讀取 newInputStream
我們接著看看 newInputStream 方法：
/**
* Returns an unbuffered input stream to read the last committed value,
* or null if no value has been committed.
*/
public InputStream newInputStream(int index) throws IOException {
synchronized (DiskLruCache.this) {
if (entry.currentEditor != this) {
throw new IllegalStateException();
}
if (!entry.readable) {
return null;
}
try {
return new FileInputStream(entry.getCleanFile(index));
} catch (FileNotFoundException e) {
return null;
}
}
}
可以通過此方法傳入 index 獲取對應 value 的 InputStream，可以從上面的代碼中看出，它返回的是一個 Clean 文件，也就是寫入成功后的文件。
DiskLruCache 采用的這種臨時文件的設計保證了寫入和讀取之間相互隔離，所有的寫入操作的記錄都是記錄在臨時文件中，而讀取則是讀取寫入成功后的緩存文件。
提交 commit
接著我們看看 commit 方法了解一下提交的流程：
/**
* Commits this edit so it is visible to readers. This releases the
* edit lock so another edit may be started on the same key.
*/
public void commit() throws IOException {
if (hasErrors) {
completeEdit(this, false);
remove(entry.key); // The previous entry is stale.
} else {
completeEdit(this, true);
}
committed = true;
}
有無 error 都會調(diào)用到 commitEdit 方法，當讀取出現(xiàn) error 時，傳入的第二個 boolean 為 false 同時調(diào)用 remove 方法把 entry 刪除。
private synchronized void completeEdit(Editor editor, boolean success) throws IOException {
Entry entry = editor.entry;
if (entry.currentEditor != editor) {
throw new IllegalStateException();
}
// If this edit is creating the entry for the first time, every index must have a value.
// 1
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;
}
}
}
// 2
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);
}
}
// 3
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);
}
}
commitEdit 方法比較長，我們慢慢分析：
在注釋 1 處，如果之前的寫入沒有出現(xiàn)失敗，但 entry 對應的 value 中有還沒有進行過寫入的，就會視為此次寫入失敗，調(diào)用 editor::abort 方法中止本次提交，并寫入 REMOVE。
在注釋 2 處，若之前的臨時文件還存在，并且寫入是成功的，則用這個臨時文件替換掉舊的 journal 文件，并重新計算大小，否則會刪除之前的臨時文件。
在注釋 3 處，若寫入是成功的，則會寫入 CLEAN 到 journal 文件，否則會寫入 REMOVE 到 journal。
而在注釋 4 處，如果當前的緩存大小超過了 maxSize，則會讓 executorService 這個線程池執(zhí)行 cleanupCallable 這一 Callable，我們猜測這個 Callable 就是用來重整空間的。
其中 editor::abort 實現(xiàn)比較簡單，內(nèi)部就是調(diào)用了commitEdit(this, false) 將狀態(tài)切換為錯誤。
空間重整 cleanupCallable
DiskLruCache 的空間重整是一個異步的過程，它的代碼如下：
private final Callable<Void> cleanupCallable = new Callable<Void>() {
public Void call() throws Exception {
synchronized (DiskLruCache.this) {
if (journalWriter == null) {
return null; // Closed.
}
trimToSize();
if (journalRebuildRequired()) {
rebuildJournal();
redundantOpCount = 0;
}
}
return null;
}
};
首先它調(diào)用了 trimToSize 方法將緩存刪除至緩存大小適當?shù)臓顟B(tài)，之后通過 journalRebuildRequired 方法判斷該 journal 需要 rebuild 時，則調(diào)用 rebuildJournal 進行 rebuild。
我們先看看 trimToSize 方法：
private void trimToSize() throws IOException {
while (size > maxSize) {
Map.Entry<String, Entry> toEvict = lruEntries.entrySet().iterator().next();
remove(toEvict.getKey());
}
}
可以看到，它在不斷地刪除 LinkedHashMap 頭部的緩存，從而實現(xiàn) LRU 的效果（和之前的 LruCache 的原理相同，這里不再贅述）
我們接著看看 journalRebuildRequired 方法：
/**
* We only rebuild the journal when it will halve the size of the journal
* and eliminate at least 2000 ops.
*/
private boolean journalRebuildRequired() {
final int redundantOpCompactThreshold = 2000;
return redundantOpCount >= redundantOpCompactThreshold //
&& redundantOpCount >= lruEntries.size();
}
通過上面的注釋就可以看到，只有當冗余的數(shù)據(jù)量超過了 2000 條并且超過了 entry 的個數(shù)時，才需要進行 rebuildJournal 操作。
其實我們在記錄 journal 文件的過程中，每次都會記錄一條 DIRTY 伴隨著一條 CLEAN 或 REMOVE，但操作完成后這些數(shù)據(jù)其實就不再那么重要了，因為我們只需要有 entry 條記錄足夠我們恢復原 entry map 的狀態(tài)即可。而如果每次都將無用的記錄刪除肯定是一種效率的消耗，所以 DiskLruCache 的設計是在這種無用的冗余數(shù)據(jù)超過了 2000 條并且比我們 entry 的個數(shù)還要多時，就調(diào)用 rebuildJounal 進行 journal 的重建從而減小 journal 文件的體積。（想起了 MMKV 也有類似的做法）
總結
DiskLruCache 是一個采用 LinkedHashMap 實現(xiàn)的 LRU 磁盤緩存類，它使用 journal 這種特殊的文件記錄用于記錄每次對緩存的寫入、讀取、刪除等操作的狀態(tài)，而這些對 journal 文件及目標緩存文件的修改都是通過創(chuàng)建一個臨時文件來進行的。這樣可以保證寫入進行的過程中的操作不會影響到已保存的文件，只有寫入完成后才會將該文件替換為原來的文件。
這樣設計的好處我認為有以下幾點：
- 保證了寫入操作的原子性，對 entry 的一次寫入操作，要么成功，要么失敗。
- 實現(xiàn)了寫入和讀取的分離，可以實現(xiàn)寫入和讀取同時進行，且互相不會沖突。
同時，DiskLruCache 在寫入的過程中產(chǎn)生的 journal 文件中的許多數(shù)據(jù)其實是存在冗余的情況的，在讀入 journal 文件及提交寫入時都會對空間進行重整，在不影響緩存數(shù)據(jù)的前提下減小 journal 文件的大小。
