Guava Cache以下的特性：

1. automatic loading of entries into the cache;

2. least-recently-used eviction when a maximum size is exceeded;

3. time-based expiration of entries, measured since last access or last write;

4. keys automatically wrapped in WeakReference;

5. values automatically wrapped in WeakReference or SoftReference soft;

6. notification of evicted (or otherwise removed) entries;

7. accumulation of cache access statistics.

總結(jié)來說：

• 一定要有的讀停士、寫、移除等接口载矿；
• 還有l(wèi)oading特性颂龙，即if cached, return; otherwise create/load/compute, cache and return葵第；
• 還需要時效策略（基于最大容量的時效税弃、和基于讀寫時間的時效）绅你；
• 基于不同引用級別的key/value伺帘；
• 緩存時效后的通知回調(diào)；
• 最后是cache相關(guān)的統(tǒng)計。

以上特性是可選的，通過CacheBuilder構(gòu)造自己的Cache玄糟。下面是兩個簡單的例子：

第一個例子泼返，構(gòu)造一個最大容量為2的cache，插入3個數(shù)據(jù)流礁。在插入第三個數(shù)據(jù)后，key為b的entry被失效了，因為基于lru原則晶伦，a多訪問過一次。

    Cache<String, Obj> cache = CacheBuilder.newBuilder().maximumSize(2).build();
    Obj obj_a = new Obj(1, 2);
    Obj obj_b = new Obj(2, 2);
    Obj obj_c = new Obj(3, 2);

    // first put count=1
    cache.put("a", obj_a);
    Assert.assertEquals(obj_a, cache.getIfPresent("a"));
    
    // 2nd put count=2
    cache.put("b", obj_b);
    
    // use a more than b
    cache.getIfPresent("a");
    Assert.assertEquals(obj_b, cache.getIfPresent("b"));
    Assert.assertEquals(obj_a, cache.getIfPresent("a"));

    // 3rd put count=3 need remove one
    cache.put("c", obj_c);
    Assert.assertEquals(obj_c, cache.getIfPresent("c"));
    Assert.assertTrue(cache.getIfPresent("b") == null);

第二個例子啄枕，構(gòu)造了一個自動實現(xiàn)load邏輯的LoadingCache婚陪。可以看到频祝，第一次取key為d的數(shù)據(jù)泌参，會自動調(diào)用用戶覆蓋的load方法返回，loadingcache會自動將該value寫入cache常空。以后再從cache中直接取的時候沽一，就可以得到值。

    LoadingCache<String, Obj> cache = CacheBuilder.newBuilder().build(new CacheLoader<String, Obj>() {
        @Override
        public Obj load(String key) throws Exception {
            return new Obj(3,3);
        }
    });
    Obj obj_d = new Obj(3, 3);
    
    // get method is the same as get(key,new Callable)
    Assert.assertEquals(obj_a,cache.get("d"));
    
    Assert.assertEquals(obj_a,cache.getIfPresent("d"));// 從cache重直接取

Guava Cache結(jié)構(gòu)

1. Cache配置
2. Cache及其實現(xiàn)和擴展（包括不同級別的引用）漓糙、 Cache的失效通知回調(diào)
3. Cache狀態(tài)

一铣缠、Cache及其實現(xiàn)和擴展

通過類圖，可以看出有一個Cache接口昆禽，不同的Cache均要實現(xiàn)該接口的方法蝗蛙，或者拓展新的方法。還有一個LoadingCache接口醉鳖，增加了get()方法捡硅，實際是一種getorload邏輯（如果cache中存在就get，否則執(zhí)行用戶指定的load邏輯）盗棵，后面會細說壮韭。針對cache和loadingCache有兩個實現(xiàn)類北发，LocalManualCache和基于LocalManualCache實現(xiàn)的LocalLoadingCache。

guava_cache_cache

代理模式

這兩個類并沒有直接實現(xiàn)“緩存”的功能泰涂，而是通過另個類的方法去實現(xiàn)緩存所需的所有功能鲫竞，這個類就是LocalCache，它的變量是包級訪問級別逼蒙。

保護(Protect or Access)代理： 控制對一個對象的訪問从绘，可以給不同的用戶提供不同級別的使用權(quán)限。

那么LocalCache是如何實現(xiàn)cache的呢是牢？

LocalCache實現(xiàn)了ConcurrentMap僵井，并且使用了Segment的設(shè)計思想（不知道是否因為ConcurrentHashMap的影響，EhCache也使用了這種思想）驳棱。

補充：

segment

// map維護segment數(shù)組
final Segment<K, V>[] segments;

