① lru算法是什么
lru算法是一种页面置换算法，在对于内存中但是又不用的数据块，叫做LRU，操作系统会根据那些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。
LRU算法：最近最少使用，简单来说就是将数据块中，每次使用过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据剔除掉这就是LRU算法。
如果进程被调度，该进程需要使用的外存页（数据）不存在于数据块中，这个现象就叫做缺页。如果这个数据此时不在，就会将这个数据从加入到数据块首部。
数据块插入与剔除：每次有新数据到来时，会将其放入数据块首部，当数据每次被访问时，将这个数据插入数据块的首部如果数据块满了，每次新进的数据都会将数据块尾部的数据挤出数据块。
差距
为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。
反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最少使用的那个页面调出内存。这就是LRU算法的全部内容。
LRU在电子系统中的解释：
Line Replaceable Unit—LRU，电子系统中常采用模块化设计，这种可更换的模块单元则被叫做LRU，中文名称是“线性可更换单元”。
② lru算法是什么
是一种缓存淘汰策略。计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。大家肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。
LRU缓存淘汰算法就是一种常用策略，也就是说认为最近使用过的数据应该是是“有用的”，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。
LRU-K原理
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
③ LRU与LFU
LFU的push遇到重复元素不删除key，只是get更新key之后对value进行覆盖。
map<int,pair<int,list<pair<int,int>>::iterator>>KeyFreq 用iterator指向FreqList的List中的一个节点。
在数据访问符合正态分布时，相比于LRU算法，LFU算法的缓存命中率会高一些。
(1)LFU的复杂度要比LRU更高一些。
(2)需要维护数据的访问频次，每次访问都需要更新。
(3)早期的数据相比于后期的数据更容易被缓存下来，导致后期的数据很难被缓存。
(4)新加入缓存的数据很容易被剔除，像是缓存的末端发生“抖动”。
④ lru的算法是什么
lru的算法是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
对于虚拟页式存储，内外存信息的替换是以页面为单位进行的——当需要一个放在外存的页面时，把它调入内存，同时为了保持原有空间的大小，还要把一个内种调动越少，进程执行的效率也就越高。
硬件支持
LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。
寄存器
为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为：
R = Rn-1 Rn-2 Rn-3…R2 R1 R0。
⑤ 分布式存储最佳缓存比
作者：深入细节的 SmartX 一线技术团队
近日，VMware 发布了 vSAN 8，对存储架构进行了重大更新。其中最主要的变化，即引入了新的 Express Storage Architecture（ESA）架构：用“存储池”替代了原存储架构（OSA）中的“磁盘组”，并不再需要专用 SSD 承担缓存加速功能，一定程度上避免了 8.0 之前版本中的专用缓存盘利用率低、易发生缓存击穿等问题。
而值得一提的是，在 vSAN 大版本更新之前，SmartX 即通过统一缓存空间和智能冷热数据管理优化了分布式存储缓存机制，有效规避了上述问题。本文将通过重点解读 vSAN（以 vSAN 7 为例）和 SmartX 分布式块存储组件 ZBS* 缓存机制的原理，并测试对比两种缓存机制下虚拟机性能表现，让读者更好地了解两种技术实现机制的区别对业务可能带来的实际影响。
* ZBS 内置于 SmartX 超融合软件 SMTX OS，可与 SmartX 原生虚拟化 ELF 搭配提供服务。
本文重点
vSAN 7 采用划分读写缓存空间的机制，将缓存磁盘按照容量占比划分为写缓冲区（30%）和读缓存区（70%）。这种方式可能出现缓存利用率低、在访问数据量过大时导致缓存击穿，进而引起性能下降等问题。
ZBS 采用统一缓存空间的机制，并通过 2 级 LRU 算法对冷热数据进行管理，在充分利用缓存容量的同时避免了因访问量激增导致虚拟机性能下降的情况。
本文基于相同的硬件配置和 I/O 读写场景，分别测试 VMware 超融合（vSphere 虚拟化 + vSAN 分布式存储）写入 300 GB 数据、SMTX OS（ELF + ZBS）写入 500 GB 数据时虚拟机的性能表现。结果显示，vSAN 7 难以充分利用缓存介质，发生缓存击穿，导致存储性能下降；而 SMTX OS 即便在写入更多数据的情况下也未发生缓存击穿，虚拟机性能保持稳定。
场景问题
混闪配置是超融合或分布式存储现阶段的主流落地模式。混闪配置是指机器中的磁盘使用 SSD + HDD 混合组成，其中 SSD 磁盘作为数据缓存层，而 HDD 磁盘作为数据容量层。以该模式构建的分布式存储池通过软件算法进行冷热数据自动判断，在提供高性能的同时，还可获得较大的存储容量，进而提升资源利用率，获得相对全闪存储更高的性价比。
在将 SSD 磁盘用作数据缓存层时，部分超融合产品会将缓存容量（Cache）划分为读和写各自独立的两部分。例如，vSAN 7 及更早版本会将每个磁盘组（Disk Group）中的缓存磁盘，按照容量占比划分为写缓冲区（30%）和读缓存区（70%），当读取数据未命中缓存或者写缓存已满，将会直接从容量层进行读写。
⑥ LRU 缓存淘汰算法
当要缓存某个数据的时候，先在链表中查找这个数据。如果没有找到，则直接将数据放到链表的尾部；如果找到了，我们就把它移动到链表的尾部，然后淘汰头部数据。
因为查找数据需要遍历链表，所以单纯用链表实现的 LRU 缓存淘汰算法的时间复杂很高，是 O(n)。如果我们将散列表和双向链表两种数据结构组合使用，可以将这三个操作的时间复杂度都降低到 O(1)。
因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext 指针是为了将结点串在散列表的拉链中。
这整个过程涉及的查找操作都可以通过散列表来完成。其他的操作，比如删除头结点、链表尾部插入数据等，通过双向链表都可以在 O(1) 的时间复杂度内完成。所以，这三个操作的时间复杂度都是 O(1)。
至此，我们就通过散列表和双向链表的组合使用，实现了一个高效的、支持 LRU 缓存淘汰算法的缓存系统原型。
散列表中数据是经过散列函数打乱之后无规律存储的，但是 LinkedHashMap可以 做到按照数据的插入顺序来存储。
每次调用 put() 函数，往 LinkedHashMap 中添加数据的时候，都会将数据添加到链表的尾部，再次将键值为 3 的数据放入到 LinkedHashMap 的时候，会先查找这个键值是否已经有了，然后，再将已经存在的 (3,11) 删除，并且将新的 (3,26) 放到链表的尾部，访问到 key 为 5 的数据的时候，我们将被访问到的数据移动到链表的尾部。
所以按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统。
散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。
因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列表和链表（或者跳表）结合在一起使用。
⑦ 如何用LinkedHashMap实现LRU缓存算法
缓存这个东西就是为了提高运行速度的，由于缓存是在寸土寸金的内存里面，不是在硬盘
里面，所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List：每次访问一个元素后把这个元素放在
List一端，这样一来最远使用的元素自然就被放到List的另一端。缓存满了t的时候就把那最远使用的元素remove掉。但更实用的是
HashMap。因为List太慢，要删掉的数据总是位于List底层数组的第一个位置，删掉之后，后面的数据要向前补位。。所以复杂度是O(n)，那就
用链表结构的LinkedHashMap呗~，LinkedHashMap默认的元素顺序是put的顺序，但是如果使用带参数的构造函数，那么
LinkedHashMap会根据访问顺序来调整内部 顺序。
LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端，这样一来每次顶端的元素就是remove的元素。
构造函数如下：
public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；
initialCapacity 初始容量
loadFactor 加载因子，一般是 0.75f
accessOrder false 基于插入顺序 true 基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU 最近最少被使用的调度算法）
来个例子吧：
import java.util.*;
class Test
{
public static void main(String[] args) throws Exception{
Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
//现在遍历的话顺序肯定是9,7,5,3
//下面访问了一下9,3这个键值对，输出顺序就变喽~
map.get(9);
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
输出
7
5
3
9
好玩吧~
下面开始实现LRU缓存喽~
import java.util.*;
//扩展一下LinkedHashMap这个类，让他实现LRU算法
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{
//定义缓存的容量
private int capacity;
private static final long serialVersionUID = 1L;
//带参数的构造器
LRULinkedHashMap(int capacity){
//调用LinkedHashMap的构造器，传入以下参数
super(16,0.75f,true);
//传入指定的缓存最大容量
this.capacity=capacity;
}
//实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
}
//测试类
class Test{
public static void main(String[] args) throws Exception{
//指定缓存最大容量为4
Map<Integer,Integer> map=new LRULinkedHashMap<>(4);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
map.put(6,6);
//总共put了5个元素，超过了指定的缓存最大容量
//遍历结果
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
输出结果如下
9=3
9=3
9=3
9=3
9=3
7
5
3
6
分析一下：使用带参数构造器，且启用LRU模式的LinkedHashMap会在每次有新元素加入的时候，判断当前储存元素是否超过了缓存上限，也就是执行
一次removeEldestEntry方法，看最后的遍历结果，发现果然把9删除了，LRU发挥作用了~
⑧ lru算法是什么
LRU是Least Recently Used的缩写，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最少使用的页面予以淘汰。
特点：
LRU 算法弊端是存在偶发性、周期性的批量操会降低缓存的命中率，对缓存造成污染，下面几个就是改进算法。
LRU-K会记录每条数据的访问历史，当达到 k 时，才将数据存放到缓存，在缓存内存回收时，缓存中越接近 k 的数据被优先删除。
Two queues（2Q）相当于 LRU-2，区别是访问历史（首次访问）数据缓存于 FIFO 队列，二次及以上的数据存放LRU缓存，FIFO 队列数据遵循该缓存的内存回收机制，LRU缓存数据遵循该缓存的内存回收机制。
⑨ 页面置换算法之LRU算法
三种常见的页面置换算法:FIFO、LFU、LRU
参考：
缓存算法（页面置换算法）-FIFO、LFU、LRU
LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是： 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小 。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1
如果让我们设计一个LRU Cache的数据结构，它应该支持两个操作：
一种是采用数组来存储每个数据项，再对每个key关联一个时间戳，在cache中维护一个最大时间戳，其设计要点如下：
另一种是采用hashmap+双向链表的数据结构，其设计要点如下：
对比上一节的两种设计思路，不难发现，设计1需要为每个key维护一个时间戳，而且set和get操作的时间复杂度都是O(n)。显而易见，随着数据量的增大，set和get操作的速度越来越慢。而设计2通过采用hashmap+双向链表，set和get操作的时间复杂度只需O(1)，下面给出设计2的具体实现。
运行结果为：
参考：
LRU Cache
LRU原理和Redis实现——一个今日头条的面试题
⑩ 举例说明用LRU替换策略cache命中率如何计算
近期最少使用法（LRU法）
近期最少使用（Least Recently Used，LRU）算法。这种方法是将近期最少使用的Cache中的信息块替换出去。该算法较先进先出算法要好一些。但此法也不能保证过去不常用将来也不常用。
LRU法是依据各块使用的情况， 总是选择那个最近最少使用的块被替换。这种方法虽然比较好地反映了程序局部性规律，但是这种替换方法需要随时记录Cache中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU算法相对合理，但实现起来比较复杂，系统开销较大。通常需要对每一块设置一个称为计数器的硬件或软件模块，用以记录其被使用的情况。
实现LRU策略的方法有多种。 下面简单介绍计数器法、寄存器栈法及硬件逻辑比较对法的设计思路。
计数器方法：缓存的每一块都设置一个计数器，计数器的操作规则是：
(1) 被调入或者被替换的块， 其计数器清“0”，而其它的计数器则加“1”。
(2) 当访问命中时，所有块的计数值与命中块的计数值要进行比较，如果计数值小于命中块的计数值，则该块的计数值加“1”；如果块的计数值大于命中块的计数值，则数值不变。最后将命中块的计数器清为0。
(3) 需要替换时，则选择计数值最大的块被替换。