Caffeine基于容量的驱逐策略分析

容量的驱逐策略分析"/>

Caffeine基于容量的驱逐策略分析

基于容量的示例

	// 基于缓存内的元素个数进行驱逐LoadingCache<Key, Graph> graphs = Caffeine.newBuilder().maximumSize(10).build(key -> createExpensiveGraph(key));

1. 如果你的缓存容量不希望超过某个特定的大小，那么记得使用Caffeine.maximumSize(long)
2. 缓存将会尝试通过基于就近度和频率的算法来驱逐掉不会再被使用到的元素

LocalManualCache#put调用栈概括

1. data的数据类型为ConcurrentHashMap<Object, Node<K, V>>，存放缓存数据
2. UML框图整理其逻辑
   
3. 通过分析，大概定位和驱逐策略相关的代码实现应该在红色标记的afterWrite(new AddTask(node, newWeight));

BoundedLocalCache#afterWrite分析

1. 替换策列任务:AddTask
   
2. 按照示例最终走调用栈为下图
   

BoundedLocalCache#scheduleAfterWrite

1. PerformCleanupTask#exec
   
   1.1 WeakReference<BoundedLocalCache<?, ?>> reference存放着put进去的值
   1.2 跟着cache.performCleanUp方法最终定位BoundedLocalCache#maintenance
   （1）在跟代码时发现，在执行完evictEntries()方法后，缓存的容量从10变为5了（调式设置容量大小为5）

BoundedLocalCache#evictEntries（驱逐策略核心）

int candidates = evictFromWindow();

1. 调式发现windowWeightedSize() = 10（调式时只放了10个元素），windowMaximum() = 1
（1）每循环一次windowWeightedSize减去1
2. 执行上图的代码逻辑后，accessOrderProbationDeque()队列中有前9个元素
3. 最后candidates累加变为9（只测试10个数据，留下最新的一个数据）

evictFromMain(candidates)核心

1. 抽出调式代码走的逻辑，见下方

   Node<K, V> victim = accessOrderProbationDeque().peekFirst();
   Node<K, V> candidate = accessOrderProbationDeque().peekLast();
   while (weightedSize() > maximum()) { //10 > 5K victimKey = victim.getKey();K candidateKey = candidate.getKey();//逐出频率最低的元素candidates--;if (admit(candidateKey, victimKey)) {Node<K, V> evict = victim;victim = victim.getNextInAccessOrder();evictEntry(evict, RemovalCause.SIZE, 0L);candidate = candidate.getPreviousInAccessOrder();} else {Node<K, V> evict = candidate;candidate = (candidates > 0)? candidate.getPreviousInAccessOrder(): candidate.getNextInAccessOrder();evictEntry(evict, RemovalCause.SIZE, 0L);}
   }
   

2. 通过FrequencySketch#frequency方法计算元素出现的次数，出现次数少的元素会被驱逐
3. 两边各往中间前进一个元素继续比较

evictEntry(evict, RemovalCause.SIZE, 0L)驱逐函数

dataputeIfPresent(keyReference, (k, n) -> {synchronized (n) {notifyEviction(key, value[0], actualCause[0]); //通知删除，但evictionListener为空makeDead(n);}discardRefresh(keyReference);removed[0] = true;return null;//执行完就删除了
});
if (evicts()) {if (node.inMainProbation()) {accessOrderProbationDeque().remove(node);}
}
if (removed[0]) {statsCounter().recordEviction(node.getWeight(), actualCause[0]);notifyRemoval(key, value[0], actualCause[0]);
}

总结

1. 在调式时发现两种任务：AddTask和PerformCleanupTask
   1.1 AddTask放入了队列中
   1.2 PerformCleanupTask提交到线程池中
2. AddTask和PerformCleanupTask的关系
   2.1 在执行PerformCleanupTask任务时，执行drainWriteBuffer方法时会从队列中取AddTask任务执行
   2.2 调用链：BoundedLocalCache#performCleanUp --> maintenance -> drainWriteBuffer()
   
3. 取队列前后两个元素，比较其出现次数，频率低会被驱逐
   3.1 计算元素出现的次数FrequencySketch#frequency方法待分析