为何SIEVE缓存没有被早点发现？
内容提要
缓存清空处理常被忽视，SIEVE是一种简单有效的缓存淘汰算法，但为何未被发现？SIEVE-k是对SIEVE的改进，但实际应用中效果不一定更好。文章探讨了新发现的缓存算法SIEVE和改进的SIEVE-k算法。
延伸解读
SIEVE的简洁性优势
SIEVE在基本FIFO队列上仅做微小改动，访问时只需设置一个bool，无需像LRU那样调整队列顺序。这减少了多租户环境中的同步开销，且性能突出：在1559条轨迹中，超过45%的缺失率低于9个先进算法。这种简单高效的设计是其核心价值。
抗扫描能力缺失或为未被发现主因
文章推测SIEVE长期未被发现，可能因其不抗扫描。在块缓存工作负载中，扫描对象与热门对象混合，导致两者都被快速驱逐。而数十年的缓存研究主要关注页面和块访问，抗扫描能力一直是改进焦点，这或许掩盖了SIEVE的潜力。
SIEVE-k的改进与代价
SIEVE-k通过为每个项目增加小计数器来提升抗扫描能力：访问时计数器递增至k饱和，驱逐指针经过时递减。但这使最坏情况驱逐次数从O(N)增至O(kN)，并可能延迟必要驱逐。实验显示，在Web缓存KV工作负载上SIEVE-2比SIEVE更差，块工作负载表现参差不齐，总体未能胜过SIEVE。
Q&A
SIEVE缓存淘汰算法是什么？它和FIFO、LRU有什么区别？
SIEVE是一种缓存淘汰算法，用于在需要放入新项时决定丢弃哪些缓存项。它基于FIFO队列，但访问时只需设置一个bool标志，而不像LRU那样需要改变队列顺序，从而减少了多租户设置中的同步开销。
SIEVE算法在性能上有什么优势？
SIEVE在1559条轨迹中，超过45%的缺失率低于9个最先进的算法，而次优算法仅在15%的缺失率上较低。它非常有效，且是在基本FIFO队列之上进行的极其简单的更改。
为什么SIEVE算法没有更早被发现？
作者推测，SIEVE缺乏抗扫描能力可能是它未被发现的原因。在经常进行扫描的块缓存工作负载中，流行的对象通常与扫描的对象混合，导致两种对象在插入后都被快速驱逐。过去几十年的缓存研究主要集中在页面和块访问上，因此可能忽略了这种简单算法。
SIEVE-k算法是什么？它如何改进SIEVE？
SIEVE-k是对SIEVE的改进，每个项目有一个小计数器而不是单一的访问位。访问时计数器递增（饱和为k），驱逐指针经过时计数器递减（饱和为0），而不是重置。这样，最受欢迎的对象在扫描启动的一轮驱逐中会被跳过，从而增加抗扫描能力。
SIEVE-k在实际应用中效果如何？
SIEVE-k在实际应用中效果不一定更好。在Web缓存类型的KV工作负载上，SIEVE-2比SIEVE更差；在块工作负载上性能参差不齐，有胜有负。因此，SIEVE-k可能有趣，但一般不能胜过SIEVE。
抗扫描能力对缓存算法为什么重要？
抗扫描能力对于块和文件工作负载非常重要，因为这些工作负载往往是随机访问和大型顺序访问的混合体。缺乏抗扫描能力会导致快速驱逐随机访问的缓存热集，为可能永远不会再被访问的顺序页腾出空间，从而降低缓存效率。
