Guava Cache缓存机制说明

在日常使用本地缓存的时候，我们经常会选择GuavaCache，使用起来很方便。不过也会有一些疑惑，主要的疑问点有:

• 如何实现的LRU缓存, LFU又是如何实现的
• 单个key失效大量请求会造成雪崩吗
• 失效key的处理是怎么样的
• Cache命中率查看

那么接下来就让我们一起来看看吧。

一切我们从CacheBuilder看起，因为这个类是我们经常用来构建GuavaCache的入口。

public  Cache build() {  
  checkWeightWithWeigher();  
 checkNonLoadingCache();  
 return new LocalCache.LocalManualCache(this);  
}

我们从这里可以看到，build方法是返回了一个LocalCache。

LocalCache是一个ConcurrentMap的实现，也是通过分段Segment和链表进行存储的数据，这里我们不展开。

找到移除的方法com.google.common.cache.LocalCache.Segment#evictEntries，我们一起理解一下。

void evictEntries(ReferenceEntry newest) {  
  if (!map.evictsBySize()) {  
    return;  
 }  
  
  drainRecencyQueue();  
  
 // If the newest entry by itself is too heavy for the segment, don't bother evicting  
 // anything else, just that if (newest.getValueReference().getWeight() > maxSegmentWeight) {  
    if (!removeEntry(newest, newest.getHash(), RemovalCause.SIZE)) {  
      throw new AssertionError();  
 }  
  }  
  
  while (totalWeight > maxSegmentWeight) {  
    ReferenceEntry e = getNextEvictable();  
 if (!removeEntry(e, e.getHash(), RemovalCause.SIZE)) {  
      throw new AssertionError();  
 }  
  }  
}

逻辑说明:

1. 判断设置了最大容量，如果不是的话直接就返回了。
2. 从名称来干，清空可以知晓一二。具体的循环弹出recencyQueue的元素，如果accessQueue包含这个元素，那么就把这个元素添加到accessQueue的末尾。
3. 如果最新添加的这个元素已经超过了maxSegmentWeight，那么就直接移除它。否则继续向下。
4. 获取可移除的元素，进行移除操作，直到totalWeight小于maxSegmentWeight。我们接下来看一下获取的具体代码。

第一步判断适用的maxWeight，在LocalCache的构造函数里可以看到即便我们没有直接设置maxWeight，也会进行com.google.common.cache.CacheBuilder#getMaximumWeight的设置。
第二步中 为什么要先判断accessQueue是否包含呢？
首先我们要看一下accessQueue什么时候会添加元素和删除元素，从代码可以看出来，在write和lockRead的时候会添加，在元素的时候也会删除，所以可以认为这里存储当前现有的元素。而recencyQueue什么时候会添加元素和删除元素呢? 只有在读取的时候com.google.common.cache.LocalCache.Segment#recordRead会添加元素，没有删除元素。 基于这两个点我们就很清楚了，如果缓存失效很快，很容易会出现在recencyQueue但是却已经不属于队列的元素了，所以要先判断是否还有效。但这个数据结构怎么能够支持LRU呢？我们接着往下看。
segmentWeight的初始化公式是long maxSegmentWeight = maxWeight / segmentCount + 1，而这里的totalWeight也是每个segment自己管理的，所以使用了这两个进行比较。

接下来我们来一起看一下getNextEvictable方法:

ReferenceEntry getNextEvictable() {  
  for (ReferenceEntry e : accessQueue) {  
    int weight = e.getValueReference().getWeight();  
 if (weight > 0) {  
      return e;  
 }  
  }  
  throw new AssertionError();  
}

我们看到是在循环accessQueue，如果value的weight大于0，那么就可以被移除。从build的com.google.common.cache.CacheBuilder#getWeigher可以看到，如果不设置，我们会有一个对key设置weight的weigher，默认都是1，所以肯定都可以返回。

但是这里问题就来了，我们前面知道accessQueue会在write的时候添加，并且在drainRecencyQueue的时候还会添加一遍，那么一个元素岂不是可以在这个queue里存在两次，那么移除的也就不是LRU了？

这里其中的奥秘就在于com.google.common.cache.LocalCache.AccessQueue#offer方法。(队列add的方法其实调用的是offer，所以这里覆盖了offer的实现，在调用add的时候就会调到。)

@Override  
public boolean offer(ReferenceEntry entry) {  
  	// unlink  
	connectAccessOrder(entry.getPreviousInAccessQueue(), entry.getNextInAccessQueue());  

	// add to tail  
	connectAccessOrder(head.getPreviousInAccessQueue(), entry);  
	connectAccessOrder(entry, head);  

	return true;
 }

