W-TinyLFU 缓存淘汰算法详解

背景#

在缓存系统中，如何高效地淘汰低价值数据、保留热点数据是一个核心问题。W-TinyLFU（Window TinyLFU）是一种结合了 Least Recently Used（最近最少使用）和 Frequency Least Frequently Used（最不频繁使用）优点的准入策略。

核心公式#

1. 布隆过滤器（Bloom Filter）#

布隆过滤器用于快速判断一个 key 是否曾经被访问过。其假阳性率（False Positive Rate）为：

其中：

• $n$ — 已插入元素数量
• $m$ — 位数组长度
• $k$ — 哈希函数数量

最优哈希函数数量为：

2. 频率计数（Frequency Counter）#

TinyLFU 使用 Count-Min Sketch 来估计访问频率：

其中 $h_i(x)$ 是 key $x$ 的第 $i$ 个哈希值对应的计数器位置。

3. W-TinyLFU 窗口#

W-TinyLFU 将缓存分为两个区域：

• Window Cache：大小为总容量的 $1\%$
• Main Cache：剩余 $99\%$

4. 准入评分（Admission Score）#

当一个新 entry 需要进入 Main Cache 时，计算其准入评分：

如果 $S_{new} > S_{old}$，则新 entry 准入，得分最低的 entry 被淘汰。

算法流程#

func (w *W TinyLFU) Admit(key string) bool {
    // 1. 计算新 key 的频率
    freq := w sketch.Estimate(key)

    // 2. 找到 Main Cache 中得分最低的 entry
    victim, victimScore := w.mainCache.EvictCandidate()

    // 3. 比较准入评分
    if freq > victimScore {
        w.mainCache.Put(key)
        return true
    }
    return false
}

性能分析#

W-TinyLFU 在 Stack Exchange 的 benchmark 中表现优异：

总结#

W-TinyLFU 通过布隆过滤器 + Count-Min Sketch 的组合，实现了 $O(1)$ 时间复杂度的频率估计，同时通过滑动窗口机制保护了短期热点数据。