Caffeine 淘汰策略

使用了 W-TinyLFU 算法，该算法主要有两部分

1. 采用 Count-Min Sketch 算法降低频率信息带来的内存消耗
2. 通过维护一个 PK 机制保障新上的热点数据能够被缓存

Count-Min Sketch 算法

该算法首先认为：对于频率统计，我们其实不需要一个精确值。在存储数据时，它首先对 key 进行多种 hash 函数运算，然后在各个 hash 函数对应的二维数组索引位置的记录值 +1

多个 hash 算法是为了避免 hash 冲突

为了解决这个问题，采用多个 hash 算法，假设使用四种 hash 算法从该 key 在所有 hash 算法下映射的位置取数值最低的一个数作为访问频率（上图访问频率为 1）

Caffeine 也利用了 Count-Min Sketch 的思想，但是它有稍微的变化

Caffeine 使用一维 long 数组用来记录数据的访问频率，数组的大小为2的 N 次方，由缓存大小决定。假设缓存大小是 100，数组的大小需要满足：

简单来说就是，数组的大小就是第一个大于等于缓存大小的 2 的 N 次方。如果缓存大小为 100，那么用于记录数据访问频率的数组大小就是128

PK 机制

Caffeine 所有的数据都存储在 ConcurrentHashMap 中。在 Caffeine 中有三个用于存储引用的 LRU 队列，分别是

• Window Cache
• Probation Cache
• Protected Cache

其中Probation Cache 和 Protected Cache 组成了 Main Cache。正常情况下，Window Cache 占比大小为 1%，Probation Cache 大小为剩下的 99% 的 20%，Protected Cache 大小为剩下的 99% 的 80%

新数据直接进入 Window 区，当 Window 区满了，就会根据 LRU 算法把 Candidate（即淘汰出来的元素）放到 Probation 区

如果在 Probation 区的数据被访问到，会直接进入到Protected区。如果Protected区满了，该区淘汰出的数据将降级到Probation区

如果 Probation 区满了，就把 Candidate 和 Probation 区的 Victim（将要淘汰的元素），两个进行 “PK”（比较两者频率大小），胜者将留在 Probation，输者就要被淘汰了。也就是说，实际上的数据淘汰，只在 Probation 区发生