LFU比LRU更好的情况是什么？

Question

我一直在寻找一个合适的案例来证明LFU比LRU更好，但我不确定。

我所做的是（但不确定是否是一个好例子）当您拥有一个缓存容量为3且缓存请求为4（如A B C D），但C和D被经常请求时。

因此，如果请求流是A B C D C A D B D C A B A C D LRU将产生10个故障，而LFU将产生9个故障。

这是一个被接受的案例吗？

- Argiris

---

LRU 对于小缓存更有效，但在较大的缓存中扩展性较差。 在这些情况下，缓存的典型 Zipf 工作负载占主导地位，因此 LFU 在更低容量下通常具有更高的命中率。 LRU 在扫描（例如数据库）中也存在问题，并经常被绕过。 现代策略结合了两者，以找到更理想的平衡。 - Ben Manes

Answer 1

可能会出现一些数据在过去很受欢迎，但目前变得暂时无关紧要，但它很可能在不久的将来再次被访问。想想在线零售商店。假设他们最畅销的物品是相机、手机等。如果情人节即将到来，人们会为情人节订购礼物。因此，如果您实施了LRU缓存（最近最少使用缓存），它将从缓存中清除您最畅销的物品。

LRU（最近最少使用）策略不能保证热门项目一定会留在缓存中，但由于它们被访问的频率更高，因此它们更有可能留在缓存中（因为它们很可能在被清除之前排队到队列的头部）。在高峰期间，如果突然变得流行的项目数量足够多，它们可能会填满缓存并迫使通常的项目被清除。这将是一个暂时的副作用，在高峰后会回归正常。在某些情况下，这也是可取的，因为在高峰期间受欢迎的项目应该比常规畅销品更快地被访问。

- Yilmaz

Answer 2

您可能会发现this有用。 LRU非常直观。

您的移动键盘使用LFU。当您输入一些字母时，您可以在键盘顶部看到与您已输入的字母匹配的几个建议单词。在开始时，当键盘应用程序的cache为空时，它可能会向您显示这4个单词（假设您输入了字母“STA”。建议的单词可能会弹出，例如开始、站立、雕像、工作人员）。这里的想法是，基于您使用的单词，它将在一定时间后忽略建议中的LRU单词。如果您没有使用它，您以后可能不会在建议中看到“staff”这个词。

如果您有一个情况，在那里您知道数据非常重复，一定要选择LFU以避免cache错过。 这两者似乎都相互独立并具有隔离意义。它取决于您想要使用任何一个的用例。

- Ankush Rathi