S3-FIFO · Reference

S3-FIFO 一页速查表

核心目标:快速淘汰 one-hit wonders,低成本保留真正热点。

三个队列

S · Small

约 10% 数据容量;新对象的试用区。

M · Main

约 90% 数据容量;已证明会复用的对象。

G · Ghost

约等于 M 的条目数;只存被 S 淘汰对象的 key。

读写与淘汰

  1. 命中 S/M:freq = min(freq + 1, 3),不重排。
  2. 新 key miss:先腾空间,再插入 S,freq = 0
  3. Ghost hit:先腾空间,从 G 删除 key,插入 M。
  4. S 淘汰:freq > 1 则进 M,否则数据淘汰、key 进 G。
  5. M 淘汰:freq > 0 则减 1 并重插队头,否则真正淘汰。

读论文时记住

效率来源

Quick demotion + Ghost 纠错 + 有限续命。

扩展性来源

命中不维护全局精确顺序,FIFO 可用环形缓冲区。

主要反例

大量对象只访问两次,且第二次晚于离开 S。

返回交互课程 · 查看原论文