TinyUFO 与内存缓存

主线位置：缓存主线的旁边。缓存主线「写入存储」之后，存储满了要挤掉旧条目，pingora-cache 的淘汰管理器底下就是本页最后一节的 pingora-lru。TinyUFO 和 pingora-memory-cache 不在任何一条主线上：工作区里没有别的 crate 依赖它们，它们是给用户在钩子里缓存自己的东西用的（比如鉴权结果、DNS 查询）。

flowchart TB
  put["put 新键"] --> full{"放得下吗"}
  full -- 放得下 --> small["进 small 队尾"]
  full -- 放不下 --> ev["evict_to_limit"]
  ev --> one{"只挤掉一个"}
  one -- 否 --> small
  one -- 是 --> lfu{"草图比频率"}
  lfu -- 新键不输 --> small
  lfu -- 旧键更热 --> back["旧键回 small"]
  es["从 small 挤"] --> u1{"uses 大于 1"}
  u1 -- 是 --> mq["移进 main"]
  u1 -- 否 --> out["淘汰"]
  em["从 main 挤"] --> u2{"uses 减 1 前非 0"}
  u2 -- 是 --> mq
  u2 -- 否 --> out

三个 crate 的 src/ 规模和用途：

连接池的 LRU 不是这里的 pingora-lru：pingora-pool 有自己的 lru.rs，建在 crates.io 的 lru 上，见连接池。

实验平台：M2 Max、macOS 27、rustc 1.99.0，pingora 各 crate 0.9.0，tokio 钉在 1.53.2（原因见怎么读这一卷），release 构建，实验 crate 在 exp-pingora/comp-cache。

TinyUFO：两条队列，一个草图

crate 文档的第一句是「TinyLFU as the admission policy and S3-FIFO as the eviction policy」。拆开看源码，数据只有三样：每个条目一个 Bucket，两条队列放在 FiFoQueues 里，外加一个频率估计器：

pub struct Bucket<T> {
    uses: Uses,
    queue: Location,
    weight: Weight,
    data: T,
}

const SMALL_QUEUE_PERCENTAGE: f32 = 0.1;

struct FiFoQueues<T> {
    total_weight_limit: usize,

    small: SegQueue<Key>,
    small_weight: AtomicUsize,

    main: SegQueue<Key>,
    main_weight: AtomicUsize,

    // this replaces the ghost queue of S3-FIFO with similar goal: track the evicted assets
    estimator: TinyLfu,

    _t: PhantomData<T>,
}

• uses 是一个 AtomicU8，get 命中一次加一，封顶 USES_CAP = 3。注释说 8 位只用到 3，是为了 main 队列最坏情况下也能很快找到可挤的条目。
• queue 是一个 AtomicBool，记条目在 small 还是 main。
• 两条队列是 crossbeam 的无锁 SegQueue，里面只放键；条目本身在另一张并发表 Buckets 里：new 用 flurry 的并发 HashMap，new_compact 用分片的 crossbeam SkipMap，省内存、get 慢一个常数。
• small 的容量是 small_weight_limit：总容量的 10% 向下取整再加 1。

S3-FIFO 的论文里有三条队列：small、main，以及一条只记键的幽灵队列（ghost queue），记住刚从 small 被挤掉的键，它再来时直接进 main。TinyUFO 没有这第三条队列，上面那行注释说得明白：由 estimator（TinyLFU）顶替，「track the evicted assets」。

挤谁：small 看用过几次，main 用时钟

