问小白 wenxiaobai
资讯
历史
科技
环境与自然
成长
游戏
财经
文学与艺术
美食
健康
家居
文化
情感
汽车
三农
军事
旅行
运动
教育
生活
星座命理

Caffeine的Window TinyLfu算法分析

创作时间:
作者:
@小白创作中心

Caffeine的Window TinyLfu算法分析

引用
CSDN
1.
https://blog.csdn.net/weixin_40803011/article/details/117950738

Caffeine是一个高性能的Java缓存框架,广泛应用于各种需要缓存机制的场景。其中,Window TinyLfu算法是Caffeine的核心算法之一,用于优化缓存的命中率和资源利用率。本文将深入分析Window TinyLfu算法的原理和实现细节。

概括

  1. 通过put操作将数据放入data属性中(ConcurrentHashMap)
  2. 创建AddTask任务,放入(offer)写缓存:writeBuffer
  3. 从writeBuffer中获取任务,并执行其run方法,追加记录频率:frequencySketch().increment(key)
  4. 往window区写入数据
  5. 如果数据超过window区大小,将数据移到probation区
  6. 比较从window区晋升的数据和probation区的老数据的频率,输者被淘汰,从data中删除

W-TinyLFU 整体设计

本部分参考了泥瓦匠BYSocket的文章,文章链接:https://jishuin.proginn.com/p/763bfbd358a0

  1. 判断一个缓存的好坏最核心的指标就是命中率
  • 影响缓存命中率因素:业务场景、淘汰策略、清理策略、缓存容量、资源占用等等
  1. 一般比较简单的缓存就会直接用到 LFU(Least Frequently Used,即最不经常使用) 或者LRU(Least Recently Used,即最近最少使用)
  • W-TinyLFU是 LFU 的变种,也是一种缓存淘汰算法
  • 先说一下 LFU 的缺点
  • 需要给每个记录项维护频率信息,每次访问都需要更新,这是个巨大的开销
  • 对突发性的稀疏流量无力,因为前期经常访问的记录已经占用了缓存,将来也不一定会使用上,一直占坑

TinyLFU是怎样去解决LFU 的缺点

  1. 解决第一个问题是采用了 Count–Min Sketch 算法
  2. 解决第二个问题是让记录尽量保持相对的“新鲜”(Freshness Mechanism)
  • caffeine增加一个window来存储最新的数据(暂时待一下),等其建立足够的频率,避免稀疏流量问题
  • 当有新的记录插入时,可以让它跟老的记录进行“PK”,输者就会被淘汰,这样一些老的、不再需要的记录就会被剔除
  1. W-TinyLFU 的设计如下所示
  2. 在 TinyLFU 中,近似频率的统计如下图所示
  • 4.1 对一个key进行多次hash函数,index到多个数组位置后进行累加,查询时取多个值中的最小值即可
  • 4.2 Caffeine 对此有进一步的优化
  • 认为达到 15 次的频率算是很高的了,那么只需要 4 个 bit 就可以满足了,一个 long 有 64bit,可以存储 16 个这样的统计数,Caffeine 就是这样的设计,使得存储效率提高了 16 倍

Caffeine的Count–Min Sketch 统计算法实现

  1. Runnable task = writeBuffer().poll()
  • 1.1 从writeBuffer中取任务,那任务是啥时候写进writeBuffer的?
  • 1.2 断点跟踪发现,在将数据放入data后,会创建AddTask任务放入writeBuffer(offer操作)

追加记录频率

  1. 追加频率方法:frequencySketch().increment(key)
  • 1.1 跟踪代码发现,如果没有初始化,是不会追加记录的频率
  • 1.2 初始化的条件:weightedSize >= (maximum >>> 1)
  • weightedSize每put一次都会累加
  • maximum是初始化容器最大容量
  1. 追加记录的频率的具体实现
    注意紫色虚线框,其中蓝色小格就是需要计算的位置
    下图是上述的代码实现
  • 2.1 计算key的hash值(做了增强处理)
  • 2.2 统计的4bit分布在table数组的四个元素,进行累加统计
  • 通过hash值计算对应四个元素的在table数组的下标
  • table数组元素为long类型,计算hash值在long类型64位的起始位置:start,后面三位+1就行
  • 进行累加,不能超过15

保鲜机制(待分析)

为了让缓存保持“新鲜”,剔除掉过往频率很高但之后不经常的缓存,Caffeine 有一个 Freshness Mechanism。做法很简答,就是当整体的统计计数(当前所有记录的频率统计之和,这个数值内部维护)达到某一个值时,那么所有记录的频率统计除以 2。

  1. size:每统计一次累加1,sampleSize默认是最大容量的10倍,在FrequencySketch#ensureCapacity初始化

淘汰策略

  1. 新的数据写入window区:drainWriteBuffer()->AddTask#run->accessOrderWindowDeque().offerLast(node);
  2. 把符合条件的记录淘汰掉,代码实现见下图
  • 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

  1. 分别获取victim和candidate的统计频率:victimFreq、candidateFreq
  2. 重点关注获取频率的方法: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;
}
  1. 驱逐PK失败的元素
© 2023 北京元石科技有限公司 ◎ 京公网安备 11010802042949号