Caffeine的Window TinyLfu算法分析
创作时间:
作者:
@小白创作中心
Caffeine的Window TinyLfu算法分析
引用
CSDN
1.
https://blog.csdn.net/weixin_40803011/article/details/117950738
Caffeine是一个高性能的Java缓存框架,广泛应用于各种需要缓存机制的场景。其中,Window TinyLfu算法是Caffeine的核心算法之一,用于优化缓存的命中率和资源利用率。本文将深入分析Window TinyLfu算法的原理和实现细节。
概括
- 通过put操作将数据放入data属性中(ConcurrentHashMap)
- 创建AddTask任务,放入(offer)写缓存:writeBuffer
- 从writeBuffer中获取任务,并执行其run方法,追加记录频率:frequencySketch().increment(key)
- 往window区写入数据
- 如果数据超过window区大小,将数据移到probation区
- 比较从window区晋升的数据和probation区的老数据的频率,输者被淘汰,从data中删除
W-TinyLFU 整体设计
本部分参考了泥瓦匠BYSocket的文章,文章链接:https://jishuin.proginn.com/p/763bfbd358a0
- 判断一个缓存的好坏最核心的指标就是命中率
- 影响缓存命中率因素:业务场景、淘汰策略、清理策略、缓存容量、资源占用等等
- 一般比较简单的缓存就会直接用到 LFU(Least Frequently Used,即最不经常使用) 或者LRU(Least Recently Used,即最近最少使用)
- W-TinyLFU是 LFU 的变种,也是一种缓存淘汰算法
- 先说一下 LFU 的缺点
- 需要给每个记录项维护频率信息,每次访问都需要更新,这是个巨大的开销
- 对突发性的稀疏流量无力,因为前期经常访问的记录已经占用了缓存,将来也不一定会使用上,一直占坑
TinyLFU是怎样去解决LFU 的缺点
- 解决第一个问题是采用了 Count–Min Sketch 算法
- 解决第二个问题是让记录尽量保持相对的“新鲜”(Freshness Mechanism)
- caffeine增加一个window来存储最新的数据(暂时待一下),等其建立足够的频率,避免稀疏流量问题
- 当有新的记录插入时,可以让它跟老的记录进行“PK”,输者就会被淘汰,这样一些老的、不再需要的记录就会被剔除
- W-TinyLFU 的设计如下所示
- 在 TinyLFU 中,近似频率的统计如下图所示
- 4.1 对一个key进行多次hash函数,index到多个数组位置后进行累加,查询时取多个值中的最小值即可
- 4.2 Caffeine 对此有进一步的优化
- 认为达到 15 次的频率算是很高的了,那么只需要 4 个 bit 就可以满足了,一个 long 有 64bit,可以存储 16 个这样的统计数,Caffeine 就是这样的设计,使得存储效率提高了 16 倍
Caffeine的Count–Min Sketch 统计算法实现
- Runnable task = writeBuffer().poll()
- 1.1 从writeBuffer中取任务,那任务是啥时候写进writeBuffer的?
- 1.2 断点跟踪发现,在将数据放入data后,会创建AddTask任务放入writeBuffer(offer操作)
追加记录频率
- 追加频率方法:frequencySketch().increment(key)
- 1.1 跟踪代码发现,如果没有初始化,是不会追加记录的频率
- 1.2 初始化的条件:weightedSize >= (maximum >>> 1)
- weightedSize每put一次都会累加
- maximum是初始化容器最大容量
- 追加记录的频率的具体实现
注意紫色虚线框,其中蓝色小格就是需要计算的位置
下图是上述的代码实现
- 2.1 计算key的hash值(做了增强处理)
- 2.2 统计的4bit分布在table数组的四个元素,进行累加统计
- 通过hash值计算对应四个元素的在table数组的下标
- table数组元素为long类型,计算hash值在long类型64位的起始位置:start,后面三位+1就行
- 进行累加,不能超过15
保鲜机制(待分析)
为了让缓存保持“新鲜”,剔除掉过往频率很高但之后不经常的缓存,Caffeine 有一个 Freshness Mechanism。做法很简答,就是当整体的统计计数(当前所有记录的频率统计之和,这个数值内部维护)达到某一个值时,那么所有记录的频率统计除以 2。
- size:每统计一次累加1,sampleSize默认是最大容量的10倍,在FrequencySketch#ensureCapacity初始化
淘汰策略
- 新的数据写入window区:drainWriteBuffer()->AddTask#run->accessOrderWindowDeque().offerLast(node);
- 把符合条件的记录淘汰掉,代码实现见下图
- 2.1 evictFromWindow()方法实现逻辑梳理见下
- 经过实验发现当 window 区配置为总容量的 1%,剩余的 99%当中的 80%分给 protected 区,20%分给 probation 区时,这时整体性能和命中率表现得最好,所以 Caffeine 默认的比例设置就是这个
- 将超过window区的元素转移到probation区
- 2.2 根据W-TinyLFU,从window晋升过来的要跟probation区的进行“PK”,胜者才能留下
- 因为probation区是尾部插入,所以晋升过来的数据肯定在后面,最终归根于队列头尾进行PK
- PK条件:cache容量不够(超过设置的最大值)
PK解析:BoundedLocalCache#admit
- 分别获取victim和candidate的统计频率:victimFreq、candidateFreq
- 重点关注获取频率的方法:FrequencySketch#frequency
@NonNegative
public int frequency(@NonNull E e) {
if (isNotInitialized()) {
return 0;
}
//得到hash值,跟上面一样
int hash = spread(e.hashCode());
//得到等分的下标,跟上面一样
int start = (hash & 3) << 2;
int frequency = Integer.MAX_VALUE;
//循环四次,分别获取在table数组中不同的下标位置
for (int i = 0; i < 4; i++) {
int index = indexOf(hash, i);
//这个操作就不多说了,其实跟上面incrementAt是一样的,定位到table[index] + 等分的位置,再根据mask取出计数值
int count = (int) ((table[index] >>> ((start + i) << 2)) & 0xfL);
//取四个中的较小值
frequency = Math.min(frequency, count);
}
return frequency;
}
- 驱逐PK失败的元素
热门推荐
怎样才算控股一家公司?
居民、工业、大工业用户的电费组成及计算实例
2025年北京中考改革方案详解:总分调整为530分,道德与法治改为开卷
全国名中医教你冬至养生
数据分析流程中的数据清洗怎么做
冰箱电磁阀的结构和工作原理
企业文化与社会责任共建可持续发展价值观
律师工作要求:技能、素养与专业素养的融合
象征堆砌下的孤独灵魂——《狗阵》
如何组建复合型人才团队
仓库经常发错货?这五大措施帮你加强管理
央视公布10大“宜居城市”!如果到了退休年龄,你会选择哪里呢?
电动执行机构是什么?
怎么恢复耳机的安全音量提醒
慈禧与缠足:一次改革的尝试与失败
虚拟仿真情景互动,我在三一职院当“财务主管”
塑料砧板好不好?在使用时需要注意什么
2024南京租房攻略:高效找房技巧分享
存量房贷利率下调,“房贷族”压力减轻?
人偷渡境外犯罪案件分析
电源管理技术如何开启能效优化新时代
深圳地铁5号线西延线最新建设进展,开通时间+线路图+站点介绍
深入探讨整数的定义、性质及其在生活中的应用与重要性
高考数学大题答题技巧有哪些
“营养”助你全面康复
故宫太和殿的楠木从何而来?
胸腺法新、胸腺五肽、胸腺肽,肿瘤患者提升免疫力,应该怎么选?
2024年全球二次元移动游戏市场研究报告
春节前后,HR们如何用AI玩转企业招聘?
儿科呼吸科专家解读:儿童哮喘的症状、诱因与管理方法