Abstract

FIFO 优势：简单，速度快，可扩展性高（无锁），闪存友好；

FIFO 劣势：缓存缺失率高。

Insight：大多数对象在短时间内只会被访问一次，将这些对象尽早地从缓存中驱逐很关键。

Introduction

缓存系统指标：效率、性能和可扩展性；
现有缓存替换算法主要聚焦于效率，即提高缓存命中率，因此往往基于 LRU 链表来做。然而这有两个问题；
- 每个对象需要额外的两个指针，对于小对象来说带来了不可忽略的存储开销；
- 每次命中需要进行加锁、显式提升，导致可扩展性差。
针对以上两个问题，现有方案往往牺牲效率而提高吞吐和可扩展性，比如使用 CLOCK 或者 FIFO。
仅使用 FIFO 队列，能否实现高效率呢？

缓存工作集往往呈现 28 定律，大部分数据是零重用对象（6594 个 trace 中的中位数一次性访问对象比率为 26%，sequences that comprise 10% of the unique objects in each trace, the median one-hit-wonder ratio skyrockets to 72%），对这些数据进行快速降级提高缓存命中率（2Q，ARC，S3LRU），而对其他重用数据，进行懒惰提升提高可扩展性（CLOCK）。
原型系统 cachelib 上，S3FIFO 在吞吐和可扩展性上，远远优于 LRU。

Design

缓存命中对哈希表加读锁，通过哈希表获得 key 对应的 value；

缓存缺失时，先对哈希表加写锁，将 key->value 对加入哈希表中；其次，维护缓存对象优先级

插入 S 或者 M 的头部：使用 CAS 维护链表顺序；

/* Linked list implemenation */
template <typename T, AtomicDListHook<T> T::*HookPtr>
void AtomicDList<T, HookPtr>::linkAtHead(T& node) noexcept {
  std::shared_lock lock(head_mutex); // 该读锁仅是为保证 remove(T& node) 存在时的正确性
  
  setPrev(node, nullptr);

  T* oldHead = head_.load();
  setNext(node, oldHead);

  while (!head_.compare_exchange_weak(oldHead, &node)) {
    // head_ == oldHead，没有被其他线程抢先，直接将 head 赋值为 &node，退出 while；
    // 否则，head_ != oldhead，被其他线程抢先执行，得先将 oldhead 赋值为新 head_，多次 
    // while 循环直到将本线程插入的 node 放到链表头部
    setNext(node, oldHead);
  }

  if (oldHead == nullptr) {
    // this is the thread that first makes head_ points to the node
    // other threads must follow this, o.w. oldHead will be nullptr
    XDCHECK_EQ(tail_, nullptr);

    T* tail = nullptr;
    tail_.compare_exchange_weak(tail, &node);
  } else {
    setPrev(*oldHead, &node);
  }

  size_++;
}

驱逐 S 或者 M 的尾部：同样使用 CAS。

template <typename T, AtomicDListHook<T> T::*HookPtr>
T* AtomicDList<T, HookPtr>::removeTail() noexcept {
  T* tail = tail_.load();
  if (tail == nullptr) {
    // empty list
    return nullptr;
  }
  T* prev = getPrev(*tail);

  // if tail has not changed, the prev is correct
  while (!tail_.compare_exchange_weak(tail, prev)) {
    prev = getPrev(*tail);
  }

  // if the tail was also the head
  if (head_ == tail) {
    T* oldHead = tail;
    head_.compare_exchange_weak(oldHead, nullptr);
  }

  setNext(*tail, nullptr);
  setPrev(*tail, nullptr);

  size_--;

  return tail;
}

FIFO 的缓存插入和缓存驱逐仅操作链表头部或尾部，CAS 可以保证原子；而如果 unlink 链表中间，无法保证原子，必须加写锁。因此，S3FIFO 具有简单（代码量少），速度快（无显式缓存提升），可扩展性高（无锁）。

Evaluation

效率：命中率
性能：吞吐量

在单核 CPU 上，S3FIFO 只需更少的缓存队列维护操作，吞吐比 LRU 更高；在多核 CPU 上，S3FIFO 在缓存命中或缓存缺失过程中无需加锁，可扩展性更高，吞吐基本随核心数增加而线性增加。
闪存友好

对于 DRAM + SSD 的缓存部署，S3FIFO 可以将队列 S 维护的缓存数据放置在 DRAM，而队列 M 维护的缓存数据放置在 SSD，队列 S 的快速降级可以减少 SSD 缓存的写入流量。

（可能因为 wiki 数据集 size 分布太广泛，左图结果有点不太合理；而右图结果相对较为合理）

Discussion

为什么 S3FIFO 有效？
- 类似于 ARC + S3LRU，能够快速降级零重用对象，抵抗扫描工作负载；
- S3FIFO 的降级速度是可控的，队列 S 越长，降级越慢，可人为控制；而 ARC 可能由于缓存容量太小，对象的平均重用时间较长，导致热链 ghost 命中过多而冷链过短，间接导致降级速度过快；WTinyLFU 会由于热链对象过热导致冷链始终降级；
S3FIFO 自适应后怎么样？

效果一般，大多数情况下不如 S3FIFO-10%。
- 过去不代表未来；
- 自适应的调整粒度难以 one-for-all（1个，2个，…）；

个人理解：

由于队列 M 的 FIFO-reinsertion，可能具有更长的尾延时（3->0）。（CLOCK）

zztaki

S3fifo (SOSP 23)

Abstract

Introduction

Design

Evaluation

Discussion