一、引言

在緩存-淘汰策略原理及其實(shí)現(xiàn)中，我們提到了常用的LRU和LFU各自的優(yōu)缺點(diǎn)，為了綜合LRU和LFU各自的優(yōu)點(diǎn)，最后演進(jìn)出了W-TinyLFU算法。該算法既能夠應(yīng)對突發(fā)性的流量場景，又能夠應(yīng)對局部周期性熱點(diǎn)數(shù)據(jù)的場景。下面我們將詳細(xì)講解W-TinyLFU在caffeine中的設(shè)計(jì)思想與源碼解析。

W-TinyLFU的總體設(shè)計(jì)思想

W-TinyLFU為了平衡訪問頻率和訪問時間新鮮程度兩個維度因素，盡量
將新鮮的訪問頻率高的緩存項(xiàng)保留在緩存中，將緩存存儲空間分為兩個大的區(qū)域：Window Cache和Main Cache，

image.png

Window Cache是一個標(biāo)準(zhǔn)的LRU Cache，Main Cache則是一個SLFU（Segmemted LFU）cache，Main Cache進(jìn)一步劃分為Protected Cache（保護(hù)區(qū)）和Probation Cache（考察區(qū)）兩個區(qū)域，這兩個區(qū)域都是基于LRU的Cache。

image.png

這三個區(qū)域的作用分別是：

• window cache區(qū)域用來存儲剛產(chǎn)生的數(shù)據(jù)；
• Protected Cache則用來存放頻率較高的熱點(diǎn)數(shù)據(jù)；
• 介于這兩者之間的，即兼顧了訪問時間和訪問頻率的數(shù)據(jù)則存放于Probation Cache。

W-TinyLFU的算法流程

1、數(shù)據(jù)剛進(jìn)入時，如果window區(qū)域未滿，則放入隊(duì)尾；如果緩存?zhèn)€數(shù)超過了window區(qū)域的最大緩存數(shù)，則將元素放入隊(duì)首。
2、緩存區(qū)域維護(hù)

• 首先維護(hù)window區(qū)域，如果window區(qū)超過了最大的限制，那么就要把“多出來”的記錄做處理。取隊(duì)首元素，從window中刪除，并且把節(jié)點(diǎn)移動到probation區(qū)域的隊(duì)首。
• 接著維護(hù)mainCache區(qū)域。會從probation隊(duì)列取出隊(duì)首元素victim（剛從window區(qū)域過來的）和隊(duì)尾元素candidate（最久未被訪問過的）pk，比較頻率大小，小的元素會被從緩存中刪除。

• producted 區(qū)域維護(hù)：probation中的元素如果被訪問過，元素則會晉升到producted區(qū)域。如果producted區(qū)域元素滿了，則根據(jù)lru會淘汰出一個元素進(jìn)入probgation(不同版本有差別)
  整體的淘汰流程如下圖所示：

  
  
  image.png

總結(jié)

從上面對W-TinyLFU的原理描述可知，caffeine綜合了LFU和LRU的優(yōu)勢，將不同特性的緩存項(xiàng)存入不同的緩存區(qū)域，最近剛產(chǎn)生的緩存項(xiàng)進(jìn)入Window區(qū)，不會被淘汰；訪問頻率高的緩存項(xiàng)進(jìn)入Protected區(qū)，也不會淘汰；介于這兩者之間的緩存項(xiàng)存在Probation區(qū)，當(dāng)緩存空間滿了時，Probation區(qū)的緩存項(xiàng)會根據(jù)訪問頻率判斷是保留還是淘汰；通過這種機(jī)制，很好的平衡了訪問頻率和訪問時間新鮮程度兩個維度因素，盡量將新鮮的訪問頻率高的緩存項(xiàng)保留在緩存中。
同時在維護(hù)緩存項(xiàng)訪問頻率時，引入計(jì)數(shù)器衰減機(jī)制（保鮮），即節(jié)省了存儲資源，也能較好的處理稀疏流量、短時超熱點(diǎn)流量等傳統(tǒng)LFU無法很好處理的場景。

