Caffeine核心设计图解
一. 参考文档
官方介绍: Caffeine是一个高性能、接近最佳的缓存库。
官方设计文档_1
官方设计文档_2
三方解析
二. 核心前提
以下是重点的设计前提
Caffeine是一个面向二级缓存设计
- 面向小内存的缓存大小
对比竞品的核心维度是在一样的缓存大小下
- 性能
- 缓存命中率
三. 结构组成
从官方介绍的两个方面切入: 高性能与接近最佳
接近最佳
可以理解为，有限的内存大小，存储命中率高的缓存
- W-TinyLFU : 最近使用+使用频率+分段
高性能
- Striped Ring Buffer : 分段和环形缓冲区(无锁队列)，读写事件队列
- ConcurrentHashMap : 主数据存储
- 缓存行填充 : 消除伪共享
- Lazyset : 延迟刷新主存
- CountMin Sketch : 高性能计数
四. 接近最佳-缓存淘汰策略
1. 基础淘汰策略LRU&LFU
LRU(最近最久未使用)是一个最常见的缓存淘汰策略，如在Java#LinkedHashMap实现removeEldestEntry方法即可实现一个LRU策略的缓存组件。
LFU(最近最少频率使用)是一个基于使用频率的淘汰策略，使用最近的使用次数判断是否淘汰缓存。
合并并平衡这两种算法阈值， 可以解决:
- 虽然最近未使用，但历史使用频率很高而不被淘汰
- 虽然历史使用频率很高，但很久没使用了而被淘汰
从而提高缓存命中率，即得到TinyLFU算法。
2. SLRU(分段最近最久未使用)
分段的意义在于应对突发稀疏 ， 大量稀疏流量超过阈值会冲散之前建立好的高命中率缓存集合， 导致在稀疏流量过后需要重新建立命中率高的缓存集合。
而分段的意义是在前置建立一个相对较小的segment(准入窗口)，这个前置段有先对宽松的升级策略，从而将哪些可能更加"火"的缓存保存下来到考量区。
3. W-TinyLFU(号称: 接近最佳)
一切的目的是在有限的缓存大小中提高命中率
- 准入窗口Segment预防稀疏流量冲走建立的缓存集合
- 使用频率&最近使用多维度计算缓存权重
- 不同的缓存状态分别存储多区
- 动态segment大小
结构设计的前提是代码中能够实现， 后续性能讲解中会解释。
动态segment大小
这种结构对于许多重要的工作负载（如数据库、搜索和分析）来说效果非常好。这些情况是频率偏差的，其中需要较小的准入窗口积极过滤。但是，对于偏近度的工作负载（如作业队列和事件流），小的准入窗口反而效果不好。还有在某些系统中，访问模式会随着时间的推移而变化.例如，缓存在白天为用户活动提供服务，在晚上为批处理作业提供服务–动态准入窗口(segment)大小。
五. 高性能
逻辑设计的前提是代码能实现
1. Striped Ring Buffer : 分段和环形缓冲区(无锁队列)，读写事件队列
1.1 使用环节
SRB(Striped Ring Buffer)是一种设计理念类如java中的Striped64、Disruptor、JCTools都有类似的设计理念，他们都是无锁的设计(只用CAS)。
Caffeine使用了JCTools中的Mpsc(多生产者单消费者队列) 作为记录读写事件的消费队列，延迟过期、使用频率等功能如果在获取缓存的主流程中会十分的耗时，所以需要高性能异步队列进行消费处理，同时统一队列处理可以合并或批量处理事件。
1.2 实现原理
四点核心:
- CAS:无锁
- 缓存对齐:消除伪共享
- lazyset:依靠os刷新主存
- 环型队列
核心设计在于可以并发的通过CAS操作快速的申请到数组中的下标，获取下标后可以无锁的对数组的槽位直接设置，当数组事件已经已经满了会阻塞的在数值末尾接上下一个数组形成一个单向链表。
2. ConcurrentHashMap : 主数据存储
1.1 使用环节
主数据存储在Java自带的并发字典ConcurrentHashMap
1.2 实现原理
Java核心集合分段锁，基于synchronized和CAS
3. 缓存行填充 : 消除伪共享
1.1 实现原理
伪共享发生在多个处理器核心修改位于不同变量但分配在同一缓存行的数据时。即使每个线程只访问自己的变量，由于这些变量位于同一缓存行，导致缓存行在不同核心之间来回传输，从而引发性能下降。现代CPU使用缓存来加速内存访问，数据按缓存行（通常是64字节）加载到缓存中。如果两个或多个线程在不同核心上操作属于同一缓存行的不同变量，就会发生伪共享。伪共享会导致不必要的缓存一致性流量，增加内存带宽消耗，并降低程序性能。
消除伪共享 :
- 对齐数据：确保可能被不同线程并发访问的数据结构跨越不同的缓存行，可以解决伪共享问题。
- 使用原子类型或volatile关键字：使用java.util.concurrent.atomic包中的类或者volatile关键字，只能能处理缓存一致性问题，但不能消除伪共享。
使变量独占一个缓存行，就可以解决因为其他cpu访问同一缓存行内的其他属性导致的伪共享问题。
方法一
public class MyClass {
private long padding1。 // 填充字段
private long padding2。
private long padding3。
private volatile long contestedField。 // 需要保护的字段
private long padding4。
private long padding5。
private long padding6。
}
方法二
public class MyClass {
@Contended
private volatile long contestedField。 // 需要保护的字段
}
现代cpu一次读取缓存行大小各有不同，有32字节、64字节、128字节使用方法一需要调整前后填充的字节，使用方法二交个JVM去填充更加便捷，这也是Java中Striped64，更为知名的是LongAddr。
4. Lazyset : 延迟刷新主存
1.1 实现原理
LazySet 方法将给定的值赋值给指定属性，但不会立即刷新到主内存，而是延迟靠OS刷新从而实现更快的赋值操作。这意味着其他线程可能不会立即看到这个更新。
在Java中的Atomic类内部都有一个签名是lazySet的方法，该方法的原理同上。
5. CountMin Sketch : 高性能计数
1.1 使用环节
LFU(最近最少使用)是基于使用频率，CountMin Sketch(一种紧凑的概率数据结构)来识别大量事件中的“高频率”。以 CountMin Sketch 为例，它使用计数器矩阵和多个哈希函数。添加一个条目会增加每行中的一个计数器，并且通过采用观察到的最小值来估计频率。这种方法让我们通过调整矩阵的宽度和深度，在空间、效率和冲突导致的错误率之间进行权衡。
1.2 实现原理
使用long[]数组建立矩阵，long类型8字节(64位)4位一组分类16快，4位最大可以表示15(2^4 - 1)
也就是说单个key最大可以记录使用频率15次，在精细设计在这没什么问题。
通过四次Hash碰撞计算出数值最小的即为使用频率，在记录使用频率时也同时对这四个槽位进行增加。