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. 判断一个缓存的好坏最核心的指标就是命中率

• 影响缓存命中率因素：业务场景、淘汰策略、清理策略、缓存容量、资源占用等等

2. 一般比较简单的缓存就会直接用到 LFU(Least Frequently Used，即最不经常使用) 或者LRU(Least Recently Used，即最近最少使用)

• W-TinyLFU是 LFU 的变种，也是一种缓存淘汰算法
• 先说一下 LFU 的缺点
• 需要给每个记录项维护频率信息，每次访问都需要更新，这是个巨大的开销
• 对突发性的稀疏流量无力，因为前期经常访问的记录已经占用了缓存，将来也不一定会使用上，一直占坑

TinyLFU是怎样去解决LFU 的缺点

1. 解决第一个问题是采用了 Count–Min Sketch 算法
2. 解决第二个问题是让记录尽量保持相对的“新鲜”（Freshness Mechanism）

• caffeine增加一个window来存储最新的数据（暂时待一下），等其建立足够的频率，避免稀疏流量问题
• 当有新的记录插入时，可以让它跟老的记录进行“PK”，输者就会被淘汰，这样一些老的、不再需要的记录就会被剔除

3. W-TinyLFU 的设计如下所示
4. 在 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是初始化容器最大容量

2. 追加记录的频率的具体实现
   注意紫色虚线框，其中蓝色小格就是需要计算的位置
   下图是上述的代码实现
   

• 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;
}

3. 驱逐PK失败的元素