一、引言
在缓存-淘汰策略原理及其实现中，我们提到了常用的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);
}
}
}
