LFU（Least Frequently Used）按访问频次淘汰数据，听起来比LRU更贴合缓存场景，但经典的LFU有个老毛病：一个曾经被疯狂访问的key，即使之后几个月再没人碰过，它的计数器依然很高，会一直赖在缓存里，把真正的新热点挤出去。要解决这个问题，通用的思路是给频率计数加上时间维度——要么让计数随时间衰减，要么在淘汰时参考最近访问时间戳。本文就围绕这个主题，用C++从零实现一套基于时间戳衰减的LFU缓存，并重点讨论命中率与空间占用之间怎么取舍。
一、为什么纯LFU会失效：污染问题剖析
先看清楚问题本身。假设一个缓存容量为1000，某个key在某一天被访问了10万次，计数器记为100000。之后这个key彻底冷了，但只要缓存没满到需要淘汰它，它就一直占着位置。更糟的情况是，缓存长期处于接近满载状态时，那些计数很高的旧数据会形成一道“屏障”，新进入的热点数据因为计数低，反而总是最先被淘汰。这种现象在缓存领域有个专门的名词，叫缓存污染（cache pollution）。
造成污染的根源在于LFU的计数器只增不减，历史信息永远不会过期。而真实的业务流量往往有明显的时间局部性：今天的热点可能是明天就无人问津的旧闻，热点会迁移。LFU需要一个遗忘机制，让旧的访问记录逐渐失去话语权。
常见的遗忘手段有两类。第一类是周期性衰减：每隔一个时间片，把所有计数器除以2或减去一个固定值。第二类是惰性衰减：在数据被访问时，根据当前时间与上次访问时间戳的差值，动态扣减计数，被访问时才计算，不用后台线程。两种方式各有优劣，周期衰减需要遍历全部条目，代价集中但实现简单；惰性衰减把成本摊到每次访问上，适合高并发场景。下面的实现采用惰性衰减，并辅以最小访问时间戳作为淘汰时的次级判断条件。
二、数据结构设计：哈希表加频率桶
要保证get和put都是平均常数复杂度，数据结构的选择很关键。单纯用哈希表加优先队列（小顶堆）也能做LFU，但堆的调整是O(log n)，且计数频繁变化会导致堆频繁下沉上浮。业界更经典的做法是O(1) LFU：用哈希表做key到节点的快速定位，节点按频率挂到不同的桶里，每个桶是一个双向链表，同一频率内部按时间顺序排列，最新访问的放在链表尾部。
这样设计后，淘汰逻辑非常直观：找到最低非空频率桶，取链表头部的节点淘汰即可——它是最低频率里最久没被访问的。计数更新时，把节点从当前频率桶摘下来，计数加一后挂到下一个频率桶的尾部，整个过程只是几个指针操作。
在我们的时间衰减版本里，每个节点额外存两个字段：last_access_ts记录上次访问的时间戳，base_count记录上次访问时刻的衰减后计数。访问时先计算衰减量，再叠加本次访问，得到逻辑计数。注意逻辑计数不落盘存储，而是在比较时实时计算，这样避免了后台遍历更新的开销。核心结构定义如下：
struct Node {
int key;
int value;
uint64_t last_access_ts; // 上次访问时间戳（毫秒）
double base_count; // 上次访问时的衰减后计数
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v),
last_access_ts(0), base_count(0),
prev(nullptr), next(nullptr) {}
};
class LFUCache {
public:
LFUCache(size_t capacity, double decay_rate, uint64_t half_life_ms);
int get(int key);
void put(int key, int value);
private:
double logicalCount(Node* n, uint64_t now); // 实时计算衰减后计数
void touch(Node* n, uint64_t now); // 访问后提升频率桶
void evict(uint64_t now); // 淘汰最低频率桶头部
size_t capacity_;
double decay_rate_; // 衰减系数
uint64_t half_life_ms_; // 半衰期，计数减半所需时间
std::unordered_map<int, Node*> index_;
std::map<long long, Node*> freq_buckets_; // 频率到桶头指针
// freq_buckets_ 也可以用最小频率变量+哈希表实现，这里用 std::map 便于演示
};
这里用std::map管理频率桶是为了代码可读性，它带来O(log F)的复杂度，F是不同频率的数量。追求极致性能的话，可以维护一个min_freq变量配合哈希表，把这部分也降到O(1)，思路是：计数只会加一或因衰减变化，衰减导致最小频率桶变化时向下扫描即可，实现上稍微繁琐一些，但原理完全一致。
三、衰减公式与淘汰逻辑的完整源码
衰减公式采用指数衰减，这是最常用的形式：逻辑计数等于基础计数乘以e的负指数，指数为经过时间除以半衰期再乘以ln2。直观理解就是每过一个半衰期，历史计数就减半。比如半衰期设为10分钟，一个key十分钟前计数是100，现在它的逻辑计数只剩约50，二十分钟前只值25。这个参数直接决定了缓存的“记忆力”：半衰期越长，缓存越偏向长期热点；越短，越偏向突发热点。
完整可编译的实现如下，接口语义与LeetCode 460保持一致，方便对照测试：
#include <cassert>
#include <cmath>
#include <cstdint>
#include <map>
#include <unordered_map>
#include <chrono>
struct Node {
int key;
int value;
uint64_t last_ts;
double base_count;
Node *prev, *next;
Node(int k, int v) : key(k), value(v), last_ts(0),
base_count(0), prev(nullptr), next(nullptr) {}
};
class LFUCache {
public:
LFUCache(size_t cap, uint64_t half_life_ms = 600000)
: cap_(cap), half_life_(half_life_ms), min_freq_(0) {
assert(cap > 0);
}
int get(int key) {
auto it = index_.find(key);
if (it == index_.end()) return -1;
Node* n = it->second;
touch(n, now_ms());
return n->value;
}
void put(int key, int value) {
uint64_t now = now_ms();
auto it = index_.find(key);
if (it != index_.end()) {
it->second->value = value;
touch(it->second, now);
return;
}
if (index_.size() >= cap_) evict(now);
Node* n = new Node(key, value);
n->last_ts = now;
n->base_count = 1.0; // 新条目初始计数为1
attach(n, 1, now);
index_[key] = n;
}
private:
static uint64_t now_ms() {
using namespace std::chrono;
return duration_cast<milliseconds>(
steady_clock::now().time_since_epoch()).count();
}
// 实时计算衰减后的逻辑计数
double logicalCount(Node* n, uint64_t now) const {
if (now <= n->last_ts) return n->base_count;
double elapsed = double(now - n->last_ts);
return n->base_count * std::exp(-0.693147 * elapsed / half_life_);
}
// 频率桶按逻辑计数向下取整挂载，同桶内按访问时间排序
long long bucketOf(Node* n, uint64_t now) const {
return std::max(1LL, (long long)std::llround(logicalCount(n, now)));
}
void touch(Node* n, uint64_t now) {
double lc = logicalCount(n, now);
detach(n);
n->base_count = lc + 1.0; // 本次访问计数加一
n->last_ts = now;
attach(n, bucketOf(n, now), now);
}
void detach(Node* n) {
n->prev->next = n->next;
n->next->prev = n->prev;
}
void attach(Node* n, long long freq, uint64_t now) {
auto& bucket = buckets_[freq];
if (!bucket.head) {
bucket.head = new Node(0, 0); // 哨兵头
bucket.tail = new Node(0, 0); // 哨兵尾
bucket.head->next = bucket.tail;
bucket.tail->prev = bucket.head;
}
Node* last = bucket.tail->prev; // 插到尾部=最新
last->next = n; n->prev = last;
n->next = bucket.tail; bucket.tail->prev = n;
if (freq < min_freq_ || buckets_.count(min_freq_) == 0)
min_freq_ = freq;
}
void evict(uint64_t now) {
// 找到最低非空频率桶，淘汰头部（该桶中最久未访问的）
while (buckets_.count(min_freq_) == 0 || buckets_[min_freq_].empty())
++min_freq_;
Node* victim = buckets_[min_freq_].head->next;
detach(victim);
index_.erase(victim->key);
delete victim;
}
struct Bucket {
Node *head = nullptr, *tail = nullptr;
bool empty() const { return head->next == tail; }
};
size_t cap_;
uint64_t half_life_;
long long min_freq_;
std::unordered_map<int, Node*> index_;
std::unordered_map<long long, Bucket> buckets_;
};
有几个实现细节值得展开说。第一，逻辑计数是double类型，衰减公式会产生小数，挂桶时取整会导致两个计数1.4和1.6的节点进入不同桶，这没有本质影响，桶只是排序的近似手段，真正的精度差异在半衰期内会被抹平。第二，新节点初始计数设为1，如果设为0，第一个被访问的新key会跟从未访问的key在同一个桶，淘汰顺序变得不确定。第三，淘汰时选最低频率桶的链表头，头部的语义是“该频率下最早被放到这个桶的”，在衰减体系下，这近似等于“逻辑计数最低且最久未冷访问”的节点，正好符合我们要淘汰陈旧冷数据的意图。
四、命中率与空间占用的权衡：参数怎么调
这套结构里真正影响命中率的是两个参数：容量和半衰期。它们之间存在明显的此消彼长关系，需要结合业务流量特征来调。
容量方面，缓存越大命中率越高，但内存成本线性增长，而且当容量超过工作集大小后，继续扩容命中率几乎不再提升，钱花在了刀背上。比较务实的做法是先统计业务的真实工作集大小（比如用一天内的去重key数量作为近似值），容量设为工作集的百分之二十到五十起步，再根据命中率曲线爬坡。每个节点约100字节左右（含哈希表槽位、链表指针），百万级条目大约占用100MB出头，这个账要提前算清楚。
半衰期的选择取决于热点迁移速度。如果业务的热点以小时为单位轮换（比如资讯类内容），半衰期设为30分钟到1小时比较合适；如果热点相对稳定（比如配置类、字典类数据），半衰期可以放宽到几小时甚至一天，甚至干脆用纯LFU。半衰期过短的问题是缓存会变得“健忘”，持续温和访问的长尾数据会被反复挤出又反复加载，命中率反而下降；过长则退化回经典LFU，污染问题重新出现。建议用回放真实访问日志的方式做离线对比：把同一份日志分别灌入不同参数组合，统计命中率，典型实验中，带1小时半衰期的版本相比纯LFU在突发热点场景下命中率能提升十几个百分点，但在稳定热点场景下两者差距很小，这说明参数必须跟着流量形态走，没有万能值。
另外提一个省空间的技巧：如果key本身很长（比如SHA1字符串），节点里不要复制key，改存哈希表迭代器或者用指针指向哈希表中的key，能省下一份拷贝。计数器也可以从double降为uint32，把小数部分丢给取整误差，百万级条目下能省几MB。这些微优化在单个实例上看不出差别，但如果你在跑几十个缓存实例，积少成多就很可观了。
五、并发场景的注意事项
上面的实现是单线程版本。要在多线程环境使用，最简单的方案是外部套一把std::mutex，读多写少的场景可以升级为std::shared_mutex，读操作加共享锁，写操作加独占锁。但要注意，我们的get内部会执行touch操作修改链表，严格来说get也是写操作，共享锁只适用于不做计数提升的只读查询路径，如果需要，可以拆出一个纯查询的peek接口。
更高吞吐的做法是分片：把key按哈希分成N个独立的小缓存实例，每个实例一把锁。分片带来的额外好处是淘汰粒度更细，单把大锁的争用被摊薄。代价是各分片容量不均时，总命中率会比单一大缓存略低一点，通常分片数取CPU核数的2到4倍，命中率损失可以控制在百分之一以内，换来接近线性的吞吐扩展，这笔交易通常是划算的。
最后提醒一点时间戳的选择。代码里用的是std::chrono::steady_clock而不是系统时钟，因为系统时钟会被NTP调整甚至回拨，一旦时间倒流，衰减计算会出现负的elapsed，导致计数异常膨胀。steady_clock单调递增，不受系统时间修改影响，是缓存类组件的正确选择。如果组件要跨进程部署或者计数需要在重启后延续，再考虑换成毫秒级Unix时间戳并容忍时钟跳变的误差。
总结一下，基于时间戳衰减的LFU在经典LFU的频率视角上叠加了时间视角，用可控的遗忘机制化解缓存污染问题。核心结构是哈希表定位加频率桶排序，配合惰性计算的指数衰减公式，全流程保持平均常数复杂度。工程落地时重点调容量和半衰期这两个参数，用真实日志回放验证命中率，再根据并发压力决定是否分片，基本就能得到一套既省内存又高命中的缓存方案。