Sieve 比 LRU 更简单

原文 ↗ Hacker News 讨论 ↗

一种名为 SIEVE 的新缓存淘汰算法被介绍为比经典 LRU 更简单、性能更高的替代方案，尤其适用于现代 Web 和类似 CDN 的工作负载。评论者仔细审视了它的实际行为、复杂度、边界情况（例如对扫描的抵抗能力）以及均摊性能，常常把学术基准与并发、CPU 缓存局部性以及对抗性访问模式等真实世界约束进行对比。带有强烈营销味道的博客风格和最初有误的动画都引发了批评，但底层研究、开源实现以及作者的澄清，仍让许多人认为 SIEVE 是一个有前景但依赖工作负载的缓存设计工具箱补充。

写作风格与沟通

  • 许多读者不喜欢这篇博客夸张、带有“营销”味道的语气（例如“superstar”“turbo boost”），认为它令人反感，并且很像 ChatGPT 的风格。
  • 也有人更能容忍，认为这是在面向非专家做传播，或者是当前“卖掉你的研究”的文化产物。
  • 作者表示这篇帖子经过了 ChatGPT 的“润色”，接受这些批评，并承诺用更直接的风格重写。

算法理解与正确性

  • 评论者将 SIEVE 关联到经典的 CLOCK/NRU：一个环形队列（或列表）、一个“手”指针，以及一个 1 位访问标志，表示“自从手上次经过以来是否被触碰过”。
  • 在未命中时，手指针向前扫描，清除访问标志，直到找到一个未访问条目并将其淘汰。
  • 也有几个人觉得文章和动画都很令人困惑。有人指出动画里有一个不一致之处（没有清除访问位）；作者随后进行了更新。

性能与工作负载适用性

  • 根据论文和额外图表，SIEVE 据称在许多 Web 以及部分多租户块 I/O 轨迹上优于强基线（例如 LRU、TinyLFU），但并非适用于所有工作负载。
  • 文中明确承认它并不具备抗扫描能力，并且在某些模式下可能退化得接近 MRU 的行为。
  • 一条关于指标的说法（“在约 45% 的轨迹上最好”）引发了对剩余 55% 的疑问；反驳是，这 55% 是由许多竞争算法共同分担的。

设计选择、复杂度与实现

  • 最坏情况下的淘汰成本是 O(N)，但评论者认为其均摊后是 O(1)，因为每次扫描都会清除访问位，而这些访问位必须逐个重新置位。
  • 讨论中的实现方式包括：链表、数组/环形缓冲区、有序字典；使用循环链表来避免空值检查；像 Segcache 这样的日志结构/分段式设计。
  • 将现有的 LRU 库改造成 SIEVE 只需要很少的代码改动，这被一些人视为实现简单性的证据。

批评、替代方案与对抗性担忧

  • 一个很长的子讨论认为：把新条目总是插入固定的“头部”，同时让手指针在一个概念上的环上游走，会因为手的位置不同而不公平地惩罚不同条目；其他人则回应说，如果命中率更高，那么对单个条目的公平性并不重要。
  • 有人提出变体：在手的位置插入、保持插入点与手之间固定偏移、加入随机性，或采用多代方案。
  • 更广泛的讨论指出，任何确定性策略都会有对抗性工作负载，而生产环境中的缓存通常会引入随机性、采样或混合策略，以避免拒绝服务模式。