SIEVE 缓存淘汰算法

定义

SIEVE 是发表于 NSDI 2024 的缓存淘汰算法,由 Yazhuo Zhang、Juncheng Yang 等研究者提出,目标是在 Web 类工作负载上以极简的实现取得优于 LRU 的命中率。

原理

SIEVE 在一条 FIFO 队列上为每个对象维护一个访问位,并用一个「手指」(hand)指针从队尾向队头扫描:命中对象只需置位,无须移动位置;淘汰时指针跳过访问位为 1 的对象(将其清零并原地保留),驱逐第一个访问位为 0 的对象。这实现了「懒惰晋升、快速降级」——新对象若未被再次访问会很快被清出。

优缺点

优点是命中路径完全无锁移动、并发友好,代码量极小,且在大量真实 Web 缓存踪迹上命中率优于 LRU 乃至部分复杂算法;缺点是对循环扫描等特定负载并非最优,也不直接处理对象大小差异。

应用

算法发布后迅速被多个开源缓存库实现,并被用作构建更复杂淘汰策略的基础组件。