2. Guava

public interface Cache<K, V> {
    V getIfPresent(@CompatibleWith("K") Object key);
    V get(K key, Callable<? extends V> loader) throws ExecutionException;
    ImmutableMap<K, V> getAllPresent(Iterable<?> keys);
    void put(K key, V value);
    void putAll(Map<? extends K, ? extends V> m);
    void invalidate(@CompatibleWith("K") 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;

  @Deprecated
  @Override
  V apply(K key);

  void refresh(K key);
  
  @Override
  ConcurrentMap<K, V> asMap();
}

//创建一个LoadingCache，并可以进行一些简单的缓存配置
private static LoadingCache<String, String > loadingCache = CacheBuilder.newBuilder()
            //最大容量为100（基于容量进行回收）
            .maximumSize(100)
            //配置写入后多久使缓存过期-下文会讲述
            .expireAfterWrite(150, TimeUnit.SECONDS)
            //配置写入后多久刷新缓存-下文会讲述
            .refreshAfterWrite(1, TimeUnit.SECONDS)
            //key使用弱引用-WeakReference
            .weakKeys()
            //当Entry被移除时的监听器
            .removalListener(notification -> log.info("notification={}", GsonUtil.toJson(notification)))
            //创建一个CacheLoader，重写load方法，以实现"当get时缓存不存在，则load，放到缓存，并返回"的效果
            .build(new CacheLoader<String, String>() {
                // 重点，自动写缓存数据的方法，必须要实现
                @Override
                public String load(String key) throws Exception {
                    return "value_" + key;
                }
                // 异步刷新缓存-下文会讲述
                @Override
                public ListenableFuture<String> reload(String key, String oldValue) throws Exception {
                    return super.reload(key, oldValue);
                }
            });

@Test
public void getTest() throws Exception {
    //测试例子，调用其get方法，cache会自动加载并返回
    String value = loadingCache.get("1");
    //返回value_1
    log.info("value={}", value);
}

@Test
public void callableTest() throws Exception {
    String key = "1";
    //loadingCache的定义跟上一面一样
    //get时定义一个Callable
    String value = loadingCache.get(key, new Callable<String>() {
        @Override
        public String call() throws Exception {
            return "call_" + key;
        }
    });
    log.info("call value={}", value);
}

@RequestMapping(value = "/get")
public Person get(int id) throws ExecutionException {
    Person person = cache.get(id, () -> {
        log.info("get person from db,id={}", id);
        return getFromDB(id);
    });
    return person;
}

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
        .maximumWeight(100000)
        .weigher(new Weigher<Key, Graph>() {
            public int weigh(Key k, Graph g) {
                return g.vertices().size();
            }
        })
        .build(
            new CacheLoader<Key, Graph>() {
                public Graph load(Key key) { // no checked exception
                    return createExpensiveGraph(key);
                }
            });

CacheBuilder.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES) // 写入10分钟后过期
    .build();

// java8后可以使用Duration设置
CacheBuilder.newBuilder()
    .expireAfterWrite(Duration.ofMinutes(10))
    .build();

CacheBuilder.newBuilder()
    .expireAfterAccess(10, TimeUnit.MINUTES) //在10分钟内未访问则过期
    .build();

// java8后可以使用Duration设置
CacheBuilder.newBuilder()
    .expireAfterAccess(Duration.ofMinutes(10))
    .build();

CacheBuilder.newBuilder() 
  .weakKeys() // 使用弱引用存储键。当键没有其它（强或软）引用时，该缓存可能会被回收。 
  .weakValues() // 使用弱引用存储值。当值没有其它（强或软）引用时，该缓存可能会被回收。 
  .softValues() // 使用软引用存储值。当内存不足并且该值没有被其它强引用引用时，该缓存就会被回收 
  .build();

// 构建一个缓存 
Cache<String, String> cache = CacheBuilder.newBuilder().build(); 

// 淘汰key为k1的缓存 
cache.invalidate("k1"); 

// 批量淘汰key为k1、k2的缓存 
List<String> invalidateKeys = new ArrayList<>(); 
invalidateKeys.add("k1"); 
invalidateKeys.add("k2"); 
cache.invalidateAll(invalidateKeys); 

