S3-FIFO 缓存

本库包含一个非线程安全的 S3-FIFO 缓存实现，根据 https://jasony.me/publication/sosp23-s3fifo.pdf 中的论文。

以下是论文的摘要。

作为缓存替换算法，FIFO 具有许多吸引人的特性，如简单性、速度、可扩展性和快速友好性。FIFO 最突出的批评是其低效率（高未命中率）。在这项工作中，我们展示了一个简单、可扩展的基于 FIFO 的算法（S3-FIFO），包含三个静态队列。在 14 个数据集的 6594 个缓存跟踪上进行评估，我们发现 S3-FIFO 在跟踪上的未命中率低于最先进的算法。此外，S3-FIFO 的效率是稳健的——在 14 个数据集的 10 个数据集中，它具有最低的平均未命中率。FIFO 队列使 S3-FIFO 能够在 16 个线程时比优化后的 LRU 提供高 6 倍的吞吐量。我们的洞察是，在偏斜的工作负载中，大多数对象在短时间内只会被访问一次，因此提前驱逐它们（也称为快速降级）至关重要。S3-FIFO 的关键是小型 FIFO 队列，它过滤掉大多数对象进入主缓存，从而提供保证的降级速度和高降级精度。

use s3_fifo::{S3FIFO, S3FIFOKey};

// The cached value must be Clone.
// Hash is optional and allows using the S3FIFOKey struct
#[derive(Clone, Hash)]
struct Foobar { a: i32 }

// Create a cache with a capacity of 128 (small: 12, main: 115, ghost: 115)
let mut cache = S3FIFO::new(128);
let value = Foobar { a: 1 };
let key = S3FIFOKey::new(&value);

// Check if the item is in the cache before inserting
if let None = cache.get(&key) {
    cache.put(key.clone(), value);
    assert!(cache.get(&key).is_some());
}

// If your value is not Hash, then supply a key yourself that implements PartialEq
// let mut hash_cache: S3FIFO<S3FIFOKey<Foobar>, Foobar> = S3Fifo::new(1234);
#[derive(Clone)]
struct Abc {}
let mut custom_cache: S3FIFO<u32, Abc> = S3Fifo::new(1234)
cache.put(42, Abc);
cache.get(&42);