当前位置:首页 > 服务端 > LRU原理和Redis实现——一个今日头条的面试题

LRU原理和Redis实现——一个今日头条的面试题

2022年11月07日 22:11:16服务端10

看了评论,发现有些地方有问题,更新了图和一些描述,希望可以更清晰一些,也欢迎关注,还会有干货文章

--------

很久前参加过今日头条的面试,遇到一个题,目前半部分是如何实现 LRU,后半部分是 Redis 中如何实现 LRU。

我的第一反应是操作系统课程里学过,应该是内存不够的场景下,淘汰旧内容的策略。LRU ... Least Recent Used,淘汰掉最不经常使用的。可以稍微多补充两句,因为计算机体系结构中,最大的最可靠的存储是硬盘,它容量很大,并且内容可以固化,但是访问速度很慢,所以需要把使用的内容载入内存中;内存速度很快,但是容量有限,并且断电后内容会丢失,并且为了进一步提升性能,还有CPU内部的 L1 Cache,L2 Cache等概念。因为速度越快的地方,它的单位成本越高,容量越小,新的内容不断被载入,旧的内容肯定要被淘汰,所以就有这样的使用背景。

LRU原理

在一般标准的操作系统教材里,会用下面的方式来演示 LRU 原理,假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,LRU就是这样工作的。

LRU原理和Redis实现——一个今日头条的面试题 _ JavaClub全栈架构师技术笔记

但是如果让我们自己设计一个基于 LRU 的缓存,这样设计可能问题很多,这段内存按照访问时间进行了排序,会有大量的内存拷贝操作,所以性能肯定是不能接受的。

那么如何设计一个LRU缓存,使得放入和移除都是 O(1) 的,我们需要把访问次序维护起来,但是不能通过内存中的真实排序来反应,有一种方案就是使用双向链表。

基于 HashMap 和 双向链表实现 LRU 的

整体的设计思路是,可以使用 HashMap 存储 key,这样可以做到 save 和 get key的时间都是 O(1),而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点,如图所示。

LRU 存储是基于双向链表实现的,下面的图演示了它的原理。其中 head 代表双向链表的表头,tail 代表尾部。首先预先设置 LRU 的容量,如果存储满了,可以通过 O(1) 的时间淘汰掉双向链表的尾部,每次新增和访问数据,都可以通过 O(1)的效率把新的节点增加到对头,或者把已经存在的节点移动到队头。

下面展示了,预设大小是 3 的,LRU存储的在存储和访问过程中的变化。为了简化图复杂度,图中没有展示 HashMap部分的变化,仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下:

save("key1", 7)

save("key2", 0)

save("key3", 1)

save("key4", 2)

get("key2")

save("key5", 3)

get("key2")

save("key6", 4)

相应的 LRU 双向链表部分变化如下:

s = save, g = get

总结一下核心操作的步骤:

save(key, value),首先在 HashMap 找到 Key 对应的节点,如果节点存在,更新节点的值,并把这个节点移动队头。如果不存在,需要构造新的节点,并且尝试把节点塞到队头,如果LRU空间不足,则通过 tail 淘汰掉队尾的节点,同时在 HashMap 中移除 Key。

get(key),通过 HashMap 找到 LRU 链表节点,因为根据LRU 原理,这个节点是最新访问的,所以要把节点插入到队头,然后返回缓存的值。

完整基于 Java 的代码参考如下

classDLinkedNode{Stringkey;intvalue;DLinkedNodepre;DLinkedNodepost;}

LRU Cache

