开发app和做网站,如何下载网站模板,推广竞价,应用分析网站本章我们会对失效算法做个简单介绍#xff0c;包括常用的失效算法#xff08;先来先淘汰#xff08;FIFO#xff09;、最久未用淘汰#xff08;LRU#xff09;、最近最少使用#xff08;LFU#xff09;#xff09;的概述、实现方式、典型场景做个说明。
什么是失效算…本章我们会对失效算法做个简单介绍包括常用的失效算法先来先淘汰FIFO、最久未用淘汰LRU、最近最少使用LFU的概述、实现方式、典型场景做个说明。
什么是失效算法
失效算法常见于缓存系统中。因为缓存往往占据大量内存而内存空间是相对昂贵且空间有限的那么针对一部分值就要依据相应的算法进行失效或移除操作。
先来先淘汰FIFO
概述
First In First Out先来先淘汰。这种算法在每一次新数据插入时如果队列已满则将最早插入的数据移除。
实现
可以方便的借助LinkedList来实现 我们借助一个案例来进行理解可以重点关注下注释
package com.ls.cloud.sys.alg.release;import java.util.Iterator;
import java.util.LinkedList;public class FIFO {LinkedListInteger fifo new LinkedListInteger();int size 3;//添加元素public void add(int i){fifo.addFirst(i);if (fifo.size() size){fifo.removeLast();}print();}//缓存命中public void read(int i){IteratorInteger iterator fifo.iterator();while (iterator.hasNext()){int j iterator.next();if (i j){System.out.println(find it!);print();return ;}}System.out.println(not found!);print();}//打印缓存public void print(){System.out.println(this.fifo);}//测试public static void main(String[] args) {FIFO fifo new FIFO();System.out.println(add 1-3:);// 添加1-3fifo.add(1);fifo.add(2);fifo.add(3);System.out.println(add 4:);// 添加4会挤出第一个进入的1fifo.add(4);System.out.println(read 2:);// 读取2进行遍历先进来的先打印fifo.read(2);System.out.println(read 100:);// 读取100进行遍历先进来的先打印fifo.read(100);System.out.println(add 5:);// 添加4会挤出第一个进入的2fifo.add(5);}
}
结果
add 1-3:
[1]
[2, 1]
[3, 2, 1]
add 4:
[4, 3, 2]
read 2:
find it!
[4, 3, 2]
read 100:
not found!
[4, 3, 2]
add 5:
[5, 4, 3]优缺点
实现非常简单不管元素的使用情况哪怕有些数据会被频繁用到时间最久也会被踢掉
最久未用淘汰LRU
概述
LRU全称是Least Recently Used即淘汰最后一次使用时间最久远的数值。FIFO非常的粗暴不管有没有用到直接踢掉时间久的元素。而LRU认为最近频繁使用过的数据将来也很大程度上会被频繁用到故而淘汰那些懒惰的数据。LinkedHashMap数组链表均可实现LRU下面仍然以链表为例新加入的数据放在头部最近访问的也移到头部空间满时将尾部元素删除。
实现
同样我们借助一个案例来进行理解可以重点关注下注释
package com.ls.cloud.sys.alg.release;import java.util.Iterator;
import java.util.LinkedList;public class LRU {LinkedListInteger lru new LinkedListInteger();int size 3;//添加元素public void add(int i){lru.addFirst(i);if (lru.size() size){lru.removeLast();}print();}//缓存命中public void read(int i){IteratorInteger iterator lru.iterator();int index 0;while (iterator.hasNext()){int j iterator.next();if (i j){System.out.println(find it!);lru.remove(index);lru.addFirst(j);print();return ;}index;}System.out.println(not found!);print();}//打印缓存public void print(){System.out.println(this.lru);}//测试public static void main(String[] args) {LRU lru new LRU();System.out.println(add 1-3:);// 加入1-3顺序加入lru.add(1);lru.add(2);lru.add(3);System.out.println(add 4:);// 加入4踢出1lru.add(4);System.out.println(read 2:);// 读取22移到首位此时变为[2,4,3]lru.read(2);System.out.println(read 100:);// 读取1002移到首位此时变为[2,4,3]lru.read(100);System.out.println(add 5:);// 加入5踢出最后一个3,5加入最后[5,2,4]lru.add(5);}
}
结果
add 1-3:
[1]
[2, 1]
[3, 2, 1]
add 4:
[4, 3, 2]
read 2:
find it!
[2, 4, 3]
read 100:
not found!
[2, 4, 3]
add 5:
[5, 2, 4]优缺点
性能较高对于偶发性、周期性的数据没有良好的抵抗力很容易就形成缓存的污染影响命中率
最近最少使用LFU
概述
Least Frequently Used即最近最少使用。它要淘汰的是最近一段时间内使用次数最少的值。可以认为比LRU多了一重判断。LFU需要时间和次数两个维度的参考指标。需要注意的是两个维度就可能涉及到同一时间段内访问次数相同的情况就必须内置一个计数器和一个队列计数器算数队列放置相同计数时的访问时间。
实现
package com.ls.cloud.sys.alg.release;public class Dto implements ComparableDto {private Integer key;private int count;private long lastTime;public Dto(Integer key, int count, long lastTime) {this.key key;this.count count;this.lastTime lastTime;}Overridepublic int compareTo(Dto o) {int compare Integer.compare(this.count, o.count);return compare 0 ? Long.compare(this.lastTime, o.lastTime) : compare;}Overridepublic String toString() {return String.format([key%s,count%s,lastTime%s],key,count,lastTime);}public Integer getKey() {return key;}public void setKey(Integer key) {this.key key;}public int getCount() {return count;}public void setCount(int count) {this.count count;}public long getLastTime() {return lastTime;}public void setLastTime(long lastTime) {this.lastTime lastTime;}
}package com.ls.cloud.sys.alg.release;import java.util.Collections;
import java.util.HashMap;
import java.util.Map;public class LFU {private final int size 3;private MapInteger,Integer cache new HashMap();private MapInteger, Dto count new HashMap();//投放public void put(Integer key, Integer value) {Integer v cache.get(key);if (v null) {if (cache.size() size) {removeElement();}count.put(key, new Dto(key, 1, System.currentTimeMillis()));} else {addCount(key);}cache.put(key, value);}//读取public Integer get(Integer key) {Integer value cache.get(key);if (value ! null) {addCount(key);return value;}return null;}//淘汰元素private void removeElement() {Dto dto Collections.min(count.values());cache.remove(dto.getKey());count.remove(dto.getKey());}//更新计数器private void addCount(Integer key) {Dto Dto count.get(key);Dto.setCount(Dto.getCount()1);Dto.setLastTime(System.currentTimeMillis());}//打印缓存结构和计数器结构private void print(){System.out.println(cachecache);System.out.println(countcount);}public static void main(String[] args) {LFU lfu new LFU();//前3个容量没满1,2,3均加入System.out.println(add 1-3:);lfu.put(1, 1);lfu.put(2, 2);lfu.put(3, 3);lfu.print();//1,2有访问3没有加入4淘汰3System.out.println(read 1,2);lfu.get(1);lfu.get(2);lfu.print();System.out.println(add 4:);lfu.put(4, 4);lfu.print();//23次1,42次但是4加入较晚再加入5时淘汰1System.out.println(read 2,4);lfu.get(2);lfu.get(4);lfu.print();System.out.println(add 5:);lfu.put(5, 5);lfu.print();}
}add 1-3:
cache{11, 22, 33}
count{1[key1,count1,lastTime1701744406838], 2[key2,count1,lastTime1701744406838], 3[key3,count1,lastTime1701744406838]}
read 1,2
cache{11, 22, 33}
count{1[key1,count2,lastTime1701744406944], 2[key2,count2,lastTime1701744406944], 3[key3,count1,lastTime1701744406838]}
add 4:
cache{11, 22, 44}
count{1[key1,count2,lastTime1701744406944], 2[key2,count2,lastTime1701744406944], 4[key4,count1,lastTime1701744406946]}
read 2,4
cache{11, 22, 44}
count{1[key1,count2,lastTime1701744406944], 2[key2,count3,lastTime1701744406947], 4[key4,count2,lastTime1701744406947]}
add 5:
cache{22, 44, 55}
count{2[key2,count3,lastTime1701744406947], 4[key4,count2,lastTime1701744406947], 5[key5,count1,lastTime1701744406948]}优缺点 LFU也能够有效的保护缓存相对场景来说比LRU有更好的缓存命中率。由于是以次数为基准因此更加准确天然能有效的保证和提升命中率。 由于LFU须要记录数据的访问频率所以需要额外的空间当访问模式改变的时候算法命中率会急剧降低这也是他最大弊端。
应用场景
redis属于缓存失效的典型应用场景常见策略如下
noeviction: 不删除策略, 达到最大内存限制时, 如果需要更多内存, 直接返回错误信息 比较危险。allkeys-lru对所有key优先删除最近最少使用的 key (LRU)。allkeys-random 对所有key 随机删除一部分听起来毫无道理。volatile-lru只限于设置了 expire 的key优先删除最近最少使用的key (LRU)。volatile-random只限于设置了 expire 的key随机删除一部分。volatile-ttl只限于设置了 expire 的key优先删除剩余时间(TTL) 短的key。
