当前位置:

首页 > 编程开发 > C++实现简单的LRU-K算法 _ 解决偶发性访问热点问题【源码】

C++实现简单的LRU-K算法 _ 解决偶发性访问热点问题【源码】

LRU-K算法不宜用链表和哈希表实现,推荐采用环形数组配合单调递增时间戳记录第K次访问时间。淘汰策略使用热度桶分层采样,避免全量排序开销。K值建议取2或3,桶数量不超过8个。需注意时间戳更新和桶重组时机必须与缓冲池操作对齐。

本文目录

    咱们先直说了吧:std::list + std::unordered_map 这套组合拳,打不了 LRU-K。哪怕 K 只取 2,只要你还想着遍历链表去更新访问记录,那缓存驱逐的延迟就会随着访问频率一路走高,最后彻底崩盘。

    C++实现简单的LRU-K算法 _ 解决偶发性访问热点问题【源码】

    为什么 std::list 不适合 LRU-K 的第 K 次访问时间维护

    LRU-K 的核心要求,是对每个 key 维护最近 K 次访问的精确时间戳。淘汰的时候,它看的不是最新那次访问,而是倒数第 K 次——也就是“第 K 次访问时间”。而 std::list 呢?它只擅长 O(1) 地把节点挪到头尾,却没法 O(1) 地定位并修改中间某次访问记录。

    常见错误有哪些?

    • 有人用链表节点存 K 个时间戳,结果每次插入新时间都得遍历去找最老的位置,平均复杂度 O(K)。K=4 时,就是 4 次指针跳转加内存访问,性能肉眼可见地往下掉。
    • 有人每次 get 都重排整个链表,按第 K 次时间排序。虽然可能留到淘汰前才真算,但 get 操作一多,隐式的重排逻辑就会被触发。实测下来,QPS 能掉 30% 以上。
    • 最典型的一个坑,是把 LRU-1 的 head/tail 模式直接套到 LRU-K 上,结果“刚被访问 K 次”的热数据,反而比“只访问了 K-1 次但沉寂很久”的冷数据更早被淘汰。这逻辑一跑,缓存命中率直接翻车。

    用环形数组 + 单调 tick 实现第 K 次访问时间推导

    核心思路就一条:别实时排序。每个 key 只存一个 std::array 和一个游标 size_t cursor。新访问进来,覆盖掉最老的那次记录。第 K 次访问时间,就是 access_ticks[(cursor - K + 1) % K]。注意负数取模在 C++ 里是未定义行为,所以计算时一定先加上 K。

    实操建议:

    • tick 用全局原子递增的 uint64_t,别依赖系统时间。系统时间可能回拨,精度也没保障。
    • 环形数组索引必须用 size_t,取模时写成 (cursor + K - 1) % K,别直接 cursor - K + 1 取模。
    • K 值建议硬编码为 2 或 3。K=4 时环形数组空间翻倍,但命中率提升还不到 0.7%,反而 cache line miss 会上升 12%,得不偿失。
    • 时间戳和 value 别放在同一个结构体里。热数据的 page buffer 和访问历史必须分离,否则驱逐时没法原子释放内存,容易出问题。

    淘汰时不扫全量,改用热度桶分层采样

    实时维护一个全局有序队列,代价太高,不值得。正确的做法是:等到需要驱逐时,才对候选 key 集合批量计算 access_ticks[(cursor - K + 1) % K],然后映射到离散热度桶。桶的划分可以参考 0–50ms、50–200ms、200–1s、>1s 这样的区间。

    关键细节:

    • 桶用 std::vector> 实现,每个桶内的 key 按插入顺序排列,不排序。
    • 淘汰时只查最冷的 1–2 个桶。如果桶为空,就向前合并相邻的桶,别让空桶卡死驱逐流程。
    • 每 100 次 insert 后触发一次桶重组:遍历所有桶,把 now_tick - access_time > 1s 的 key 移到新桶,防止冷数据永久滞留。
    • 桶数量别超过 8。实测 16 桶时,hash 分布会严重倾斜,30% 的 key 挤在前两个桶,淘汰效率反而下降。

    说实话,写对逻辑本身并不难。真正棘手的地方,在于控制 tick 更新和桶重组的时机——它们必须和缓冲池的 page pin/unpin、脏页刷盘节奏对齐。否则就会出现“刚标记为冷数据,下一秒就被事务强制 pin 住”的竞态问题。这一层耦合,在很多开源实现里都被忽略了。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发 热点 C++
    相关文章 更多
    C++动态数组初始化怎么写?常用语句与代码示例
    C++动态数组初始化怎么写?常用语句与代码示例

    深入解析C++中动态数组的初始化机制,涵盖new操作符的不同用法、基本类型与类对象的初始化差异,以及为何在现代C++开发中应优先使用std::vector。

    摩托罗拉edge 70怎么修改热点名称 摩托罗拉edge 70个人热点设置教程
    摩托罗拉edge 70怎么修改热点名称 摩托罗拉edge 70个人热点设置教程

    摩托罗拉Edge70可通过三种方式修改个人热点名称:在设置中进入连接与个人热点选项;通过下拉通知栏长按热点图标快速进入设置;或在高级设置中找到网络共享功能进行修改。修改时需输入不超过32个字符的新名称,建议使用英文、数字及短横线组合以确保兼容性,最后保存即可生效。

    360浏览器如何关闭热点新闻
    360浏览器如何关闭热点新闻

    可关闭360浏览器右下角热点新闻弹窗:一、在【实验室】中取消勾选“360热点资讯”等资讯类选项;二、在【高级设置】中关闭消息推送与闪动提醒;三、通过【弹窗设置】直接关闭热点新闻提醒;四、用se://settings/直达实验室设置;五、弹窗出现时点击右上角↓选择“不再弹出”。 相信不少朋友在使用36

    Win7创建虚拟WiFi热点
    Win7创建虚拟WiFi热点

    开启隐藏技能:让Windows 7电脑秒变无线路由器 你知道吗?其实你的Windows 7电脑里,藏着一个相当实用的“隐藏功能”——虚拟Wi-Fi和SoftAP。利用它,你可以轻松把台式机或笔记本变身为一台临时无线路由器,让手机、平板等其他设备共享同一个网络连接。这招不仅省去了额外购买硬件的开销,操

    edge浏览器如何关闭新闻推荐
    edge浏览器如何关闭新闻推荐

    可彻底关闭Edge新闻资讯流:一、新标签页点击齿轮→“自定义”→关“资讯源”;二、设置→“开始、主页和新建标签页”→关“显示信息提要”;三、设置→“隐私、搜索和服务”→关两个“个性化内容”开关;四、设置→“侧边栏”→关“发现”;五、通知权限中阻止news.microsoft.com等域名。 是不是每

    登录入口今日头条官网
    登录入口今日头条官网

    今日头条的官网登录入口,其实就藏在它的官方网站https://www.toutiao.com/里。通过电脑访问这个地址,输入账号密码完成验证,你就能顺利登入。当然,更常见的场景是在手机App上,那里提供了手机号验证、第三方账号绑定等多种便捷的登录方式,几步操作就能搞定。 “今日头条官网的登录入口到底

    C++类构造与析构函数详解
    C++类构造与析构函数详解

    C++类构造与析构函数详解 C++这门语言,可以说是从C语言这棵大树上衍生出的高级果实,如今的应用普及度有目共睹。作为一种静态类型的通用编程语言,它厉害的地方在于融合了多种编程哲学——无论是传统的面向过程,还是主流的面向对象,乃至数据抽象、泛型编程这些高级概念,它都能很好地支持。正因为这份卓越的扩展

    C++中std::upper
    C++中std::upper

    C++中std::upper_bound用法解析 在C++标准模板库(STL)的算法工具箱里,upper_bound() 绝对算得上是一把精准的“探针”。它的核心任务很明确:在一个已经排好序的区间 [first, last) 内,帮你快速定位到第一个**严格大于**指定值 value 的那个元素。这

    vivo浏览器怎么关闭热点推送
    vivo浏览器怎么关闭热点推送

    vivo浏览器可通过五步关闭首页热点资讯:一、在“我的→设置→消息通知”中关闭“热点资讯”等开关;二、于“首页设置”禁用信息流与个性化推荐;三、在系统“通知管理”中彻底关闭浏览器通知权限;四、启用“简洁模式”或“极简首页”;五、通过首页“频道管理”手动取消勾选不需栏目。 不少用户都遇到过这个困扰:一

    QQ浏览器怎么关闭热搜榜单
    QQ浏览器怎么关闭热搜榜单

    关闭qq浏览器首页热搜榜需依次操作:一、搜索栏点击“隐藏”按钮;二、设置中关闭“新标签页和搜索栏显示搜索热词”;三、负一屏设置中关闭“热点资讯”等推荐开关;四、系统通知与后台权限中禁用相关内容推送;五、清除缓存或数据重置推荐逻辑。 打开QQ浏览器,首页搜索栏下那些不断跳动、更新的热搜榜单,是不是总在

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。