本地缓存—Caffeine Cache

文章目录

• 缓存淘汰策略
• • FIFO
  • • 优点
    • 局限性
  • LRU
  • • 优点
    • 局限性
  • LFU
  • • 优点
    • 局限性
  • W-TinyLFU
  • • 维护频率
    • • CountMin Sketch
    • 支持随时间变化的访问模式-分段LRU(SLRU)
    • hill climbing——爬山算法
    • • 算法思路
      • 优点
      • 缺点
• Caffeine Cache使用
• • 缓存填充策略
  • • 手动加载
    • 同步加载
    • 异步加载
  • 驱逐回收策略
  • • 基于大小回收
    • 基于时间回收
    • 基于引用回收

缓存淘汰策略 FIFO

先进先出（First in First out），在这种淘汰算法中，先进入缓存的会先被淘汰，会导致命中率很低，实现比较简单

优点

最简单、最公平的一种数据淘汰算法，逻辑简单清晰，易于实现

局限性

算法逻辑设计所实现的缓存的命中率是比较低的，因为没有任何额外逻辑能够尽可能的保证常用数据不被淘汰掉

LRU

最近最少使用 or 最近最不常使用 算法（Least Recently Used），每次访问数据都会将其放在队尾，如果需要淘汰数据，就只需要淘汰队首即可。

仍然有个问题，如果有个数据在 1 分钟访问了 1000次，再后 1 分钟没有访问这个数据，但是有其他的数据访问，就导致了这个热点数据被淘汰。

优点

LRU可以有效的对访问比较频繁的数据进行保护，也就是针对热点数据的命中率提高有明显的效果

局限性

LRU可以很好的应对突发流量的情况，因为他不需要累计数据频率。但LRU通过历史数据来预测未来是局限的，它会认为最后到来的数据是最可能被再次访问的，从而给与它最高的优先级，也就是置换出去了热点数据，把这些偶发性数据留下了，从而导致LRU的数据命中率急剧下降。

LFU

最近最少频率使用（Least Frequently Used），利用额外的空间记录每个数据的使用频率，然后选出频率最低进行淘汰。这样就避免了 LRU 不能处理时间段的问题

优点

LFU可以有效的保护缓存，相对场景来讲，比LRU有更好的缓存命中率。因为是以次数为基准，所以更加准确，自然能有效的保证和提高命中率

局限性

在 LFU 中只要数据访问模式随时间保持不变时，LFU能带来最佳的缓存命中率，但是对于淘汰历史突发流量的缓存就有点力不从心了。

比如有部新剧出来了，使用 LFU 给他缓存下来，这部新剧在这几天大概访问了几亿次，这个访问频率也在 LFU 中记录了几亿次。但是新剧总会过气的，比如一个月之后这个新剧的前几集其实已经过气了，但是他的访问量的确是太高了，其他的电视剧根本无法淘汰这个新剧，所以在这种模式下是有局限性。

也就是说：

1. 需要给每个缓存项维护频率信息，每次访问都需要更新，这是个巨大的开销；
2. 如果数据访问模式随时间有变，LFU的频率信息无法随之变化，因此早先频繁访问的记录可能会占据缓存，而后期访问较多的记录则无法被命中；

因此，大多数的缓存设计都是基于LRU或者其变种来进行的。相比之下，LRU并不需要维护昂贵的缓存记录元信息，同时也能够反应随时间变化的数据访问模式。然而，在许多负载之下，LRU依然需要更多的空间才能做到跟LFU一致的缓存命中率。因此，一个“现代”的缓存，应当能够综合两者的长处。

在现有算法的局限性下，会导致缓存数据的命中率或多或少的受损，而命中略又是缓存的重要指标

W-TinyLFU

前Google工程师发明的W-TinyLFU，是一种现代的缓存。Caffeine Cache就是使用这种缓存淘汰算法。如前所述，作为现代的缓存，W-TinyLFU需要解决两个挑战：

1. 如何避免维护频率信息的高开销，给每个记录项维护频率信息，每次访问都需要更新，需要一个巨大的空间记录所有出现过的 key 和其对应的频次——低内存占用；
2. 如何反应随时间变化的访问模式，如果数据访问模式随时间有变，LFU 的频率信息无法随之变化，因此早先频繁访问的记录可能会占据缓存，而后期访问较多的记录则无法被命中——高命中率；

维护频率

W-TinyLFU算法的基础——TinyLFU算法首先在存储数据的使用频率上用了CountMin Sketch算法。

CountMin Sketch

CountMin Sketch算法原理类似于布隆过滤器，能够得出元素出现的频率（不精确的频率）。

该算法由计数矩阵d[m][n]和多个哈希方法hash[m]实现，当给数据a增加频率时：

1. 用m个哈希方法处理数据a，hash[i](a)，能够得出m个哈希值h[i]（其中1<=i<=m 且h[i] <= n）；
2. d[i][h[i]] = d[i][h[i]] +1（其中1<=i<=m）；

发生一次读取时，矩阵中每行对应的计数器增加计数。

可以发现存在哈希冲突，因此，可能出现假正例，但是通过多个哈希方法及计数矩阵的方式，可以保证很低的False Positive Rate（假正率）。

统计数据a的频率：P(a) = min(d[i][hash[i](a)])（其中1<=i<=m）

估算频率时，取数据对应是所有行中计数的最小值（因为哈希冲突的存在，统计的频率不会比真实频率小）。这个方法从空间、效率、以及适配矩阵的长宽引起的哈希碰撞的错误率上做权衡。

在 Caffeine Cache 中，维护了一个 4 bit CountMin Sketch用来记录 key 的使用频率。4 bit 也就意味着，统计的 key 最大使用频率为 15。

