返回文章列表

用 Rust 从零实现 LFU 与 TinyLFU:比 LRU 更抗扫描的缓存

647 字·5 分钟阅读
Rust从零造轮子缓存

前面写过 LRU。它能解决大部分场景,但有一个众所周知的弱点——一次全表扫描就够了。

原因不难理解:扫描产生的访问也"刚发生过",在 LRU 眼里它们和真正的热数据没区别。十万条扫描记录会把真正的热点全部挤出缓存。

这篇从 LFU 开始,一路写到工业界实际在用的 TinyLFU 方案。


LFU 的直觉:按频率淘汰

LFU(Least Frequently Used)的思路很直接:淘汰访问次数最少的那个。

pub struct LfuEntry<V> {
    value: V,
    freq: u64,
    last_access: std::time::Instant,
}

朴素的实现:维护一个 HashMap<K, LfuEntry<V>>,淘汰时遍历找最小 freq——O(n),太慢。

要 O(1) 淘汰,需要按频率分桶 + 双向链表:

freq=1: [key A] <-> [key B]
freq=2: [key C]
freq=5: [key D] <-> [key E] <-> [key F]
         ↑ 每个 freq 一个双向链表,链表内按访问时间排序
use std::collections::HashMap;
 
pub struct FreqBucket<K> {
    freq: u64,
    keys: std::collections::LinkedList<K>,
}
 
pub struct LfuCache<K, V> {
    map: HashMap<K, (V, u64)>,          // key -> (value, freq)
    buckets: std::collections::BTreeMap<u64, Vec<K>>, // freq -> keys
    capacity: usize,
}

用 BTreeMap<freq, keys> 而不是链表,是因为需要快速找到"最小 freq"。 BTreeMap 的 first_key_value() 就是 O(log n) 拿到最小频率。

访问时提升频率:

impl<K: std::hash::Hash + Eq + Clone, V> LfuCache<K, V> {
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let (_, freq) = self.map.get(key)?;
        let freq = *freq;
        let key_clone = key.clone();
 
        // 从旧桶移除
        if let Some(keys) = self.buckets.get_mut(&freq) {
            keys.retain(|k| k != &key_clone);
            if keys.is_empty() {
                self.buckets.remove(&freq);
            }
        }
 
        // 加入新桶
        self.buckets.entry(freq + 1).or_default().push(key_clone);
        self.map.get_mut(key).unwrap().1 = freq + 1;
 
        self.map.get(key).map(|(v, _)| v)
    }
 
    pub fn put(&mut self, key: K, value: V) {
        if self.map.contains_key(&key) {
            self.map.get_mut(&key).unwrap().0 = value;
            self.get(&key);
            return;
        }
 
        if self.map.len() >= self.capacity {
            self.evict();
        }
 
        self.buckets.entry(1).or_default().push(key.clone());
        self.map.insert(key, (value, 1));
    }
 
    fn evict(&mut self) {
        // 找最小 freq 的桶
        let (&min_freq, _) = self.buckets.iter().next().unwrap();
        let keys = self.buckets.get_mut(&min_freq).unwrap();
 
        if let Some(victim) = keys.pop() {   // 同频率内淘汰最久未访问的
            self.map.remove(&victim);
        }
        if keys.is_empty() {
            self.buckets.remove(&min_freq);
        }
    }
}

注意淘汰时是"同一频率内,淘汰最先进入桶的"——这就把 LRU 的语义融进了 LFU,避免同频率下随机淘汰。

LFU 的两个硬伤

1. 老热点永远不走(cache pollution)。 一个 key 在很久以前被访问了 10 万次,之后再也不用了,但它的 freq 是 10 万——永远排在最前面,把真正的新热点挤掉。

2. 新热点进不来。 新 key 的 freq 从 1 开始,而缓存里随便一个 key 的 freq 都可能是几十。新 key 刚放入就立刻被淘汰。

这两个问题的本质是:freq 是一个只增不减的绝对量,无法反映"最近"的访问模式。

