含咖啡因的 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. The Caffeine documentation includes a page on Efficiency 的策略，它讨论了这种设计选择的基本原理。引用该页面：

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

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

如果您绝对必须具有 LRU 行为，那么 JDK 标准 LinkedHashMap is a good, straightforward choice. You would need to subclass it and override removeEldestEntry 具有在缓存变得比您想要的大时发出信号的逻辑。如果需要 multi-threaded 使用，则需要使用适当的同步来包装操作。

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

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

This prior question 在 Java 中也对 LRU 缓存选项进行了很好的讨论。

How would you implement an LRU cache in Java?

含咖啡因的 LRU

LRU with Caffeine

java

lru

caffeine