1. Segment

Segment繼承ReentrantLock，說明在cache的segments數(shù)組中的每個segment加鎖笙以√适担基本上所有的cache功能都是在segment上實現(xiàn)的。我們一步一步來看：

Segment中的put操作

• 首先它需要獲得鎖猖腕，然后做一些清理工作（guava的cache都是這種基于懶清理的模式拆祈，在put、get等操作的前/后執(zhí)行清理）倘感；

    long now = map.ticker.read();//當次進入的時間放坏，nano
    preWriteCleanup(now);// 基于當前時間做清理，比如寫入后3s中失效這種場景
  

• 接下來老玛，根據(jù)長度判斷是否需要expand轻姿，expand后會生成一個newTable；

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

• 然后逻炊，根據(jù)put的語義，如果已存在entry犁享，需要返回舊的entry余素。那么根據(jù)二次hash找到segment中的一個鏈表的頭，開始遍歷炊昆，找到存在的entry桨吊。

• 當找到一個已存在的entry時威根，需要先判斷當前的ValueRefernece中的值事實上已經(jīng)被回收，因為它們可以是WeakReference或者SoftReferenc類型视乐。對于弱引用和軟引用如果被回收洛搀，valueReference.get()會返回null。如果沒有回收佑淀，就替換舊的值留美，換做新值。

• 然后伸刃，針對移除的對象谎砾，構(gòu)造移除通知對象（RemovalNotification），指定相應的原因：COLLECTED捧颅、REPLACED等景图，進入隊列。之后碉哑，會統(tǒng)一順序利用LocalCache注冊的RemovalListener挚币，執(zhí)行針對通知對象的回調(diào)。由于回調(diào)事件處理可能會有很長時間扣典，因而這里將事件處理的邏輯在退出鎖以后才做妆毕。代碼中是hash值，是第二次的hash值激捏。

    enqueueNotification(key, hash, valueReference, RemovalCause.COLLECTED);
    enqueueNotification(key, hash, valueReference, RemovalCause.REPLACED);
  

• 如果鏈表中沒有該key對應的entry设塔。create后，加入到鏈表頭远舅。

    // Create a new entry.
    ++modCount;
    ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
    // Sets a new value of an entry. Adds newly created entries at the end of the access queue.
    setValue(newEntry, key, value, now);
    // 設(shè)入新的table
    table.set(index, newEntry);
    newCount = this.count + 1;
    this.count = newCount; // write-volatile
  

注意闰蛔，返回null不能代表需要被移除

因為有一種value是LoadingValueReference類型的。在需要動態(tài)加載一個key的值時（場景就是第二個例子：如果cache中沒有key图柏，會調(diào)用load方法加載）序六，實現(xiàn)是：

• 先把該值封裝在LoadingValueReference中，以表達該key對應的值已經(jīng)在加載了蚤吹；
• 如果其他線程也要查詢該key對應的值例诀，就能得到該引用，然后同步執(zhí)行l(wèi)oad方法裁着；
• 在該只加載完成后繁涂，將LoadingValueReference替換成其他ValueReference類型。

所以二驰，在load()執(zhí)行完成之前扔罪，在其他線程得到的value一定是一個 不完全對象 ，因此不能認為應該將它remove桶雀。

那么如何區(qū)分呢

• 在valueReference增加了一個active方法矿酵，用來標明這個entry是否已經(jīng)正確在cache中唬复，由于新建的LoadingValueReference，其內(nèi)部初始值是UNSET全肮，它的isActive為false敞咧，這樣通過isActive就可以判斷該ValueReference是否是一個完全狀態(tài)。

• put中對Active的判斷辜腺，可以看到如果active為false就直接賦值休建。不過很可能，一會load執(zhí)行完后哪自，值又被替換成load后的值了（替換的時候丰包，count會減1）。

    if (valueReference.isActive()) {
        enqueueNotification(key, hash, valueReference, RemovalCause.COLLECTED);
        setValue(e, key, value, now);
        newCount = this.count; // count remains unchanged
    } else {
        setValue(e, key, value, now);
        newCount = this.count + 1;
    }   
  

Segment的get操作

get操作分為兩種壤巷，一種是get邑彪，另一種是帶CacheLoader的get。邏輯分別是：

• get從緩存中取結(jié)果胧华；
• 帶CacheLoader的get寄症，如果緩存中無結(jié)果，返回cacheloader的load的方法返回的結(jié)果矩动，然后寫入緩存entry有巧。

具體介紹一下帶CacheLoader的get操作：

1. 則獲取對象引用（引用可能是非alive的，比如是需要失效的悲没、比如是loading的）篮迎；