容量超了，evict_one 先看 small 是否已经超过它那 10%，超了从 small 挤，否则从 main 挤。evict_one_from_small 从队头弹一个键：

                    if bucket.uses.uses() > 1 {
                        // move to main
                        bucket.queue.move_to_main();
                        self.main.push(to_evict);
                        self.main_weight.fetch_add(weight as usize, SeqCst);
                        // continue until find one to evict
                        None
                    } else {
                        let data = bucket.data.clone();
                        let weight = bucket.weight;
                        buckets.remove(&to_evict);
                        Some(KV {

在 small 里至少被读过两次的，搬进 main 队尾，接着弹下一个；否则就是它了。新条目进来时 uses 是 0，所以「读过一次」的条目照样被挤掉。small 里所有条目都够格搬走、一个也没挤掉时，evict_one 再去 main 里挤。

evict_one_from_main 是一个时钟（CLOCK）：弹出队头，decr_uses 返回减一之前的值，大于 0 就放回队尾、再弹下一个，等于 0 才挤掉。uses 封顶 3，所以一个之后不再被读的条目最多被放回三次。

让不让进：草图只在挤掉一个时说话

admit 处理新键时先腾地方，再决定谁留下：

        let new_freq = self.estimator.incr(key);
        // ...
                let mut evicted = self.evict_to_limit(weight, buckets);
                // TODO: figure out the right way to compare frequencies of different weights across
                // many evicted assets. For now TinyLFU is only used when only evicting 1 item.
                let (key, data, weight) = if !ignore_lfu && evicted.len() == 1 {
                    // Apply the admission algorithm of TinyLFU: compare the incoming new item
                    // and the evicted one. The more popular one is admitted to cache
                    let evicted_first = &evicted[0];
                    let evicted_freq = self.estimator.get(evicted_first.key);
                    if evicted_freq > new_freq {
                        // put it back
                        let first = evicted.pop().expect("just check non-empty");
                        // return the put value
                        evicted.push(KV { key, data, weight });
                        (first.key, first.data, first.weight)
                    } else {
                        (key, data, weight)
                    }

几个和「TinyLFU 准入」字面意思不一样的地方：

• 频率只在 put 时记。 incr 只在 admit 里调，get 命中只动 uses，不碰草图。函数开头的注释写了原因：草图因此主要记的是不太热的键，对它们更准；也就不需要 W-TinyLFU 那样另开一个窗口缓存。用「缺了就 put」的方式用缓存时，草图记的其实是每个键缺过几次。
• 只在恰好挤掉一个时才比。 腾地方挤掉了两个以上（新条目权重大），直接收下新条目，注释里的 TODO 说还没想好怎么比不同权重的多个条目。
• 输了的新键不进缓存，赢了的旧键回到 small。 旧条目以 uses = 0、Location::new_small() 重新插入，原来在 main 里也一样；被拒的新条目出现在 put 的返回值里，调用方要是只看返回值，会以为它被「挤掉」了。
• force_put 传 ignore_lfu = true，跳过这一步，保证放进去。文档注释说命中率大约低 0.5 个百分点以内，下面的实验在 1 万个键时测到 0.7 到 1.1 个点，100 万个键时 0.7 到 2.4 个点。

草图有多大

TinyLfu 是一个 Count-Min 草图（Count-Min Sketch），注释写着「bare-minimum TinyLFU with CM-Sketch, no doorkeeper for now」，8 位计数器，每 cache_size * 8 次 incr 把所有计数器右移一位（老化）。尺寸由 optimal_paras 按误差 1/n、失败概率 1/n 算：

    fn optimal_paras(items: usize) -> (usize, usize) {
        use std::cmp::max;
        // derived from https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
        // width = ceil(e / ε)
        // depth = ceil(ln(1 − δ) / ln(1 / 2))
        let error_range = 1.0 / (items as f64);
        let failure_probability = 1.0 / (items as f64);
        (
            max((std::f64::consts::E / error_range).ceil() as usize, 16),
            max((failure_probability.ln() / 0.5f64.ln()).ceil() as usize, 2),
        )
    }

宽是 e·n，深是 log₂ n，每格一个字节。这里的 n 是 TinyUfo::new(total_weight_limit, estimated_size) 的第二个参数。它的文档注释叫它「the given size limit of the ghost queue」，可代码里 TinyUFO 没有幽灵队列，estimated_size 只被传给 TinyLfu::new（草图尺寸和老化窗口）和 Buckets::new_fast（哈希表预分配）。new_compact 的草图按 estimated_size / 100 算。

不存键

TinyUfo<K, T> 的键类型 K 只出现在 PhantomData 里。get 和 put 的第一步都是 self.random_status.hash_one(key)，此后一切按这个 u64 走；被挤出来的 KV 的 key 字段注释也写着「just the hash of it」。

实验：同一条 Zipf 访问序列

comp-cache 的 hit_ratio：用逆 CDF 生成 Zipf 分布的访问序列（固定的 xorshift 种子，键先过一遍 splitmix64），同一条序列喂给五个缓存，每个都是「get 不中就放进去」：

• TinyUFO：TinyUfo::new(size, size)，不中时 put；
• force_put：同上，不中时 force_put（RTCache 用的就是它）；
• pingora-lru<16>：Lru::<(), 16>，命中时 promote，不中时 admit 再 evict_to_limit，这是 pingora-cache 默认的用法；
• pingora-lru<1>：同上，只有一个分片；
• lru crate：crates.io 的 lru 0.18.5，get / push。

1 万个键、500 万次访问、Zipf 指数 1.0（out/hit_10k.txt，单次运行；序列固定，结果每次相同）：

items=10000 zipf=1 requests=5000000
size	TinyUFO	force_put	pingora-lru<16>	pingora-lru<1>	lru crate
0.5%	45.06%	44.34%	29.60%	30.94%	30.94%
1.0%	52.22%	51.27%	38.48%	39.06%	39.06%
5.0%	68.77%	67.87%	58.50%	58.67%	58.67%
10.0%	75.89%	74.95%	67.46%	67.57%	67.57%
25.0%	85.25%	84.49%	79.87%	79.90%	79.90%

100 万个键、2000 万次访问、Zipf 指数 1.0（out/hit_1m.txt）：

items=1000000 zipf=1 requests=20000000
size	TinyUFO	force_put	pingora-lru<16>	pingora-lru<1>	lru crate
0.5%	62.31%	60.80%	52.94%	52.95%	52.95%
1.0%	66.94%	65.29%	58.51%	58.51%	58.51%
5.0%	77.60%	75.87%	71.84%	71.84%	71.84%
10.0%	82.05%	80.61%	77.82%	77.82%	77.82%
25.0%	87.81%	87.15%	85.93%	85.93%	85.93%

• pingora-lru<1> 和 lru crate 每一格都相同。 两者都是精确的 LRU，同一条序列下行为完全一样，这一列可以当作实验本身的校验。
• TinyUFO 比 LRU 高多少，看缓存相对于键空间有多小。 1 万个键时 0.5% 的缓存（50 个条目）高 14.1 个点，25% 时高 5.4 个点；100 万个键时依次是 9.4 和 1.9 个点。缓存越小，「只来一次的键把热键挤出去」越伤 LRU，small 队列和准入挡住的正是这些键。
• 和 README 的表对得上。 README 写 Zipf 1、0.5% 时 TinyUFO 45.26%、比 LRU 高 14.21 个点（它的 benchmark 用 rand_distr 的 Zipf、1 万个键、500 万次，每次随机），这里是 45.06% 和 14.12 个点。README 是项目方的数据，这一次在本机复现了。
• 分片只在缓存很小的时候有代价。 1 万个键、0.5% 时 16 个分片比 1 个分片低 1.3 个点：50 个条目分到 16 个分片里，每片三四个，「最近最少用」只在片内成立。100 万个键时 0.5% 是 5000 个条目，每片三百多个，差别在 0.01 个点以内。
• Zipf 指数 0.9 时结论一样，TinyUFO 在 1 万键 0.5% 时高 14.1 个点，见 out/hit_10k.txt。

pingora-memory-cache：TinyUFO 加 TTL

MemoryCache<K, T> 里只有一个 TinyUfo<u64, Node<T>> 和一个哈希器，Node 是值加一个可选的 expire_on: Option<Instant>：

• new(size) 就是 TinyUfo::new(size, size)，size 是条目数，因为 put 的权重永远是 1（注释「weight is always 1 for now」）。按上面的草图公式，MemoryCache::new(1_000_000) 光草图就是 54 MB。
• put 的 TTL 是 Some(Duration::ZERO) 时什么也不做；None 表示永不过期。
• get 返回 (Option<T>, CacheStatus)：过期的条目返回 (None, Expired)，但不删除它，它照样占着位置，等 TinyUFO 自己把它挤掉（源码末尾的 // TODO: evict expired first）。读到一个过期条目也会给它的 uses 加一，过期的热键因此可能被搬进 main。
• get_stale 把过期的值也还回来，状态是 Stale(过期了多久)。

RTCache：读穿与查询合并

RTCache<K, T, CB, S> 不提供 put，缺了就调用户实现的 Lookup::lookup（一个没有 self 的关联函数，extra 用来传额外参数）去查，查到的值连同 TTL 放进缓存。同一个键同时有很多请求缺失时，只有一个去查，其余的等它，这叫查询合并（lookup coalescing）。

合并靠一张 RwLock<HashMap<u64, Arc<CacheLock>>>，CacheLock 是一个初始 0 个许可的 Semaphore 加一个创建时间。get 缺失后：

1. 读锁下查这张表。有锁，且没超过 lock_age，自己就是读者；锁太老了，自己去查，但不写缓存。
2. 没有锁，拿写锁再查一次，还没有就插一把新锁，自己是写者。
3. 读者等 Semaphore::acquire。设了 lock_timeout 就用 pingora_timeout::timeout 包着等，等超时就自己去查，查到的值直接返回，不写缓存。等到了，再读一次缓存，命中返回 LockHit。
4. 写者调 lookup，成功就 force_put（不让 TinyLFU 拒掉它，读者马上要读），然后：

            if let Some(my_write) = my_write {
                /* add permit so that reader can start. Any number of permits will do,
                 * since readers will return permits right away. */
                my_write.lock.add_permits(10);

                {
                    // remove the lock from locker
                    let mut lockers = self.lockers.write();
                    lockers.remove(&hashed_key);
                } // write lock dropped here
            }

放许可、删锁，都在 lookup().await 之后，而且只有写者自己做。

实验：合并，以及被取消的写者

comp-cache 的 rtcache：lookup 睡 100 ms 后返回 key * 10，并给一个全局计数器加一。第一段 100 个任务同时 get 同一个键；后三段先让第一个调用方用 tokio::time::timeout(10 ms, ..) 包着 get，在它的 lookup 进行到一半时取消，然后对同一个键再 get 三次，每次外面套 2 s 的看门狗（out/rtcache.txt）：

coalesce: 100 concurrent gets, lookups=1, statuses={"LockHit": 99, "Miss": 1}, took 103.281583ms
lock_age=None lock_timeout=None: first get cancelled: true
  get #0: still waiting after 2.002091917s, lookups so far 1
  get #1: still waiting after 2.003114208s, lookups so far 1
  get #2: still waiting after 2.002875334s, lookups so far 1
lock_age=None lock_timeout=Some(300ms): first get cancelled: true
  get #0: Some(70) Miss after 416.946791ms, lookups so far 2
  get #1: Some(70) Miss after 408.124584ms, lookups so far 3
  get #2: Some(70) Miss after 416.251917ms, lookups so far 4
lock_age=Some(200ms) lock_timeout=None: first get cancelled: true
  get #0: Some(70) Miss after 103.100375ms, lookups so far 2
  get #1: Some(70) Miss after 102.154875ms, lookups so far 3
  get #2: Some(70) Miss after 102.05225ms, lookups so far 4

• 合并按设计工作：100 个并发请求只查了一次，一个 Miss、99 个 LockHit，总共 103 ms。
• 写者的 future 在 lookup().await 处被 drop，后面那段放许可、删锁的代码不会执行。锁留在表里，Semaphore 永远是 0 个许可。
• 两个参数都不设：之后这个键的每个 get 都永远等下去。
• 设了 lock_timeout：每次先白等 300 ms（pingora_timeout 的 10 ms 粒度让它实际等到 308 ms 上下，见超时），再自己查 100 ms，而且超时这条路径不写缓存，所以每次都是 Miss，缓存永远填不上。
• 设了 lock_age：锁太老了以后每个请求都自己查，同样不写缓存，同样永远 Miss；锁也没人删，因为删锁的只有写者。

异步代码里 future 被取消很常见：外面套一层超时、select! 的另一个分支先完成，都会 drop 正在 lookup 的写者。一次取消就可能让这个键再也缓存不上。0.9.0 之后 main 上没有改 pingora-memory-cache 的提交。要绕开，可以把 get 放进 tokio::spawn 里，让它不随请求一起被取消。

pingora-lru：给缓存淘汰用的分片 LRU

Lru<T, const N: usize> 是 N 个 RwLock<LruUnit<T>>，键是调用方算好的 u64，get_shard 就是 key % N。每个 LruUnit 是一张 hashbrown 表（键到 Box<LruNode>）加一条 LinkedList：链表节点放在一个连续的 Vec 里，前后指针是 u32 下标（0.9.0 的 74675bc 从 usize 改成 u32），头尾各一个哨兵节点。权重和条目数是外面的几个原子变量。

和 TinyUFO 不同的几处：

• admit 只插入不淘汰，返回分片号；淘汰要调用方接着调 evict_to_limit，被挤掉的条目以 Vec<(T, usize)> 返回，由调用方去删存储里的东西。
• promote 每次都拿分片的写锁。promote_top_n 先用读锁看是不是已经在前 n 个，文档注释说按项目自己的 benchmark，在每片十万条目以上的规模反而更慢，建议直接用 promote。
• 淘汰从哪个分片挤，靠「二选一」：

            let start = if N <= 1 {
                0
            } else {
                let a = rng.gen_range(0..N);
                let b = rng.gen_range(0..N);
                if self.shard_len(a) >= self.shard_len(b) {
                    a
                } else {
                    b
                }
            };

随机挑两个分片，挤条目多的那个的队尾。所以这是一个近似的 LRU：被挤掉的是某个分片里最旧的，不一定是全局最旧的。上面实验里 pingora-lru<16> 比 <1> 低的那一点，就是这个近似的代价。pingora-pool 的 LRU 给每个节点一个全局序号、一次锁住全部分片比出全局最旧的，见连接池；两者的取舍方向相反。

pingora-cache 怎么用它（eviction::lru::Manager 把它包成 EvictionManager，async_lru 是一个每分片一个 actor 的版本），见存储与淘汰。

动脑筋答案

comp-cache 的 hit_ratio mem 用一个计数的全局分配器量建出来那一刻的净分配（out/mem.txt）：

new(10000): TinyUfo::new 522731 B, new_compact 164696 B, pingora_lru::Lru<16>::with_capacity 438912 B
new(100000): TinyUfo::new 6729334 B, new_compact 1627670 B, pingora_lru::Lru<16>::with_capacity 3828608 B
new(1000000): TinyUfo::new 71154089 B, new_compact 16381234 B, pingora_lru::Lru<16>::with_capacity 51651968 B

TinyUfo::new(1_000_000, 1_000_000) 空着就分配了 71 MB。草图：宽 ⌈e × 10⁶⌉ = 2718282，深 ⌈log₂ 10⁶⌉ = 20，每格一个 AtomicU8，共 54365640 字节，占 76%；剩下约 16.8 MB 是哈希表等其他结构。new_compact 的草图按 n/100 算，总共 16 MB。pingora-lru 的一列是 with_capacity(n, n / 16 + 1) 的预分配（每个分片的 hashbrown 表和链表）。MemoryCache::new(size) 就是 TinyUfo::new(size, size)，所以「先开一个一百万条目的缓存备着」本身就要七十多兆。

小结

• TinyUFO = small（一成）和 main 两条无锁 FIFO + 每条目一个封顶 3 的 uses + 一个 Count-Min 草图；草图顶替了 S3-FIFO 的幽灵队列。
• small 里至少读过两次的搬进 main，main 用时钟法放回或挤掉；TinyLFU 只在恰好挤掉一个时比频率，频率只在 put 时记。
• 只存 64 位哈希，不存键；estimated_size 决定草图大小，一百万时空缓存就有 71 MB。
• Zipf 1、缓存为键空间 0.5% 时，TinyUFO 比 LRU 高 14 个点（1 万键）、9 个点（100 万键）；force_put 比 put 低 0.7 到 2.4 个点；README 的数在本机复现。
• MemoryCache 是 TinyUFO 加 TTL，过期不删；RTCache 合并同键查询，但写者被取消后锁永远留下，这个键要么永远等、要么永远 Miss。
• pingora-lru 按 key % N 分片、二选一挑分片淘汰，是近似 LRU，admit 不淘汰、由调用方调 evict_to_limit；给 pingora-cache 的淘汰管理器用。