// 淘汰所有缓存 
cache.invalidateAll();

//有些键不需要刷新，并且我们希望刷新是异步完成的
LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
        .maximumSize(1000)
        .refreshAfterWrite(1, TimeUnit.MINUTES)
        .build(
            new CacheLoader<Key, Graph>() {
                public Graph load(Key key) { // no checked exception
                    return getGraphFromDatabase(key);
                }

                public ListenableFuture<Key, Graph> reload(final Key key, Graph prevGraph) {
                    if (neverNeedsRefresh(key)) {
                        return Futures.immediateFuture(prevGraph);
                    }else{
                        // asynchronous!
                        ListenableFutureTask<Key, Graph> task=ListenableFutureTask.create(new Callable<Key, Graph>() {
                            public Graph call() {
                                return getGraphFromDatabase(key);
                            }
                        });
                        executor.execute(task);
                        return task;
                    }
                }
            });

//Map的数组
final Segment<K, V>[] segments;
//并发量，即segments数组的大小
final int concurrencyLevel;
//key的比较策略，跟key的引用类型有关
final Equivalence<Object> keyEquivalence;
//value的比较策略，跟value的引用类型有关
final Equivalence<Object> valueEquivalence;
//key的强度，即引用类型的强弱
final Strength keyStrength;
//value的强度，即引用类型的强弱
final Strength valueStrength;
//访问后的过期时间，设置了expireAfterAccess就有
final long expireAfterAccessNanos;
//写入后的过期时间，设置了expireAfterWrite就有
final long expireAfterWriteNanos;
//刷新时间，设置了refreshAfterWrite就有
final long refreshNanos;
//removal的事件队列，缓存过期后先放到该队列
final Queue<RemovalNotification<K, V>> removalNotificationQueue;
//设置的removalListener
final RemovalListener<K, V> removalListener;
//时间器
final Ticker ticker;
//创建Entry的工厂，根据引用类型不同
final EntryFactory entryFactory;

static class Segment<K, V> extends ReentrantLock

//LocalCache
final LocalCache<K, V> map;
//segment存放元素的数量
volatile int count;
//修改、更新的数量，用来做弱一致性
int modCount;
//扩容用
int threshold;
//segment维护的数组，用来存放Entry。这里使用AtomicReferenceArray是因为要用CAS来保证原子性
volatile @MonotonicNonNull AtomicReferenceArray<ReferenceEntry<K, V>> table;
//如果key是弱引用的话，那么被GC回收后，就会放到ReferenceQueue，要根据这个queue做一些清理工作
final @Nullable ReferenceQueue<K> keyReferenceQueue;
//跟上同理
final @Nullable ReferenceQueue<V> valueReferenceQueue;
//如果一个元素新写入，则会记到这个队列的尾部，用来做expire
@GuardedBy("this")
final Queue<ReferenceEntry<K, V>> writeQueue;
//读、写都会放到这个队列，用来进行LRU替换算法
@GuardedBy("this")
final Queue<ReferenceEntry<K, V>> accessQueue;
//记录哪些entry被访问，用于accessQueue的更新。
final Queue<ReferenceEntry<K, V>> recencyQueue;

final K key;
final int hash;
//指向下一个Entry，说明这里用的链表（从上图可以看出）
final @Nullable ReferenceEntry<K, V> next;
//value
volatile ValueReference<K, V> valueReference = unset();

//LocalLoadingCache的get方法，直接调用LocalCache
public V get(K key) throws ExecutionException {
      return localCache.getOrLoad(key);
    }

V getOrLoad(K key) throws ExecutionException {
    return get(key, defaultLoader);
  }

V get(K key, CacheLoader<? super K, V> loader) throws ExecutionException {
    //根据key获取hash值
    int hash = hash(checkNotNull(key));
    //通过hash定位到是哪个Segment，然后是Segment的get方法
    return segmentFor(hash).get(key, hash, loader);
  }

