1、 前言
guava cache是Google 出品的 Java 核心增强库的缓存部分，有着非常广泛的应用，有别于ConcurrentHashMap，guava cache可以按照多种策略来清理存储在其中的缓存值且保持很高的并发读写性能。guava cache的设计运用了LRU算法，java的设计模式，实现了缓存数据统计，线程安全等很多功能，本文仅仅从guava cache 线程安全和高并发性能的角度，对guava cache的设计哲学进行简单分析。为了更好的理解guava cache的缓存设计，我们首先自己设计一个简单的线程安全的缓存系统，然后再看guava cache的相关源码并简单分析。
2、多阶段设计线程安全的缓存系统#
假设公司有一个“time-honored”的类叫ExpensiveCompution，其通过一个方法可以传入一个long类型的数字，返回一个BigDecimal类型的数字，其代码如下：
public class ExpensiveCompution {
public BigDecimal compute(Long key) {
BigDecimal along = new BigDecimal(0);
/**
* 利用string计算出一个长整型的数复制给along
* 方法比较耗时间
*/
return along;
}
}
现在公司要求我们设计个缓存系统来改善下性能，要求缓存系统线程安全。
第一阶段
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;
大家都可以不加思索的设计出这这个版本，但是这个版本在并发效率上是非常低的，在多线程环境下，有时候Cache1类反而可能成为累赘。具体如下图所示：
图中浅红色表示缓存没有命中的情况，浅蓝色表示缓存命中的情况。我们假设线程1，线程2，线程3同时分别请求对1,2,3的计算请求。为了方便，假设三个线程获取锁的先后顺序为 线程1，线程2，线程3（如无特殊说明，本文都采用这个假设）。因为Cache1为了保证线程安全性，其用了synchrnozied关键字。这使得同一时间只能有一个线程调用Cache1.compute方法。如果把cache不能命中时Cache1.compute方法的执行时间设为1单位时间。cache命中时从map中取key对应的value值用时为0.1单位时间（实际上用不了这么长时间，为了直观而用了一个较大的值）。取锁（Lock）和释放锁（UnLock）用时为0.1个单位时间（实际上用时远远达不到0.1单位时间这么长，这里为了直观而用了一个较大的时间单位）。那么三个线程平均用时为1.9个单位时间(（1.1+（1.1+1.1）+(1.1+1.1+0.2))/3 = 1.9)。Cache1的引用在某些情况下甚至起到了负作用，因为即使不用缓存直接使用ExpensiveCompution.compute方法，其线程的平均用时也只有1单位时间。这肯定需要改善。
第二阶段
根据第一阶段的分析，我们知道即使像线程3那种缓存命中的情况下，也需要有取锁和释放锁的操作，而这也增加了额外的耗时。受启发设计Cache2类如下：
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类首先在不加锁的情况下判断map中是否已有查询的key值，如果存在那么直接返回其对应的value值；如果不存在，其算法和Cache1中的一样：加锁，判空，计算值。这是在单例设计模式中很常见的DCL方式（double check lock）。
如果有线程1、线程2、线程3同时分别调用Cache2.compute方法分别计算1、2、3对应的返回值，则每个线程的平均用时为1.86（（1.1 + （1.1+1.1）+（1.1+1.1+0.1））/3=1.86)。Cache2较Cache1时间上还是有一定的优化，特别是在高并发的条件下，对于不加锁的命中缓存情况效果是很可观的。但是看过java内存模型这篇文章的朋友应该能发现Cache2有个线程安全问题:线程3，在执行 //1处的map.get(key)方法时，不一定能获取线程1在 //2 处放到map中的value值，这是可见性问题。而如果线程3不能在 //1处拿到值，则需要加锁，判空，计算值。这样每个线程的平均用时和Cache1的一样，都是1.9单位时间，没有任何优势可言。
第三阶段
同样根据java内存模型可知，volatile关键字的设计就是为了满足操作可见性的。受此启发设计Cache3类如下：
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变量被定义为一个volatile的变量，//1处的读volatile变量就是为了触发了“volatile的happen-before原则”和“happen-before的传递性原则”。所以可以保证线程3在//2处一定可以拿到线程1放到map中的value值，从而保证了在Cache3系统中，三个线程的平均用时为1.86个单位时间。Cache3的//3处某个key的具体的value值计算放在了锁中，而这个计算时间是比较长的（本文中假设为1时间单位），这意味着各个线程将长时间持有锁，而持有锁的时间越长，线程之间对锁的竞争就越严重。我们知道多个线程同时竞争统一把锁时只能有一个胜出者，而失败者因拿不到其运行的必要资源而从运行态进入阻塞态，等胜出者释放锁以后，失败者还要从阻塞态进入就绪态然后重新等待拿锁，线程各种运行态的切换是需要CPU成本，而线程长时间的持有锁则增加了这种CPU成本。这是需要改进的。
第四阶段
受到第三阶段的启发，我们把用时1时间单位的compute计算放在锁的外面，来减少线程持有锁的时间：
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的最大持有锁时间为0.2个时间单位（加锁的获取key值和加锁的存储key，其耗时分别假设为0.1个时间单位），这极大的降低了线程对锁的竞争，从而提高了并发效率。但是Cache4存在同一个key值可能重复计算的问题：
上图是Cache4的主体结构图，lockedGet方法代表Cache4中的 //1部分，compute方法代表Cache4中的 //2部分，lockedSave方法代表Cache4中的 //3部分。如果线程1在计算key=1时的value值时，线程3在图中0.1到1.1的时间范围内也开始计算key=1时的value值，那么线程1和线程3将重复执行 Cache4中的 //2部分。同一个key值重复计算了2次，这是和缓存系统设计的理念向佐的（同一个key值，计算且今计算一次）。这是需要改进的。
第五阶段
根据Cache3和Cache4的分析可知，如果把compute放在锁中计算，存在着线程对锁的竞争严重问题而浪费CPU资源，而不把compute放在锁中则存在重复计算相同key值的问题。有没有即让缓存系统那锁时间短，同时又不重复计算相同key值呢？答案是肯定的，具体见如下类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; //是否需要创建一个计算任务
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 方法此刻开始执行
}
} 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类，FutureTask代表一个计算操作可能正在执行，也可能已经执行完毕，FutureTask的get方法会在计算任务完成后的第一时间返回计算结果。这样当别的线程从map中通过指定的key值拿到其对应的FutureTask对象时，那么这个线程最快的获取这个key对应的value值的方式不在是重新创建一个新的计算任务，而是调用其对应的FutureTask的get方法来获取对应的值。
Cache5的主体结构图如下：
Cache5 的 //1 部分代表图中的lockedGetOrPut模块，//2部分代表图中的compute模块。当线程3在0.1到1.1的时间范围内开始计算key=1对应的value值时，其不会在重新创建一个对key=1的计算任务，而是直接调用FutureTask的get方法。从而避免了对相同key值的重复计算。至此一个简单的线程安全的缓存系统就设计完成了。
3、guava cache线程安全源码分析
guava cache中我们先看其LoadingCache的get方法源码的核心是调用LocalCache内部类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方法通过key值拿到对应的ReferenceEntry对象，而这个对象中存储着所需要的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方法的作用是一样的：通过key值获取其对应的ReferenceEntry对象，不过这段代码是在锁中执行的。再结合Segement.get方法 //3处的对 volatile变量 count的读取，这三处代码的作用其实和我们设计的Cache3缓存是一样的,都是尽可能的减少线程持有锁的DCL方式。再看lockedGetOrLoad方法的 //2处，其作用和Cache5的 //1处 “valueTask == null”成立后的代码块是一样的，都是先在指定的key值处放一个对应的表示计算过程对象，只不过在guava cache中这个对象是LoadingValueReference。最后我们看lockedGetOrLoad方法 //3处的loadSync代码，在这个方法内会执行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处会最终调用我们的在定义guava缓存时定义的CacheLoader对象的load方法。lockedGetOrLoad方法//3处的代码和Cache5处 //2的代码作用是一样的：把真正执行计算key值对应的value值的代码放在锁外。这里的锁是指Segement对象这个粗粒度锁。有别于Cache5中任何key值都用同一把锁（Cache5.class 对象），guava通过Segement类和ReferenceEntry类实现更细粒度的锁（具体可参考ConcurrentHashMap设计）从而实现不同key值可能用不同的锁而提高并发性。
4、 结束语
通过对guava cache的Segement.get方法和 Segement.lockedGetOrLoad方法的分析，我们发现其基本上和Cache5的设计理念是大同小异的。当然设计一个高效的缓存远远不止Cache5考虑的那么简单，本文也全当抛砖引玉，希望和大家一起讨论guava cache的相关设计哲学。