2. 判斷對象引用是否是alive的（如果entry是非法的、部分回收的示姿、loading狀態(tài)甜橱、需要失效的，則認為不是alive）栈戳。

3. 如果對象是alive的岂傲，如果設(shè)置refresh，則異步刷新查詢value子檀，然后等待返回最新value镊掖。

4. 針對不是alive的，但卻是在loading的褂痰，等待loading完成（阻塞等待）亩进。

5. 這里如果value還沒有拿到，則查詢loader方法獲取對應的值（阻塞獲人跬帷）镐侯。

以上就是get的邏輯，代碼如下：

V get(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException {
  checkNotNull(key);
  checkNotNull(loader);
  try {
    if (count != 0) { // read-volatile
      // don't call getLiveEntry, which would ignore loading values
      ReferenceEntry<K, V> e = getEntry(key, hash);
      if (e != null) {
        // 記錄進入時間
        long now = map.ticker.read();
        // 判斷是否為alive（此處是懶失效，在每次get時才檢查是否達到失效時機）
        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()) {
          // 如果正在加載的苟翻，等待加載完成后，返回加載的值骗污。（阻塞崇猫，future的get)
          return waitForLoadingValue(e, key, valueReference);
        }
      }
    }
    // 此處或者為null，或者已經(jīng)被失效需忿。
    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();
  }
}

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;

  // 對segment加鎖
  lock();
  try {
    // re-read ticker once inside the lock
    long now = map.ticker.read();
    // 加鎖清清理GC遺留引用數(shù)據(jù)和超時數(shù)據(jù)（重入鎖）
    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)) {
        // 在鏈表中找到e
        valueReference = e.getValueReference();
        // 正在loading 不需要新load
        if (valueReference.isLoading()) {
          createNewEntry = false;
        } else {
          V value = valueReference.get();
          // 為null诅炉，說明被gc回收了。
          if (value == null) {
            // 相關(guān)通知操作
            enqueueNotification(entryKey, hash, valueReference, 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, valueReference, RemovalCause.EXPIRED);
          } else {
            recordLockedRead(e, now);
            statsCounter.recordHits(1);
            // we were concurrent with loading; don't consider refresh
            return value;
          }

          // 清除掉非法的數(shù)據(jù)（被回收的屋厘、失效的）
          writeQueue.remove(e);
          accessQueue.remove(e);
          this.count = newCount; // write-volatile
        }
        break;
      }
    }

    if (createNewEntry) {
      // LoadingValueReference類型
      loadingValueReference = new LoadingValueReference<K, V>();

      if (e == null) {
        // 新建一個entry
        e = newEntry(key, hash, first);
        e.setValueReference(loadingValueReference);
        // 寫入index的位置
        table.set(index, e);
      } else {
        // 到此涕烧，說e找到，但是是非法的汗洒，數(shù)據(jù)已被移除议纯。e放入新建的引用
        e.setValueReference(loadingValueReference);
      }
    }
  } finally {
    unlock();
    postWriteCleanup();
  }

  // 上面加鎖部分建完了新的entry，設(shè)置完valueReference（isAlive為false溢谤，isLoading 為false）瞻凤，到此，鎖已經(jīng)被釋放世杀，其他線程可以拿到一個loading狀態(tài)的引用阀参。這就符合get時，拿到loading狀態(tài)引用后瞻坝，阻塞等待加載的邏輯了蛛壳。
  if (createNewEntry) {
    try {
      // 這里只對e加鎖，而不是segment所刀，允許get操作進入衙荐。
      synchronized (e) {
        // 這個方法同步、線程安全的將key和value都放到cache中勉痴。
        return loadSync(key, hash, loadingValueReference, loader);
      }
    } finally {
      statsCounter.recordMisses(1);
    }
  } else {
    // The entry already exists. Wait for loading.
    return waitForLoadingValue(e, key, valueReference);
  }
}

2. ReferenceEntry和ValueReference

之前說過赫模，guava cache支持不同級別的的引用。首先來確認一下蒸矛，java中的四種引用瀑罗。

四種引用

1. 強引用
   • StringBuffer buffer = new StringBuffer();
   • 如果一個對象通過一串強引用鏈接可到達(Strongly reachable)，它是不會被回收的