解法一:频率老化(aging)

定期把所有 freq 减半:

    /// 每 N 次访问做一次老化,让"老热点"衰减
    fn maybe_age(&mut self) {
        self.access_count += 1;
        if self.access_count % self.age_interval != 0 {
            return;
        }
 
        let mut new_buckets = std::collections::BTreeMap::new();
 
        for (freq, keys) in std::mem::take(&mut self.buckets) {
            let new_freq = freq / 2;
            new_buckets.entry(new_freq).or_insert_with(Vec::new).extend(keys);
        }
 
        // 更新 map 里的 freq
        for (freq, keys) in &new_buckets {
            for k in keys {
                if let Some((_, f)) = self.map.get_mut(k) {
                    *f = *freq;
                }
            }
        }
 
        self.buckets = new_buckets;
    }

减半是把"最近一段时间的访问量"估成"频率" ——这和 Linux 的 load average、TCP 的 RTT 平滑是同一类做法:用指数衰减把历史累积变成"近期加权"。

解法二:准入策略(admission)

与其"放进来再淘汰",不如在放入时就决定它配不配进缓存。

这就是 TinyLFU 的核心思想。

LRU 的问题是"先放进来再说",TinyLFU 改成"先评估再决定"。 这个视角的转变,是它性能更好的根本原因。

TinyLFU:用一张小草图记下所有访问

TinyLFU 的洞察是:判断一个 key 该不该进缓存,只需要知道它的访问频率,不需要知道具体是什么 key。

于是可以用一个**固定大小的频率草图(frequency sketch)**来记录所有 key 的访问次数,与缓存容量解耦。

这里用的是 Count-Min Sketch:一个二维计数器数组 + 多个哈希函数。

pub struct CountMinSketch {
    /// table[i][j],i 是哈希函数序号
    table: Vec<Vec<u8>>,
    /// 每个哈希函数的种子
    seeds: Vec<u64>,
    /// 总访问次数,用于触发老化
    sample_size: u64,
    /// 老化阈值
    reset_threshold: u64,
}

为什么每个计数器只用 u8? 因为频率不需要精确值——超过 255 就饱和在 255。

这个饱和特性恰好解决了"老热点问题":一个 key 无论访问了 100 万次还是 255 次,在草图里都是 255。这样新热点只要访问了几十次,就能在评估中胜出。

const COUNTER_MAX: u8 = 15;   // 实际实现常用 4 bit,省内存
 
impl CountMinSketch {
    pub fn new(depth: usize, width: usize) -> Self {
        Self {
            table: vec![vec![0u8; width]; depth],
            seeds: (0..depth).map(|i| 0x9E37_79B9_7F4A_7C15u64.wrapping_mul(i as u64 + 1)).collect(),
            sample_size: 0,
            reset_threshold: (width * 10) as u64, // 经验值:宽度的 10 倍
        }
    }
 
    pub fn increment(&mut self, key: &[u8]) {
        for i in 0..self.table.len() {
            let idx = self.hash(i, key) % self.table[i].len();
            // 饱和递增
            if self.table[i][idx] < COUNTER_MAX {
                self.table[i][idx] += 1;
            }
        }
 
        self.sample_size += 1;
        if self.sample_size >= self.reset_threshold {
            self.reset();
        }
    }
 
    /// 估计频率:取所有哈希位置上计数器的**最小值**
    pub fn estimate(&self, key: &[u8]) -> u8 {
        (0..self.table.len())
            .map(|i| {
                let idx = self.hash(i, key) % self.table[i].len();
                self.table[i][idx]
            })
            .min()
            .unwrap_or(0)
    }
 
    /// 老化:所有计数器右移一位(相当于减半)
    fn reset(&mut self) {
        for row in &mut self.table {
            for c in row.iter_mut() {
                *c >>= 1;
            }
        }
        self.sample_size = self.sample_size / 2;
    }
 
