Guava作為Google開(kāi)源出來(lái)的工具庫(kù)，Google自己對(duì)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實(shí)現(xiàn)，足以證明Cache應(yīng)用的廣泛程度。
然而作為工具庫(kù)中的一部分，我們自然不能期待Guava對(duì)Cache有比較完善的實(shí)現(xiàn)。因而Guava中的Cache只能用于一些把Cache作為一種輔助設(shè)計(jì)的項(xiàng)目或者在項(xiàng)目的前期為了實(shí)現(xiàn)簡(jiǎn)單而引入。
在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
對(duì)于這樣的需求，如果要我們自己來(lái)實(shí)現(xiàn)，我們應(yīng)該怎么設(shè)計(jì)？對(duì)于我來(lái)說(shuō)，對(duì)于其核心實(shí)現(xiàn)我會(huì)做如下的設(shè)計(jì)：
- 定義一個(gè)CacheConfig類用于紀(jì)錄所有的配置，如CacheLoader，maximum size、expire time、key reference level、value reference level、eviction listener等。
- 定義一個(gè)Cache接口，該接口類似Map（或ConcurrentMap），但是為了和Map區(qū)別開(kāi)來(lái)，因而重新定義一個(gè)Cache接口。
- 定義一個(gè)實(shí)現(xiàn)Cache接口的類CacheImpl，它接收CacheConfig作為參數(shù)的構(gòu)造函數(shù)，并將CacheConfig實(shí)例保存在字段中。
- 在實(shí)現(xiàn)上模仿ConcurrentHashMap的實(shí)現(xiàn)方式，有一個(gè)Segment數(shù)組，其長(zhǎng)度由配置的concurrencyLevel值決定。為了實(shí)現(xiàn)最近最少使用算法（LRU），添加AccessQueue和WriteQueue字段，這兩個(gè)Queue內(nèi)部采用雙鏈表，每次新創(chuàng)建一個(gè)Entry，就將這個(gè)Entry加入到這兩個(gè)Queue的末尾，而每讀取一個(gè)Entry就將其添加到AccessQueue的末尾，沒(méi)更新一個(gè)Entry將該Entry添加到WriteQueue末尾。為了實(shí)現(xiàn)key和value上的WeakReference、SoftReference，添加ReferenceQueue<K>類型的keyReferenceQueue和valueReferenceQueue字段。
- 在每次調(diào)用方法之前都遍歷AccessQueue和WriteQueue，如果發(fā)現(xiàn)有Entry已經(jīng)expire，就將該Entry從這兩個(gè)Queue上和Cache中移除。然后遍歷keyReferenceQueue和valueReference，如果發(fā)現(xiàn)有項(xiàng)存在，同樣將它們移除。在移除時(shí)如果有EvictionListener注冊(cè)著，則調(diào)用該listener。
- 對(duì)Segment實(shí)現(xiàn)，它時(shí)一個(gè)CacheEntry數(shù)組，CacheEntry是一個(gè)鏈節(jié)點(diǎn)，它包含hash、key、vlaue、next。CacheEntry根據(jù)是否需要包裝在WeakReference中創(chuàng)建WeakEntry或StrongEntry，而對(duì)value根據(jù)是否需要包裝在WeakReference、SoftReference中創(chuàng)建WeakValueReference、SoftValueReference、StrongValueReference。在get操作中對(duì)于需要使用CacheLoader加載的值先添加一個(gè)具有LoadingValueReference值的Entry，這樣可以保證同一個(gè)Key只加載依次。在加載成功后將LoadingValueReference根據(jù)配置替換成其他Weak、Soft、Strong ValueReference。
- 對(duì)于cache access statistics，只需要有一個(gè)類在需要的地方做一些統(tǒng)計(jì)計(jì)數(shù)即可。
- 最后我必須得承認(rèn)以上的設(shè)計(jì)有很多是對(duì)Guava Cache的參考，我有點(diǎn)后悔沒(méi)有在看源碼之前考慮這個(gè)問(wèn)題，等看過(guò)以后思路就被它的實(shí)現(xiàn)給羈絆了。。。。
Guava Cache的數(shù)據(jù)結(jié)構(gòu)
因?yàn)樾逻M(jìn)一家公司，要熟悉新公司項(xiàng)目以及項(xiàng)目用到的第三方庫(kù)的代碼，因而幾個(gè)月來(lái)看了許多代碼。然后越來(lái)越發(fā)現(xiàn)要理解一個(gè)項(xiàng)目的最快方法是先搞清楚該項(xiàng)目的底層數(shù)據(jù)結(jié)構(gòu)，然后再去看構(gòu)建于這些數(shù)據(jù)結(jié)構(gòu)以上的邏輯就會(huì)容易許多。記得在還是學(xué)生的時(shí)候，有在一本書(shū)上看到過(guò)一個(gè)大牛說(shuō)的一句話：程序＝數(shù)據(jù)結(jié)構(gòu)＋算法；當(dāng)時(shí)對(duì)這句話并不是和理解，現(xiàn)在是很贊同這句話，我對(duì)算法接觸的不多，因而我更傾向于將這里的算法理解長(zhǎng)控制數(shù)據(jù)流動(dòng)的邏輯。因而我們先來(lái)熟悉一下Guava Cache的數(shù)據(jù)結(jié)構(gòu)。
Cache類似于Map，它是存儲(chǔ)鍵值對(duì)的集合，然而它和Map不同的是它還需要處理evict、expire、dynamic load等邏輯，需要一些額外信息來(lái)實(shí)現(xiàn)這些操作。在面向?qū)ο笏枷胫校?jīng)常使用類對(duì)一些關(guān)聯(lián)性比較強(qiáng)的數(shù)據(jù)做封裝，同時(shí)把操作這些數(shù)據(jù)相關(guān)的操作放到該類中。因而Guava Cache使用ReferenceEntry接口來(lái)封裝一個(gè)鍵值對(duì)，而用ValueReference來(lái)封裝Value值。這里之所以用Reference命令，是因?yàn)镚uava Cache要支持WeakReference Key和SoftReference、WeakReference value。
ValueReference
對(duì)于ValueReference，因?yàn)镚uava Cache支持強(qiáng)引用的Value、SoftReference Value以及WeakReference Value，因而它對(duì)應(yīng)三個(gè)實(shí)現(xiàn)類：StrongValueReference、SoftValueReference、WeakValueReference。為了支持動(dòng)態(tài)加載機(jī)制，它還有一個(gè)LoadingValueReference，在需要?jiǎng)討B(tài)加載一個(gè)key的值時(shí)，先把該值封裝在LoadingValueReference中，以表達(dá)該key對(duì)應(yīng)的值已經(jīng)在加載了，如果其他線程也要查詢?cè)搆ey對(duì)應(yīng)的值，就能得到該引用，并且等待改值加載完成，從而保證該值只被加載一次（可以在evict以后重新加載）。在該只加載完成后，將LoadingValueReference替換成其他ValueReference類型。對(duì)新創(chuàng)建的LoadingValueReference，由于其內(nèi)部oldValue的初始值是UNSET，它isActive為false，isLoading為false，因而此時(shí)的LoadingValueReference的isActive為false，但是isLoading為true。每個(gè)ValueReference都紀(jì)錄了weight值，所謂weight從字面上理解是“該值的重量”，它由Weighter接口計(jì)算而得。weight在Guava Cache中由兩個(gè)用途：1. 對(duì)weight值為0時(shí)，在計(jì)算因?yàn)閟ize limit而evict是忽略該Entry（它可以通過(guò)其他機(jī)制evict）；2. 如果設(shè)置了maximumWeight值，則當(dāng)Cache中weight和超過(guò)了該值時(shí)，就會(huì)引起evict操作。但是目前還不知道這個(gè)設(shè)計(jì)的用途。最后，Guava Cache還定義了Stength枚舉類型作為ValueReference的factory類，它有三個(gè)枚舉值：Strong、Soft、Weak，這三個(gè)枚舉值分別創(chuàng)建各自的ValueReference，并且根據(jù)傳入的weight值是否為1而決定是否要?jiǎng)?chuàng)建Weight版本的ValueReference。以下是ValueReference的類圖：
這里ValueReference之所以要有對(duì)ReferenceEntry的引用是因?yàn)樵赩alue因?yàn)閃eakReference、SoftReference被回收時(shí)，需要使用其key將對(duì)應(yīng)的項(xiàng)從Segment的table中移除；copyFor()函數(shù)的存在是因?yàn)樵趀xpand(rehash)重新創(chuàng)建節(jié)點(diǎn)時(shí)，對(duì)WeakReference、SoftReference需要重新創(chuàng)建實(shí)例（個(gè)人感覺(jué)是為了保持對(duì)象狀態(tài)不會(huì)相互影響，但是不確定是否還有其他原因），而對(duì)強(qiáng)引用來(lái)說(shuō)，直接使用原來(lái)的值即可，這里很好的展示了對(duì)彼變化的封裝思想；notifiyNewValue只用于LoadingValueReference，它的存在是為了對(duì)LoadingValueReference來(lái)說(shuō)能更加及時(shí)的得到CacheLoader加載的值。
ReferenceEntry
ReferenceEntry是Guava Cache中對(duì)一個(gè)鍵值對(duì)節(jié)點(diǎn)的抽象。和ConcurrentHashMap一樣，Guava Cache由多個(gè)Segment組成，而每個(gè)Segment包含一個(gè)ReferenceEntry數(shù)組，每個(gè)ReferenceEntry數(shù)組項(xiàng)都是一條ReferenceEntry鏈。并且一個(gè)ReferenceEntry包含key、hash、valueReference、next字段。除了在ReferenceEntry數(shù)組項(xiàng)中組成的鏈，在一個(gè)Segment中，所有ReferenceEntry還組成access鏈（accessQueue）和write鏈（writeQueue），這兩條都是雙向鏈表，分別通過(guò)previousAccess、nextAccess和previousWrite、nextWrite字段鏈接而成。在對(duì)每個(gè)節(jié)點(diǎn)的更新操作都會(huì)將該節(jié)點(diǎn)重新鏈到write鏈和access鏈末尾，并且更新其writeTime和accessTime字段，而沒(méi)找到一個(gè)節(jié)點(diǎn)，都會(huì)將該節(jié)點(diǎn)重新鏈到access鏈末尾，并更新其accessTime字段。這兩個(gè)雙向鏈表的存在都是為了實(shí)現(xiàn)采用最近最少使用算法（LRU）的evict操作（expire、size limit引起的evict）。
Guava Cache中的ReferenceEntry可以是強(qiáng)引用類型的key，也可以WeakReference類型的key，為了減少內(nèi)存使用量，還可以根據(jù)是否配置了expireAfterWrite、expireAfterAccess、maximumSize來(lái)決定是否需要write鏈和access鏈確定要?jiǎng)?chuàng)建的具體Reference：StrongEntry、StrongWriteEntry、StrongAccessEntry、StrongWriteAccessEntry等。創(chuàng)建不同類型的ReferenceEntry由其枚舉工廠類EntryFactory來(lái)實(shí)現(xiàn)，它根據(jù)key的Strongth類型、是否使用accessQueue、是否使用writeQueue來(lái)決定不同的EntryFactry實(shí)例，并通過(guò)它創(chuàng)建相應(yīng)的ReferenceEntry實(shí)例。ReferenceEntry類圖如下：
WriteQueue和AccessQueue
為了實(shí)現(xiàn)最近最少使用算法，Guava Cache在Segment中添加了兩條鏈：write鏈（writeQueue）和access鏈（accessQueue），這兩條鏈都是一個(gè)雙向鏈表，通過(guò)ReferenceEntry中的previousInWriteQueue、nextInWriteQueue和previousInAccessQueue、nextInAccessQueue鏈接而成，但是以Queue的形式表達(dá)。WriteQueue和AccessQueue都是自定義了offer、add（直接調(diào)用offer）、remove、poll等操作的邏輯，對(duì)于offer（add）操作，如果是新加的節(jié)點(diǎn)，則直接加入到該鏈的結(jié)尾，如果是已存在的節(jié)點(diǎn)，則將該節(jié)點(diǎn)鏈接的鏈尾；對(duì)remove操作，直接從該鏈中移除該節(jié)點(diǎn)；對(duì)poll操作，將頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)移除，并返回。
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;
}
....
}
對(duì)于不需要維護(hù)WriteQueue和AccessQueue的配置（即沒(méi)有expire time或size limit的evict策略）來(lái)說(shuō)，我們可以使用DISCARDING_QUEUE以節(jié)省內(nèi)存：
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在解決了所有數(shù)據(jù)結(jié)構(gòu)的問(wèn)題以后，讓我們來(lái)看看LocalCache中的核心類Segment的實(shí)現(xiàn)，首先從evict開(kāi)始。在Guava Cache的evict時(shí)機(jī)上，它沒(méi)有使用另一個(gè)后臺(tái)線程每隔一段時(shí)間掃瞄一次table以evict那些已經(jīng)expire的entry。而是它在每次操作開(kāi)始和結(jié)束時(shí)才做一遍清理工作，這樣可以減少開(kāi)銷，但是如果長(zhǎng)時(shí)間不調(diào)用方法的話，會(huì)引起有些entry不能及時(shí)被evict出去。evict主要處理四個(gè)Queue：1. keyReferenceQueue；2. valueReferenceQueue；3. writeQueue；4. accessQueue。前兩個(gè)queue是因?yàn)閃eakReference、SoftReference被垃圾回收時(shí)加入的，清理時(shí)只需要遍歷整個(gè)queue，將對(duì)應(yīng)的項(xiàng)從LocalCache中移除即可，這里keyReferenceQueue存放ReferenceEntry，而valueReferenceQueue存放的是ValueReference，要從LocalCache中移除需要有key，因而ValueReference需要有對(duì)ReferenceEntry的引用。這里的移除通過(guò)LocalCache而不是Segment是因?yàn)樵谝瞥龝r(shí)因?yàn)閑xpand（rehash）可能導(dǎo)致原來(lái)在某個(gè)Segment中的ReferenceEntry后來(lái)被移動(dòng)到另一個(gè)Segment中了。而對(duì)后兩個(gè)Queue，只需要檢查是否配置了相應(yīng)的expire時(shí)間，然后從頭開(kāi)始查找已經(jīng)expire的Entry，將它們移除即可。有不同的是在移除時(shí)，還會(huì)注冊(cè)移除的事件，這些事件將會(huì)在接下來(lái)的操作調(diào)用注冊(cè)的RemovalListener觸發(fā)，這些代碼比較簡(jiǎn)單，不詳述。
在put的時(shí)候，還會(huì)清理recencyQueue，即將recencyQueue中的Entry添加到accessEntry中，此時(shí)可能會(huì)發(fā)生某個(gè)Entry實(shí)際上已經(jīng)被移除了，但是又被添加回accessQueue中了，這種情況下，如果沒(méi)有使用WeakReference、SoftReference，也沒(méi)有配置expire時(shí)間，則會(huì)引起一些內(nèi)存泄漏問(wèn)題。recencyQueue在get操作時(shí)被添加，但是為什么會(huì)有這個(gè)Queue的存在一直沒(méi)有想明白。
Segment中的put操作put操作相對(duì)比較簡(jiǎn)單，首先它需要獲得鎖，然后嘗試做一些清理工作，接下來(lái)的邏輯類似ConcurrentHashMap中的rehash，不詳述。需要說(shuō)明的是當(dāng)找到一個(gè)已存在的Entry時(shí)，需要先判斷當(dāng)前的ValueRefernece中的值事實(shí)上已經(jīng)被回收了，因?yàn)樗鼈兛梢詴r(shí)WeakReference、SoftReference類型，如果已經(jīng)被回收了，則將新值寫(xiě)入。并且在每次更新時(shí)注冊(cè)當(dāng)前操作引起的移除事件，指定相應(yīng)的原因：COLLECTED、REPLACED等，這些注冊(cè)的事件在退出的時(shí)候統(tǒng)一調(diào)用LocalCache注冊(cè)的RemovalListener，由于事件處理可能會(huì)有很長(zhǎng)時(shí)間，因而這里將事件處理的邏輯在退出鎖以后才做。最后，在更新已存在的Entry結(jié)束后都嘗試著將那些已經(jīng)expire的Entry移除。另外put操作中還需要更新writeQueue和accessQueue的語(yǔ)義正確性。
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操作這部分的代碼有點(diǎn)不知道怎么說(shuō)了，大概上的步驟是：1. 先查找table中是否已存在沒(méi)有被回收、也沒(méi)有expire的entry，如果找到，并在CacheBuilder中配置了refreshAfterWrite，并且當(dāng)前時(shí)間間隔已經(jīng)操作這個(gè)事件，則重新加載值，否則，直接返回原有的值；2. 如果查找到的ValueReference是LoadingValueReference，則等待該LoadingValueReference加載結(jié)束，并返回加載的值；3. 如果沒(méi)有找到entry，或者找到的entry的值為null，則加鎖后，繼續(xù)table中已存在key對(duì)應(yīng)的entry，如果找到并且對(duì)應(yīng)的entry.isLoading()為true，則表示有另一個(gè)線程正在加載，因而等待那個(gè)線程加載完成，如果找到一個(gè)非null值，返回該值，否則創(chuàng)建一個(gè)LoadingValueReference，并調(diào)用loadSync加載相應(yīng)的值，在加載完成后，將新加載的值更新到table中，即大部分情況下替換原來(lái)的LoadingValueReference。
Segment中的其他操作其他操作包括不含CacheLoader的get、containsKey、containsValue、replace等操作邏輯重復(fù)性很大，而且和ConcurrentHashMap的實(shí)現(xiàn)方式也類似，不在詳述。
Cache StatsCounter和CacheStats為了紀(jì)錄Cache的使用情況，如果命中次數(shù)、沒(méi)有命中次數(shù)、evict次數(shù)等，Guava Cache中定義了StatsCounter做這些統(tǒng)計(jì)信息，它有一個(gè)簡(jiǎn)單的SimpleStatsCounter實(shí)現(xiàn)，我們也可以通過(guò)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實(shí)例后，可以使用CacheStats獲取具體的統(tǒng)計(jì)信息：
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實(shí)現(xiàn)以后，其他的方法基本上都是代理給Segment內(nèi)部方法，因而在LocalCache類中的其他方法看起來(lái)就比較容易理解，不在詳述。然而Guava Cache并沒(méi)有將ConcurrentMap直接提供給用戶使用，而是為了區(qū)分Cache和Map，它自定義了一個(gè)自己的Cache接口和LoadingCache接口，我們可以通過(guò)CacheBuilder配置不同的參數(shù)，然后使用build()方法返回一個(gè)Cache或LoadingCache實(shí)例：
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 閱讀(25414)
評(píng)論(3) 編輯 收藏 所屬分類:
Guava