皮皮网

1.LRU的缓缓存原理是什么？ Redis是如何实现LRU的？
2.keep-alive的vue2和vue3的源码以及LRU算法
3.聊聊缓存淘汰算法-LRU 实现原理
4.java如何实现简单lru缓存机制?
5.实现LRU/LFU缓存
6.缓存驱逐算法原理与实现：LRU、CLOCK、存源LFU

LRU的实现原理是什么？ Redis是如何实现LRU的？

       深入探索：Redis与MySQL中LRU算法的原理与实现

       LRU算法，全称Least Recently Used，缓缓存即最近最少使用，存源是实现八六互联知识付费源码一种数据管理和淘汰策略，常被用于操作系统和数据库优化。缓缓存在面试中，存源它是实现热门话题，尤其是缓缓存在Redis和MySQL这样的数据存储系统中，如何高效地利用内存，存源LRU算法起着关键作用。实现本文将深入解析LRU的缓缓存工作原理，以及Redis和MySQL中的存源具体实现和优化。

       首先，实现LRU的核心思想是缓存那些最近被频繁访问的数据，以减少磁盘I/O操作。当缓存空间满时，会淘汰最长时间未被访问的数据。以一个缓存容量为3的示例来说：

       1. 访问1，数据不在缓存，加载到缓存，链表变为[1]；

       2. 访问2，加载[2,1]，2成为新访问数据，排在1前面；

       3. 访问3，加载[3,2,1]，3是最新的，链表不变；

       4. 访问4，满载，淘汰1，链表变为[4,3,2]；

       5. 再次访问3，链表变为[3,4,2]。

       在实际应用中，LRU的实现通常结合双向链表和哈希表，通过更新访问时间并在链表头部插入新访问数据来管理缓存。然而，Redis作为内存型数据库，为了节省空间和性能，它没有采用传统链表+哈希表的方式，而是利用对象结构体中的访问时间字段，通过随机采样淘汰数据，减少了内存开销。

       Redis的内存淘汰策略包括volatile-lru和allkeys-lru，其中LRU是核心。不同于哈希表的频繁移动，Redis采用更高效的随机采样策略，减少不必要的在线阅读 源码操作。

       在MySQL的InnoDB引擎中，Buffer Pool的LRU策略则更为复杂。它分为年轻区域（最近访问）和旧区域（访问次数较少），遵循空间局部性原理。初次读取时，页面会被放入旧区域，只有当真正被访问时才会移动到年轻区域。为避免全表扫描导致的缓存污染，InnoDB引入了innodb_old_blocks_time参数，限制了旧区域页面移动到年轻区域的时间，保持热点数据的稳定性。

       总结来说，无论是Redis的内存优化还是MySQL的Buffer Pool管理，LRU算法都是关键一环。它在内存有限的场景下，通过智能的淘汰策略，确保了数据的高效访问，提升了系统的整体性能。深入理解LRU，能帮助我们更好地驾驭这些数据存储技术。

keep-alive的vue2和vue3的源码以及LRU算法

       0.LRU算法

       LRU（leastrecentlyused）根据数据的历史记录来淘汰数据，重点在于保护最近被访问/使用过的数据，淘汰现阶段最久未被访问的数据

       LRU的主体思想在于：如果数据最近被访问过,那么将来被访问的几率也更高

       经典的LRU实现一般采用双向链表+Hash表。借助Hash表来通过key快速映射到对应的链表节点，然后进行插入和删除操作。这样既解决了hash表无固定顺序的缺点，又解决了链表查找慢的缺点。

       但实际上在js中无需这样实现，可以参考文章第三部分。先看vue的keep-alive实现。