    fn hash(&self, i: usize, key: &[u8]) -> usize {
        let mut h = self.seeds[i];
        for &b in key {
            h ^= b as u64;
            h = h.wrapping_mul(0x100_0000_01b3);
        }
        h as usize
    }
}

为什么取最小值? 这是 Count-Min Sketch 的精髓。多个哈希可能把不同的 key 映射到同一格,导致计数偏高(不会偏低)。取最小值就是把"被污染的格"的影响去掉——估计值永远是真实值的上界,取 min 让上界尽量紧。

reset 里的 >>= 1 就是老化。 它让所有频率周期性减半,让"老热点"衰减。这一步和 LFU 的 aging 是同一个目的,但代价只有遍历一个固定大小的数组。

Count-Min Sketch 用 4 倍于"预计 key 数"的内存,就能以很小的误差估计任意 key 的频率。 这是 TinyLFU 能做到"和缓存容量解耦"的关键。

W-TinyLFU:窗口 + 分段 LRU

只靠频率草图还是不够。TinyLFU 的完整形态叫 W-TinyLFU(Window TinyLFU),结构是:

       新的访问
          │
          v
   ┌─────────────┐
   │  Window LRU │  占 1% 容量
   │  (新 key 先落这里) │
   └──────┬──────┘
          │ 淘汰出 window 时
          v
   ┌──────────────┐   ┌──────────────┐
   │   Main (80%) │   │  Probation   │
   │   SLRU       │<--│  (20%)       │
   └──────────────┘   └──────────────┘
          │                  ^
          │                  │
          └── 淘汰时和候选者比频率 ──┘

三个部件各司其职:

  1. Window LRU:新来的 key 先进这里,给它们一个被观察的机会。这解决了 LFU"新热点进不来"的问题。
  2. Main SLRU:主力存储区,分两段(Protected 80% + Probation 20%)。
  3. 频率草图:决定"从 window 淘汰的 key,能不能挤掉 main 里的候选"。

准入判断是整个设计的核心:

pub struct WTinyLfu<K, V> {
    window: LruCache<K, V>,
    probation: LruCache<K, V>,
    protected: LruCache<K, V>,
    sketch: CountMinSketch,
    window_capacity: usize,
}
    /// 从 window 淘汰一个 key 时,判断它能不能进 main
    fn try_admit(&mut self, candidate: K, value: V) -> Option<(K, V)> {
        // main 满了,从 probation 的尾部找一个"受害者"
        let Some((victim_key, _)) = self.probation.peek_lru() else {
            // main 还空着,直接放
            self.probation.put(candidate, value);
            return None;
        };
 
        // 关键:比较频率
        let victim_freq = self.sketch.estimate(&encode(&victim_key));
        let candidate_freq = self.sketch.estimate(&encode(&candidate));
 
        if candidate_freq > victim_freq {
            // 候选者更热,挤掉受害者
            let (vk, vv) = self.probation.pop_lru().unwrap();
            self.probation.put(candidate, value);
            Some((vk, vv))  // 返回被淘汰的,让调用方清理
        } else {
            // 候选者不够热,直接丢弃
            Some((candidate, value))
        }
    }

这个"候选 vs 受害者"的比较,就是 TinyLFU 的精髓所在。 它不再是"谁最老就淘汰谁",而是"谁更可能被再次访问,就留下谁"。

W-TinyLFU 用 Window 解决"新热点准入",用 Count-Min Sketch 解决"频率估计",用 SLRU 解决"扫描攻击",三个问题各有一个对策。

get/put 的完整路径

    pub fn get(&mut self, key: &K) -> Option<&V> {
        // 所有访问都记进草图(包括没命中的!)
        self.sketch.increment(&encode(key));
 
        if let Some(v) = self.window.get(key) {
            return Some(v);
        }
        if let Some(v) = self.probation.get(key) {
            return Some(v);
        }
        if let Some(v) = self.protected.get(key) {
            // 命中 protected,说明它是真热点,提升到 protected 头部
            return Some(v);
        }
        None
    }

