[Home - S3-FIFO: Simple, scalable and efficient caching (s3fifo.com)](https://s3fifo.com/) ## Introduction S3-FIFO：simple,scalable,staic queue LRU的问题： - 每个对象需要两个指针，存储开销 - 它不可扩展，因为每次缓存命中都需要将请求的对象提升到由锁定保护的队列的头部 大部分数据只出现一次(one hit wonder)，快速降级是十分重要的 跟其他的驱逐算法比十分高效 S3FIFO是无锁实现，

FIFO的拓展性极好，但是不够高效
FIFO的限制是无法保留经常访问的对象，有研究尝试保留这些经常访问的对象，但是性能无法达到sota，作者的见解是one hit wonder十分频繁，快速删除大多数新对象是十分重要的

Design and implementation

design

3个FIFO队列

  • small S 占用10%的空间
  • mian M 占用90%的空间
  • ghost G 和M存储相同数量的元素（无数据）
    使用每个对象两位计数器来追踪对象访问状态，最大是3，当cache hit，计数器加一。注意，大多数对流行对象的请求不需要更新
    cache write
    新对象如果不在G就插入S，如果在G就插入M
    当S满了，队尾的对象如果访问超过一次就移动到M，否则移动到G。移动时清空访问位
    M使用两位计数来跟踪访问信息，至少访问过一次的对象将被重新插入，并将一位设置为0
    image.png

image.png
image.png
small FIFO可以快速驱逐one hit wonder以便它们不会占用cache太久

Implementation

基于链表或者ring buffer
基于链表的实现可以更轻松地添加到现有的基于 LRU 的缓存中。然而，它具有三个缺点。首先，它每个对象使用两个指针。对于具有微小对象的工作负载 ，这会带来巨大的存储开销。其次，遍历队列需要随机内存访问。第三，基于链表的实现中的逐出和插入需要昂贵的原子操作：compare_and_set，这降低了可伸缩性。

相比之下，基于环缓冲区的实现开销较小且可扩展性更强，但可能与现有的基于 LRU 的缓存系统不兼容。当使用环形缓冲区实现 S3-FIFO 时，环形缓冲区维护 FIFO 顺序，每个槽存储对象或指针。驱逐需要碰撞环形缓冲区中的尾部指针。尽管具有较低的存储开销和更高的可扩展性，但当工作负载包含许多删除操作时，基于环缓冲区的实现会浪费空间，因为已删除对象的空间在驱逐之前无法重用

ghost FIFO G可以作为索引结构的一部分，可以在基于桶的hash表中存储指纹和插入时间，当对象被其他FIFO队列请求或者遇到hash冲突时，移出ghost对象。