Java教程

【架构师面试-缓存与搜索-1】-缓存与缓存置换策略源码实现

本文主要是介绍【架构师面试-缓存与搜索-1】-缓存与缓存置换策略源码实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1:什么是缓存

缓存:加速数据访问的存储,降低延迟(latency),提升吞吐量(Throughput)的利器。

1:缓存演进历史

1. 查库

2. ConcurrentHashMap

3. LRU

4. Guava Cache

5. 分布式缓存(redis,MemCache)

6. 多级缓存

2:在什么地方加缓存

缓存对于每个开发者来说是相当熟悉了,为了提高程序的性能我们会去加缓存,但是在什么地方加缓存,如何加缓存呢?

举个栗子:假设一个网站,需要提高性能,缓存可以放在浏览器,可以放在反向代理服务器,还可以放在应用程序进程内,同时可以放在分布式缓存系统中。

从用户请求数据到数据返回,数据经过了浏览器,CDN,代理服务器,应用服务器,以及数据库各个环节。每个环节都可以运用缓存技术。从浏览器/客户端开始请求数据,通过 HTTP 配合 CDN 获取数据的变更情况,到达代理服务器(Nginx)可以通过反向代理获取静态资源。再往下来到应用服务器可以通过进程内(堆内)缓存,分布式缓存等递进的方式获取数据。如果以上所有缓存都没有命中数据,才会回源到数据库。

缓存的顺序:用户请求 → HTTP 缓存 → CDN 缓存 → 代理服务器缓存 → 进程内缓存 → 分布式缓存 →数据库。

距离用户越近,缓存能够发挥的效果也就越好。

3:缓存读写流程

缓存读取:没有读取到数据就读取缓存后的存储

关注穿透路径:一级-->二级 --> 三级 --> 内存 --> 磁盘

穿透率:

命中缓存(hit)

穿透缓存(Penetration)

穿透率:没有命中/总访问次数

命中率:1-穿透率

缓存写入:什么时候写入

write Through:穿透写入

Write Back:回写

预先写入:预热

延迟写入:定时、事件触发

2:缓存置换策略

空间有限,先到先得(FIFO),保留热数据,移除冷数据【什么样的数据是冷数据?】

FIFO

先进先出,先进入缓存的会先被淘汰。

最简单的策略,但是会导致我们命中率很低。

试想一下我们如果有个访问频率很高的数据是所有数据第一个访问的,而那些不是很高的是后

面再访问的,那这样就会把我们的首个数据但是他的访问频率很高给挤出。

最近最久未使用(Least Recently Used)简称LRU

在这种算法中避免了上面的问题,每次访问数据都会将其放在我们的队头,如果需要淘汰数

据,就只需要淘汰队尾即可。

潜在问题:淘汰热点数据,如果有个数据在1个小时的前59分钟访问了1万次(可见这是个热点

数据),再后一分钟没有访问这个数据,但是有其他的数据访问,就导致了我们这个热点数据被

淘汰。

最近最少使用(Least Frequently Used) 简称LFU

利用额外的空间记录每个数据的使用频率,然后选出频率最低进行淘汰。这样就避免了LRU不能处理时间段的问题。

最近最常使用算法(MRU)

这个缓存算法最先移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久,越容易被访问的情况。

自适应缓存替换算法(ARC)

在IBM Almaden研究中心开发,这个缓存算法同时跟踪记录LFU和

LRU,以及驱逐缓存条目,来获得可用缓存的最佳使用。

3:LRU(Least Frequently Used) 跳表在LRU中的应用

1. FIFO:先进先出

2. LRU:最近最少使用算法。

3. LFU:最近最少频率使用。

上面列举了三种淘汰策略,对于这三种,实现成本是一个比一个高,同样的命中率也是一个比一个好。

而我们一般来说选择的方案居中即可,即实现成本不是太高,而命中率也还行的LRU。

如何实现一个LRU

①我们可以通过继承LinkedHashMap,重写removeEldestEntry方法,即可完成一个简单的LRU。

②在LinkedHashMap中维护了一个entry(用来放key和value的对象)链表。

③在每一次get或者put的时候都会把插入的新entry,或查询到的老entry放在我们链表末尾。

④可以注意到我们在构造方法中,设置的大小特意设置到max*1.4,在下面的removeEldestEntry方法中只需要size>max就淘汰,这样我们这个map永远也走不到扩容的逻辑了,通过重写LinkedHashMap,几个简单的方法我们实现了我们的LRUMap。

class LRUMap extends LinkedHashMap {
private final int max;
private Object lock;
public LRUMap(int max, Object lock) {
//重点1:无需扩容
super((int) (max * 1.4f), 0.75f, true);
this.max = max;
this.lock = lock;
}
/**
* 重点2:重写LinkedHashMap的removeEldestEntry方法即可,在Put的时候判断,
如果为true,就会删除最老的
*/
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > max;
}
public Object getValue(Object key) {
synchronized (lock) {
return get(key);
}
}
public void putValue(Object key, Object value) {
synchronized (lock) {
put(key, value);
}
}
public boolean removeValue(Object key) {
synchronized (lock) {
return remove(key) != null;
}
}
public boolean removeAll(){
clear();
return true;
}
}

如果您觉得文章好看,欢迎点赞收藏加关注,一连三击呀,感谢!!☺☻ 

这篇关于【架构师面试-缓存与搜索-1】-缓存与缓存置换策略源码实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!