我们从代码上可以看到，首先是将元素从原来的链表里删除，让它的前后两个元素连接在一起，之后再添加到队列，这样就不会出现在一个队列里出现两个元素。这么写的方法有点难理解，我简单画了一个图示意一下，基本就是head的pre指针每次都指向最后一个元素，然后再下次再把新的元素连接到最后。

到这里我们基本就能明白了，LRU的实现。简单来说就是一个先入先出的队列，再遇到一个元素时就把这个元素移动到末尾，原来也很简单。

接下来我们来看一下与它关联性很强，由Caffeine代言的Window-TinyLFU又是如何实现的。

我简单画了一下下面的图总结了一下，里面的实现复杂度还是挺高的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c5cvXaW2-1633494503795)(https://raw.githubusercontent.com/Sutonline/md-img-bed/master/Caffeine%E4%B8%AD%E7%9A%84LFU.png)]

缓存穿透查询，这个对应在Guava中是LoadingCache，所以我们看一下com.google.common.cache.LocalCache#get(K, com.google.common.cache.CacheLoader)方法。

 V get(K key, int hash, CacheLoader loader) throws ExecutionException {
  checkNotNull(key);
  checkNotNull(loader);
  try {
    // count是当前segement中元素的数量
    if (count != 0) { // read-volatile
      // don't call getLiveEntry, which would ignore loading values
      ReferenceEntry e = getEntry(key, hash);
      if (e != null) {
        long now = map.ticker.read();
        V value = getLivevalue(e, now);
        if (value != null) {
          recordRead(e, now);
          statsCounter.recordHits(1);
		  // 判断是否有设置刷新并且已经需要刷新，如果是的话就异步load返回旧值 否则返回新值
          return scheduleRefresh(e, key, hash, value, now, loader);
        }
        ValueReference valueReference = e.getValueReference();
		// 
        if (valueReference.isLoading()) {
          return waitForLoadingValue(e, key, valueReference);
        }
      }
    }

	// 用锁的方式去获取key
    return lockedGetOrLoad(key, hash, loader);
  } catch (ExecutionException ee) {
  ...
}

从这里我们看到了三个去load的场景:

• value不为null，那么按scheduleRefresh的方式去获取
• 否则value正在加载中，那么就waitForLoadingValue方式去获取
• 如果segement中没有存活的元素，那么就按lockedGetOrLoad方式去获取

接下来就让我们分别来看一下这三种都是如何获取的。

if (map.refreshes()  
    && (now - entry.getWriteTime() > map.refreshNanos)  
    && !entry.getValueReference().isLoading()) {  
  V newValue = refresh(key, hash, loader, true);  
 if (newValue != null) {  
    return newValue;  
 }  
}  
return oldValue;

首先判断map是否设置了刷新，此Entry是否需要刷新，此Entry不在loading中，那么就会执行refresh获取。

V refresh(K key, int hash, CacheLoader loader, boolean checkTime) {
  final LoadingValueReference loadingValueReference =
      insertLoadingValueReference(key, hash, checkTime);
  if (loadingValueReference == null) {
    return null;
  }

  ListenableFuture result = loadAsync(key, hash, loadingValueReference, loader);
  if (result.isDone()) {
    try {
      return Uninterruptibles.getUninterruptibly(result);
    } catch (Throwable t) {
      // don't let refresh exceptions propagate; error was already logged
    }
  }
  return null;
}

在refresh的开始就会先锁的方式设置loadingReference，如果发现此时已经其他线程已经开始load了，那么就会返回null。对于scheduleRefresh方法来说就会返回旧值。注意此时loadAsync方法中穿透时使用了线程池。

结论: 不会造成多个穿透，每一个Entry过期后只会有一个线程进行load的状态，其他返回旧值。

前提条件: 如果是当前Entry存在，并且value是null，并且是在加载过程中。我们一起来看一下waitForLoadingValue的具体实现。

V waitForLoadingValue(ReferenceEntry e, K key, ValueReference valueReference)
        throws ExecutionException {
  if (!valueReference.isLoading()) {
    throw new AssertionError();
  }

  checkState(!Thread.holdsLock(e), "Recursive load of: %s", key);
  // don't consider expiration as we're concurrent with loading
  try {
    V value = valueReference.waitForValue();
    if (value == null) {
      throw new InvalidCacheLoadException("CacheLoader returned null for key " + key + ".");
    }
    // re-read ticker now that loading has completed
    long now = map.ticker.read();
    recordRead(e, now);
    return value;
  } finally {
    statsCounter.recordMisses(1);
  }
}

首先判断了不是当前线程在Loading，否则就抛出一个异常，异常信息是递归加载这个key。之所以这么写，还是需要结合getLivevalue一起来分析，在loading的时候会返回null， 所以在loading的线程，按道理肯定不会进入这里，而是会进入到scheduleRefresh或者lockedGetOrLoad。

然后调用valueReference.waitForValue()方法，在这个方法里是等待同一个com.google.common.cache.LocalCache.LoadingValueReference#futurevalue返回。

结论: 如果value正在loading的，会进入循环等待获取之前进入Loading线程返回的值。

前提条件: Entry不存在 或者 Entry存在但是value已经失效。

V lockedGetOrLoad(K key, int hash, CacheLoader loader) throws ExecutionException {
  ReferenceEntry e;
  ValueReference valueReference = null;
  LoadingValueReference loadingValueReference = null;
  boolean createNewEntry = true;

  lock();
  try {

    int newCount = this.count - 1;
    AtomicReferenceArray> table = this.table;
    int index = hash & (table.length() - 1);
    ReferenceEntry first = table.get(index);

    for (e = first; e != null; e = e.getNext()) {
      K entryKey = e.getKey();
      if (e.getHash() == hash
          && entryKey != null
          && map.keyEquivalence.equivalent(key, entryKey)) {
        valueReference = e.getValueReference();

        if (valueReference.isLoading()) {
          createNewEntry = false;
        } else {
          V value = valueReference.get();
          ...
          return value;

          ...
        }
        break;
      }
    }

    if (createNewEntry) {
      loadingValueReference = new LoadingValueReference();

      if (e == null) {
        e = newEntry(key, hash, first);
        e.setValueReference(loadingValueReference);
        table.set(index, e);
      } else {
        e.setValueReference(loadingValueReference);
      }
    }
  } 
  ...

  if (createNewEntry) {
     ...
      synchronized (e) {
        return loadSync(key, hash, loadingValueReference, loader);
      }
    ...
  } else {
    // The entry already exists. Wait for loading.
    return waitForLoadingValue(e, key, valueReference);
  }
}

重点说明:

1. 会先加载，没有获取到锁的就会等待
2. 是否已经在loading中，如果是的话就会等待loading value的返回
3. 否则就会同步加载，返回value

结论: 使用了锁，不会造成单个key不存在多个线程同时load的情况。

看了三个穿透场景，我们就可以下结论了，这里不可能出现单个key需要穿透，而多个线程一起穿透的情况。

但有一点要注意的是，refresh不是按time去refresh的，而是access的时候触发的。

一般来想，我们都会想到失效key是立即就不存在了。但是如果熟悉Redis失效机制的同学就会知道，这个事情并不能每次都做，最好的方式是先逻辑失效再清理空间，guava也采用的是这种方式。关键的代码在com.google.common.cache.LocalCache.Segment#getLiveEntry中。

ReferenceEntry e = getEntry(key, hash);  
 if (e == null) {  
    return null;  
 } else if (map.isExpired(e, now)) {  
    tryExpireEntries(now);  
 return null; 
 }  
  return e;  
}

代码也比较简单，获取这个Entry的时候回判断是否已经失效了，如果是的话就会在不在清理中，如果不在就会进行清理，然后返回null，否则会直接返回null。

当我们想使用一个JVM本地内存优化时，命中率的指标相当关键，根据命中率我们会调整我们设置的最大容量或者失效时间。那么如何能够查看命中率呢？其实也比较简单。我们当时的做法是在在Cache的build过程中开启recordStats，然后将cache放入到集合中，压测的时候通过Controller的方式定时查看。

代码如下:

public baseCache(long maxSize, long duration, TimeUnit timeUtil, ExecutorService executorService)  
{  
    cache = CacheBuilder.newBuilder()  
            .maximumSize(maxSize)  
            .refreshAfterWrite(duration, timeUtil)  
			.recordStats()
            .build(CacheLoader.asyncReloading(new CacheLoader() {  
                @Override  
 public V load(K k) {  
                    return loadData(k);  
 }  
  
            }, executorService));  
  
}

当然这种方式比较low。如果能主动将这些缓存命中的信息，甚至key的信息上报，那么是不是就可以做更多的事情了，现在很多的自我调整缓存就是这样的思路，比如JD-hotkey。