2. 弱引用

   • 在垃圾回收器線程掃描它所管轄的內(nèi)存區(qū)域的過程中雏掠，一旦發(fā)現(xiàn)了只具有弱引用的對象斩祭，不管當前內(nèi)存空間足夠與否，都會回收它的內(nèi)存乡话。

   • 不過摧玫，由于垃圾回收器是一個優(yōu)先級很低的線程，因此不一定會很快發(fā)現(xiàn)那些只具有弱引用的對象。

       Car obj = new Car("red");
       WeakReference<Car> weakCar = new WeakReference<Car>(obj);
       //  obj=new Car("blue");
       while(true){
           String[] arr = new String[1000];
           if(weakCar.get()!=null){
               // do something
           }else{
               System.out.println("Object has been collected.");
               break;
           }
       }
     

   • 如上述代碼诬像，weak引用的對象屋群，有個強引用也就是red Car，所以是不會回收的坏挠。

   • 但是芍躏，如果就上面的注釋刪去，那么原來的obj引用了新的對象也就是blue car降狠。原來對象已經(jīng)沒有強引用了对竣，所以虛擬機會將weak回收掉。

3. 軟引用
   • 軟引用基本上和弱引用差不多榜配，只是相比弱引用
   • 當內(nèi)存不足時垃圾回收器才會回收這些軟引用可到達的對象否纬。
4. 虛引用
   • 與軟引用，弱引用不同蛋褥，虛引用指向的對象十分脆弱临燃，我們不可以通過get方法來得到其指向的對象。
   • 它的唯一作用就是當其指向的對象被回收之后壁拉，自己被加入到引用隊列谬俄，用作記錄該引用指向的對象已被銷毀。

引用隊列(Reference Queue)

• 引用隊列可以很容易地實現(xiàn)跟蹤不需要的引用弃理。
• 一旦弱引用對象開始返回null溃论，該弱引用指向的對象就被標記成了垃圾。
• 當你在構(gòu)造WeakReference時傳入一個ReferenceQueue對象痘昌，當該引用指向的對象被標記為垃圾的時候钥勋，這個引用對象會自動地加入到引用隊列里面。

ReferenceEntry的類圖

• Cache中的所有Entry都是基于ReferenceEntry的實現(xiàn)辆苔。
• 信息包括：自身hash值算灸，寫入時間，讀取時間驻啤。每次寫入和讀取的隊列菲驴。以及鏈表指針。
• 每個Entry中均包含一個ValueReference類型來表示值骑冗。

guava_cache_reference

ValueReference的類圖

• 對于ValueReference赊瞬，有三個實現(xiàn)類：StrongValueReference、SoftValueReference贼涩、WeakValueReference巧涧。為了支持動態(tài)加載機制，它還有一個LoadingValueReference遥倦，在需要動態(tài)加載一個key的值時谤绳，先把該值封裝在LoadingValueReference中，以表達該key對應的值已經(jīng)在加載了，如果其他線程也要查詢該key對應的值缩筛，就能得到該引用消略，并且等待改值加載完成，從而保證該值只被加載一次（可以在evict以后重新加載）歪脏。在該值加載完成后疑俭，將LoadingValueReference替換成其他ValueReference類型。（后面會細說）
• 每個ValueReference都紀錄了weight值婿失，所謂weight從字面上理解是“該值的重量”，它由Weighter接口計算而得啄寡。
• 還定義了Stength枚舉類型作為ValueReference的factory類豪硅，它有三個枚舉值：Strong、Soft挺物、Weak懒浮，這三個枚舉值分別創(chuàng)建各自的ValueReference。

guava_cache_value

WeakEntry為例子

在cache的put操作和帶CacheBuilder中的都有newEntry的操作识藤。newEntry根據(jù)cache builder的配置生成不用級別的引用砚著，比如put操作：

// Create a new entry.
++modCount;
// 新建一個entry
ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
// 設(shè)置值，也就是valueRerence
setValue(newEntry, key, value, now);

newEntry方法

根據(jù)cache創(chuàng)建時的配置（代碼中生成的工廠）痴昧，生成不同的Entry稽穆。

ReferenceEntry<K, V> newEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
  return map.entryFactory.newEntry(this, checkNotNull(key), hash, next);
}

調(diào)用WEAK的newEntry，其中segment.keyReferenceQueue是key的引用隊列赶撰。還有一個value的引用隊列舌镶，valueReferenceQueue一會會出現(xiàn)。

WEAK {
  @Override
  <K, V> ReferenceEntry<K, V> newEntry(
      Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
    return new WeakEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
  }
},

setValue方法

首先要生成一個valueReference豪娜，然后set到entry中餐胀。

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

Value的WEAK跟key的WEAK形式很像。只不過瘤载，增加了weight值（cachebuilder復寫不同k否灾，v對應的權(quán)重）和value的比較方法。

