java - 含咖啡因的 LRU

Question

我正在尝试使用 Caffeine 作为 LRU 缓存，因此首先添加的条目将首先被逐出。运行这段代码:

final Cache<Object, Object> map = Caffeine.newBuilder()
            .maximumSize(10)
            .initialCapacity(10)
            .build();

for (long i=0; i<20;i++) {
        map.put(i, i);
}

map.cleanUp();
System.out.println(map.ge.getAllPresent(map.asMap().keySet()));

打印:

{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 19=19}

但我预料到了

{10=10, 11=11, 12=12, 13=13, 14=14, 15=15, 16=16, 17=17, 18=18, 19=19}

我做错了什么？

Answer 1

Caffeine 没有实现 LRU 作为其缓存逐出策略。相反，Caffeine 使用名为 TinyLFU 的策略. Caffeine 文档包括关于 Efficiency 的页面，其中讨论了这种设计选择的基本原理。引用该页面:

TinyLfu relies on a frequency sketch to probabilistically estimate the historic usage of an entry.

由于 Caffeine 实际上并没有实现 LRU，我认为当您检查缓存中的条目时，您不能可靠地期望它表现出严格的 LRU 行为。

如果您绝对必须具有 LRU 行为，那么 JDK 标准 LinkedHashMap是一个很好的、直接的选择。您需要对其进行子类化并覆盖 removeEldestEntry当缓存变得比你想要的大时，逻辑会发出信号。如果需要使用多线程，则需要使用适当的同步来包装操作。

咖啡因深受 Guava Cache 启发，它同样提供并发访问并具有近似 LRU 行为。针对 Guava 缓存对您的代码进行的快速测试显示了类似的结果。我不知道有任何标准库可以提供可预测的、外部可观察的 LRU 结果和真正的并发访问而无需粗粒度锁。

您可能会重新考虑是否真的需要严格的、外部可观察的 LRU 结果。就其本质而言，缓存是提供优化查找的快速临时存储。我不认为程序行为会根据缓存是否实现严格的 LRU、LRU、LFU 的近似值或其他一些逐出策略而发生巨大变化。

这个先前的问题也对 Java 中的 LRU 缓存选项进行了很好的讨论。

How would you implement an LRU cache in Java?