V get(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException {
      checkNotNull(key);
      checkNotNull(loader);
      try {
        //这里是进行快速判断，如果count != 0则说明呀已经有数据
        if (count != 0) {
          //根据hash定位到table的第一个Entry
          ReferenceEntry<K, V> e = getEntry(key, hash);
          if (e != null) {
            //跟currentTimeMillis类似
            long now = map.ticker.read();
            //获取还没过期的value，如果过期了，则返回null。getLiveValue下面展开
            V value = getLiveValue(e, now);
            //Entry还没过期
            if (value != null) {
              //记录被访问过
              recordRead(e, now);
              //命中率统计
              statsCounter.recordHits(1);
              //判断是否需要刷新，如果需要刷新，那么会去异步刷新，且返回旧值。scheduleRefresh下面展开
              return scheduleRefresh(e, key, hash, value, now, loader);
            }
            
            ValueReference<K, V> valueReference = e.getValueReference();
            /* 如果entry过期了且数据还在加载中，则等待直到加载完成。这里的ValueReference是LoadingValueReference，
             * 其waitForValue方法是调用内部的Future的get方法，具体读者可以点进去看。
             */
            if (valueReference.isLoading()) {
              return waitForLoadingValue(e, key, valueReference);
            }
          }
        }
        
        //重点方法。lockedGetOrLoad下面展开
        //走到这一步表示: 之前没有写入过数据 || 数据已经过期 || 数据不是在加载中。
        return lockedGetOrLoad(key, hash, loader);
      } 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();
      }
    }

    //getLiveValue
    V getLiveValue(ReferenceEntry<K, V> entry, long now) {
      //被GC回收了
      if (entry.getKey() == null) {
        //
        tryDrainReferenceQueues();
        return null;
      }
      V value = entry.getValueReference().get();
      //被GC回收了
      if (value == null) {
        tryDrainReferenceQueues();
        return null;
      }
      //判断是否过期
      if (map.isExpired(entry, now)) {
        tryExpireEntries(now);
        return null;
      }
      return value;
    }

    //isExpired，判断Entry是否过期
    boolean isExpired(ReferenceEntry<K, V> entry, long now) {
      checkNotNull(entry);
      //如果配置了expireAfterAccess，用当前时间跟entry的accessTime比较
      if (expiresAfterAccess() && (now - entry.getAccessTime() >= expireAfterAccessNanos)) {
        return true;
      }
      //如果配置了expireAfterWrite，用当前时间跟entry的writeTime比较
      if (expiresAfterWrite() && (now - entry.getWriteTime() >= expireAfterWriteNanos)) {
        return true;
      }
      return false;
    }

 V scheduleRefresh(
      ReferenceEntry<K, V> entry,
      K key,
      int hash,
      V oldValue,
      long now,
      CacheLoader<? super K, V> loader) {
    //1、是否配置了refreshAfterWrite
    //2、用writeTime判断是否达到刷新的时间
    //3、是否在加载中，如果是则没必要再进行刷新
    if (map.refreshes()
        && (now - entry.getWriteTime() > map.refreshNanos)
        && !entry.getValueReference().isLoading()) {
      //异步刷新数据。refresh下面展开
      V newValue = refresh(key, hash, loader, true);
      //返回新值
      if (newValue != null) {
        return newValue;
      }
    }
    //否则返回旧值
    return oldValue;
  }

//refresh
V refresh(K key, int hash, CacheLoader<? super K, V> loader, boolean checkTime) {
    //为key插入一个LoadingValueReference，实质是把对应Entry的ValueReference替换为新建的LoadingValueReference。insertLoadingValueReference下面展开
    final LoadingValueReference<K, V> loadingValueReference =
        insertLoadingValueReference(key, hash, checkTime);
    if (loadingValueReference == null) {
      return null;
    }
    //通过loader异步加载数据，这里返回的是Future。loadAsync下面展开
    ListenableFuture<V> result = loadAsync(key, hash, loadingValueReference, loader);
    //这里立即判断Future是否已经完成，如果是则返回结果。否则返回null。因为是可能返回immediateFuture或者ListenableFuture。
    //这里的官方注释是: Returns the newly refreshed value associated with key if it was refreshed inline, or null if another thread is performing the refresh or if an error occurs during
    if (result.isDone()) {
      try {
        return Uninterruptibles.getUninterruptibly(result);
      } catch (Throwable t) {
        // don't let refresh exceptions propagate; error was already logged
      }
    }
    return null;
  }

