LRU与Caffeine

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}

我做错了什么？

- bgme_one

Answer 1

Caffeine不采用LRU作为其缓存驱逐策略。相反，Caffeine使用一种名为TinyLFU的策略。 Caffeine文档包括Efficiency页面，讨论了这种设计选择的原因。引用该页面的话：“TinyLfu依靠频率草图来概率地估计条目的历史使用情况。”由于Caffeine实际上并未实现LRU，因此我认为您不能可靠地期望它在检查缓存中的条目时表现出严格的LRU行为。

如果您绝对需要LRU行为，则JDK标准的LinkedHashMap是一个很好、直接的选择。您需要对其进行子类化，并重写removeEldestEntry，使用逻辑来发出缓存已经增长到您想要的大小时的信号。如果需要多线程使用，则需要使用适当的同步包装操作。

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

你可能需要重新考虑是否真的需要强制要求严格、外部可观察的LRU结果。缓存本质上是快速临时存储，以提供优化的查找。我不会期望程序行为在缓存实现严格的LRU、近似LRU、LFU或其他清除策略方面发生巨大变化。

这个先前的问题还有一个很好的讨论关于Java中的LRU缓存选项。 你如何在Java中实现LRU缓存？

- Chris Nauroth

---

谢谢，但我需要它是并发的。关于ConcurrentLinkedHashMap的参考会导向Caffeine。 - bgme_one

@bgme_one，我刚刚编辑了我的回答，声明我不知道有哪个库可以同时提供并发和严格的、外部可观察的LRU结果。然而，我还添加了一个潜在的理由，解释为什么你实际上不需要绝对严格的LRU作为程序要求。目前为止，这个答案包含了我所知道的所有选项。希望这能帮到你。祝好运！ - Chris Nauroth

Caffeine v1.x使用LRU算法，而2.x版本的目标是采用更有效的替代方案。通过Polic API，仅公开了按逐出顺序进行迭代的功能。这对应于ConcurrentLinkedHashMap的可选升序/降序迭代器。请注意，CLHM相对严格地遵循LRU，但由于并发可能会出现一些偏差。如果使用concurrencyLevel(1)，Guava是严格的，但不公开驱逐顺序。 - Ben Manes

@BenManes，谢谢！非常高兴收到作者的回复。 - Chris Nauroth