publicclassLRUCache{privateHashtablecache=newHashtable();privateintcount;privateintcapacity;privateDLinkedNodehead,tail;publicLRUCache(intcapacity){this.count=0;this.capacity=capacity;head=newDLinkedNode();head.pre=null;tail=newDLinkedNode();tail.post=null;head.post=tail;tail.pre=head;}publicintget(Stringkey){DLinkedNodenode=cache.get(key);if(node==null){return-1;// should raise exception here.}// move the accessed node to the head;this.moveToHead(node);returnnode.value;}publicvoidset(Stringkey,intvalue){DLinkedNodenode=cache.get(key);if(node==null){DLinkedNodenewNode=newDLinkedNode();newNode.key=key;newNode.value=value;this.cache.put(key,newNode);this.addNode(newNode);++count;if(count>capacity){// pop the tailDLinkedNodetail=this.popTail();this.cache.remove(tail.key);--count;}}else{// update the value.node.value=value;this.moveToHead(node);}}/*** Always add the new node right after head;*/privatevoidaddNode(DLinkedNodenode){node.pre=head;node.post=head.post;head.post.pre=node;head.post=node;}/*** Remove an existing node from the linked list.*/privatevoidremoveNode(DLinkedNodenode){DLinkedNodepre=node.pre;DLinkedNodepost=node.post;pre.post=post;post.pre=pre;}/*** Move certain node in between to the head.*/privatevoidmoveToHead(DLinkedNodenode){this.removeNode(node);this.addNode(node);}// pop the current tail.privateDLinkedNodepopTail(){DLinkedNoderes=tail.pre;this.removeNode(res);returnres;}}

那么问题的后半部分,是 Redis 如何实现,这个问题这么问肯定是有坑的,那就是redis肯定不是这样实现的。

Redis的LRU实现

如果按照HashMap和双向链表实现,需要额外的存储存放 next 和 prev 指针,牺牲比较大的存储空间,显然是不划算的。所以Redis采用了一个近似的做法,就是随机取出若干个key,然后按照访问时间排序后,淘汰掉最不经常使用的,具体分析如下:

为了支持LRU,Redis 2.8.19中使用了一个全局的LRU时钟,server.lruclock,定义如下,

#define REDIS_LRU_BITS 24unsignedlruclock:REDIS_LRU_BITS;/* Clock for LRU eviction */

默认的LRU时钟的分辨率是1秒,可以通过改变REDIS_LRU_CLOCK_RESOLUTION宏的值来改变,Redis会在serverCron()中调用updateLRUClock定期的更新LRU时钟,更新的频率和hz参数有关,默认为100ms一次,如下,

#define REDIS_LRU_CLOCK_MAX ((1lru */#define REDIS_LRU_CLOCK_RESOLUTION 1/* LRU clock resolution in seconds */voidupdateLRUClock(void){server.lruclock=(server.unixtime/REDIS_LRU_CLOCK_RESOLUTION)&REDIS_LRU_CLOCK_MAX;}

server.unixtime是系统当前的unix时间戳,当 lruclock 的值超出REDIS_LRU_CLOCK_MAX时,会从头开始计算,所以在计算一个key的最长没有访问时间时,可能key本身保存的lru访问时间会比当前的lrulock还要大,这个时候需要计算额外时间,如下,

/* Given an object returns the min number of seconds the object was never* requested, using an approximated LRU algorithm. */unsignedlongestimateObjectIdleTime(robj*o){if(server.lruclock>=o->lru){return(server.lruclock-o->lru)*REDIS_LRU_CLOCK_RESOLUTION;}else{return((REDIS_LRU_CLOCK_MAX-o->lru)+server.lruclock)*REDIS_LRU_CLOCK_RESOLUTION;}}

Redis支持和LRU相关淘汰策略包括,

volatile-lru设置了过期时间的key参与近似的lru淘汰策略

allkeys-lru所有的key均参与近似的lru淘汰策略

当进行LRU淘汰时,Redis按如下方式进行的,

....../* volatile-lru and allkeys-lru policy */elseif(server.maxmemory_policy==REDIS_MAXMEMORY_ALLKEYS_LRU||server.maxmemory_policy==REDIS_MAXMEMORY_VOLATILE_LRU){for(k=0;kexpires. */if(server.maxmemory_policy==REDIS_MAXMEMORY_VOLATILE_LRU)de=dictFind(db->dict,thiskey);o=dictGetVal(de);thisval=estimateObjectIdleTime(o);/* Higher idle time is better candidate for deletion */if(bestkey==NULL||thisval>bestval){bestkey=thiskey;bestval=thisval;}}}......

Redis会基于server.maxmemory_samples配置选取固定数目的key,然后比较它们的lru访问时间,然后淘汰最近最久没有访问的key,maxmemory_samples的值越大,Redis的近似LRU算法就越接近于严格LRU算法,但是相应消耗也变高,对性能有一定影响,样本值默认为5。

总结

看来,虽然一个简单的概念,在工业界的产品中,为了追求空间的利用率,也会采用权衡的实现方案。

来源链接:https://www.cnblogs.com/ExMan/p/9777440.html

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/server/68430.html

分享给朋友:

“LRU原理和Redis实现——一个今日头条的面试题” 的相关文章

Redis的搭建(win和linux版)

Redis的搭建(win和linux版)

一、Redis是什么 redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。Redis是一种非关系型数据库,我们常用的数据库,例如mysql、Oracle、Sql Server都属于关系型数据库,Redis的...

4.面试必问:线程池的原理是什么?

4.面试必问:线程池的原理是什么?

虽然线程给我们程序带来了更高的执行效率,但是线程不是创建的越多越好,那么线程创建的过多,会带来什么问题呢? 线程之间频繁的进行上下文切换,增加系统的负载 线程的创建和销毁本身也是非常消耗资源的 所以为了解决上面这个问题,让...

59面试常问:MySQL索引是如何提高查询效率的呢?(MySQL面试第二弹)

59面试常问:MySQL索引是如何提高查询效率的呢?(MySQL面试第二弹)

  About MySQL MySQL(读作/maɪ ˈsiːkwəl/“My Sequel”)是一个开放源码的关系数据库管理系统,原开发者为瑞典的MySQL AB公司,目前为Oracle旗下产品。 被甲骨文公司收购后,自由软件社群们...

java基础面试题:运行时异常与一般异常有何异同?error和exception有什么区别? 请写出你最常见到的5个runtimeexception?

Throwable是Java错误处理的父类,有两个子类:Error和Exception。   Error:无法预期的严重错误,导致JVM虚拟机无法继续执行,几乎无法恢复捕捉的 Exception:可恢复捕捉的。java健壮程序的手段。  ...

rabbitmq面试题

rabbit面试题 1.什么是rabbitmq 采用AMQP高级消息队列协议的一种消息队列技术,最大的特点就是消费并不需要确保提供方存在,实现了服务之间的高度解耦 2.为什么要使用rabbitmq 1.在分布式系统下具备异步,削峰...

Java基础:异常怎么分类的(面试题:Exception和Error的区别),看完这篇就都捋清了

1 Throwable类 它是所有异常类型的根类。 其下有2个直接子类:Exception 和 Error。 注意:别看 Throwable 处于异常树形结构的最顶部,但它并不是一个接口,也不是一个抽象类,它是一个具体类。不信大家可以去看源码或JDK文档。 它的类声明是这样...

分布式|redis持久化,面试必问!!!

分布式|redis持久化,面试必问!!!

四、redis持久化 为什么需要持久化? redis的数据都是存放到内存中的,如果突然宕机,数据就会全部丢失,因此必须有一种机制来保证redis在内存中的数据不会丢失,这种机制就叫redis持久化机制。 持久化的方式...

分布式专题|肝了这篇,再也不怕面试官问BIO、NIO、AIO了,我先肝了,你随意

分布式专题|肝了这篇,再也不怕面试官问BIO、NIO、AIO了,我先肝了,你随意

IO模型指的是在网络数据传输过程中,使用什么通道去发送和接收数据,我们常见的有BIO、NIO、AIO(NIO2.0),我接下来会对这些进行详细的介绍 同步/异步/阻塞/非阻塞 到底是什么意思? 同步/异步 指的是你去调用一个方法,如...

python面试题之下面这些是什么意思:@classmethod, @staticmethod, @property?

回答背景知识 这些都是装饰器(decorator)。装饰器是一种特殊的函数,要么接受函数作为输入参数,并返回一个函数,要么接受一个类作为输入参数,并返回一个类。 @标记是语法糖(syntactic sugar),可以让你以简单易读得方式装饰目标对象。 @my...

2019 最全支付宝高级Java现场面试37题

2019 最全支付宝高级Java现场面试37题

支付宝现场三面面试题目,文末有福利:阿里经典面试88题目答案 01 支付宝一面 介绍一下自己。 项目参与的核心设计有哪些 ArrayList和LinkedList底层 HashMap及线...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。