金点网络-全网资源,一网打尽
  • 网站首页
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
登录/注册
  • 专享大神特权
立即开通开通会员抄底价

Java 理论概念·LRU 缓存淘汰算法

作者 : jamin 本文共2892个字,预计阅读时间需要8分钟 发布时间: 2020-10-18 共1071人阅读

LRU 缓存淘汰算法

本文为个人学习摘要笔记。
原文地址:聊聊缓存淘汰算法-LRU 实现原理

我们常用缓存提升数据查询速度,由于缓存容量有限,当缓存容量到达上限,就需要删除部分数据挪出空间,这样新数据才可以添加进来。缓存数据不能随机删除,一般情况下我们需要根据某种算法删除缓存数据。常用淘汰算法有 LRU,LFU,FIFO,本文说明 LRU 算法。

LRU 算法

LRU 即 Least Recently Used,这种算法认为最近使用的数据是热门数据,下一次很大概率将会再次被使用。而最近很少被使用的数据,很大概率下一次不再用到。当缓存容量的满时候,优先淘汰最近很少使用的数据。

假设现在缓存内部数据如下图,当调用缓存获取 key=1 的数据,LRU 算法需要将 1 这个节点移动到头结点,其余节点不变:

缓存数据

然后我们插入一个 key=8 节点,此时缓存容量到达上限,所以加入之前需要先删除数据,然后再将数据添加到头结点。由于每次查询都会将数据移动到头结点,未被查询的数据就将会下沉到尾部节点,尾部的数据就可以认为是最少被访问的数据,所以删除尾结点的数据。

插入数据

这里总结一下 LRU 算法具体步骤:

  1. 新数据直接插入到列表头部
  2. 缓存数据被命中,将数据移动到列表头部
  3. 缓存已满的时候,移除列表尾部数据。

LRU 算法实现

上面例子中可以看到,LRU 算法需要添加头节点,删除尾结点。而链表添加节点/删除节点时间复杂度 O(1),非常适合当做存储缓存数据容器。但是不能使用普通的单向链表,单向链表有几点劣势:

  1. 每次获取任意节点数据,都需要从头结点遍历下去,这就导致获取节点复杂度为 O(N)。
  2. 移动中间节点到头结点,我们需要知道中间节点前一个节点的信息,单向链表就不得不再次遍历获取信息。

针对以上问题,可以结合散列表解决。使用散列表存储节点,获取节点的复杂度将会降低为 O(1)。节点移动问题可以在节点中再增加前驱指针,记录上一个节点信息,这样链表就从单向链表变成了双向链表。

综上使用双向链表加散列表结合体,数据结构如图所示:

双向链表加散列表

在双向链表中特意增加两个『哨兵』节点,不用来存储任何数据。使用哨兵节点,增加/删除节点的时候就可以不用考虑边界节点不存在情况,简化编程难度,降低代码复杂度。

LRU 算法实现代码如下,为了简化 key ,val 都认为 int 类型:

public class LRUCache {

