[编程技术] LRU缓存机制,你想知道的这里都有
作者:CC下载站 日期:2021-11-23 18:00:51 浏览:26 分类:编程开发
概述
LRU是Least Recently Used
的缩写,译为最近最少使用。它的理论基础为 “最近使用的数据会在未来一段时期内仍然被使用,已经很久没有使用的数据大概率在未来很长一段时间仍然不会被使用” 由于该思想非常契合业务场景 ,并且可以解决很多实际开发中的问题,所以我们经常通过LRU的思想来作缓存,一般也将其称为LRU缓存机制。
原理
实现LRU时,我们需要关注它的读性能和写性能,理想的LRU应该可以在O(1)
的时间内读取一条数据或更新一条数据,也就是说读写的时间复杂度都是O(1)
。
此时很容易想到使用哈希表,根据数据的键访问数据可以达到O(1)
的速度。但是更新缓存的速度却无法达到O(1),因为需要确定哪一条数据的访问时间最早,这需要遍历所有缓存才能找到。
因此,我们需要一种既按访问时间排序,又能在常数时间内随机访问的数据结构。
这可以通过哈希表+双向链表实现:
- 哈希表保证通过key访问数据的时间为O(1).
- 双向链表则按照访问时间的顺序依次穿过每个数据。
之所以选择双向链表而不是单链表,是为了可以从中间任意结点修改链表结构,而不必从头结点开始遍历。
图解示例
假如我们设计一个容量大小为4的LRU缓存。
1.先添加4个元素
上排是哈希表的 key, 我们依次添加:k1, k2, k3, k4
。
下排是哈希表的 node 结构体,里面包括(key, value) pair
,我们用双向链表连接。分别为n1, n2, n3, n4
。
最新添加的在链表头部,表示最近使用。
2.添加k5
把k5放在哈希表中,然后把n5放在链表头部,此时由于hash表的size大于容量4,我们需要删除一个元素,从尾部删除,尾部代表最久没使用。
同时从哈希表中删除尾部n1对应的k1。
3.访问k3
k3最近访问,把n3从当前位置删除,并插入到链表头部。
结论:
- 每次添加元素到链表中的时候都是从头部添加
- 每次删除元素的时候都是从尾部删除
- 删除的时候同时从哈希表里面删除对应的key
- 再次访问的元素,需要把元素移动到链表的头部
Leetcode
Leetcode有LRU Cache
经典算法题,这道题并不难,也是我当面试官经常考的一道题。
这道题算是LRU实现的简单版本,可以当作入门练习。
https://leetcode.com/problems/lru-cache/
146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类:
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
- void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?
C++解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<unordered_map>
using namespace std;
class LRUCache {
public:
struct Node {
Node(int key, int val) {
key_ = key;
val_ = val;
left_ = right_ = nullptr;
}
int key_, val_;
Node* left_, *right_;
};
LRUCache(int capacity) {
capacity_ = capacity;
head_ = new Node(-1, -1);
tail_ = new Node(-1, -1);
head_->right_ = tail_;
tail_->left_ = head_;
}
~LRUCache() {
Node *node = head_;
while (node != nullptr) {
Node *next = node->right_;
delete node;
node = next;
}
}
int get(int key) {
if(hash_.count(key) == 0) return -1;
Node *node = hash_[key];
if (node->left_ != head_) {
unlink(node);
insertToHead(node);
}
return node->val_;
}
void put(int key, int value) {
if (hash_.count(key) == 0) {
if (hash_.size() >= capacity_) {
Node *node = tail_->left_;
unlink(node);
hash_.erase(node->key_);
delete node;
}
Node *node = new Node(key, value);
hash_[key] = node;
insertToHead(node);
} else {
Node *node = hash_[key];
node->val_ = value;
if (node->left_ != head_) {
unlink(node);
insertToHead(node);
}
}
}
void insertToHead(Node *node) {
node->right_ = head_->right_;
head_->right_ = node;
node->left_ = head_;
node->right_->left_ = node;
}
void unlink(Node *node) {
node->left_->right_ = node->right_;
node->right_->left_ = node->left_;
}
private:
int capacity_;
unordered_map<int, Node*> hash_;
Node *head_, *tail_;
};
开源项目应用
这里我会介绍LRU在各个常用的开源项目中的使用。
我会用尽量简短的语言概述,但是又能尽量包含关键信息。
Redis中使用LRU淘汰策略
Redis 作为缓存使用时,一些场景下需要考虑内存的空间消耗问题。
Redis 有很多淘汰策略,其中和LRU相关的有其中的两种:
allkeys-lru: 对所有的键都采取LRU淘汰
volatile-lru: 仅对设置了过期时间的键采取LRU淘汰
我们知道,LRU算法需要一个双向链表来记录数据的最近被访问顺序,但是出于节省内存的考虑,Redis的LRU算法并非完整的实现。
Redis并不会选择最久未被访问的键进行回收,相反它会尝试运行一个近似LRU的算法,通过对少量键进行取样,然后回收其中的最久未被访问的键。通过调整每次回收时的采样数量maxmemory-samples,可以实现调整算法的精度。
在Redis3.0中,还新增加了一个淘汰池,本质上它是一个大根堆,新随机出来的key会添加到淘汰池,然后淘汰最旧的key。
关于Redis的淘汰策略或者LRU源码分析,也可以单独出一遍博客分析,这里篇幅所限不做详细分析了。
MySQL中InnoDB引擎中缓存池LRU算法
InnoDB的缓存池:简单来说就是一块内存区域,该区域内缓存着InnoDB访问存储在磁盘的数据和索引信息。缓冲池有两个作用,一是提高了大容量读取操作的效率,二是提高了缓存管理的效率。
MySQL的InnoDB引擎从磁盘加载数据页到缓存池时,往往连带着目标数据页相邻的数据页一起加载到缓存池中–MySQL预读机制。
为什么MySQL
会存在预读机制呢?
其实就是提升性能。
但是另一方面可能会发生,预读进去的数据页几乎不被访问,但是由于LRU的特性,这部分数据页在预读进去后会处于链表的头节点附近,还可能淘汰一部分本身访问比较频繁的数据页。
所以MySQL采用了基于冷热隔离的LRU策略
LRU链被拆为两部分:一部分存储热数据,一部分存储冷数据。
当数据初次加载到缓存池中时,会首先放在冷链的头部,经过 innodb_old_blocks_time (默认1s)后如果再被访问,则将缓存页移动至热链头部。
实际业务使用
实际业务中主要针对热点数据使用内存LRU缓存来降低后端数据库或者Redis缓存的压力。
电商大促
大促期间秒杀促销或者人气店铺
我们在实际业务中使用了LRU缓存,主要是为了解决热点数据的访问问题。
我们的一些数据存在MySQL中,然后使用Redis的集群作为缓存。平时由于命中率比较高,MySQL的读取的QPS相对比较低,一切都很顺利。
但是在一些大促活动期间(双11),有些热门店铺的访问量就非常高,就导致了一些热点数据,其中几个Redis节点的CPU就直接100%使用率。
于是我们针对热点数据,我们让它通过LRU缓存,来极大的缓解Redis和MySQL的压力。
怎么区分热点数据呢,有两种方式:
- 我们可以在服务端设置一些规则区分热点,请求数据满足特定的规则就认为是热点数据。
- 也可以在API请求中加入一个标记来告诉服务端这个请求的数据当作热点数据来处理,比如秒杀页面的请求就可以自动带有这个标记。
当请求到达的时候,就看是否匹配热点标记,如果是热点数据,查询LRU缓存,如果命中直接返回。 不命中就继续向Redis读取,并写入LRU,Redis如果也不命中就向MySQL读取,写入Redis。这样层层的方式,可以极大的减轻Redis和MySQL的压力。
微博热搜
还有一种类似的场景就是微博热搜。
微博热搜也是一种瞬间大流量的热点数据,经常听到明星八卦导致微博直接宕机,就是热点数据没有处理好的会导致的风险。
一般可以对从热点页面进入的请求或者被服务器标记为热点的事件,都当做是热点数据,经过LRU缓存。
总结
LRU是一个在产品业务中很有用的算法,它追求空间的利用率,使用权衡的方案来把最近最少访问的数据剔除出内存。是一个很有用的算法,同时也是找工作面试中经常考察的算法之一,值得我们好好学习。
<全文完>
猜你还喜欢
- 03-29 [编程相关] Winform窗体圆角以及描边完美解决方案
- 03-29 [前端问题] has been blocked by CORS policy跨域问题解决
- 03-29 [编程相关] GitHub Actions 入门教程
- 03-29 [编程探讨] CSS Grid 网格布局教程
- 10-12 [编程相关] python实现文件夹所有文件编码从GBK转为UTF8
- 10-11 [编程算法] opencv之霍夫变换:圆
- 10-11 [编程算法] OpenCV Camshift算法+目标跟踪源码
- 10-11 [Python] python 创建 Telnet 客户端
- 10-11 [编程相关] Python 基于 Yolov8 + CPU 实现物体检测
- 03-15 [脚本工具] 使用go语言开发自动化脚本 - 一键定场、抢购、预约、捡漏
- 01-08 [编程技术] 秒杀面试官系列 - Redis zset底层是怎么实现的
- 01-05 [编程技术] 《Redis设计与实现》pdf
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[电影] 《环太平洋两部合集》 4K REMUX原盘 [杜比视界] 国英双语音轨 [内封特效字幕] [133.8G]
[电影] 异人之下 The Traveller 2024✨【影版】【4K正式版/HQ超高码/DDP5.1】✚【1080高码】无水印/无压缩
[动漫] 头文字D 动漫 (1998) S01-S06季 1080P 国粤日音轨 续作 剧场版 电影
[小说] 知轩藏书全站7667册txt小说合集精心校对版
[杂志] 电脑爱好者杂志14年 超全 [PDF]
[电影] 西游记全部版本-4K高清修复-总计384G-1986+1996+1998+2002+2010浙版+西游记后传
[纪录片] 【国家地理百年纪念典藏】超经典100集全 MP4格式 (绝佳学习资料)27GB
[纪录片] B站食贫道收费纪录片 *迷失东京* [1080P] 揭露日本大家感兴趣却不为人知的秘密
[网络线报] 城通网盘福利线报解析器 - 获取直连下载地址
[福利线报] 一个「脚本」搞定六大网盘(百度/阿里/天翼/迅雷/夸克/移动)
[游戏] 《黑神话悟空》免安装学习版【全dlc整合完整版】+Steam游戏解锁+游戏修改工具!
[动画] 《名侦探柯南》名侦探柯南百万美元的五菱星 [TC] [MP4]
[电视剧集] [BT下载][黑暗城市- 清扫魔 Dark City: The Cleaner 第一季][全06集][英语无字][MKV][720P/1080P][WEB-RAW]
[涨点姿势] 男性性技宝典:14招实战驭女术——爱抚、按摩、催情、姿势、高潮全攻略
[动画] 2002《火影忍者》720集全【4K典藏版】+11部剧场版+OVA+漫画 内嵌简日字幕
[剧集] 《斯巴达克斯》1-4季合集 无删减版 1080P 内嵌简英特效字幕
[CG剧情] 《黑神话:悟空》158分钟CG完整剧情合集 4K120帧最高画质
[短剧] 被下架·禁播的羞羞短剧·午夜短剧合集
[游戏] 黑神话悟空离线完整版+修改器
[图像处理] 光影魔术手v4.6.0.578绿色版
[影视] 美国内战 4K蓝光原盘下载+高清MKV版/内战/帝国浩劫:美国内战(台)/美帝崩裂(港) 2024 Civil War 63.86G
[影视] 一命 3D 蓝光高清MKV版/切腹 / 切腹:武士之死 / Hara-Kiri: Death of a Samurai / Ichimei 2011 一命 13.6G
[影视] 爱情我你他 蓝光原盘下载+高清MKV版/你、我、他她他 2005 Me and You and Everyone We Know 23.2G
[影视] 穿越美国 蓝光原盘下载+高清MKV版/窈窕老爸 / 寻找他妈…的故事 2005 Transamerica 20.8G
[电影] 《黄飞鸿》全系列合集
[Android] 开罗游戏 ▎像素风格的模拟经营的游戏厂商安卓游戏大合集
[游戏合集] 要战便战 v0.9.107 免安装绿色中文版
[资源] 精整2023年知识星球付费文合集136篇【PDF格式】
[系统]【黑果小兵】macOS Big Sur 11.0.1 20B50 正式版 with Clover 5126 黑苹果系统镜像下载
[美图] 【经典收藏美图集合】1500多张韩国美女高清图片让你的收藏夹更加丰富多彩
- 最新评论
-
有靳东!嘻嘻奥古斯都.凯撒 评论于:10-28 流星花园是F4处女作也是4人集体搭配的唯一一部!奥古斯都.凯撒 评论于:10-28 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢AAAAA 评论于:10-26 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢password63 评论于:10-26 找了好久的资源,终于在这里找齐了!!!!blog001 评论于:10-21 找了好久的资源,终于在这里找齐了!!!!blog001 评论于:10-21 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢WillKwok 评论于:10-09 感谢分享1234123 评论于:10-07 太好了终于找到了谢谢Tom 评论于:10-07 谢谢分享loonghd 评论于:09-30
- 热门tag