标准std::list + std::unordered_map不适用于LRU-K，因其无法高效维护每个key最近K次访问时间戳并按第K次时间排序淘汰；std::list仅支持O(1) LRU-1，而LRU-K需O(K)随机定位与重排，高频场景成瓶颈。
为什么标准std::list + std::unordered_map不适用于LRU-K
LRU-K要求记录每个key最近K次访问的时间戳，并按第K次访问时间排序淘汰——不是简单维护“最后一次”，而是维护一个访问历史窗口。用std::list只能高效做LRU-1，插入/更新第K次访问时需随机定位、重排节点，平均O(K)甚至O(N)，在缓冲池高频读写场景下会成为瓶颈。
真实数据库缓冲池（如PostgreSQL的clock-sweep变种）几乎不用纯LRU-K，因为K≥2时维护成本陡增；但若业务强依赖访问模式识别（比如预判热点区间），仍需折中实现。
- 别直接复用LRU-1结构：把
std::list节点塞K个时间戳进去，会导致每次访问都要shift数组、内存局部性差 - K值不宜大于4：K=2已能过滤大量瞬时抖动访问；K>4后命中率提升极小，但链表分裂/合并开销翻倍
- 必须分离“访问记录”和“数据存储”：热数据实体（如page buffer）不能和访问时间戳耦合，否则缓存驱逐时无法原子释放资源
如何用双哈希表 + 定长环形缓冲区实现O(1)更新
核心是把“第K次访问时间”变成可推导值：对每个key，只存最近K次访问的tick（单调递增计数器），用环形数组+游标管理，新访问覆盖最老一次；第K次访问时间就是环形数组尾部前K-1位的值。
示例结构：
立即学习“C++免费学习笔记（深入）”；
struct LruKEntry {
uint64_t access_ticks[4]; // K=4，固定大小
size_t cursor = 0; // 下次写入位置
bool full = false; // 是否填满过
};
std::unordered_map<Key, LruKEntry> history_;
std::unordered_map<Key, Value*> data_;
- 每次
get()：更新history_[key]的环形数组，不挪动节点，O(1) - 淘汰候选计算：只在需要驱逐时，对候选key集合批量算
access_ticks[(cursor - K + 1) % K]，避免实时维护全局有序队列 - 注意
cursor溢出：用uint64_t当tick，但环形数组索引必须用size_t并取模，否则负数取模行为不一致
淘汰时如何避免全量扫描？用分段热度桶做粗筛
数据库缓冲池常驻数万页，每轮淘汰若遍历全部history_，延迟不可控。实际做法是把key按“第K次访问距今ticks”映射到热度桶（如0–100ms、100–500ms…），只扫最冷的1–2个桶。
关键点：
- 桶不是精确时间分区，而是用
(now - kth_tick) >> shift做快速散列，shift取6–8（对应64–256ms粒度） - 淘汰线程定期（如每100次insert后）触发桶重组：把过期桶里的key移到新桶，避免桶内数据永久滞留
- 绝不依赖
std::priority_queue：它底层是vector，每次pop后堆重建O(log N)，且无法删除中间元素 - 如果使用mmap文件页作value存储，淘汰时必须先
msync(MS_SYNC)再munmap，否则脏页丢失
与生产级缓冲池（如SQLite Pcache）的关键差异点
SQLite的Pcache用clock算法+LRU辅助链表，本质是近似LRU-K的轻量实现：它不存K次时间戳，而用单比特“被访问过”标记+两次扫描周期来模拟K=2效果。C++手写LRU-K真正难的不是逻辑，而是和底层IO协同。
- 缓存项析构必须异步：
Value*指向的buffer可能正被另一个线程read()，需用引用计数+RCU式延迟回收 - 不要在
get()里做磁盘IO：用户调用get()期望O(1)，加载缺失页应走单独prefetch()通道 - 警惕虚假共享：
LruKEntry若和其他热字段同cache line，频繁更新cursor会导致多核间line bouncing
真正卡性能的往往不是算法复杂度，而是tick计数器的获取方式——别用std::chrono::steady_clock::now()，改用__rdtsc()或clock_gettime(CLOCK_MONOTONIC_COARSE)，否则单次get耗时从20ns飙到300ns。