WEAK {
  @Override
  <K, V> ValueReference<K, V> referenceValue(
      Segment<K, V> segment, ReferenceEntry<K, V> entry, V value, int weight) {
    return (weight == 1)
        ? new WeakValueReference<K, V>(segment.valueReferenceQueue, value, entry)
        : new WeightedWeakValueReference<K, V>(
            segment.valueReferenceQueue, value, entry, weight);
  }

  @Override
  Equivalence<Object> defaultEquivalence() {
    return Equivalence.identity();
  }
};

cache如何基于引用做清理

如果key或者value的引用不是Strong類型鸣奔，那么它們必然會被gc回收掉墨技。回收掉后溃蔫，引用對象依然存在健提，只是值為null了，這也是上文提到從entry中得到的ValueReference要判斷的原因了伟叛。

/**
 * Drain the key and value reference queues, cleaning up internal entries containing garbage
 * collected keys or values.
 */
@GuardedBy("this")
void drainReferenceQueues() {
  if (map.usesKeyReferences()) {
    drainKeyReferenceQueue();
  }
  if (map.usesValueReferences()) {
    drainValueReferenceQueue();
  }
}

如何失效私痹，因為k和v的失效方法基本一樣，只舉例drainValueReferenceQueue。（執(zhí)行前都會tryLock紊遵，執(zhí)行時保證有鎖）

void drainValueReferenceQueue() {
  Reference<? extends V> ref;
  int i = 0;
  while ((ref = valueReferenceQueue.poll()) != null) {
    @SuppressWarnings("unchecked")
    ValueReference<K, V> valueReference = (ValueReference<K, V>) ref;
    // 回收
    map.reclaimValue(valueReference);
    if (++i == DRAIN_MAX) {
      break;
    }
  }
}

如何回收呢

1. map是segment維護的cache的引用账千，再次hash到segment。
2. 找到segment后暗膜，加鎖匀奏，hash找到entry table。遍歷鏈表学搜，根據(jù)key找到一個entry娃善。
3. 如果找到，且跟入?yún)⒌膙alueReference==比較相等瑞佩，執(zhí)行removeValueFromChain（一會細講）聚磺。
4. 如果沒找到，返回false炬丸。
5. 如果找到瘫寝，不等，返回false稠炬。

removeValueFromChain

ReferenceEntry<K, V> removeValueFromChain(ReferenceEntry<K, V> first,
    ReferenceEntry<K, V> entry, @Nullable K key, int hash, ValueReference<K, V> valueReference,
    RemovalCause cause) {
  enqueueNotification(key, hash, valueReference, cause);
  writeQueue.remove(entry);
  accessQueue.remove(entry);

  if (valueReference.isLoading()) {
    valueReference.notifyNewValue(null);
    return first;
  } else {
    return removeEntryFromChain(first, entry);
  }
}

1. 需要執(zhí)行remove的通知焕阿，入隊列。
2. 針對LoadingValueReference首启，直接返回暮屡。
3. 非loading執(zhí)行移除。

具體如何執(zhí)行remove呢闽坡？removeEntryFromChain

ReferenceEntry<K, V> removeEntryFromChain(ReferenceEntry<K, V> first,
                                          ReferenceEntry<K, V> entry) {
    int newCount = count;
    ReferenceEntry<K, V> newFirst = entry.getNext();
    for (ReferenceEntry<K, V> e = first; e != entry; e = e.getNext()) {
        // 這個方法是copy當前結(jié)點（e）栽惶，然后將新的結(jié)點指向newFirst，返回copy得到的結(jié)點（next）疾嗅。
        // 如果改entry是需要回收的外厂，那么該方法返回null。
        ReferenceEntry<K, V> next = copyEntry(e, newFirst);
        if (next != null) {
            newFirst = next;
        } else {
             // 如果偶遇k或者v已經(jīng)回收了的entry代承，進入需要通知的隊列汁蝶。
            removeCollectedEntry(e);
            newCount--;
        }
    }
    this.count = newCount;
    return newFirst;
}

這段邏輯是，從first開始论悴，一直到要remove結(jié)點（entry）的next（newFirst）掖棉，依次copy每個結(jié)點，指向newFirst膀估，然后將newFirst變成自身幔亥。最后這條鏈表的頭就變成，最后copy的那個結(jié)點察纯，也就是entry的上一個結(jié)點帕棉。不過為什么要copy呢针肥？

3. Cache的失效和回調(diào)

基于讀寫時間失效

失效邏輯和過程：

• Entry在進行一次讀寫操作后，會標識accessTime和writeTime香伴。

    f (map.recordsAccess()) {
        entry.setAccessTime(now);
    }
    if (map.recordsWrite()) {
        entry.setWriteTime(now);
    }
  

