1耍共、 前言
guava cache是Google 出品的 Java 核心增強(qiáng)庫(kù)的緩存部分，有著非常廣泛的應(yīng)用猎塞，有別于ConcurrentHashMap试读，guava cache可以按照多種策略來(lái)清理存儲(chǔ)在其中的緩存值且保持很高的并發(fā)讀寫(xiě)性能。guava cache的設(shè)計(jì)運(yùn)用了LRU算法荠耽，java的設(shè)計(jì)模式钩骇，實(shí)現(xiàn)了緩存數(shù)據(jù)統(tǒng)計(jì)，線程安全等很多功能铝量，本文僅僅從guava cache 線程安全和高并發(fā)性能的角度倘屹，對(duì)guava cache的設(shè)計(jì)哲學(xué)進(jìn)行簡(jiǎn)單分析。為了更好的理解guava cache的緩存設(shè)計(jì)慢叨，我們首先自己設(shè)計(jì)一個(gè)簡(jiǎn)單的線程安全的緩存系統(tǒng)纽匙，然后再看guava cache的相關(guān)源碼并簡(jiǎn)單分析。
2插爹、多階段設(shè)計(jì)線程安全的緩存系統(tǒng)#
假設(shè)公司有一個(gè)“time-honored”的類(lèi)叫ExpensiveCompution哄辣，其通過(guò)一個(gè)方法可以傳入一個(gè)long類(lèi)型的數(shù)字，返回一個(gè)BigDecimal類(lèi)型的數(shù)字赠尾，其代碼如下：
public class ExpensiveCompution {
public BigDecimal compute(Long key) {
BigDecimal along = new BigDecimal(0);
/**
* 利用string計(jì)算出一個(gè)長(zhǎng)整型的數(shù)復(fù)制給along
* 方法比較耗時(shí)間
*/
return along;
}
}
現(xiàn)在公司要求我們?cè)O(shè)計(jì)個(gè)緩存系統(tǒng)來(lái)改善下性能力穗，要求緩存系統(tǒng)線程安全。
第一階段
public class Cache1 {
private final static ExpensiveCompution computer = new ExpensiveCompution();
private final static Map<Long, BigDecimal> map = new HashMap<>();
private Cache1() {
throw new RuntimeException("the Cache1 cannot be instantiated!");
}
public static synchronized BigDecimal compute(long key) {
BigDecimal value = map.get(key);
if (value == null) {
value = computer.compute(key);
map.put(key, value);
}
return value;
大家都可以不加思索的設(shè)計(jì)出這這個(gè)版本气嫁，但是這個(gè)版本在并發(fā)效率上是非常低的当窗，在多線程環(huán)境下，有時(shí)候Cache1類(lèi)反而可能成為累贅寸宵。具體如下圖所示：
圖中淺紅色表示緩存沒(méi)有命中的情況崖面，淺藍(lán)色表示緩存命中的情況元咙。我們假設(shè)線程1，線程2巫员，線程3同時(shí)分別請(qǐng)求對(duì)1,2,3的計(jì)算請(qǐng)求庶香。為了方便，假設(shè)三個(gè)線程獲取鎖的先后順序?yàn)?線程1简识，線程2赶掖，線程3（如無(wú)特殊說(shuō)明，本文都采用這個(gè)假設(shè)）七扰。因?yàn)镃ache1為了保證線程安全性奢赂，其用了synchrnozied關(guān)鍵字。這使得同一時(shí)間只能有一個(gè)線程調(diào)用Cache1.compute方法颈走。如果把cache不能命中時(shí)Cache1.compute方法的執(zhí)行時(shí)間設(shè)為1單位時(shí)間膳灶。cache命中時(shí)從map中取key對(duì)應(yīng)的value值用時(shí)為0.1單位時(shí)間（實(shí)際上用不了這么長(zhǎng)時(shí)間，為了直觀而用了一個(gè)較大的值）立由。取鎖（Lock）和釋放鎖（UnLock）用時(shí)為0.1個(gè)單位時(shí)間（實(shí)際上用時(shí)遠(yuǎn)遠(yuǎn)達(dá)不到0.1單位時(shí)間這么長(zhǎng)轧钓，這里為了直觀而用了一個(gè)較大的時(shí)間單位）。那么三個(gè)線程平均用時(shí)為1.9個(gè)單位時(shí)間(（1.1+（1.1+1.1）+(1.1+1.1+0.2))/3 = 1.9)拆吆。Cache1的引用在某些情況下甚至起到了負(fù)作用聋迎，因?yàn)榧词共挥镁彺嬷苯邮褂肊xpensiveCompution.compute方法，其線程的平均用時(shí)也只有1單位時(shí)間枣耀。這肯定需要改善霉晕。
第二階段
根據(jù)第一階段的分析，我們知道即使像線程3那種緩存命中的情況下，也需要有取鎖和釋放鎖的操作，而這也增加了額外的耗時(shí)搪锣。受啟發(fā)設(shè)計(jì)Cache2類(lèi)如下：
public class Cache2 {
private final static ExpensiveCompution computer = new ExpensiveCompution();
private final static Map<Long, BigDecimal> map = new HashMap<Long, BigDecimal>();
private Cache2() {
throw new RuntimeException("the Cache2 cannot be instantiated!");
}
public static BigDecimal compute(Long key) {
BigDecimal value = map.get(key); //1
if (value == null) {
synchronized(Cache2.class) {
value = map.get(key);
if (value == null) {
value = computer.compute(key);
map.put(key, value); //2
}
}
}
return value;
}
}
Cache2類(lèi)首先在不加鎖的情況下判斷map中是否已有查詢(xún)的key值樱衷，如果存在那么直接返回其對(duì)應(yīng)的value值车胡；如果不存在，其算法和Cache1中的一樣：加鎖，判空，計(jì)算值筏养。這是在單例設(shè)計(jì)模式中很常見(jiàn)的DCL方式（double check lock）。
如果有線程1常拓、線程2渐溶、線程3同時(shí)分別調(diào)用Cache2.compute方法分別計(jì)算1、2弄抬、3對(duì)應(yīng)的返回值茎辐，則每個(gè)線程的平均用時(shí)為1.86（（1.1 + （1.1+1.1）+（1.1+1.1+0.1））/3=1.86)。Cache2較Cache1時(shí)間上還是有一定的優(yōu)化，特別是在高并發(fā)的條件下拖陆，對(duì)于不加鎖的命中緩存情況效果是很可觀的弛槐。但是看過(guò)java內(nèi)存模型這篇文章的朋友應(yīng)該能發(fā)現(xiàn)Cache2有個(gè)線程安全問(wèn)題:線程3，在執(zhí)行 //1處的map.get(key)方法時(shí)依啰，不一定能獲取線程1在 //2 處放到map中的value值乎串，這是可見(jiàn)性問(wèn)題。而如果線程3不能在 //1處拿到值速警，則需要加鎖灌闺，判空，計(jì)算值坏瞄。這樣每個(gè)線程的平均用時(shí)和Cache1的一樣，都是1.9單位時(shí)間甩卓，沒(méi)有任何優(yōu)勢(shì)可言鸠匀。
第三階段
同樣根據(jù)java內(nèi)存模型可知，volatile關(guān)鍵字的設(shè)計(jì)就是為了滿(mǎn)足操作可見(jiàn)性的逾柿。受此啟發(fā)設(shè)計(jì)Cache3類(lèi)如下：
public class Cache3 {
private final static ExpensiveCompution computer = new ExpensiveCompution();
private final static Map<Long, BigDecimal> map = new HashMap<Long, BigDecimal>();
private static volatile long num = 0;
private Cache3() {
throw new RuntimeException("the Cache3 cannot be instantiated!");
}
public static BigDecimal compute(Long key) {
BigDecimal value;
if (num > 0) { //1
value = map.get(key); //2
if (value == null) {
synchronized (Cache3.class) {
value = map.get(key);
if (value == null) {
value = computer.compute(key); //3
map.put(key, value);
num++;
}
}
}
} else {
synchronized (Cache3.class) {
value = map.get(key);
if (value == null) {
value = computer.compute(key);
map.put(key, value);
num++;
}
}
}
return value;
}
}
在Cache3中缀棍，num變量被定義為一個(gè)volatile的變量，//1處的讀volatile變量就是為了觸發(fā)了“volatile的happen-before原則”和“happen-before的傳遞性原則”机错。所以可以保證線程3在//2處一定可以拿到線程1放到map中的value值爬范，從而保證了在Cache3系統(tǒng)中，三個(gè)線程的平均用時(shí)為1.86個(gè)單位時(shí)間弱匪。Cache3的//3處某個(gè)key的具體的value值計(jì)算放在了鎖中青瀑，而這個(gè)計(jì)算時(shí)間是比較長(zhǎng)的（本文中假設(shè)為1時(shí)間單位），這意味著各個(gè)線程將長(zhǎng)時(shí)間持有鎖萧诫，而持有鎖的時(shí)間越長(zhǎng)斥难，線程之間對(duì)鎖的競(jìng)爭(zhēng)就越嚴(yán)重。我們知道多個(gè)線程同時(shí)競(jìng)爭(zhēng)統(tǒng)一把鎖時(shí)只能有一個(gè)勝出者帘饶，而失敗者因拿不到其運(yùn)行的必要資源而從運(yùn)行態(tài)進(jìn)入阻塞態(tài)哑诊，等勝出者釋放鎖以后，失敗者還要從阻塞態(tài)進(jìn)入就緒態(tài)然后重新等待拿鎖及刻，線程各種運(yùn)行態(tài)的切換是需要CPU成本镀裤，而線程長(zhǎng)時(shí)間的持有鎖則增加了這種CPU成本。這是需要改進(jìn)的缴饭。
第四階段
受到第三階段的啟發(fā)暑劝，我們把用時(shí)1時(shí)間單位的compute計(jì)算放在鎖的外面，來(lái)減少線程持有鎖的時(shí)間：
public class Cache4 {
private final static ExpensiveCompution computer = new ExpensiveCompution();
private final static Map<Long, BigDecimal> map = new ConcurrentHashMap<>();
private static volatile long num = 0;
private Cache4() {
throw new RuntimeException("the Cache4 cannot be instantiated!");
}
public static BigDecimal compute(Long key) {
BigDecimal value;
if (num > 0) {
value = map.get(key);
if (value == null) {
synchronized (Cache4.class) { //1
value = map.get(key); //1
} //1
if (value == null) {
value = computer.compute(key); //2
synchronized (Cache4.class) { //3
map.put(key, value); //3
num++; //3
} //3
}
}
} else {
synchronized (Cache4.class) {
value = map.get(key);
}
if (value == null) {
value = computer.compute(key);
synchronized (Cache4.class) {
map.put(key, value);
num++;
}
}
}
return value;
}
}
Cache4的最大持有鎖時(shí)間為0.2個(gè)時(shí)間單位（加鎖的獲取key值和加鎖的存儲(chǔ)key茴扁，其耗時(shí)分別假設(shè)為0.1個(gè)時(shí)間單位）铃岔，這極大的降低了線程對(duì)鎖的競(jìng)爭(zhēng)，從而提高了并發(fā)效率。但是Cache4存在同一個(gè)key值可能重復(fù)計(jì)算的問(wèn)題：
上圖是Cache4的主體結(jié)構(gòu)圖毁习，lockedGet方法代表Cache4中的 //1部分智嚷，compute方法代表Cache4中的 //2部分，lockedSave方法代表Cache4中的 //3部分纺且。如果線程1在計(jì)算key=1時(shí)的value值時(shí)盏道，線程3在圖中0.1到1.1的時(shí)間范圍內(nèi)也開(kāi)始計(jì)算key=1時(shí)的value值，那么線程1和線程3將重復(fù)執(zhí)行 Cache4中的 //2部分载碌。同一個(gè)key值重復(fù)計(jì)算了2次猜嘱，這是和緩存系統(tǒng)設(shè)計(jì)的理念向佐的（同一個(gè)key值，計(jì)算且今計(jì)算一次）嫁艇。這是需要改進(jìn)的朗伶。
第五階段
根據(jù)Cache3和Cache4的分析可知，如果把compute放在鎖中計(jì)算步咪，存在著線程對(duì)鎖的競(jìng)爭(zhēng)嚴(yán)重問(wèn)題而浪費(fèi)CPU資源论皆，而不把compute放在鎖中則存在重復(fù)計(jì)算相同key值的問(wèn)題。有沒(méi)有即讓緩存系統(tǒng)那鎖時(shí)間短猾漫，同時(shí)又不重復(fù)計(jì)算相同key值呢点晴？答案是肯定的，具體見(jiàn)如下類(lèi)Cache5:
public class Cache5 {
private final static ExpensiveCompution computer = new ExpensiveCompution();
private final static Map<Long, FutureTask<BigDecimal>> map = new ConcurrentHashMap<>();
private static volatile long num = 0;
private Cache5() {
throw new RuntimeException("the Cache5 cannot be instantiated!");
}
public static BigDecimal compute(Long key) throws Exception {
FutureTask<BigDecimal> valueTask;
boolean needRun = false; //是否需要?jiǎng)?chuàng)建一個(gè)計(jì)算任務(wù)
if (num > 0) {
valueTask = map.get(key);
if (valueTask == null) {
synchronized (Cache5.class) { //1
valueTask = map.get(key); //1
if (valueTask == null) { //1
valueTask = new FutureTask<>(() -> {
return computer.compute(key);
}); //1
map.put(key, valueTask); //1
needRun = true; //1
num++; //1
}
}
}
if (needRun) {
valueTask.run(); //2 computer.compute 方法此刻開(kāi)始執(zhí)行
}
} else {
synchronized (Cache5.class) {
valueTask = map.get(key);
if (valueTask == null) {
valueTask = new FutureTask<>(() -> {
return computer.compute(key);
});
map.put(key, valueTask);
num++;
needRun = true;
}
}
if (needRun) {
valueTask.run();
}
}
return valueTask.get();
}
}
Cache5用了java concurrent包中的FutureTask類(lèi)悯周，F(xiàn)utureTask代表一個(gè)計(jì)算操作可能正在執(zhí)行粒督，也可能已經(jīng)執(zhí)行完畢，F(xiàn)utureTask的get方法會(huì)在計(jì)算任務(wù)完成后的第一時(shí)間返回計(jì)算結(jié)果禽翼。這樣當(dāng)別的線程從map中通過(guò)指定的key值拿到其對(duì)應(yīng)的FutureTask對(duì)象時(shí)屠橄，那么這個(gè)線程最快的獲取這個(gè)key對(duì)應(yīng)的value值的方式不在是重新創(chuàng)建一個(gè)新的計(jì)算任務(wù)，而是調(diào)用其對(duì)應(yīng)的FutureTask的get方法來(lái)獲取對(duì)應(yīng)的值捐康。
Cache5的主體結(jié)構(gòu)圖如下：
Cache5 的 //1 部分代表圖中的lockedGetOrPut模塊仇矾，//2部分代表圖中的compute模塊。當(dāng)線程3在0.1到1.1的時(shí)間范圍內(nèi)開(kāi)始計(jì)算key=1對(duì)應(yīng)的value值時(shí)解总，其不會(huì)在重新創(chuàng)建一個(gè)對(duì)key=1的計(jì)算任務(wù)贮匕，而是直接調(diào)用FutureTask的get方法。從而避免了對(duì)相同key值的重復(fù)計(jì)算花枫。至此一個(gè)簡(jiǎn)單的線程安全的緩存系統(tǒng)就設(shè)計(jì)完成了刻盐。
3、guava cache線程安全源碼分析
guava cache中我們先看其LoadingCache的get方法源碼的核心是調(diào)用LocalCache內(nèi)部類(lèi)Segement的get方法：
V get(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException {
checkNotNull(key);
checkNotNull(loader);
try {
if (count != 0) { //3 read-volatile
// don't call getLiveEntry, which would ignore loading values
ReferenceEntry<K, V> e = getEntry(key, hash); //1
if (e != null) {
long now = map.ticker.read();
V value = getLiveValue(e, now);
if (value != null) {
recordRead(e, now);
statsCounter.recordHits(1);
return scheduleRefresh(e, key, hash, value, now, loader);
}
ValueReference<K, V> valueReference = e.getValueReference();
if (valueReference.isLoading()) {
return waitForLoadingValue(e, key, valueReference);
}
}
}
// at this point e is either null or expired;
return lockedGetOrLoad(key, hash, loader); //2
} catch (ExecutionException ee) {
Throwable cause = ee.getCause();
if (cause instanceof Error) {
throw new ExecutionError((Error) cause);
} else if (cause instanceof RuntimeException) {
throw new UncheckedExecutionException(cause);
}
throw ee;
} finally {
postReadCleanup();
}
}
代碼中//1處的getEntry方法通過(guò)key值拿到對(duì)應(yīng)的ReferenceEntry對(duì)象劳翰，而這個(gè)對(duì)象中存儲(chǔ)著所需要的value值敦锌，再看最后的//2處的lockedGetOrLoad方法：
V lockedGetOrLoad(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException {
ReferenceEntry<K, V> e;
ValueReference<K, V> valueReference = null;
LoadingValueReference<K, V> loadingValueReference = null;
boolean createNewEntry = true;
lock();
try {
// re-read ticker once inside the lock
long now = map.ticker.read();
preWriteCleanup(now);
int newCount = this.count - 1;
AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table; //1
int index = hash & (table.length() - 1); //1
ReferenceEntry<K, V> first = table.get(index); //1
for (e = first; e != null; e = e.getNext()) { //1
K entryKey = e.getKey(); //1
if (e.getHash() == hash //1
&& entryKey != null //1
&& map.keyEquivalence.equivalent(key, entryKey)) { //1
valueReference = e.getValueReference();
if (valueReference.isLoading()) {
createNewEntry = false;
} else {
V value = valueReference.get();
if (value == null) {
enqueueNotification(
entryKey, hash, value, valueReference.getWeight(), RemovalCause.COLLECTED);
} else if (map.isExpired(e, now)) {
// This is a duplicate check, as preWriteCleanup already purged expired
// entries, but let's accomodate an incorrect expiration queue.
enqueueNotification(
entryKey, hash, value, valueReference.getWeight(), RemovalCause.EXPIRED);
} else {
recordLockedRead(e, now);
statsCounter.recordHits(1);
// we were concurrent with loading; don't consider refresh
return value;
}
// immediately reuse invalid entries
writeQueue.remove(e);
accessQueue.remove(e);
this.count = newCount; // write-volatile
}
break;
}
}
if (createNewEntry) {
loadingValueReference = new LoadingValueReference<K, V>(); //2
if (e == null) { //2
e = newEntry(key, hash, first); //2
e.setValueReference(loadingValueReference); //2
table.set(index, e); //2
} else {
e.setValueReference(loadingValueReference); //2
}
}
} finally {
unlock();
postWriteCleanup();
}
if (createNewEntry) {
try {
// Synchronizes on the entry to allow failing fast when a recursive load is
// detected. This may be circumvented when an entry is copied, but will fail fast most
// of the time.
synchronized (e) {
return loadSync(key, hash, loadingValueReference, loader); //3
}
} finally {
statsCounter.recordMisses(1);
}
} else {
// The entry already exists. Wait for loading.
return waitForLoadingValue(e, key, valueReference);
}
}
lockedGetOrLoad 方法中的 //1 處代碼作用和 Segement.get方法中的getEntry方法的作用是一樣的：通過(guò)key值獲取其對(duì)應(yīng)的ReferenceEntry對(duì)象，不過(guò)這段代碼是在鎖中執(zhí)行的佳簸。再結(jié)合Segement.get方法 //3處的對(duì) volatile變量 count的讀取乙墙，這三處代碼的作用其實(shí)和我們?cè)O(shè)計(jì)的Cache3緩存是一樣的,都是盡可能的減少線程持有鎖的DCL方式颖变。再看lockedGetOrLoad方法的 //2處，其作用和Cache5的 //1處 “valueTask == null”成立后的代碼塊是一樣的听想，都是先在指定的key值處放一個(gè)對(duì)應(yīng)的表示計(jì)算過(guò)程對(duì)象腥刹，只不過(guò)在guava cache中這個(gè)對(duì)象是LoadingValueReference。最后我們看lockedGetOrLoad方法 //3處的loadSync代碼汉买，在這個(gè)方法內(nèi)會(huì)執(zhí)行LoadingValueReference.loadFuture方法：
public ListenableFuture<V> loadFuture(K key, CacheLoader<? super K, V> loader) {
try {
stopwatch.start();
V previousValue = oldValue.get();
if (previousValue == null) {
V newValue = loader.load(key); //1
return set(newValue) ? futureValue : Futures.immediateFuture(newValue);
}
ListenableFuture<V> newValue = loader.reload(key, previousValue);
if (newValue == null) {
return Futures.immediateFuture(null);
}
// To avoid a race, make sure the refreshed value is set into loadingValueReference
// *before* returning newValue from the cache query.
return Futures.transform(
newValue,
new Function<V, V>() {
@Override
public V apply(V newValue) {
LoadingValueReference.this.set(newValue);
return newValue;
}
});
} catch (Throwable t) {
ListenableFuture<V> result = setException(t) ? futureValue : fullyFailedFuture(t);
if (t instanceof InterruptedException) {
Thread.currentThread().interrupt();
}
return result;
}
}
在loadFuture方法的 //1處會(huì)最終調(diào)用我們的在定義guava緩存時(shí)定義的CacheLoader對(duì)象的load方法衔峰。lockedGetOrLoad方法//3處的代碼和Cache5處 //2的代碼作用是一樣的：把真正執(zhí)行計(jì)算key值對(duì)應(yīng)的value值的代碼放在鎖外。這里的鎖是指Segement對(duì)象這個(gè)粗粒度鎖蛙粘。有別于Cache5中任何key值都用同一把鎖（Cache5.class 對(duì)象）垫卤，guava通過(guò)Segement類(lèi)和ReferenceEntry類(lèi)實(shí)現(xiàn)更細(xì)粒度的鎖（具體可參考ConcurrentHashMap設(shè)計(jì)）從而實(shí)現(xiàn)不同key值可能用不同的鎖而提高并發(fā)性。
4出牧、 結(jié)束語(yǔ)
通過(guò)對(duì)guava cache的Segement.get方法和 Segement.lockedGetOrLoad方法的分析穴肘，我們發(fā)現(xiàn)其基本上和Cache5的設(shè)計(jì)理念是大同小異的。當(dāng)然設(shè)計(jì)一個(gè)高效的緩存遠(yuǎn)遠(yuǎn)不止Cache5考慮的那么簡(jiǎn)單舔痕，本文也全當(dāng)拋磚引玉梢褐，希望和大家一起討論guava cache的相關(guān)設(shè)計(jì)哲學(xué)。
