LRU-K 通过要求 key 至少访问 K 次才进入主缓存，天然过滤单次噪声（如 debug 请求），避免污染；K=2 是常用折中，K＞3 易引发锁争用；需双哈希表+定长环形缓冲区实现 O(1) 历史记录，promotion/demotion 需细粒度锁与原子操作，并配 runtime 可调 K 值及采样监控。
LRU-K 在 C++ 中无法直接“高效实现”——它天然比 LRU 多出 K 次历史访问追踪开销，所谓“高效”只能靠结构裁剪和访问局部性优化，不是靠算法本身变快。
为什么标准 LRU 无法解决偶发性数据污染
当某个 key 偶然被访问一次（比如 debug 日志误刷、爬虫试探请求），标准 std::list + unordered_map 实现的 LRU 会立即将其提到队首，挤掉真正高频但近期略沉寂的 key。这不是缓存失效，是缓存被“污染”。LRU-K 要求一个 key 至少被访问 K 次才进入主缓存队列，天然过滤单次噪声。
常见错误现象：cache.get("debug_flag") 被调一次，后续半小时内真实热 key 全部被淘汰。
- K=2 是最常用折中：既防单次污染，又不显著提高冷启动延迟
- 不要设 K＞3 —— 实测在 QPS＞5k 场景下，K=4 的
history_queue锁争用导致吞吐下降 18% - 必须区分“历史访问记录”和“主缓存”，二者生命周期、淘汰策略、线程安全级别都不同
用双哈希表 + 定长环形缓冲区实现 O(1) 历史记录
不用 std::deque 或链表存历史访问——每次插入要 realloc 或 new node，且遍历查 K 次很慢。正确做法是每个 key 对应一个长度为 K 的环形缓冲区（std::array），只存时间戳：
struct HistorySlot {
std::array<uint64_t> ts; // K=2，只存最近两次访问时间戳
uint8_t count = 0; // 当前有效次数（0/1/2）
};
std::unordered_map<key historyslot> history_map;
</key></uint64_t>
每次 access(key) 时：
- 若
history_map.count(key) == 0，插入新 slot，count = 1，ts[0] = now() - 否则，右移已有时间戳（
ts[1] = ts[0]），填入新时间戳，count = min(count + 1, K) - 不查全量历史，只看
count == K就触发 promotion 到主 LRU 队列
这样避免了链表遍历、内存分配、迭代器失效，所有操作都是 cache-line 局部的。
主缓存仍用 list + map，但 promotion/demotion 必须原子
主缓存结构仍是 std::list + std::unordered_map，但关键在 promotion 时机和线程安全：
- promotion 不在每次访问时做，只在
count == K的瞬间做一次，且必须加细粒度锁（如shared_mutex写锁）保护主缓存结构 - demotion（降级回历史区）不能简单删节点——要保留其最后访问时间戳，写回
history_map[key].ts[0] = now()，count = 1，否则下次访问又要重走 K 次流程 - 禁止在持有主缓存锁时调用任何可能阻塞的操作（如日志、网络回调），否则 history_map 的读锁也会被卡住
错误示例：if (hit_in_history && history.count == K) { promote(); log_debug(...); } —— 日志 IO 可能拖慢整个缓存通路。
实际部署时 K 值必须 runtime 可调，且带采样监控
硬编码 K = 2 在压测环境 OK，上线后会出问题：某业务突发扫描行为导致大量 key 卡在 K-1 状态，主缓存命中率断崖下跌。必须支持运行时调整：
- 暴露
/cache/lruk/k?value=2HTTP 接口（或 SIGUSR2 信号），修改全局g_k_value原子变量 - 同时采集两个指标：
history_full_rate（history_map 中count == K的比例）、promotion_latency_p99（promotion 操作耗时 99 分位） - 当
history_full_rate > 0.7且promotion_latency_p99 > 50us，说明 K 值偏高或 history_map 容量不足，需扩容或降 K
没监控的 LRU-K 就是定时污染源——它不报错，只悄悄让缓存失效率从 5% 慢慢爬到 40%。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