• accessQueue和writeQueue分別會在讀寫操作適時的添加慰枕。

    accessQueue.add(entry);
    writeQueue.add(entry);
  

• 遍歷accessQueue和writeQueue

    void expireEntries(long now) {
      drainRecencyQueue();
  
      ReferenceEntry<K, V> e;
      // 取出entry，判斷是否失效
      while ((e = writeQueue.peek()) != null && map.isExpired(e, now)) {
        if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
          throw new AssertionError();
        }
      }
      while ((e = accessQueue.peek()) != null && map.isExpired(e, now)) {
        if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
          throw new AssertionError();
        }
      }
    }  
  

• 判斷是否失效

    if (expiresAfterAccess()
        && (now - entry.getAccessTime() >= expireAfterAccessNanos)) {
        return true;
    }  
  

• removeEntry就是調(diào)用上文的removeValueFromChain即纲。

write鏈（writeQueue）和access鏈（accessQueue）

這兩條鏈都是一個雙向鏈表具帮，通過ReferenceEntry中的previousInWriteQueue、nextInWriteQueue和previousInAccessQueue低斋、nextInAccessQueue鏈接而成蜂厅，但是以Queue的形式表達。

WriteQueue和AccessQueue都是自定義了offer膊畴、add（直接調(diào)用offer）葛峻、remove、poll等操作的邏輯巴比。

• 對于offer（add）操作，如果是新加的節(jié)點礁遵，則直接加入到該鏈的隊首轻绞，如果是已存在的節(jié)點，則將該節(jié)點鏈接的鏈首佣耐。（head始終保持在隊首政勃，新節(jié)點不斷插入到隊首。邏輯上最先插入的結(jié)點保持在兼砖，允許訪問的頭部）
• 對remove操作奸远，直接從該鏈中移除該節(jié)點；
• 對poll操作讽挟，將頭節(jié)點的下一個節(jié)點移除懒叛，并返回。

代碼如下：

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

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

  return true;
}

失效的通知回調(diào)

enqueueNotification

void enqueueNotification(@Nullable K key, int hash, ValueReference<K, V> valueReference,
                         RemovalCause cause) {
    totalWeight -= valueReference.getWeight();
    if (cause.wasEvicted()) {
        statsCounter.recordEviction();
    }
    if (map.removalNotificationQueue != DISCARDING_QUEUE) {
        V value = valueReference.get();
        RemovalNotification<K, V> notification = new RemovalNotification<K, V>(key, value, cause);
        map.removalNotificationQueue.offer(notification);
    }
}

1. 首先判斷移除的原因RemovalCause：EXPLICIT（remove耽梅、clear等用戶有預期的操作）薛窥，REPLACED（put、replace）眼姐，COLLECTED诅迷，EXPIRED，SIZE众旗。RemovalCause有個方法wasEvicted罢杉，表示是否是被驅(qū)逐的。前兩種是false贡歧，后三種是true滩租。
2. cause.wasEvicted()赋秀，只是對命中的計數(shù)略有不同。
3. 生成一個notification對象持际，入隊列沃琅。

removalNotificationQueue何時被清理

在讀寫操作的finally階段，都會執(zhí)行蜘欲。

 void processPendingNotifications() {
  RemovalNotification<K, V> notification;
  while ((notification = removalNotificationQueue.poll()) != null) {
    try {
      // 這里就是回調(diào)構(gòu)造cache時注冊的listener了
      removalListener.onRemoval(notification);
    } catch (Throwable e) {
      logger.log(Level.WARNING, "Exception thrown by removal listener", e);
    }
  }
}

二益眉、Cache的統(tǒng)計功能

1. CacheStats

描述了cache的統(tǒng)計方便的表現(xiàn)，類的實例是不可變的姥份。其中包含了以下屬性：

private final long hitCount;//命中次數(shù)
private final long missCount;// 未命中次數(shù)
private final long loadSuccessCount;//load成功的次數(shù)
private final long loadExceptionCount;//load發(fā)生異常的次數(shù)
private final long totalLoadTime;//執(zhí)行l(wèi)oad所花費的時間
private final long evictionCount;//被移除的entry的數(shù)量

提供的方法：

requestCount()//總體請求次數(shù)
hitRate()//命中率
missRate()//未命中率
loadCount()//執(zhí)行l(wèi)oad的總數(shù)
loadExceptionRate()
averageLoadPenalty()//平均執(zhí)行l(wèi)oad所花費的時間

統(tǒng)計對象的比較