//insertLoadingValueReference方法。
  //这个方法虽然看上去有点长，但其实挺简单的，如果你熟悉HashMap的话。
LoadingValueReference<K, V> insertLoadingValueReference(
      final K key, final int hash, boolean checkTime) {
    ReferenceEntry<K, V> e = null;
    //把segment上锁
    lock();
    try {
      long now = map.ticker.read();
      //做一些清理工作
      preWriteCleanup(now);

      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);
      
      //如果key对应的entry存在
      for (e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        //通过key定位到entry
        if (e.getHash() == hash
            && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          
          ValueReference<K, V> valueReference = e.getValueReference();
          //如果是在加载中，或者还没达到刷新时间，则返回null
          //这里对这个判断再进行了一次，我认为是上锁lock了，再重新获取now，对时间的判断更加准确
          if (valueReference.isLoading()
              || (checkTime && (now - e.getWriteTime() < map.refreshNanos))) {

            return null;
          }
          
          //new一个LoadingValueReference，然后把entry的valueReference替换掉。
          ++modCount;
          LoadingValueReference<K, V> loadingValueReference =
              new LoadingValueReference<>(valueReference);
          e.setValueReference(loadingValueReference);
          return loadingValueReference;
        }
      }
      
      ////如果key对应的entry不存在，则新建一个Entry，操作跟上面一样。
      ++modCount;
      LoadingValueReference<K, V> loadingValueReference = new LoadingValueReference<>();
      e = newEntry(key, hash, first);
      e.setValueReference(loadingValueReference);
      table.set(index, e);
      return loadingValueReference;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }

//loadAsync
ListenableFuture<V> loadAsync(
      final K key,
      final int hash,
      final LoadingValueReference<K, V> loadingValueReference,
      CacheLoader<? super K, V> loader) {
    //通过loadFuture返回ListenableFuture。loadFuture下面展开
    final ListenableFuture<V> loadingFuture = loadingValueReference.loadFuture(key, loader);
    //对ListenableFuture添加listener，当数据加载完后的后续处理。
    loadingFuture.addListener(
        new Runnable() {
          @Override
          public void run() {
            try {
              //这里主要是把newValue set到entry中。还涉及其他一系列操作，读者可自行阅读。
              getAndRecordStats(key, hash, loadingValueReference, loadingFuture);
            } catch (Throwable t) {
              logger.log(Level.WARNING, "Exception thrown during refresh", t);
              loadingValueReference.setException(t);
            }
          }
        },
        directExecutor());
    return loadingFuture;
  }

