用 Rust 从零实现 LFU 与 TinyLFU:比 LRU 更抗扫描的缓存
前面写过 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%) │
└──────────────┘ └──────────────┘
│ ^
│ │
└── 淘汰时和候选者比频率 ──┘三个部件各司其职:
- Window LRU:新来的 key 先进这里,给它们一个被观察的机会。这解决了 LFU"新热点进不来"的问题。
- Main SLRU:主力存储区,分两段(Protected 80% + Probation 20%)。
- 频率草图:决定"从 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 对扫描的脆弱性比大多数人以为的更严重。