为了解决数据访问模式随时间变化的问题，也为了避免计数无限增长，TinyLFU 还采用了一种基于滑动窗口的时间衰减设计机制，借助于一种简易的 reset 操作：每次添加一条记录到 Sketch 的时候，都会给一个计数器上加 1，当计数器达到一个尺寸 W 的时候，把所有记录的 Sketch 数值都除以 2，该 reset 操作可以起到衰减的作用。可以证明，reset 操作带来的频率估计期望不变。

支持随时间变化的访问模式-分段LRU(SLRU)

在对同一对象的"稀疏突发"的场景下，TinyLFU 会出现问题。在这种情况下，新突发的 key 无法建立足够的频率以保留在缓存中，从而导致不断的 cache miss。

Window-TinyLFU（W-TinyLFU）通过两个缓存区域：主缓存 和 窗口缓存 解决这个问题：

主缓存（main cache），使用 SLRU 逐出策略 和 TinyLRU 接纳策略，大小为总缓存的 99％；

窗口缓存（window cache），采用 LRU 逐出策略而没有任何接纳策略，大小为总缓存的 1％。

主缓存根据 SLRU 策略静态划分为 A1 和 A2 两个区域，80％的空间分配给热门项目（A2），并从 20％的非热门项目（A1）中挑选 victim（牺牲块，驱逐块）。所有请求的 key 都会被允许进入窗口缓存，而窗口缓存的 victim 则有机会被允许进入主缓存。如果被接受，则 W-TinyLFU 的 victim 是主缓存的 victim，否则是窗口缓存的 victim。

同时窗口缓存和主空间的大小是根据工作负载特征动态确定的。如果偏向新近度，则倾向于使用大窗口，而偏向频率倾向使用较小的窗口。Caffeine Cache 使用 hill climbing 算法（爬山算法，一种局部择优方法）来采样命中率，进行调整并将其配置为最佳平衡。

W-TinyLFU 的目的是使该方案的行为像 TinyLFU 一样适用于 LFU 工作负载，同时仍然能够利用诸如突发之类的 LRU 模式。因为 99％的缓存分配给了主缓存（使用 TinyLFU），所以对 LFU 工作负载的性能影响可以忽略不计。另一方面，某些工作负载允许使用 LRU 友好模式。

---

hill climbing——爬山算法

爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策，属于人工智能算法的一种。

算法思路

1. 随机选择一个登山的起点；
2. 每次拿相邻点与当前点进行比对，取两者中较优者,作为爬坡的下一步；
3. 重复第2步，直至该点的邻近点中不再有比其大的点；
4. 选择该点作为本次爬山的顶点，即为该算法获得的最优解。

优点

避免遍历，通过启发选择部分节点，从而达到提高效率的目的。

缺点

1. 局部最大：某个节点比周围任何一个邻居都高，但是它却不是整个问题的最高点，局部最优解。
2. 高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。
3. 山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。

解决方法：随机重启爬山算法

---

Caffeine Cache使用

maven依赖：

  com.github.ben-manes.caffeine
  caffeine
  2.9.0

缓存填充策略

Caffeine Cache 提供了3种缓存填充策略：手动加载、同步加载 和 异步加载。

手动加载

在每次 get key 的时候指定一个同步的函数，如果key不存在就调用这个函数生成一个值。

public static void main(String[] args) throws Exception {
    manulCache("姓名", "张三");
}


public static void manulCache(String key, String value) throws Exception {
    Cache cache = Caffeine.newBuilder()
            //写入后1s自动失效
            .expireAfterWrite(1, TimeUnit.SECONDS)
            .maximumSize(10)
            .build();

    //判断是否存在如果不存返回null
    System.out.println(cache.getIfPresent(key));

    //如果一个key不存在，那么会进入指定的函数生成value
    System.out.println(cache.get(key, t -> t + "value"));

    cache.put(key, value);
    System.out.println(cache.get(key, t->t));

    //key自动失效
    TimeUnit.SECONDS.sleep(1);
    System.out.println(cache.getIfPresent(key));

    cache.put(key, value);
    System.out.println(cache.get(key, t->t));

    //移除一个key
    cache.invalidate(key);
    System.out.println(cache.getIfPresent(key));
}

输出：

null
姓名value
张三
null
张三
null

同步加载

构造Cache时候，build方法传入一个CacheLoader实现类。实现load方法，通过key加载value。

public static void syncCache() throws Exception {
    LoadingCache cache = Caffeine.newBuilder()
            .maximumSize(10)
            .expireAfterAccess(1, TimeUnit.SECONDS)
            //key不存在时生成value的load方法
            .build(k -> k + "value");

    System.out.println(cache.get("张三"));

    cache.put("张三", "zhangsan");
    System.out.println(cache.get("张三"));

    Map all = cache.getAll(List.of("A", "张三"));
    System.out.println(all.get("A"));
    System.out.println(all.get("张三"));

    //key自动失效
    TimeUnit.SECONDS.sleep(1);
    System.out.println(cache.get("张三"));
}

输出：

张三value
zhangsan
Avalue
zhangsan
张三value

异步加载

AsyncLoadingCache是继承自LoadingCache类的，异步加载使用Executor去调用方法并返回一个CompletableFuture。异步加载缓存使用了响应式编程模型。

public static void asyncCache() throws Exception {
    AsyncLoadingCache cache = Caffeine.newBuilder()
            .maximumSize(10)
            .expireAfterWrite(1, TimeUnit.SECONDS)
            .buildAsync(k -> k + "value");

    CompletableFuture