CacheStats minus(CacheStats other)//表示兩個緩存統(tǒng)計的區(qū)別
CacheStats plus(CacheStats other)//表示兩個緩存統(tǒng)計的總和

2. StatsCounter

提供了在操作緩存過程中的統(tǒng)計接口比如命中郭脂、未命中、成功load時間澈歉、異常load時間展鸡、返回一個CacheStats的snapshot。

SimpleStatsCounter是一個線程安全的實現(xiàn)類埃难。代碼中利用的是LongAdder莹弊。而不是AtomicLong。

這篇文章對LongAdder有著詳細的闡述涡尘，http://coolshell.cn/articles/11454.html（作者是追風）

為什么說LongAdder引起了我的注意忍弛，原因有二：作者是Doug lea ，地位實在舉足輕重考抄。他說這個比AtomicLong高效细疚。

三、Cache配置

現(xiàn)在川梅，已經(jīng)大致了解guava cache的結(jié)構(gòu)疯兼，再來看cache的配置就一目了然了。

在Effective Java第二版中贫途，Josh Bloch在第二章中就提到使用Builder模式處理需要很多參數(shù)的構(gòu)造函數(shù)吧彪。他不僅展示了Builder的使用，也描述了相這種方法相對使用帶很多參數(shù)的構(gòu)造函數(shù)帶來的好處潮饱。在本文的結(jié)尾我將進一步總結(jié)Builde模式的優(yōu)點来氧。需要指出的是Josh Bloch已經(jīng)在他的書本貫穿了這一思想。

Guava Cache它為我們提供了CacheBuilder工具類來構(gòu)造不同配置的Cache實例香拉。

1. CacheBuilder

參數(shù)

Map相關(guān)變量和初始值

• map的容量相關(guān)

    private static final int DEFAULT_INITIAL_CAPACITY = 16; // 默認的初始化Map大小
    static final int UNSET_INT = -1;
  
    int initialCapacity = UNSET_INT;
    int concurrencyLevel = UNSET_INT;
    long maximumSize = UNSET_INT;
    long maximumWeight = UNSET_INT;
  

• CONCURRENCY_LEVEL：這個參數(shù)決定了其允許多少個線程并發(fā)操作修改該數(shù)據(jù)結(jié)構(gòu)啦扬。這是因為這個參數(shù)是最后map使用的segment個數(shù)，而每個segment對應一個鎖凫碌，因此扑毡，對于一個map來說，并發(fā)環(huán)境下盛险，理論上最大可以有segment個數(shù)的線程同時安全地操作修改數(shù)據(jù)結(jié)構(gòu)瞄摊。

    private static final int DEFAULT_CONCURRENCY_LEVEL = 4; // 默認并發(fā)水平 
  

補充變量：

• 權(quán)重：用來定量每個entry的權(quán)重勋又；

    Weigher<? super K, ? super V> weigher;
  

• key和value的引用類型：

    Strength keyStrength;
    Strength valueStrength;
  

• 失效時間和刷新時間：

    private static final int DEFAULT_EXPIRATION_NANOS = 0; // 默認超時
    private static final int DEFAULT_REFRESH_NANOS = 0; // 默認刷新時間
    long expireAfterWriteNanos = UNSET_INT;
    long expireAfterAccessNanos = UNSET_INT;
    long refreshNanos = UNSET_INT;
  

• key和value的比較相等的策略：

    Equivalence<Object> keyEquivalence;
    Equivalence<Object> valueEquivalence;
  

• 失效的回調(diào)邏輯：

    RemovalListener<? super K, ? super V> removalListener;
  

構(gòu)造

采用默認參數(shù)構(gòu)造一個CacheBuilder。

public static CacheBuilder<Object, Object> newBuilder() {
    return new CacheBuilder<Object, Object>();
}

通過builder的方法换帜，設(shè)置參數(shù)楔壤。

public CacheBuilder<K, V> initialCapacity(int initialCapacity) {
    checkState(this.initialCapacity == UNSET_INT, "initial capacity was already set to %s",
        this.initialCapacity);
    checkArgument(initialCapacity >= 0);
    this.initialCapacity = initialCapacity;
    return this;
  }

通過build方法生成cache

• 默認配置

    public <K1 extends K, V1 extends V> Cache<K1, V1> build() {
        checkWeightWithWeigher();
        checkNonLoadingCache();
        return new LocalCache.LocalManualCache<K1, V1>(this);
    }
  

