Guava Cache

[diaosichengxuyuan]

基本介绍

Guava Cache与ConcurrentMap很相似，但也不完全一样。最基本的区别是ConcurrentMap会一直保存所有添加的元素，直到显式地移除。相对地，Guava Cache为了限制内存占用，通常都设定为自动回收元素。在某些场景下，尽管LoadingCache 不回收元素，它也是很有用的，因为它会自动加载缓存。
Guava Cache是在内存中缓存数据，相比较于数据库或redis存储，访问内存中的数据会更加高效。

Guava官网介绍，下面的这几种情况可以考虑使用Guava Cache：
(1)愿意消耗一些内存空间来提升速度。
(2)预料到某些键会被多次查询。
(3)缓存中存放的数据总量不会超出内存容量。
所以，可以将程序频繁用到的少量数据存储到Guava Cache中，以改善程序性能。

数据结构

Guava Cache的数据结构与ConcurrentHashMap1.6的结构类似，采用了分段锁的机制，不同的Segment可以并发修改，每个Segment中保存一个Entry table和两个队列，table用来存储数据，两个队列用来实现LRU淘汰策略。

用法

   /**
     * expireAfterWrite
     */
    private void test1() throws Exception {
        Cache<String, Object> cache = CacheBuilder.newBuilder().maximumSize(1000).expireAfterWrite(5, TimeUnit.SECONDS)
            .build();
        cache.put("1", 10);
        cache.put("2", 20);
        cache.put("3", 30);
        cache.put("4", 40);

        TimeUnit.SECONDS.sleep(4);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));

        TimeUnit.SECONDS.sleep(4);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));
    }

    /**
     * expireAfterAccess
     */
    private void test2() throws Exception {
        Cache<String, Object> cache = CacheBuilder.newBuilder().maximumSize(1000).expireAfterAccess(5, TimeUnit.SECONDS)
            .build();
        cache.put("1", 10);
        cache.put("2", 20);
        cache.put("3", 30);
        cache.put("4", 40);

        TimeUnit.SECONDS.sleep(4);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));

        TimeUnit.SECONDS.sleep(4);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));
    }

    /**
     * load
     */
    private void test3() throws Exception {
        LoadingCache<String, Object> cache = CacheBuilder.newBuilder().maximumSize(1000).expireAfterWrite(5,
            TimeUnit.SECONDS).build(new CacheLoader<String, Object>() {
            @Override
            public Object load(String key) throws Exception {
                if("1".equals(key)) {
                    return 100;
                } else if("2".equals(key)) {
                    return 200;
                } else if("3".equals(key)) {
                    return 300;
                } else if("4".equals(key)) {
                    return 400;
                }
                return null;
            }
        });

        cache.put("1", 10);
        cache.put("2", 20);
        cache.put("3", 30);
        cache.put("4", 40);

        TimeUnit.SECONDS.sleep(5);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));

        System.out.println(cache.get("1"));
        System.out.println(cache.get("2"));
        System.out.println(cache.get("3"));
        System.out.println(cache.get("4"));
    }

    /**
     * maximumSize 通过AccessQueue进行LRU淘汰
     */
    private void test4() throws Exception {
        Cache<String, Object> cache = CacheBuilder.newBuilder().maximumSize(3).build();
        cache.put("1", 10);
        cache.put("2", 20);
        //2->1->3->4
        System.out.println(cache.getIfPresent("1"));
        cache.put("3", 30);
        cache.put("4", 40);

        System.out.println();
        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));
    }

    /**
     * weakValues
     */
    private void test5() throws Exception {
        Cache<String, Object> cache = CacheBuilder.newBuilder().maximumSize(1000).expireAfterAccess(1000,
            TimeUnit.SECONDS).weakValues().build();
        cache.put("1", new Integer(10));
        cache.put("2", new Integer(20));
        cache.put("3", new Integer(30));
        cache.put("4", new Integer(40));

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));

        System.gc();

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));
    }

    /**
     * weakKeys
     */
    private void test6() throws Exception {
        Cache<Object, Object> cache = CacheBuilder.newBuilder().maximumSize(1000).expireAfterAccess(1000,
            TimeUnit.SECONDS).weakKeys().build();
        cache.put(new Integer(1), new Integer(10));
        cache.put(new Integer(2), new Integer(20));
        cache.put(new Integer(3), new Integer(30));
        cache.put(new Integer(4), new Integer(40));

        //weakKeys和weakValues是通过==来判断是否相等，而不是通过equals
        System.out.println(cache.getIfPresent(new Integer(1)));
        System.out.println(cache.getIfPresent(new Integer(2)));
        System.out.println(cache.getIfPresent(new Integer(3)));
        System.out.println(cache.getIfPresent(new Integer(4)));

        Integer integer1 = new Integer(1);
        Integer integer2 = new Integer(2);
        Integer integer3 = new Integer(3);
        Integer integer4 = new Integer(4);
        cache = CacheBuilder.newBuilder().maximumSize(1000).expireAfterAccess(1000, TimeUnit.SECONDS).weakKeys()
            .build();
        cache.put(integer1, new Integer(10));
        cache.put(integer2, new Integer(20));
        cache.put(integer3, new Integer(30));
        cache.put(integer4, new Integer(40));

        //weakKeys和weakValues是通过==来判断是否相等，而不是通过equals
        System.out.println(cache.getIfPresent(integer1));
        System.out.println(cache.getIfPresent(integer2));
        System.out.println(cache.getIfPresent(integer3));
        System.out.println(cache.getIfPresent(integer4));

        integer1 = null;
        integer2 = null;
        integer3 = null;
        integer4 = null;
        System.gc();

        //weakKeys和weakValues是通过==来判断是否相等，而不是通过equals
        try {
            System.out.println(cache.getIfPresent(integer1));
        } catch(Exception e) {
            System.out.println(e.getMessage());
        }
        try {
            System.out.println(cache.getIfPresent(integer2));
        } catch(Exception e) {
            System.out.println(e.getMessage());
        }
        try {
            System.out.println(cache.getIfPresent(integer3));
        } catch(Exception e) {
            System.out.println(e.getMessage());
        }
        try {
            System.out.println(cache.getIfPresent(integer4));
        } catch(Exception e) {
            System.out.println(e.getMessage());
        }
    }

    /**
     * removalListener 只有在手动删除或者超过容量删除时才会通知，过期删除不会通知
     */
    private void test7() throws Exception {
        Cache<String, Object> cache = CacheBuilder.newBuilder().maximumSize(10000).expireAfterWrite(5, TimeUnit.SECONDS)
            .removalListener(new RemovalListener<String, Object>() {
                public void onRemoval(RemovalNotification<String, Object> notification) {
                    System.out.println(notification);
                }
            }).build();
        cache.put("1", 10);
        cache.put("2", 20);
        cache.put("3", 30);
        cache.put("4", 40);

        cache.invalidate("4");

        TimeUnit.SECONDS.sleep(5);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));
    }

    /**
     * recordStats
     */
    private void test8() throws Exception {
        Cache<String, Object> cache = CacheBuilder.newBuilder().maximumSize(1000).expireAfterWrite(5, TimeUnit.SECONDS)
            .recordStats().build();
        cache.put("1", 10);
        cache.put("2", 20);
        cache.put("3", 30);
        cache.put("4", 40);

        TimeUnit.SECONDS.sleep(4);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));

        TimeUnit.SECONDS.sleep(4);

        System.out.println(cache.getIfPresent("1"));
        System.out.println(cache.getIfPresent("2"));
        System.out.println(cache.getIfPresent("3"));
        System.out.println(cache.getIfPresent("4"));

        System.out.println(cache.stats());
    }

