为什么缓存使用最近使用(MRU)算法作为逐出策略？

Question

我知道MRU的算法及其反向最近最少使用(LRU).

我认为LRU是合理的,因为LRU元素意味着它将来至少可以使用.但是,MRU元素意味着将来很有可能使用该元素,为什么要逐出它？什么是合理的情况？

Answer 1

想象一下,当他们到达公共汽车站时,根据他们的公交车号码(或您使用的任何标识符)查看公交车的详细信息.

考虑到如果你刚刚看到36号公共汽车,你不太可能看到另一辆公共汽车,而不是看到停在那里的其他公共汽车.

只是一个例子,但这个想法更为笼统:在某些情况下,"只是看到一些东西"是一个很好的指标,你很快就不会再看到同样的东西了.

Answer 2

我认为 @Jon Skeet 和 @Jeremiah Willcock 的答案都描述了使用 MRU 作为避免无用条目污染缓存的方法。

1. 仅当您的缓存 API 允许您动态更改策略时，这才有效；例如，基于每个请求。在“正常”情况下将缓存策略设置为 MRU 可能是一个坏主意……因为一旦填满，缓存就会变得无效。

2. MRU 存在一个问题，如果您在进行 MRU 查找时命中了经常在“正常”模式下使用的条目，那么您最终会丢弃该条目......

在不污染缓存的情况下进行扫描的 MRU 更好的替代方案是：

• 完全绕过缓存，
• 探测缓存而不进行读取/更新，并且不改变 LRU 链。

就其价值而言，我想不出任何不符合这种一般模式的 MRU 用例。

顺便说一句，由于聚集效应，@Jon Skeet 的公交车到达示例在现实中并不总是得到证实。

• 如果公交车晚点，每个公交车站等候的人数可能会超过平均水平。公交车必须更频繁地停靠，并且在每个站点停留的时间更长。这会减慢迟到的公共汽车的速度。

• 在晚点巴士之后准时到达的巴士通常会比每个巴士站的平均等候人数要少。（因为他们只是上了晚点的公共汽车。）这会加快后面的公共汽车的速度。

• 最终的结果是公交车往往会聚集在一起。

请参阅： https: //en.wikipedia.org/wiki/Bus_bunching

Answer 3

也许一个更具体的例子是媒体服务器。当用户完成观看视频（假设它是电视节目的一集）时，他们大概最不可能想要再次观看它。因此，如果您必须驱逐某些内容，请驱逐最近查看的项目。

但在实践中，我相信这种类型的缓存通常与 LRU 或 LFU 缓存一起使用，其中两个缓存的串联允许您涵盖各种情况。