c - 避免 LRU 缓存中的“大规模驱逐”

Question

我已经实现了一个 LRU 缓存。插入新项目的过程如下所示：

1. 检查干草堆中是否有足够的空间。如果是，请跳至 4。
2. 删除最近最少使用的项目。
3. 检查是否有足够的空间。如果没有，请重复 2。
4. 在可用空间中插入项目。

物品在大海捞针中有效地随机排序。

当需要插入比以前的项目更大的项目时，就会出现问题。它会导致“大规模驱逐”，在这种情况下，它会继续驱逐，直到有足够的项目被驱逐，以至于恰好有几个连续的项目被驱逐。

这种“大规模驱逐”通常涉及驱逐数以万计的物品。

可以做些什么来避免或减轻这种“大规模驱逐”？

Answer 1

我会检查给每个缓存条目一个与其大小和年龄成正比的权重。

（例如，非常旧的非常大的物品有很大的重量。一个非常小的尺寸非常旧的物品几乎没有那么大的重量）

然后根据“重量”驱逐事物。这将有利于驱逐大型和中等旧的项目，而不是驱逐一万个较旧的小项目。

Answer 2

也许您可以查看在 Linux 内核中使用的 Buddy 内存分配：

http://en.wikipedia.org/wiki/Buddy_memory_allocation

这样，我想你仍然会驱逐比严格必要的更多的项目，但是因为伙伴方法在避免碎片方面很有效，我假设你会更快地找到一个大块。