• 帶cacheLoader

    public <K1 extends K, V1 extends V> LoadingCache<K1, V1> build(CacheLoader<? super K1, V1> loader) {
    checkWeightWithWeigher();
    return new LocalCache.LocalLoadingCache<K1, V1>(this, loader);
    }
  

2. LocalCache

從CacheBuilder中的build()方法看出，生成的cache分別是LocalManualCache和LocalLoadingCache惯驼。之前還說過蹲嚣，LocalCache作為緩存的直接實現(xiàn)，LocalManualCache和LocalLoadingCache分別利用LocalCache去實現(xiàn)cache接口祟牲，對外提供功能隙畜。

• LocalManualCache的構(gòu)造

    LocalManualCache(CacheBuilder<? super K, ? super V> builder) {
        this(new LocalCache<K, V>(builder, null));
    }
  

• LocalLoadingCache的構(gòu)造

    LocalLoadingCache(CacheBuilder<? super K, ? super V> builder,
    CacheLoader<? super K, V> loader) {
        super(new LocalCache<K, V>(builder, checkNotNull(loader)));
    }
  

LocalCache的構(gòu)造：從構(gòu)造函數(shù)可以看到档押，Cache的所有參數(shù)配置都是從Builder對象中獲取的挖藏，Builder完成了作為該模式最典型的應用，多配置參數(shù)構(gòu)建對象腹泌。

/**
 * Creates a new, empty map with the specified strategy, initial capacity and concurrency level.
 */
LocalCache(
        CacheBuilder<? super K, ? super V> builder, @Nullable CacheLoader<? super K, V> loader) {
    concurrencyLevel = Math.min(builder.getConcurrencyLevel(), MAX_SEGMENTS);

    keyStrength = builder.getKeyStrength();
    valueStrength = builder.getValueStrength();

    keyEquivalence = builder.getKeyEquivalence();
    valueEquivalence = builder.getValueEquivalence();

    maxWeight = builder.getMaximumWeight();
    weigher = builder.getWeigher();
    expireAfterAccessNanos = builder.getExpireAfterAccessNanos();
    expireAfterWriteNanos = builder.getExpireAfterWriteNanos();
    refreshNanos = builder.getRefreshNanos();

    removalListener = builder.getRemovalListener();
    removalNotificationQueue = (removalListener == CacheBuilder.NullListener.INSTANCE)
            ? LocalCache.<RemovalNotification<K, V>>discardingQueue()
            : new ConcurrentLinkedQueue<RemovalNotification<K, V>>();

    ticker = builder.getTicker(recordsTime());
    entryFactory = EntryFactory.getFactory(keyStrength, usesAccessEntries(), usesWriteEntries());
    globalStatsCounter = builder.getStatsCounterSupplier().get();
    defaultLoader = loader;

    int initialCapacity = Math.min(builder.getInitialCapacity(), MAXIMUM_CAPACITY);
    if (evictsBySize() && !customWeigher()) {
        initialCapacity = Math.min(initialCapacity, (int) maxWeight);
    }

    // Find the lowest power-of-two segmentCount that exceeds concurrencyLevel, unless
    // maximumSize/Weight is specified in which case ensure that each segment gets at least 10
    // entries. The special casing for size-based eviction is only necessary because that eviction
    // happens per segment instead of globally, so too many segments compared to the maximum size
    // will result in random eviction behavior.
    int segmentShift = 0;
    int segmentCount = 1;
    while (segmentCount < concurrencyLevel
            && (!evictsBySize() || segmentCount * 20 <= maxWeight)) {
        ++segmentShift;
        segmentCount <<= 1;
    }
    this.segmentShift = 32 - segmentShift;
    segmentMask = segmentCount - 1;

    this.segments = newSegmentArray(segmentCount);

    int segmentCapacity = initialCapacity / segmentCount;
    if (segmentCapacity * segmentCount < initialCapacity) {
        ++segmentCapacity;
    }

    int segmentSize = 1;
    while (segmentSize < segmentCapacity) {
        segmentSize <<= 1;
    }

    if (evictsBySize()) {
        // Ensure sum of segment max weights = overall max weights
        long maxSegmentWeight = maxWeight / segmentCount + 1;
        long remainder = maxWeight % segmentCount;
        for (int i = 0; i < this.segments.length; ++i) {
            if (i == remainder) {
                maxSegmentWeight--;
            }
            this.segments[i] =
                    createSegment(segmentSize, maxSegmentWeight, builder.getStatsCounterSupplier().get());
        }
    } else {
        for (int i = 0; i < this.segments.length; ++i) {
            this.segments[i] =
                    createSegment(segmentSize, UNSET_INT, builder.getStatsCounterSupplier().get());
        }
    }
}