    Entry head, tail;
    int capacity;
    int size;
    Map<Integer, Entry> cache;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 初始化链表
        initLinkedList();
        size = 0;
        cache = new HashMap<>(capacity + 2);
    }

    /**
     * 如果节点不存在,返回 -1.如果存在,将节点移动到头结点,并返回节点的数据。
     *
     * @param key
     * @return
     */
    public int get(int key) {
        Entry node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 存在移动节点
        moveToHead(node);
        return node.value;
    }

    /**
     * 将节点加入到头结点,如果容量已满,将会删除尾结点
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        Entry node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        // 不存在。先加进去,再移除尾结点
        // 此时容量已满 删除尾结点
        if (size == capacity) {
            Entry lastNode = tail.pre;
            deleteNode(lastNode);
            cache.remove(lastNode.key);
            size--;
        }
        // 加入头结点

        Entry newNode = new Entry();
        newNode.key = key;
        newNode.value = value;
        addNode(newNode);
        cache.put(key, newNode);
        size++;

    }

    private void moveToHead(Entry node) {
        // 首先删除原来节点的关系
        deleteNode(node);
        addNode(node);
    }

    private void addNode(Entry node) {
        head.next.pre = node;
        node.next = head.next;

        node.pre = head;
        head.next = node;
    }

    private void deleteNode(Entry node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }


    public static class Entry {
        public Entry pre;
        public Entry next;
        public int key;
        public int value;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Entry() {
        }
    }

    private void initLinkedList() {
        head = new Entry();
        tail = new Entry();

        head.next = tail;
        tail.pre = head;

    }

    public static void main(String[] args) {

        LRUCache cache = new LRUCache(2);

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));

    }
}

LRU 算法分析

缓存命中率是缓存系统的非常重要指标,如果缓存系统的缓存命中率过低,将会导致查询回流到数据库,导致数据库的压力升高。

结合以上分析 LRU 算法优缺点:

  • LRU 算法优势在于算法实现难度不大,对于对于热点数据,LRU 效率会很好。
  • LRU 算法劣势在于对于偶发的批量操作,比如说批量查询历史数据,就有可能使缓存中热门数据被这些历史数据替换,造成缓存污染,导致缓存命中率下降,减慢了正常数据查询。

LRU 算法改进方案

以下方案来源与 MySQL InnoDB LRU 改进算法,将链表拆分成两部分,分为热数据区,与冷数据区,如图所示:

MySQL InnoDB LRU

改进之后算法流程将会变成下面一样:

  1. 访问数据如果位于热数据区,与之前 LRU 算法一样,移动到热数据区的头结点。
  2. 插入数据时,若缓存已满,淘汰尾结点的数据。然后将数据插入冷数据区的头结点。
  3. 处于冷数据区的数据每次被访问需要做如下判断:
    • 若该数据已在缓存中超过指定时间,比如说 1s,则移动到热数据区的头结点。
    • 若该数据存在在时间小于指定的时间,则位置保持不变。

对于偶发的批量查询,数据仅仅只会落入冷数据区,然后很快就会被淘汰出去。热门数据区的数据将不会受到影响,这样就解决了 LRU 算法缓存命中率下降的问题。

Atom ExecutorService ForkJoin Java ReentrantLock synchronized ThreadLocal volatile 后台
本站所提供的部分资源来自于网络,版权争议与本站无关,版权归原创者所有!仅限用于学习和研究目的,不得将上述内容资源用于商业或者非法用途,否则,一切后果请用户自负。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源。如果上述内容资对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本站不保证所提供下载的资源的准确性、安全性和完整性,源码仅供下载学习之用!如用于商业或者非法用途,与本站无关,一切后果请用户自负!本站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。如有侵权、不妥之处,请联系站长以便删除!
金点网络-全网资源,一网打尽 » Java 理论概念·LRU 缓存淘汰算法

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用?
本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
是否提供免费更新服务?
持续更新,永久免费
是否经过安全检测?
安全无毒,放心食用
jamin

jamin 大神

下一篇
网络协议-组播介绍

相关推荐

Java 实战系列·Kaptcha 与数学公式验证码

Java 实战系列·Kaptcha 与数学公式验证码

大闹天宫 网页游戏单机版火凰冰蛟一键服务端GM无限元宝VIP11

大闹天宫 网页游戏单机版火凰冰蛟一键服务端GM无限元宝VIP11

赤壁【虚拟机一键端】赤壁法强超变虚拟机一键端

赤壁【虚拟机一键端】赤壁法强超变虚拟机一键端

魔神争霸3D网游单机虚拟机镜像一键服务端 

魔神争霸3D网游单机虚拟机镜像一键服务端 

【烈焰遮天】一键运行服务端+工具+视频教程 

【烈焰遮天】一键运行服务端+工具+视频教程 

标签云
Android Atom ExecutorService ForkJoin GM GM后台 GM授权后台 H5 Java Javascript Linux手工服务端 pipbestcom Python ReentrantLock synchronized ThreadLocal volatile Win一键即玩服务端 一键端 传奇 写作 创业 单机 后台 商业端 外网 安卓 安卓苹果双端 工具 手工端 手游 搭建教程 教程 数据分析 文案 游戏源码 端游 经典 网单 职场 自媒体 视频教程 详细搭建教程 运营后台 页游

近期文章

  • 回合手游【逍遥西游之繁华西游】最新整理单机一键既玩镜像服务端_Linux手工端_GM后台_教程
  • 最新整理精品回合制手游【天书奇谈3D混沌完整版】VM一键单机版_linux手工外网端_隐盟视频教程_授权GM后台_双端
  • 典藏修真页游【诸仙列传OL】最新整理Win系服务端_GM工具_详细外网搭建教程
  • MT3换皮MH【浮生若梦尊享挂机修复版】最新整理单机一键即玩镜像端_Linux手工服务端_安卓苹果双端_GM后台_详细搭建教程
  • 大话回合手游【最新引擎之缥缈西游渡劫版】最新整理Linux手工服务端_安卓苹果双端_管理后台_CDK后台_详细搭建教程_视频教程

分类

  • | wordpress插件 |
  • | wordpress模板 |
  • | 其它模板 |
  • | 帝国模板 |
  • | 织梦插件 |
  • | 织梦模板 |
  • A5源码
  • Android软件
  • APP引流
  • E语言
  • H5
  • LUA
  • QQ营销
  • SEO推广
  • Windows软件
  • 体育运动
  • 信息数据
  • 创业专题
  • 办公教程
  • 口才演讲
  • 名师讲座
  • 商城/淘客/交易
  • 小吃技术
  • 小说/漫画/阅读
  • 建站教程
  • 引流脚本
  • 影视/音乐/视频
  • 影视资源
  • 微信/微商/微擎
  • 微信小程序
  • 微信营销
  • 微擎模块
  • 手游源码
  • 技能学习
  • 抖音课程
  • 摄影教程
  • 棋牌教程
  • 模板/主题/插件
  • 游戏源码
  • 爆粉引流
  • 理财/金融/货币
  • 生活老师
  • 电商客
  • 电子文档
  • 电脑教程
  • 社群营销
  • 站长工具
  • 精品网单
  • 系统工具
  • 素材资料
  • 综合资料
  • 编程经验
  • 网站源码
  • 网络安全
  • 网赚教程
  • 网赚源码
  • 考研资料
  • 脚本/AI/智能
  • 自媒体
  • 英语学习
  • 营销软件
  • 设计素材
  • 说书小说
  • 贴吧引流
  • 软件工具
  • 软文营销
  • 逆向软件
  • 音频讲座
  • 页游源码

提供最优质的资源集合

立即加入 友好社区
金点网络-全网资源,一网打尽

新一代全网资源综合门户网(www.pipbest.com-金点网络)专注服务于互联网,提供各类最新最全的免费源码下载(PHP、ASP、JSP、.NET),更提供免费工具,免费源码下载,软件下载,素材下载,赚钱教程下载,交流论坛等网站运营相关的一切内容,为网友搜罗最有价值的网站源码下载与技术教程等服务!

服务目录
  • 金点OpenAPI
  • 金点云
  • 金点支付
友情链接
  • 数媒派
  • 国家电网
快速搜索

本站由Nice强力驱动

声明: 本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!

本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!
© 2016-2023 PipBest.Com - 金点网络 & 金点部落. All rights reserved 京ICP备2022005359号-1
  • 关注有礼
  • 签到
  • 客服
    官方QQ群 常见问题 FAQ

    在线客服

    点我联系

    直接说出您的需求!
    切记!带上资源连接与问题!

    工作时间: 9:30-21:30

  • 暗黑
    模式
  • 全屏
  • 投稿
    赚钱
  • 首页

  • 签到

  • 切换

  • 客服

金点网络-全网资源,一网打尽
  • 登录
  • 注册
or
or
忘记密码?
金点网络-全网资源,一网打尽
  • 网站首页 ►
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习 ►
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程 ►
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码 ►
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码 ►
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料 ►
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座 ►
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具 ►
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    ►
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
×
u3** 刚刚下载了 爆款吸金文案训练

    全网资源·一网打尽

  • 金点出品,必属精品!
  • 发布原创内容,获取高额提成!
  • 我们与你共创美好数字生态!
  • 无特殊说明密码默认:pipbest.com