//loadFuture
public ListenableFuture<V> loadFuture(K key, CacheLoader<? super K, V> loader) {
    try {
      stopwatch.start();
      //这个oldValue指的是插入LoadingValueReference之前的ValueReference，如果entry是新的，那么oldValue就是unset，即get返回null。
      V previousValue = oldValue.get();
      //这里要注意***
      //如果上一个value为null，则调用loader的load方法，这个load方法是同步的。
      //这里需要使用同步加载的原因是，在上面的“缓存失效机制”也说了，即使用异步，但是还没有oldValue也是没用的。如果在系统启动时来高并发请求的话，那么所有的请求都会阻塞，所以给热点数据预加热是很有必要的。
      if (previousValue == null) {
        V newValue = loader.load(key);
        return set(newValue) ? futureValue : Futures.immediateFuture(newValue);
      }
      //否则，使用reload进行异步加载
      ListenableFuture<V> newValue = loader.reload(key, previousValue);
      if (newValue == null) {
        return Futures.immediateFuture(null);
      }
      
      return transform(
          newValue,
          new com.google.common.base.Function<V, V>() {
            @Override
            public V apply(V newValue) {
              LoadingValueReference.this.set(newValue);
              return newValue;
            }
          },
          directExecutor());
    } catch (Throwable t) {
      ListenableFuture<V> result = setException(t) ? futureValue : fullyFailedFuture(t);
      if (t instanceof InterruptedException) {
        Thread.currentThread().interrupt();
      }
      return result;
    }
  }

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;
    //用来判断是否需要创建一个新的Entry
    boolean createNewEntry = true;
    //segment上锁
    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;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      //通过key定位entry
      for (e = first; e != null; e = e.getNext()) {
        K entryKey = e.getKey();
        if (e.getHash() == hash
            && entryKey != null
            && map.keyEquivalence.equivalent(key, entryKey)) {
          //找到entry
          valueReference = e.getValueReference();
          //如果value在加载中则不需要重复创建entry
          if (valueReference.isLoading()) {
            createNewEntry = false;
          } else {
            V value = valueReference.get();
            //value为null说明已经过期且被清理掉了
            if (value == null) {
              //写通知queue
              enqueueNotification(
                  entryKey, hash, value, valueReference.getWeight(), RemovalCause.COLLECTED);
            //过期但还没被清理
            } else if (map.isExpired(e, now)) {
              //写通知queue
              // This is a duplicate check, as preWriteCleanup already purged expired
              // entries, but let's accommodate an incorrect expiration queue.
              enqueueNotification(
                  entryKey, hash, value, valueReference.getWeight(), RemovalCause.EXPIRED);
            } else {
              recordLockedRead(e, now);
              statsCounter.recordHits(1);
              /* 其他情况则直接返回value
               * 来到这步，是不是觉得有点奇怪，我们分析一下: 
               * 进入lockedGetOrLoad方法的条件是数据已经过期 || 数据不是在加载中，但是在lock之前都有可能发生并发，
               * 进而改变entry的状态，所以在上面中再次判断了isLoading和isExpired。所以来到这步说明，
               * 原来数据是过期的且在加载中，lock的前一刻加载完成了，到了这步就有值了。
               */
              return value;
            }
            
            writeQueue.remove(e);
            accessQueue.remove(e);
            this.count = newCount; // write-volatile
          }
          break;
        }
      }
      //创建一个Entry，且set一个新的LoadingValueReference。
      if (createNewEntry) {
        loadingValueReference = new LoadingValueReference<>();

        if (e == null) {
          e = newEntry(key, hash, first);
          e.setValueReference(loadingValueReference);
          table.set(index, e);
        } else {
          e.setValueReference(loadingValueReference);
        }
      }
    } finally {
      unlock();
      postWriteCleanup();
    }
  // 同步加载数据。里面的方法都是在上面有提及过的，读者可自行阅读。
    if (createNewEntry) {
      try {
        synchronized (e) {
          return loadSync(key, hash, loadingValueReference, loader);
        }
      } finally {
        statsCounter.recordMisses(1);
      }
    } else {
      // The entry already exists. Wait for loading.
      return waitForLoadingValue(e, key, valueReference);
    }
  }

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    //Segment上锁
    lock();
    try {
      long now = map.ticker.read();
      preWriteCleanup(now);

      int newCount = this.count + 1;
      if (newCount > this.threshold) { // ensure capacity
        expand();
        newCount = this.count + 1;
      }

      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
      int index = hash & (table.length() - 1);
      ReferenceEntry<K, V> first = table.get(index);

      //根据key找entry
      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)) {

          //定位到entry
          ValueReference<K, V> valueReference = e.getValueReference();
          V entryValue = valueReference.get();
          //value为null说明entry已经过期且被回收或清理掉
          if (entryValue == null) {
            ++modCount;
            if (valueReference.isActive()) {
              enqueueNotification(
                  key, hash, entryValue, valueReference.getWeight(), 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(e);
            return null;
          } else if (onlyIfAbsent) {
            //如果是onlyIfAbsent选项则返回旧值
            recordLockedRead(e, now);
            return entryValue;
          } else {
            //不是onlyIfAbsent，设值
            ++modCount;
            enqueueNotification(
                key, hash, entryValue, valueReference.getWeight(), RemovalCause.REPLACED);
            setValue(e, key, value, now);
            evictEntries(e);
            return entryValue;
          }
        }
      }
      
      //没有找到entry，则新建一个Entry并设值
      ++modCount;
      ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
      setValue(newEntry, key, value, now);
      table.set(index, newEntry);
      newCount = this.count + 1;
      this.count = newCount; // write-volatile
      evictEntries(newEntry);
      return null;
    } finally {
      unlock();
      postWriteCleanup();
    }
  }