源码分析

Guava Cache的核心代码主要在com.google.common.cache.LocalCache类中

1.Reference
jdk中的Reference ReferenceQueue ReferenceHandler可以用来监控垃圾回收中的某些过程，在guava中用到的比较多

  static class SoftValueReference<K, V> extends SoftReference<V> implements ValueReference<K, V> {
    final ReferenceEntry<K, V> entry;

    SoftValueReference(ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry) {
      super(referent, queue);
      this.entry = entry;
    }
  }

  static class WeakValueReference<K, V> extends WeakReference<V> implements ValueReference<K, V> {
    final ReferenceEntry<K, V> entry;

    WeakValueReference(ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry) {
      super(referent, queue);
      this.entry = entry;
    }
  }

2.Segment

static class Segment<K, V> extends ReentrantLock {
	volatile int count;
	int modCount;
	int threshold;

	//AtomicReferenceArray是可以完成CAS操作的数组，并发编程中用的比较多
	volatile  AtomicReferenceArray<ReferenceEntry<K, V>> table;

	//用来实现LRU的写队列
	final Queue<ReferenceEntry<K, V>> writeQueue;
	//用来实现LRU的访问队列
	final Queue<ReferenceEntry<K, V>> accessQueue;

	//key的Reference回收时的通知队列
	final ReferenceQueue<K> keyReferenceQueue;
	//value的Reference回收时的通知队列
	final ReferenceQueue<V> valueReferenceQueue;
}