附錄：caffeine源碼

 final class AddTask implements Runnable {
    final Node<K, V> node;
    final int weight;

    AddTask(Node<K, V> node, int weight) {
      this.weight = weight;
      this.node = node;
    }

    @Override
    @GuardedBy("evictionLock")
    @SuppressWarnings("FutureReturnValueIgnored")
    public void run() {
      if (evicts()) {
       //當(dāng)前緩存?zhèn)€數(shù)
        long weightedSize = weightedSize();
        //設(shè)置當(dāng)前緩存?zhèn)€數(shù)
        setWeightedSize(weightedSize + weight);
        //設(shè)置window區(qū)域緩存?zhèn)€數(shù)
        setWindowWeightedSize(windowWeightedSize() + weight);
        node.setPolicyWeight(node.getPolicyWeight() + weight);

        long maximum = maximum();
        if (weightedSize >= (maximum >>> 1)) {
          // Lazily initialize when close to the maximum
          long capacity = isWeighted() ? data.mappingCount() : maximum;
          frequencySketch().ensureCapacity(capacity);
        }

        K key = node.getKey();
        if (key != null) {
          //更新訪問頻率
          frequencySketch().increment(key);
        }

        setMissesInSample(missesInSample() + 1);
      }

      // ignore out-of-order write operations
      boolean isAlive;
      synchronized (node) {
        isAlive = node.isAlive();
      }
      if (isAlive) {
        if (expiresAfterWrite()) {
          writeOrderDeque().add(node);
        }
        //如果有驅(qū)逐策略并且當(dāng)前緩存?zhèn)€數(shù)已經(jīng)大于了window區(qū)域最大的緩存數(shù)，
        //則把新來的緩存key放到deque的頭部
        if (evicts() && (weight > windowMaximum())) {
          accessOrderWindowDeque().offerFirst(node);
        } else if (evicts() || expiresAfterAccess()) {
          //如果有驅(qū)逐策略（并且當(dāng)前緩存?zhèn)€數(shù)已經(jīng)小于window區(qū)域最大的緩存 
          //數(shù)） 或者 設(shè)置了key進(jìn)入后失效，則把緩存key放到deque的尾部
          accessOrderWindowDeque().offerLast(node);
        }
        if (expiresVariable()) {
          timerWheel().schedule(node);
        }
      }

      // Ensure that in-flight async computation cannot expire (reset on a completion callback)
      if (isComputingAsync(node)) {
        synchronized (node) {
          if (!Async.isReady((CompletableFuture<?>) node.getValue())) {
            long expirationTime = expirationTicker().read() + ASYNC_EXPIRY;
            setVariableTime(node, expirationTime);
            setAccessTime(node, expirationTime);
            setWriteTime(node, expirationTime);
          }
        }
      }
    }
  }



//從window區(qū)淘汰
int evictFromWindow() {
    int candidates = 0;
    //取window deque的隊(duì)首第一個元素（LRU策略，最先達(dá)到的元素在隊(duì)尾，后 
    //到的元素在其前面）
    Node<K, V> node = accessOrderWindowDeque().peek();
    //一直循環(huán)： 如果window區(qū)超過了最大的限制，那么就要把“多出來”的記錄做處理
    while (windowWeightedSize() > windowMaximum()) {
      // The pending operations will adjust the size to reflect the correct weight
      if (node == null) {
        break;
      }

      Node<K, V> next = node.getNextInAccessOrder();
      if (node.getPolicyWeight() != 0) {
        //設(shè)置 node 的類型： 為觀察類型 probation
        node.makeMainProbation();
       // 從window區(qū)去掉
        accessOrderWindowDeque().remove(node);
        //加入到probation queue,相當(dāng)于把節(jié)點(diǎn)移動到probation區(qū)（開始準(zhǔn)備晉升）
        accessOrderProbationDeque().add(node);
        candidates++;

        setWindowWeightedSize(windowWeightedSize() - node.getPolicyWeight());
      }
      node = next;
    }

    return candidates;
  }

  //從mainCache區(qū)淘汰
  void evictFromMain(int candidates) {
    int victimQueue = PROBATION;
    //victim 從probation cache區(qū)域取出隊(duì)首元素（window區(qū)域淘汰的）
    Node<K, V> victim = accessOrderProbationDeque().peekFirst();
    //candidate = 從probation cache區(qū)域取出隊(duì)尾元素（最久沒有被訪問過）
    Node<K, V> candidate = accessOrderProbationDeque().peekLast();
    while (weightedSize() > maximum()) {
      (省略部分代碼)
      ......... 

      /**
       *candidate和victim進(jìn)行頻率比較，頻率小的會被從緩存中刪除。
       */
      if (admit(candidateKey, victimKey)) {
        Node<K, V> evict = victim;
        victim = victim.getNextInAccessOrder();
        // 刪除 victim ，從而留下 candidate
        evictEntry(evict, RemovalCause.SIZE, 0L);
        candidate = candidate.getPreviousInAccessOrder();
      } else {
        Node<K, V> evict = candidate;
        candidate = (candidates > 0)
            ? candidate.getPreviousInAccessOrder()
            : candidate.getNextInAccessOrder();
        // 刪除 candidate ，從而留下 victim
        evictEntry(evict, RemovalCause.SIZE, 0L);
      }
    }
  }