1.keep-alive

       keep-alive是vue中的内置组件，使用KeepAlive后，被包裹的组件在经过第一次渲染后的vnode会被缓存起来，然后再下一次再次渲染该组件的时候，直接从缓存中拿到对应的vnode进行渲染，并不需要再走一次组件初始化，render和patch等一系列流程，减少了script的执行时间，性能更好。

       使用原则：当我们在某些场景下不需要让页面重新加载时我们可以使用keepalive

       当我们从首页–>列表页–>商详页–>再返回，这时候列表页应该是需要keep-alive

       从首页–>列表页–>商详页–>返回到列表页(需要缓存)–>返回到首页(需要缓存)–>再次进入列表页(不需要缓存)，这时候可以按需来控制页面的keep-alive

       在路由中设置keepAlive属性判断是否需要缓存。

2.vue2的实现

       实现原理：通过keep-alive组件插槽，获取第一个子节点。根据include、exclude判断是否需要缓存，通过组件的flash动画源码key，判断是否命中缓存。利用LRU算法，更新缓存以及对应的keys数组。根据max控制缓存的最大组件数量。

       先看vue2的实现：

exportdefault{ name:'keep-alive',abstract:true,props:{ include:patternTypes,exclude:patternTypes,max:[String,Number]},created(){ this.cache=Object.create(null)this.keys=[]},destroyed(){ for(constkeyinthis.cache){ pruneCacheEntry(this.cache,key,this.keys)}},mounted(){ this.$watch('include',val=>{ pruneCache(this,name=>matches(val,name))})this.$watch('exclude',val=>{ pruneCache(this,name=>!matches(val,name))})},render(){ constslot=this.$slots.defaultconstvnode:VNode=getFirstComponentChild(slot)constcomponentOptions:?VNodeComponentOptions=vnode&&vnode.componentOptionsif(componentOptions){ //checkpatternconstname:?string=getComponentName(componentOptions)const{ include,exclude}=thisif(//notincluded(include&&(!name||!matches(include,name)))||//excluded(exclude&&name&&matches(exclude,name))){ returnvnode}const{ cache,keys}=thisconstkey:?string=vnode.key==null?componentOptions.Ctor.cid+(componentOptions.tag?`::${ componentOptions.tag}`:''):vnode.keyif(cache[key]){ vnode.componentInstance=cache[key].componentInstance//makecurrentkeyfreshestremove(keys,key)keys.push(key)}else{ cache[key]=vnodekeys.push(key)//pruneoldestentryif(this.max&&keys.length>parseInt(this.max)){ pruneCacheEntry(cache,keys[0],keys,this._vnode)}}vnode.data.keepAlive=true}returnvnode||(slot&&slot[0])}}

       可以看到<keep-alive>组件的实现也是一个对象，注意它有一个属性abstract为true，是一个抽象组件，它在组件实例建立父子关系的时候会被忽略，发生在initLifecycle的过程中：

//忽略抽象组件letparent=options.parentif(parent&&!options.abstract){ while(parent.$options.abstract&&parent.$parent){ parent=parent.$parent}parent.$children.push(vm)}vm.$parent=parent

       然后在?created?钩子里定义了?this.cache?和?this.keys，用来缓存已经创建过的?vnode。

       <keep-alive>直接实现了render函数，执行<keep-alive>组件渲染的时候，就会执行到这个render函数，接下来我们分析一下它的实现。

       首先通过插槽获取第一个子元素的vnode：

constslot=this.$slots.defaultconstvnode:VNode=getFirstComponentChild(slot)

       <keep-alive>只处理第一个子元素，所以一般和它搭配使用的有component动态组件或者是router-view。

       然后又判断了当前组件的名称和include、exclude（白名单、黑名单）的关系：

//checkpatternconstname:?string=getComponentName(componentOptions)const{ include,exclude}=thisif(//notincluded(include&&(!name||!matches(include,name)))||//excluded(exclude&&name&&matches(exclude,name))){ returnvnode}functionmatches(pattern:string|RegExp|Array<string>,name:string):boolean{ if(Array.isArray(pattern)){ returnpattern.indexOf(name)>-1}elseif(typeofpattern==='string'){ returnpattern.split(',').indexOf(name)>-1}elseif(isRegExp(pattern)){ returnpattern.test(name)}returnfalse}

       组件名如果不满足条件，那么就直接返回这个组件的vnode，否则的话走下一步缓存：

const{ cache,keys}=thisconstkey:?string=vnode.key==null?componentOptions.Ctor.cid+(componentOptions.tag?`::${ componentOptions.tag}`:''):vnode.keyif(cache[key]){ vnode.componentInstance=cache[key].componentInstance//makecurrentkeyfreshestremove(keys,key)keys.push(key)}else{ cache[key]=vnodekeys.push(key)//pruneoldestentryif(this.max&&keys.length>parseInt(this.max)){ pruneCacheEntry(cache,keys[0],keys,this._vnode)}}

       如果命中缓存，则直接从缓存中拿vnode的组件实例，并且重新调整了key的顺序放在了最后一个；否则把vnode设置进缓存，如果配置了max并且缓存的长度超过了this.max，还要从缓存中删除第一个。

       这里的实现有一个问题：判断是否超过最大容量应该放在put操作前。为什么呢？我们设置一个缓存队列，都已经满了你还塞进来？最好先删一个才能塞进来新的。

       继续看删除缓存的实现：

functionpruneCacheEntry(cache:VNodeCache,key:string,keys:Array<string>,current?:VNode){ constcached=cache[key]if(cached&&(!current||cached.tag!==current.tag)){ cached.componentInstance.$destroy()}cache[key]=nullremove(keys,key)}

       除了从缓存中删除外，还要判断如果要删除的缓存的组件tag不是当前渲染组件tag，则执行删除缓存的组件实例的$destroy方法。

       ————————————

       可以发现，vue实现LRU算法是通过Array+Object，数组用来记录缓存顺序，Object用来模仿Map的功能进行vnode的缓存（created钩子里定义的this.cache和this.keys）

2.vue3的实现

       vue3实现思路基本和vue2类似，这里不再赘述。主要看LRU算法的实现。

       vue3通过set+map实现LRU算法：

constcache:Cache=newMap()constkeys:Keys=newSet()

       并且在判断是否超过缓存容量时的实现比较巧妙：

if(max&&keys.size>parseInt(maxasstring,)){ pruneCacheEntry(keys.values().next().value)}

       这里巧妙的利用Set是可迭代对象的特点，通过keys.value()获得包含keys中所有key的可迭代对象，并通过next().value获得第一个元素，然后进行删除。

3.借助vue3的思路实现LRU算法

       Leetcode题目——LRU缓存

varLRUCache=function(capacity){ this.map=newMap();this.capacity=capacity;};LRUCache.prototype.get=function(key){ if(this.map.has(key)){ letvalue=this.map.get(key);//删除后，再set，相当于更新到map最后一位this.map.delete(key);this.map.set(key,value);returnvalue;}return-1;};LRUCache.prototype.put=function(key,value){ //如果已经存在，那就要更新，即先删了再进行后面的setif(this.map.has(key)){ this.map.delete(key);}else{ //如果map中不存在，要先判断是马士兵 源码否超过最大容量if(this.map.size===this.capacity){ this.map.delete(this.map.keys().next().value);}}this.map.set(key,value);};

       这里我们直接通过Map来就可以直接实现了。

       而keep-alive的实现因为缓存的内容是vnode，直接操作Map中缓存的位置代价较大，而采用Set/Array来记录缓存的key来模拟缓存顺序。

       参考：

       LRU缓存-keep-alive实现原理

       带你手撸LRU算法

       Vue.js技术揭秘

原文;/post/

聊聊缓存淘汰算法-LRU 实现原理

       我们常使用缓存提升数据查询速度，面对缓存容量限制，需要淘汰数据以容纳新数据。常用淘汰算法包括LRU、LFU、FIFO等，本文重点介绍LRU算法。LRU全称Least Recently Used，这一算法假设最近被使用的数据在短时间内再次被访问的几率较高，因此优先淘汰那些长时间未被访问的数据。

       当缓存数据量达到上限，调用获取特定key数据时，LRU算法将该数据移动至链表头部。插入新数据时，同样需要先移除尾部的最少使用数据。LRU算法具体步骤包括：查询数据后移动节点至头部，新数据插入头部。

       为了实现LRU算法，我们采用双向链表与散列表结合的数据结构。双向链表便于快速添加与删除节点，而散列表则提高了节点查找效率。此外，引入哨兵节点简化边界处理，使得操作更为便捷。

       LRU算法代码实现相对简单，关键在于合理利用双向链表与散列表特性。优化后的算法能够高效管理热点与非热点数据，提升系统性能。

       在考量缓存系统时，缓存命中率是核心指标之一。LRU算法在热点数据处理方面表现出色，但面对偶发批量操作时，可能存在缓存污染问题，导致缓存命中率下降，进而影响数据查询速度。

       为解决LRU算法的局限性，引入了改进方案。如MySQL InnoDB中的算法改进，通过将链表分为热数据区与冷数据区，能够有效应对偶发批量操作，避免热门数据被冷数据替换，从而维持较高的缓存命中率。

       其他改进方法，如LRU-K、语音识别 源码2Q、LIRS等算法，各有特点与应用场景，具体选择需根据实际需求与系统特性进行评估。在实际应用中，优化与改进缓存算法是提升系统性能的关键步骤。

java如何实现简单lru缓存机制?

       LRU（Least Recently Used）缓存机制是一种用于优化内存使用的技术，主要思想是优先丢弃最近不常用的缓存项。实现简单，使用双向链表维护缓存项的访问顺序，新元素插入时移除头节点并加入队尾，访问元素时将其移至队尾。

       为保证读写操作的高效性，可采用哈希表和链表结合的方式实现。哈希表用于存储缓存键值对，链表则维护访问顺序。这种方式下，操作逻辑清晰，但直接使用链表可能使读写操作的时间复杂度达到O(n)。优化实现为利用LinkedHashMap，它在默认情况下按照插入顺序排序，通过设置accessOrder=true，可实现按访问顺序排序，每个节点包含前驱和后继指针，便于快速调整节点位置。

       在实现LRUCache时，需通过LinkedHashMap的removeEldestEntry方法，来决定是否移除最不常用的节点。默认情况下，此方法返回false，需子类重写以满足特定需求，如当映射表大小超过上限时，返回true以移除最早访问的节点。

       考虑到多线程安全，可使用SynchronizedMap对所有操作加锁，但此方法并发性能不佳。更优策略是采用读写锁机制，分别处理读取和修改缓存场景。使用ConcurrentHashMap和ConcurrentLinkedDeque作为并发容器，以减少锁定范围，提高读性能。对于get操作，需小心处理加锁范围和一致性问题，确保数据一致性。

       在ConcurrentLRUCache实现中，采用removeLastOccurrence方法替换传统remove操作，以从链表尾部开始遍历，更快找到并删除最近访问的缓存项。这种设计符合LRU算法的假设，即最近访问的数据有更高的概率被后续请求访问。

       完整实现代码如下，展示了如何利用并发容器、读写锁机制以及优化操作顺序，构建高效且线程安全的LRUCache。通过合理设计，保证了缓存机制在多线程环境下的稳定性和性能。

实现LRU/LFU缓存

       实现LRU/LFU缓存

       在计算机系统中，缓存容量有限，因此需要设计淘汰算法以选择替换出去的数据。常见的淘汰算法包括LRU和LFU。

       LRU全称为Least Recently Used（最近最少使用），其核心思想是最近最长时间未被访问的数据最有可能在未来较长时间内也不会被访问，因此应该被优先淘汰。

       实现LRUCache类，需确保get和put函数的平均时间复杂度为O(1)。主要通过双链表和哈希表实现。每次get时，将节点移动至链表尾部；put时检查容量，若已满，则淘汰链表头部节点；然后将新节点插入链表尾部。

       LFU全称为Least Frequently Used（最不经常使用），其核心思想是访问频率最低的数据最有可能在未来较长时间内也不会被访问，因此应该被优先淘汰。

       实现LFUCache类，需确保get和put函数的平均时间复杂度为O(1)。主要通过双链表、哈希表和计数器实现。每次访问节点，更新计数器并调整节点位置。若容量已满，淘汰访问频率最低的节点。

       实现代码如下：

缓存驱逐算法原理与实现：LRU、CLOCK、LFU

       在操作系统与数据库等众多领域中，驱逐策略算法（亦称换出调度算法）被广泛用于实现数据页面在主存与磁盘之间的高频交换。当主存空间不足，需要从磁盘调度新页面时，必须选择一个页面进行驱逐。理想情况下，被驱逐的页面在未来应该尽可能少地再次被换入，而主存中的页面应尽可能多地被访问。因此，研究更有效的驱逐策略算法显得尤为重要。

       本文将详细解析三种驱逐策略算法的原理，并展示它们的C++代码实现。

       LRU（Least-Recently Used 最久未使用）算法采用简单直观的策略，即驱逐缓存中最久未使用的数据。逻辑上，先进入缓存的数据先被移出。为实现这一算法，我们可以使用“双端队列”结构，利用双向链表来构建这样的队列。

       然而，实现过程中需要注意，双端队列中不能出现重复节点。例如，若节点B已在队列中，再次使用B时，需先将其从队列中删除，再从队首插入。否则，单纯的插入操作并未更新节点在队列中的状态。

       因此，我们还需要一种数据结构来记录队列中的节点，哈希表是一个合适的选择。创建哈希表来记录已存在的节点，每次进行put或get操作时，先查询哈希表，若不存在则直接在队首插入新节点；若存在，则先删除后插入。

       接下来，我们将展示LRU的代码实现。首先定义节点结构体，然后构建LRU数据结构，包括哈希表、链表、LRU容量和节点数。接着，编写链表操作函数，例如删除任意节点、从头部插入节点和从尾部删除节点。最后，调用这些函数实现get和put操作函数。

       CLOCK（时钟置换）算法是LRU的变种，具有更“优雅”的外观。为每个节点增加一个bool类型的REF属性，当节点对应页面被使用时，将REF置为true。创建一个clock指针hand，周期性地指向缓存中的每个节点。需要换出时，选择hand遇到的第一个REF=false的节点。当hand遇到一个REF=true的节点时，将其置为false，然后指向下一个节点。

       LFU（Least-Frequently Used 最不常用）算法旨在解决LRU和CLOCK的局限性。在LFU算法中，记录每个节点在缓存中被访问的次数。需要换出时，选择使用次数最少的节点。若存在多个节点持有最小访问次数，则选择这些节点中最久未使用的一个（LRU）。

       LFU需要两种双向链表和两个哈希表。两种链表和相关的节点数据结构实现如下。重点介绍freq_list类下的add_cur_freq函数，使用节点后需将其从freq=x移到freq=x+1的链表头部。若freq_list中不存在freq=x+1的freq_node，则创建一个新的freq_node插入到freq_list中。

       LFU算法存在局限性：节点的使用次数具有累加性质，导致新加入LFU的节点很可能是下一个被换出的节点，因为其freq最小。相比之下，LRU和CLOCK算法不会出现这个问题，新加入的节点或页面总会在缓存中生存一段时间。

       最后，本文建议读者进一步研究和实现经典的驱逐策略算法。在下一篇文章中，我们将介绍MySQL中buffer pool采用的驱逐算法，它使用的是有冷热区的双向链表。

详解工程师不可不会的LRU缓存淘汰算法

       欢迎来到算法数据结构专题，我们探讨一个常用的缓存算法，LRU。

       LRU代表“最不经常使用”，结合缓存使用。缓存是用于过渡数据的存储，提升响应速度。在工程中，缓存对互联网应用至关重要。

       缓存机制用于存储可能需要的数据，避免重复计算。当请求重复出现时，直接从内存中获取结果，节省时间和计算资源，尤其是在处理复杂的推荐流程。

       以淘宝首页商品推荐为例，通过缓存存储之前的结果，下次请求时直接读取，而非重新计算，显著提高响应速度。

       缓存虽好，但内存有限。LRU算法通过记录最近使用时间，优先淘汰最久未使用的数据，保持缓存价值。当缓存满时，新数据插入前需淘汰最久未使用数据。

       LRU算法通过链表和HashMap实现。链表用于快速插入和删除，HashMap用于快速查找和更新数据。通过节点位置表示使用频率，实现高效管理。

       查找时，检查是否存在，不存在则返回空。存在则更新节点位置至链表尾部。更新时，先检查是否已存在，再根据缓存容量调整。若已满，需删除最久未使用数据。

       代码实现上，可以使用自定义链表和HashMap，或利用Python的OrderedDict数据结构简化实现。LRU算法通过合理管理缓存，提高系统性能。

       希望本文内容对您有所帮助。如果有兴趣和喜爱，请三连支持。感谢阅读。

cache中LRU实现方法与对比

       常规的age法在实现缓存的LRU（最近最少使用）策略时，采用存储每个缓存线的age（2位）的方式，总共需要位的存储空间。每次hit后，相关缓存线的age被设置为，之后对同一set的访问，除非hit该缓存线，否则其age会依次递减，最终让最近最多使用的缓存线变为最久未使用的。这种方式下，对同一set的访问三次后，最近最少使用的缓存线会变为最久未使用的。

       伪LRU方法，根据姚永斌老师的《超标量处理器设计》一书中的描述，对8-way缓存，需要使用7位来实现LRU逻辑。这种方法通过三级逻辑串行判定最旧的缓存线。初始时，所有位都是空的，hit中了某个缓存线后，对应位变为。之后hit中其他缓存线，位的变化会继续进行。这种方法虽然节省了位数，但并不精确，因为最近访问的缓存线会刷新所属分组，如果该分组中包含最旧的缓存线，则会直接导致miss。以特定的hit顺序初始化后，寻找最旧缓存线的过程会导致四个位置的错位，这种现象在任意顺序初始化的情况下也可能发生。

       age matrix方法则使用了一种更为复杂的方式实现LRU策略。它使用了寄存器构建了一个大小为x的双端口tagram，data宽度为位，包含有效位和tag位，其中LRU位用于记录访问顺序。通过计算得到的dc_hit_way和LRU位进入LRU模块，模块内部是一个2x2的age矩阵。这种方法通过抽象的代码实现，其写法涉及了获取更新、更新矩阵上半部的三角形以及对应矩阵位置的映射，通过循环操作实现了矩阵的更新和选择最旧缓存线的过程。相较于其他方法，age matrix方法在实现LRU时可能需要更多的位宽（如8-way Dcache需要位），但同样效果下，它能够节省每组的4位位宽。

       在比较这些方法的优劣时，age matrix方法能够在八次访问后将最近最多使用的缓存线变为最久未使用的缓存线，而采用2位age的方法只能坚持三次。如果需要坚持八次，则age需要增加到4位，成本变为位。因此，age matrix方法在同样效果下节省了位宽。另一方面，age方法的灵活性更高，可以根据缓存线数量调整age位宽，尽管这会牺牲一些精度。伪LRU方法则在节省位数方面表现出色，但其精确度有限，并且实现上存在timing问题。