为何SIEVE缓存没有被早点发现？

缓存对于从 CPU 到存储再到整个分布式架构的每一层系统的性能都至关重要。
缓存如此重要意味着设计人员需要仔细考虑缓存清空时会发生什么，但他们并不总是做得很好

SIEVE 是一种逐出算法，是一种在需要放入新项时决定丢弃哪些缓存项的方法。
文献中有数百种此类算法。至少。经典包括丢弃最近最少插入的事物（FIFO）、最近最少访问的事物（LRU）、最不经常访问的事物（LFU），甚至只是随机的事物。

逐出很有趣，因为它是准确性、速度（每次逐出和每次访问需要多少工作）和元数据大小之间的权衡。算法越慢，缓存带来的延迟和效率就越低。元数据越大，存储实际数据的空间就越少。

SIEVE 表现良好。用他们的话来说：
此外，SIEVE 在 1559 条轨迹中超过 45% 的缺失率低于 9 个最先进的算法，而次优算法仅在 15% 的缺失率上较低。

SIEVE 的超级有趣之处在于，它非常有效，而且是在基本 FIFO 队列之上进行的极其简单的更改。

• 与 LRU 的经典实现不同，SIEVE 不需要更改访问时的队列顺序，这减少了多租户设置中所需的同步。
• 访问时所需的只是设置 一个bool，这在大多数处理器上是一个简单的原子操作。

对于性能如此出色的算法来说，这是一件大事。

为什么我们不使用？
SIEVE 提出了一个有趣的问题——如果它如此有效、如此简单，并且与一个一直存在的算法如此密切相关，为什么还没有人发现它呢？他们可能有，但我以前没见过，作者说他们也没有见过。他们的假设很有趣：

在经常进行扫描的块缓存工作负载中，流行的对象通常与扫描的对象混合在一起。因此，两种类型的对象在插入后都会被快速驱逐。

和

我们推测，不抗扫描可能是 SIEVE 在数十年的缓存研究中仍未被发现的原因，这些研究主要集中在页面和块访问上。

这是可信的。扫描阻力很重要，并且是几十年来许多缓存改进的焦点

抗扫描能力对于块和文件工作负载非常重要，因为这些工作负载往往是随机访问（更新数据库页 面、移动文件）和大型顺序访问（备份整个数据库、进行无索引查询）的混合体。我们不希望快速驱逐随机访问的高速缓存热集，为可能永远不会再被访问的顺序页腾出空间。

抗扫描的 SIEVE？
这个历史上的小谜团引发了一个问题：是否有类似的简单但更耐扫描的缓存驱逐方法？其中一种算法，我称之为 SIEVE-k，它只需对 SIEVE 稍作改动即可。

• 每个项目都有一个小计数器，而不是单一的访问位、
• 在访问时，小计数器会递增而不是设置，在值 k 时达到饱和、
• 当驱逐指针经过时，计数器会递减（饱和为 0），而不是重置。

我的意思是，最受欢迎的对象的驱逐计数器会上升，导致它们在扫描启动的一轮驱逐中被跳过。这种方法有一些缺点。其一，驱逐次数从最坏情况下的 O(N) 增加到最坏情况下的 O(kN)，平均驱逐次数似乎也会增加 k（虽然我不喜欢我的分析）。另一个原因是，这可能会延迟驱逐需要驱逐的东西。权衡这些因素，SIEVE-k 最有趣的变体可能是 SIEVE-2（以及 SIEVE-1，后者与 Zhang 等人的原始算法相同）。

使用优秀的开源libCacheSim，，我在一系列真实世界的跟踪上尝试了 SIEVE-2 与 SIEVE。正如预期的那样，在 Web 缓存类型的 KV 工作负载上，它比 SIEVE 更糟糕。块工作负载5 的性能确实参差不齐，有一些胜利，也有一些失败。因此，SIEVE-k 似乎可能很有趣，但一般来说并不能胜过 SIEVE。

如果您想进行更多实验，我已经在libCacheSim 的一个分支中实现了 SIEVE-k 。

总结

• 缓存是系统性能的关键，但缓存清空时的处理往往被忽视。
• SIEVE是一种有效且简单的缓存淘汰算法，但为什么没有更早被发现呢？
• SIEVE-k是一种对SIEVE算法的改进，但在实际应用中并不一定表现更好。