Guava作為Google開源出來的工具庫，Google自己對Guava的描述：The Guava project contains several of Google's core libraries that we rely on in our Java-based projects: collections, caching, primitives support, concurrency libraries, common annotations, string processing, I/O, and so forth.作為Google的core libraries，直接提供Cache實現，足以證明Cache應用的廣泛程度。
然而作為工具庫中的一部分，我們自然不能期待Guava對Cache有比較完善的實現。因而Guava中的Cache只能用于一些把Cache作為一種輔助設計的項目或者在項目的前期為了實現簡單而引入。
在Guava CacheBuilder的注釋中給定Guava Cache以下的需求：
- automatic loading of entries into the cache
- least-recently-used eviction when a maximum size is exceeded
- time-based expiration of entries, measured since last access or last write
- keys automatically wrapped in WeakReference
- values automatically wrapped in WeakReference or SoftReference soft
- notification of evicted (or otherwise removed) entries
- accumulation of cache access statistics
對于這樣的需求，如果要我們自己來實現，我們應該怎么設計？對于我來說，對于其核心實現我會做如下的設計：
- 定義一個CacheConfig類用于紀錄所有的配置，如CacheLoader，maximum size、expire time、key reference level、value reference level、eviction listener等。
- 定義一個Cache接口，該接口類似Map（或ConcurrentMap），但是為了和Map區別開來，因而重新定義一個Cache接口。
- 定義一個實現Cache接口的類CacheImpl，它接收CacheConfig作為參數的構造函數，并將CacheConfig實例保存在字段中。
- 在實現上模仿ConcurrentHashMap的實現方式，有一個Segment數組，其長度由配置的concurrencyLevel值決定。為了實現最近最少使用算法（LRU），添加AccessQueue和WriteQueue字段，這兩個Queue內部采用雙鏈表，每次新創建一個Entry，就將這個Entry加入到這兩個Queue的末尾，而每讀取一個Entry就將其添加到AccessQueue的末尾，沒更新一個Entry將該Entry添加到WriteQueue末尾。為了實現key和value上的WeakReference、SoftReference，添加ReferenceQueue<K>類型的keyReferenceQueue和valueReferenceQueue字段。
- 在每次調用方法之前都遍歷AccessQueue和WriteQueue，如果發現有Entry已經expire，就將該Entry從這兩個Queue上和Cache中移除。然后遍歷keyReferenceQueue和valueReference，如果發現有項存在，同樣將它們移除。在移除時如果有EvictionListener注冊著，則調用該listener。
- 對Segment實現，它時一個CacheEntry數組，CacheEntry是一個鏈節點，它包含hash、key、vlaue、next。CacheEntry根據是否需要包裝在WeakReference中創建WeakEntry或StrongEntry，而對value根據是否需要包裝在WeakReference、SoftReference中創建WeakValueReference、SoftValueReference、StrongValueReference。在get操作中對于需要使用CacheLoader加載的值先添加一個具有LoadingValueReference值的Entry，這樣可以保證同一個Key只加載依次。在加載成功后將LoadingValueReference根據配置替換成其他Weak、Soft、Strong ValueReference。
- 對于cache access statistics，只需要有一個類在需要的地方做一些統計計數即可。
- 最后我必須得承認以上的設計有很多是對Guava Cache的參考，我有點后悔沒有在看源碼之前考慮這個問題，等看過以后思路就被它的實現給羈絆了。。。。
Guava Cache的數據結構
因為新進一家公司，要熟悉新公司項目以及項目用到的第三方庫的代碼，因而幾個月來看了許多代碼。然后越來越發現要理解一個項目的最快方法是先搞清楚該項目的底層數據結構，然后再去看構建于這些數據結構以上的邏輯就會容易許多。記得在還是學生的時候，有在一本書上看到過一個大牛說的一句話：程序＝數據結構＋算法；當時對這句話并不是和理解，現在是很贊同這句話，我對算法接觸的不多，因而我更傾向于將這里的算法理解長控制數據流動的邏輯。因而我們先來熟悉一下Guava Cache的數據結構。
Cache類似于Map，它是存儲鍵值對的集合，然而它和Map不同的是它還需要處理evict、expire、dynamic load等邏輯，需要一些額外信息來實現這些操作。在面向對象思想中，經常使用類對一些關聯性比較強的數據做封裝，同時把操作這些數據相關的操作放到該類中。因而Guava Cache使用ReferenceEntry接口來封裝一個鍵值對，而用ValueReference來封裝Value值。這里之所以用Reference命令，是因為Guava Cache要支持WeakReference Key和SoftReference、WeakReference value。
ValueReference
對于ValueReference，因為Guava Cache支持強引用的Value、SoftReference Value以及WeakReference Value，因而它對應三個實現類：StrongValueReference、SoftValueReference、WeakValueReference。為了支持動態加載機制，它還有一個LoadingValueReference，在需要動態加載一個key的值時，先把該值封裝在LoadingValueReference中，以表達該key對應的值已經在加載了，如果其他線程也要查詢該key對應的值，就能得到該引用，并且等待改值加載完成，從而保證該值只被加載一次（可以在evict以后重新加載）。在該只加載完成后，將LoadingValueReference替換成其他ValueReference類型。對新創建的LoadingValueReference，由于其內部oldValue的初始值是UNSET，它isActive為false，isLoading為false，因而此時的LoadingValueReference的isActive為false，但是isLoading為true。每個ValueReference都紀錄了weight值，所謂weight從字面上理解是“該值的重量”，它由Weighter接口計算而得。weight在Guava Cache中由兩個用途：1. 對weight值為0時，在計算因為size limit而evict是忽略該Entry（它可以通過其他機制evict）；2. 如果設置了maximumWeight值，則當Cache中weight和超過了該值時，就會引起evict操作。但是目前還不知道這個設計的用途。最后，Guava Cache還定義了Stength枚舉類型作為ValueReference的factory類，它有三個枚舉值：Strong、Soft、Weak，這三個枚舉值分別創建各自的ValueReference，并且根據傳入的weight值是否為1而決定是否要創建Weight版本的ValueReference。以下是ValueReference的類圖：
這里ValueReference之所以要有對ReferenceEntry的引用是因為在Value因為WeakReference、SoftReference被回收時，需要使用其key將對應的項從Segment的table中移除；copyFor()函數的存在是因為在expand(rehash)重新創建節點時，對WeakReference、SoftReference需要重新創建實例（個人感覺是為了保持對象狀態不會相互影響，但是不確定是否還有其他原因），而對強引用來說，直接使用原來的值即可，這里很好的展示了對彼變化的封裝思想；notifiyNewValue只用于LoadingValueReference，它的存在是為了對LoadingValueReference來說能更加及時的得到CacheLoader加載的值。
ReferenceEntry
ReferenceEntry是Guava Cache中對一個鍵值對節點的抽象。和ConcurrentHashMap一樣，Guava Cache由多個Segment組成，而每個Segment包含一個ReferenceEntry數組，每個ReferenceEntry數組項都是一條ReferenceEntry鏈。并且一個ReferenceEntry包含key、hash、valueReference、next字段。除了在ReferenceEntry數組項中組成的鏈，在一個Segment中，所有ReferenceEntry還組成access鏈（accessQueue）和write鏈（writeQueue），這兩條都是雙向鏈表，分別通過previousAccess、nextAccess和previousWrite、nextWrite字段鏈接而成。在對每個節點的更新操作都會將該節點重新鏈到write鏈和access鏈末尾，并且更新其writeTime和accessTime字段，而沒找到一個節點，都會將該節點重新鏈到access鏈末尾，并更新其accessTime字段。這兩個雙向鏈表的存在都是為了實現采用最近最少使用算法（LRU）的evict操作（expire、size limit引起的evict）。
Guava Cache中的ReferenceEntry可以是強引用類型的key，也可以WeakReference類型的key，為了減少內存使用量，還可以根據是否配置了expireAfterWrite、expireAfterAccess、maximumSize來決定是否需要write鏈和access鏈確定要創建的具體Reference：StrongEntry、StrongWriteEntry、StrongAccessEntry、StrongWriteAccessEntry等。創建不同類型的ReferenceEntry由其枚舉工廠類EntryFactory來實現，它根據key的Strongth類型、是否使用accessQueue、是否使用writeQueue來決定不同的EntryFactry實例，并通過它創建相應的ReferenceEntry實例。ReferenceEntry類圖如下：
WriteQueue和AccessQueue
為了實現最近最少使用算法，Guava Cache在Segment中添加了兩條鏈：write鏈（writeQueue）和access鏈（accessQueue），這兩條鏈都是一個雙向鏈表，通過ReferenceEntry中的previousInWriteQueue、nextInWriteQueue和previousInAccessQueue、nextInAccessQueue鏈接而成，但是以Queue的形式表達。WriteQueue和AccessQueue都是自定義了offer、add（直接調用offer）、remove、poll等操作的邏輯，對于offer（add）操作，如果是新加的節點，則直接加入到該鏈的結尾，如果是已存在的節點，則將該節點鏈接的鏈尾；對remove操作，直接從該鏈中移除該節點；對poll操作，將頭節點的下一個節點移除，并返回。
static final class WriteQueue<K, V> extends AbstractQueue<ReferenceEntry<K, V>> {
final ReferenceEntry<K, V> head = new AbstractReferenceEntry<K, V>() ....
@Override
public boolean offer(ReferenceEntry<K, V> entry) {
// unlink
connectWriteOrder(entry.getPreviousInWriteQueue(), entry.getNextInWriteQueue());
// add to tail
connectWriteOrder(head.getPreviousInWriteQueue(), entry);
connectWriteOrder(entry, head);
return true;
}
@Override
public ReferenceEntry<K, V> peek() {
ReferenceEntry<K, V> next = head.getNextInWriteQueue();
return (next == head) ? null : next;
}
@Override
public ReferenceEntry<K, V> poll() {
ReferenceEntry<K, V> next = head.getNextInWriteQueue();
if (next == head) {
return null;
}
remove(next);
return next;
}
@Override
public boolean remove(Object o) {
ReferenceEntry<K, V> e = (ReferenceEntry) o;
ReferenceEntry<K, V> previous = e.getPreviousInWriteQueue();
ReferenceEntry<K, V> next = e.getNextInWriteQueue();
connectWriteOrder(previous, next);
nullifyWriteOrder(e);
return next != NullEntry.INSTANCE;
}
@Override
public boolean contains(Object o) {
ReferenceEntry<K, V> e = (ReferenceEntry) o;
return e.getNextInWriteQueue() != NullEntry.INSTANCE;
}
....
}
對于不需要維護WriteQueue和AccessQueue的配置（即沒有expire time或size limit的evict策略）來說，我們可以使用DISCARDING_QUEUE以節省內存：
static final Queue<? extends Object> DISCARDING_QUEUE = new AbstractQueue<Object>() {
@Override
public boolean offer(Object o) {
return true;
}
@Override
public Object peek() {
return null;
}
@Override
public Object poll() {
return null;
}
....
};
Segment中的evict在解決了所有數據結構的問題以后，讓我們來看看LocalCache中的核心類Segment的實現，首先從evict開始。在Guava Cache的evict時機上，它沒有使用另一個后臺線程每隔一段時間掃瞄一次table以evict那些已經expire的entry。而是它在每次操作開始和結束時才做一遍清理工作，這樣可以減少開銷，但是如果長時間不調用方法的話，會引起有些entry不能及時被evict出去。evict主要處理四個Queue：1. keyReferenceQueue；2. valueReferenceQueue；3. writeQueue；4. accessQueue。前兩個queue是因為WeakReference、SoftReference被垃圾回收時加入的，清理時只需要遍歷整個queue，將對應的項從LocalCache中移除即可，這里keyReferenceQueue存放ReferenceEntry，而valueReferenceQueue存放的是ValueReference，要從LocalCache中移除需要有key，因而ValueReference需要有對ReferenceEntry的引用。這里的移除通過LocalCache而不是Segment是因為在移除時因為expand（rehash）可能導致原來在某個Segment中的ReferenceEntry后來被移動到另一個Segment中了。而對后兩個Queue，只需要檢查是否配置了相應的expire時間，然后從頭開始查找已經expire的Entry，將它們移除即可。有不同的是在移除時，還會注冊移除的事件，這些事件將會在接下來的操作調用注冊的RemovalListener觸發，這些代碼比較簡單，不詳述。
在put的時候，還會清理recencyQueue，即將recencyQueue中的Entry添加到accessEntry中，此時可能會發生某個Entry實際上已經被移除了，但是又被添加回accessQueue中了，這種情況下，如果沒有使用WeakReference、SoftReference，也沒有配置expire時間，則會引起一些內存泄漏問題。recencyQueue在get操作時被添加，但是為什么會有這個Queue的存在一直沒有想明白。
Segment中的put操作put操作相對比較簡單，首先它需要獲得鎖，然后嘗試做一些清理工作，接下來的邏輯類似ConcurrentHashMap中的rehash，不詳述。需要說明的是當找到一個已存在的Entry時，需要先判斷當前的ValueRefernece中的值事實上已經被回收了，因為它們可以時WeakReference、SoftReference類型，如果已經被回收了，則將新值寫入。并且在每次更新時注冊當前操作引起的移除事件，指定相應的原因：COLLECTED、REPLACED等，這些注冊的事件在退出的時候統一調用LocalCache注冊的RemovalListener，由于事件處理可能會有很長時間，因而這里將事件處理的邏輯在退出鎖以后才做。最后，在更新已存在的Entry結束后都嘗試著將那些已經expire的Entry移除。另外put操作中還需要更新writeQueue和accessQueue的語義正確性。
V put(K key, int hash, V value, boolean onlyIfAbsent) {
....
for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
K entryKey = e.getKey();
if (e.getHash() == hash && entryKey != null && map.keyEquivalence.equivalent(key, entryKey)) {
ValueReference<K, V> valueReference = e.getValueReference();
V entryValue = valueReference.get();
if (entryValue == null) {
++modCount;
if (valueReference.isActive()) {
enqueueNotification(key, hash, valueReference, RemovalCause.COLLECTED);
setValue(e, key, value, now);
newCount = this.count; // count remains unchanged
} else {
setValue(e, key, value, now);
newCount = this.count + 1;
}
this.count = newCount; // write-volatile
evictEntries();
return null;
} else if (onlyIfAbsent) {
recordLockedRead(e, now);
return entryValue;
} else {
++modCount;
enqueueNotification(key, hash, valueReference, RemovalCause.REPLACED);
setValue(e, key, value, now);
evictEntries();
return entryValue;
}
}
}
...
} finally {
...
postWriteCleanup();
}
}
Segment帶CacheLoader的get操作這部分的代碼有點不知道怎么說了，大概上的步驟是：1. 先查找table中是否已存在沒有被回收、也沒有expire的entry，如果找到，并在CacheBuilder中配置了refreshAfterWrite，并且當前時間間隔已經操作這個事件，則重新加載值，否則，直接返回原有的值；2. 如果查找到的ValueReference是LoadingValueReference，則等待該LoadingValueReference加載結束，并返回加載的值；3. 如果沒有找到entry，或者找到的entry的值為null，則加鎖后，繼續table中已存在key對應的entry，如果找到并且對應的entry.isLoading()為true，則表示有另一個線程正在加載，因而等待那個線程加載完成，如果找到一個非null值，返回該值，否則創建一個LoadingValueReference，并調用loadSync加載相應的值，在加載完成后，將新加載的值更新到table中，即大部分情況下替換原來的LoadingValueReference。
Segment中的其他操作其他操作包括不含CacheLoader的get、containsKey、containsValue、replace等操作邏輯重復性很大，而且和ConcurrentHashMap的實現方式也類似，不在詳述。
Cache StatsCounter和CacheStats為了紀錄Cache的使用情況，如果命中次數、沒有命中次數、evict次數等，Guava Cache中定義了StatsCounter做這些統計信息，它有一個簡單的SimpleStatsCounter實現，我們也可以通過CacheBuilder配置自己的StatsCounter。
public interface StatsCounter {
public void recordHits(int count);
public void recordMisses(int count);
public void recordLoadSuccess(long loadTime);
public void recordLoadException(long loadTime);
public void recordEviction();
public CacheStats snapshot();
}
在得到StatsCounter實例后，可以使用CacheStats獲取具體的統計信息：
public final class CacheStats {
private final long hitCount;
private final long missCount;
private final long loadSuccessCount;
private final long loadExceptionCount;
private final long totalLoadTime;
private final long evictionCount;
}
同ConcurrentHashMap，在知道Segment實現以后，其他的方法基本上都是代理給Segment內部方法，因而在LocalCache類中的其他方法看起來就比較容易理解，不在詳述。然而Guava Cache并沒有將ConcurrentMap直接提供給用戶使用，而是為了區分Cache和Map，它自定義了一個自己的Cache接口和LoadingCache接口，我們可以通過CacheBuilder配置不同的參數，然后使用build()方法返回一個Cache或LoadingCache實例：
public interface Cache<K, V> {
V getIfPresent(Object key);
V get(K key, Callable<? extends V> valueLoader) throws ExecutionException;
ImmutableMap<K, V> getAllPresent(Iterable<?> keys);
void put(K key, V value);
void putAll(Map<? extends K,? extends V> m);
void invalidate(Object key);
void invalidateAll(Iterable<?> keys);
void invalidateAll();
long size();
CacheStats stats();
ConcurrentMap<K, V> asMap();
void cleanUp();
}
public interface LoadingCache<K, V> extends Cache<K, V>, Function<K, V> {
V get(K key) throws ExecutionException;
V getUnchecked(K key);
ImmutableMap<K, V> getAll(Iterable<? extends K> keys) throws ExecutionException;
V apply(K key);
void refresh(K key);
ConcurrentMap<K, V> asMap();
}
posted on 2013-10-20 00:17
DLevin 閱讀(25416)
評論(3) 編輯 收藏 所屬分類:
Guava