注意第一行:所有访问都要记进草图,包括未命中的。

这一点至关重要。缓存未命中的那些 key,它们的频率信息正是用来判断"它该不该进来"的依据。 如果只记录命中的,那么"反复访问但一直被淘汰"的 key 就永远进不来——这正是 LRU 在扫描场景下的失败模式。

    pub fn put(&mut self, key: K, value: V) {
        self.sketch.increment(&encode(&key));
 
        // 1. 已在某个区,更新并提升
        if self.try_update(&key, &value) {
            return;
        }
 
        // 2. 新 key 进 window
        self.window.put(key, value);
 
        // 3. window 满了,淘汰的候选者去和 main 比较
        while self.window.len() > self.window_capacity {
            if let Some((ck, cv)) = self.window.pop_lru() {
                self.try_admit(ck, cv);
            }
        }
    }

SLRU 的提升与降级

Main 区内部的 SLRU 语义:

  • probation(试用区) 命中 → 提升到 protected
  • protected 满了 → 尾部降级回 probation
  • 淘汰永远从 probation 尾部发生
    fn on_main_hit(&mut self, key: K, value: V) {
        self.probation.remove(&key);
        self.protected.put(key.clone(), value);
 
        // protected 超容量,降级一个到 probation
        while self.protected.len() > self.protected_capacity {
            if let Some((dk, dv)) = self.protected.pop_lru() {
                self.probation.put(dk, dv);
            }
        }
    }

这套"命中一次才进 protected"的设计,正是为了抵御扫描攻击:扫描的 key 每个只会被访问一次,永远停在 probation 的尾部,很快被淘汰,碰不到 protected 区里的真热点。

为什么它比 LRU 好:一张对比表

场景 LRU W-TinyLFU
顺序扫描(每个 key 访问一次) 冲光缓存 停在 window/probation,几乎不影响
热点稳定 好 好
新热点出现 好(立刻进) 好(先进 window 观察)
老热点不再使用 会自然淘汰 草图老化后淘汰
频率倾斜的分布 一般 好(这是它的主场)

Caffeine(Java 那条最出名的缓存库)的作者做过对比测试,在真实 trace 上 W-TinyLFU 的命中率比 LRU 高 5-20 个百分点,而且在高并发下因为读路径更简单(不需要像 LRU 那样移动链表节点),吞吐也更好。

代价与坑

1. 频率草图的参数需要调。 宽度太小会导致哈希冲突严重,估计值虚高;太大浪费内存。经验值是"宽度的 10 倍作为老化阈值"。

2. 草图会饱和。 COUNTER_MAX = 15 意味着频率超过 15 的 key 之间无法区分。这在大部分场景没问题(超过 15 次的都是热数据),但如果你的访问分布非常集中,可能需要更大的计数器。

3. 需要处理"频率估计为 0"的情况。 如果草图因内存限制做了降采样(每 N 次只记 1 次),新 key 可能被估成 0,导致永远进不了 main。方案是给所有 key 一个最小的基准频率。

4. 序列化 / 分布式场景不友好。 LRU 的状态就是链表顺序,很好复制;TinyLFU 的状态包含一个哈希草图,跨节点保持一致成本很高。多节点缓存一致性场景下,简单 LRU 反而更实用。

TinyLFU 的复杂度换来的是命中率。如果命中率不是瓶颈(比如缓存的是计算很便宜的数据),那它就是过度设计。

结论

从 LRU 到 TinyLFU,改编的是三件事:

淘汰依据从"时间"换成"频率"(LFU);频率用一张可老化、可饱和的紧凑草图估计(Count-Min Sketch);准入从"先放进来"改成"和受害者比一比"(W-TinyLFU 的 window + SLRU + admission)。

理解了这套结构,你会明白为什么 Caffeine、Ristretto 这些"高性能缓存"都不直接用 LRU——因为在真实负载下,LRU 对扫描的脆弱性比大多数人以为的更严重。