3.put

  public V put(K key, V value) {
    //判空
    checkNotNull(key);
    checkNotNull(value);
    //计算hash值
    int hash = hash(key);
    //求得segment位置，执行put
    return segmentFor(hash).put(key, hash, value, false);
  }

  
  V put(K key, int hash, V value, boolean onlyIfAbsent) {
      //加锁
      lock();
      try {
        //当前时间
        long now = map.ticker.read();

        //清理，如果table或者队列中的元素过期，就清理掉
        preWriteCleanup(now);

        //元素个数+1
        int newCount = this.count + 1;
        if (newCount > this.threshold) {
          //超过扩容阈值，进行扩容
          expand();
          newCount = this.count + 1;
        }

        //在segment的table中计算此Entry所处的位置，用first取出
        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
        int index = hash & (table.length() - 1);
        ReferenceEntry<K, V> first = table.get(index);

        //如果此位置不为空，则沿着链表进行查找
        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
          K entryKey = e.getKey();

          //如果key值相同，需要覆盖；如果不相同，进行下次循环
          if (e.getHash() == hash
              && entryKey != null
              && map.keyEquivalence.equivalent(key, entryKey)) {

            ValueReference<K, V> valueReference = e.getValueReference();
            V entryValue = valueReference.get();
            
            //如果value==null，cache一般不会允许put null，但是value可能因为WeakReference变成null，此时也是把Entry中的value覆盖一下
            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;
            } 
            //如果调用putIfAbsent方法，此时由于该位置有值，所以不覆盖，仅仅是调整下AccessQueue的元素顺序
            else if (onlyIfAbsent) {             
              recordLockedRead(e, now);
              return entryValue;
            }
            //如果value不是null，进行覆盖 
            else {
              ++modCount;
              enqueueNotification(
                  key, hash, entryValue, valueReference.getWeight(), RemovalCause.REPLACED);
              //覆盖
              setValue(e, key, value, now);
              evictEntries(e);
              return entryValue;
            }
          }
        }

        //如果此位置为空或者链表中没有找到相同的key，则新增
        //变更次数+1
        ++modCount;
        //新创建一个Entry
        ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
        //上一步创建的Entry中只有key hash next，没有value，这一步是为了将value设置到Entry中
        setValue(newEntry, key, value, now);
        //将Entry添加到table中
        table.set(index, newEntry);
        //segment中元素个数+1
        newCount = this.count + 1;
        this.count = newCount;
        evictEntries(newEntry);
        return null;
      } finally {
        //释放锁
        unlock();
        postWriteCleanup();
      }
    }

    
    //将value设置到Entry中，同时recordWrite中会调整AccessQueue和WriteQueue中Entry的顺序，将元素移动到队列尾
    void setValue(ReferenceEntry<K, V> entry, K key, V value, long now) {
      ValueReference<K, V> previous = entry.getValueReference();
      int weight = map.weigher.weigh(key, value);
      checkState(weight >= 0, "Weights must be non-negative");

      ValueReference<K, V> valueReference =
          map.valueStrength.referenceValue(this, entry, value, weight);
      entry.setValueReference(valueReference);
      recordWrite(entry, weight, now);
      previous.notifyNewValue(value);
    }

4.get

  //get时可以传入加载器，在获取不到value或者entry过期时，guava会用加载器去加载
  V get(K key, CacheLoader<? super K, V> loader) throws ExecutionException {
    //计算hash值
    int hash = hash(checkNotNull(key));
    //找到segment位置然后获取元素
    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 {
        //如果segment中元素不为空
        if (count != 0) { 
          //沿着链表找到对应的Entry
          ReferenceEntry<K, V> e = getEntry(key, hash);
          //如果能找到
          if (e != null) {
            long now = map.ticker.read();
            //找到未过期的Entry对应的value
            V value = getLiveValue(e, now);
            //如果value存在，返回value
            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);
            }
          }
        }

        //如果链表中未找到Entry或者value为null，则用加载器去加载
        return lockedGetOrLoad(key, hash, loader);
      } catch (ExecutionException ee) {
        throw ee;
      } finally {
        postReadCleanup();
      }
    }

    //加锁后加载，因为可能有多个线程并发get
    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 {
        //当前时间
        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);
        
        //在链表中寻找
        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();
            //value正在加载，此时不创建新的Entry
            if (valueReference.isLoading()) {
              createNewEntry = false;
            }
            //否则清理writeQueue和accessQueue，并开始createNewEntry
            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 accommodate 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;
          }
        }

        //创建一个新的Entry，此时value还是null
        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();
      }

      //此时只对Entry加锁，而不用对segment加锁了。再对Entry中的value进行load
      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);
      }
    }

总结

guava中有很多可以值得借鉴的点：
1.借用开源框架的思想，guava借用了ConcurrentHashMap分段锁的设计
2.使用了软引用、弱引用等方式加快垃圾回收
3.锁的使用非常精细，比如在lockedGetOrLoad时，由segment锁变成Entry锁
4.LRU淘汰队列类似于LinkedHashMap中的LRU队列
当然还有一些坑：
1.WeakReference和SoftReference是通过==判断key是否相等
2.removalListener过期删除不会通知
3.LocalCache这个类过于庞大和臃肿，不太符合编程规范