【第258期】今日头条面试题：LRU原理与Redis实现

2022年5月17日 4:06 pm • 面试问题 • 阅读 1 很早之前参加今日头条的采访，遇到一个问题。前半部分是关于如何实现LRU，后半部分是关于如何在Redis中实现LRU。 我的第一反应是我在操作系统课程中学过，应该是内存不足时淘汰旧内容的策略。 LRU...LeastRecentUsed，剔除最不常用的。 我还可以补充几句，因为在计算机架构中，最大、最可靠的存储就是硬盘。容量大，可以固化内容，但访问速度很慢，需要将使用过的内容加载到内存中；内存速度很快，但容量有限，断电后内容会丢失。为了进一步提高性能，CPU内部存在L1 Cache、L2 Cache等概念。 因为速度越快，单位成本越高，容量越小。新的内容不断被加载，旧的内容必须被淘汰，所以就有了这样的使用背景。 LRU原理 一般标准操作系统教材中，都是采用以下方法来演示LRU原理。假设内存只能容纳3个页面大小，页面的访问顺序为7 0 1 2 0 3 0 4。假设内存是按照栈来描述访问时间的。顶部的是最近访问的，下面的是最远访问的。这就是 LRU 的工作原理。 但如果让我们自己设计一个基于LRU的缓存，这个设计可能会有很多问题。这块内存是按照访问时间排序的，会出现大量的内存复制操作，所以性能肯定是无法接受的。 那么如何设计一个LRU缓存，使得插入和删除都是O(1)。我们需要维护访问顺序，但无法通过内存中真正的排序来体现。一种解决方案是使用双向链表。 基于HashMap和双向链表实现LRU 总体设计思路是可以使用HashMap来存储key，这样保存和获取key的时间都是O(1)，并且HashMap的Value指向双向链表实现的LRU的Node节点，如下如图所示。LRU存储是基于双向链表实现的，下图展示了其原理。其中h代表双向链表的头，t代表尾部。首先，提前设置LRU容量。如果存储已满，则可以在 O(1) 时间内消除双向链表的尾部。每次添加和访问数据时，都可以将新节点添加到 LRU 中，效率为 O(1)。转到头部，或将现有节点移动到队列的头部。 下面展示了默认大小为3时LRU存储在存储和访问过程中的变化，为了简化图的复杂度，图中没有展示HashMap部分的变化，只展示了LRU双链的变化上图中的列表进行了演示。我们对此 LRU 缓存的操作顺序如下：......            /* 易失性-lru 和 allkeys-lru 策略*/            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU )            {                 for (k = 0; k < server.maxmemory_samples; k++) {                    sds thiskey;                    long thisval;                    robj *o;                     de = dictGetRandomKey(dict);                    thiskey = dictGetKey(de);                    /* When policy is volatile-lru we need an additional lookup                     * to locate the real key, as dict is set to db-> 过期。* /                    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)                        de = dictFind(db->dict, thiskey);                    o = dictGetVal(de );                    thisval = estimateObjectIdleTime(o);                     /* 空闲时间越长越适合删除*/                     if ( bestkey == NULL || thisval > bestval) {                        bestkey = thiskey;                       bestval = thisval;                    }                 }            }            ...... Redis会基于server.maxmemory_samples配置一些固定数量的key，然后比较它们的lru访问时间，然后剔除最近最近没有访问的key，maxmemory_samples的值很大，Redis的近似LRU算法近似于严格LRU算法，但相应消耗也变高，对性能有一定影响，样本值默认为5。 总结看来，虽然是一个简单的概念，但在工业产品中，为了追求空间利用率，也采用了权衡的实现方案。 来源：www.sychzs.cn/hopeztm/article/details/79547052 结尾 推荐十期 【第241期】面试官：你了解JVM中的ZGC垃圾收集器吗？ 【第242期】面试官：Spring AOP中有哪些通知类型，它们的执行顺序是什么？ 【第243期】面试官：什么是前缀索引，为什么要使用它，在什么场景下使用？ 【第244期】一万字+图解Redis，面试不用愁！ 【第245期】面试官：MySQL死锁的原因有哪些，如何避免？ 【第246期】面试官：说说你对RabbitMQ的理解以及使用场景【第247期】记住你在Java面试中遇到的三个问题和感悟！ 【第248期】面试官：能介绍一下Java8中Stream列表去重的几种方法吗？ 【第249期】关于Java中的异常，面试时可以问的问题全在这里！ 【第250期】关于Mybatis知识点，面试能问的都在这里！ 而不是在网上搜索问题？还不赶快关注我们吧~ 版权声明：本文内容由网友自愿贡献，本文所表达的观点仅代表作者自己的观点。本网站仅提供信息存储空间服务，不拥有任何所有权，也不承担相关法律责任。如果您发现本站有任何涉嫌侵权/非法内容，请发送邮件举报。一经核实，该网站将立即删除。 本文由斑马博客整理。本文链接为：https://www.sychzs.cn/index.php/post/8084.html