一、引言

在缓存-淘汰策略原理及其实现中，我们提到了常用的LRU和LFU各自的优缺点，为了综合LRU和LFU各自的优点，最后演进出了W-TinyLFU算法。该算法既能够应对突发性的流量场景，又能够应对局部周期性热点数据的场景。下面我们将详细讲解W-TinyLFU在caffeine中的设计思想与源码解析。

W-TinyLFU的总体设计思想

W-TinyLFU为了平衡访问频率和访问时间新鲜程度两个维度因素，尽量
将新鲜的访问频率高的缓存项保留在缓存中，将缓存存储空间分为两个大的区域：Window Cache和Main Cache，

image.png

Window Cache是一个标准的LRU Cache，Main Cache则是一个SLFU（Segmemted LFU）cache，Main Cache进一步划分为Protected Cache（保护区）和Probation Cache（考察区）两个区域，这两个区域都是基于LRU的Cache。

image.png

这三个区域的作用分别是：

• window cache区域用来存储刚产生的数据；
• Protected Cache则用来存放频率较高的热点数据；
• 介于这两者之间的，即兼顾了访问时间和访问频率的数据则存放于Probation Cache。

W-TinyLFU的算法流程

1、数据刚进入时，如果window区域未满，则放入队尾；如果缓存个数超过了window区域的最大缓存数，则将元素放入队首。
2、缓存区域维护

• 首先维护window区域，如果window区超过了最大的限制，那么就要把“多出来”的记录做处理。取队首元素，从window中删除，并且把节点移动到probation区域的队首。
• 接着维护mainCache区域。会从probation队列取出队首元素victim（刚从window区域过来的）和队尾元素candidate（最久未被访问过的）pk，比较频率大小，小的元素会被从缓存中删除。

• producted 区域维护：probation中的元素如果被访问过，元素则会晋升到producted区域。如果producted区域元素满了，则根据lru会淘汰出一个元素进入probgation(不同版本有差别)
  整体的淘汰流程如下图所示：

  
  
  image.png

总结

从上面对W-TinyLFU的原理描述可知，caffeine综合了LFU和LRU的优势，将不同特性的缓存项存入不同的缓存区域，最近刚产生的缓存项进入Window区，不会被淘汰；访问频率高的缓存项进入Protected区，也不会淘汰；介于这两者之间的缓存项存在Probation区，当缓存空间满了时，Probation区的缓存项会根据访问频率判断是保留还是淘汰；通过这种机制，很好的平衡了访问频率和访问时间新鲜程度两个维度因素，尽量将新鲜的访问频率高的缓存项保留在缓存中。
同时在维护缓存项访问频率时，引入计数器衰减机制（保鲜），即节省了存储资源，也能较好的处理稀疏流量、短时超热点流量等传统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()) {
       //当前缓存个数
        long weightedSize = weightedSize();
        //设置当前缓存个数
        setWeightedSize(weightedSize + weight);
        //设置window区域缓存个数
        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);
        }
        //如果有驱逐策略并且当前缓存个数已经大于了window区域最大的缓存数，
        //则把新来的缓存key放到deque的头部
        if (evicts() && (weight > windowMaximum())) {
          accessOrderWindowDeque().offerFirst(node);
        } else if (evicts() || expiresAfterAccess()) {
          //如果有驱逐策略（并且当前缓存个数已经小于window区域最大的缓存 
          //数） 或者 设置了key进入后失效，则把缓存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区淘汰
int evictFromWindow() {
    int candidates = 0;
    //取window deque的队首第一个元素（LRU策略，最先达到的元素在队尾，后 
    //到的元素在其前面）
    Node<K, V> node = accessOrderWindowDeque().peek();
    //一直循环： 如果window区超过了最大的限制，那么就要把“多出来”的记录做处理
    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) {
        //设置 node 的类型： 为观察类型 probation
        node.makeMainProbation();
       // 从window区去掉
        accessOrderWindowDeque().remove(node);
        //加入到probation queue,相当于把节点移动到probation区（开始准备晋升）
        accessOrderProbationDeque().add(node);
        candidates++;

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

    return candidates;
  }

  //从mainCache区淘汰
  void evictFromMain(int candidates) {
    int victimQueue = PROBATION;
    //victim 从probation cache区域取出队首元素（window区域淘汰的）
    Node<K, V> victim = accessOrderProbationDeque().peekFirst();
    //candidate = 从probation cache区域取出队尾元素（最久没有被访问过）
    Node<K, V> candidate = accessOrderProbationDeque().peekLast();
    while (weightedSize() > maximum()) {
      (省略部分代码)
      ......... 

      /**
       *candidate和victim进行频率比较，频率小的会被从缓存中删除。
       */
      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);
      }
    }
  }