如何设计一个本地缓存?需要考虑哪些方面?
缓存的应用很多,比如操作系统中的页面置换,计算机网络中的网站缓存,DNS缓存,数据库中的缓存
更多场景设计题参看:
场景设计题 汇总 (一)_trigger333的博客-CSDN博客
目录
DNS的缓存,浏览器页面的缓存,内容分发网络CDN也是缓存。
面试官:设计一个本地缓存,需要考虑那些点?_胡庚申的博客-CSDN博客
缓存需要考虑的点
考虑点主要在数据用何种方式存储,能存储多少数据,多余的数据如何处理等几个点,
1.数据结构
首要考虑的就是数据该如何存储,用什么数据结构存储,最简单的就直接用Map来存储数据;或者复杂的如redis一样提供了多种数据类型哈希,列表,集合,有序集合等,底层使用了双端链表,压缩列表,集合,跳跃表等数据结构;
2.对象上限
因为是本地缓存,内存有上限,所以一般都会指定缓存对象的数量比如1024,当达到某个上限后需要有某种策略去删除多余的数据;
3.清除策略
上面说到当达到对象上限之后需要有清除策略,常见的比如有LRU(最近最少使用)、FIFO(先进先出)、LFU(最近最不常用)、SOFT(软引用)、WEAK(弱引用)等策略;
4.过期时间
除了使用清除策略,一般本地缓存也会有一个过期时间设置,比如redis可以给每个key设置一个过期时间,这样当达到过期时间之后直接删除,采用清除策略+过期时间双重保证;
5.线程安全
像redis是直接使用单线程处理,所以就不存在线程安全问题;而我们现在提供的本地缓存往往是可以多个线程同时访问的,所以线程安全是不容忽视的问题;并且线程安全问题是不应该抛给使用者去保证;
6.简明的接口
提供一个傻瓜式的对外接口是很有必要的,对使用者来说使用此缓存不是一种负担而是一种享受;提供常用的get,put,remove,clear,getSize方法即可;
7.是否持久化
这个其实不是必须的,是否需要将缓存数据持久化看需求;本地缓存如ehcache是支持持久化的,而guava是没有持久化功能的;分布式缓存如redis是有持久化功能的,memcached是没有持久化功能的;
8.阻塞机制
在看Mybatis源码的时候,二级缓存提供了一个blocking标识,表示当在缓存中找不到元素时,它设置对缓存键的锁定;这样其他线程将等待此元素被填充,而不是命中数据库;其实我们使用缓存的目的就是因为被缓存的数据生成比较费时,比如调用对外的接口,查询数据库,计算量很大的结果等等;这时候如果多个线程同时调用get方法获取的结果都为null,每个线程都去执行一遍费时的计算,其实也是对资源的浪费;最好的办法是只有一个线程去执行,其他线程等待,计算一次就够了;但是此功能基本上都交给使用者来处理,很少有本地缓存有这种功能;
具体例子
面试官:给我实现一下带有过期时间的LRU(java版)
在Node中加入过期时间属性,表示该缓存key在 time时间过期。
在添加缓存时,也把缓存加入到一个小根堆中,堆顶表示过期时间最近的缓存。
再起一个线程,while true循环判断 堆顶缓存是否已经过期,如果过期就删除,没有过期就继续判断。
Redis中的缓存策略
Redis 提供 8 种数据淘汰策略
两种LRU 不同是删除数据的集合不同 第一种是已设置过期时间的数据集
第二种是当前的键空间,包含所有的键。
两种LFU的区别和LRU一样。
1. volatile-lru ( least recently used ) :从已设置过期时间的数据集( server.db[i].expires )
中挑选最近最少使⽤的数据淘汰
2. volatile-ttl :从已设置过期时间的数据集( server.db[i].expires )中挑选将要过期的数据淘汰
3. volatile-random :从已设置过期时间的数据集( server.db[i].expires )中任意选择数据淘汰
4. allkeys-lru(least recently used):当内存不⾜以容纳新写⼊数据时,在键空间中,移除
最近最少使⽤的 key(这个是最常⽤的)
5. allkeys-random :从数据集( server.db[i].dict )中任意选择数据淘汰
6. no-eviction :禁⽌驱逐数据,也就是说当内存不⾜以容纳新写⼊数据时,新写⼊操作会报
错。
7. volatile-lfu ( least frequently used ) :从已设置过期时间的数据集 (server.db[i].expires) 中
挑选最不经常使⽤的数据淘汰
8. allkeys-lfu ( least frequently used ) :当内存不⾜以容纳新写⼊数据时,在键空间中,移
除最不经常使⽤的 key
操作系统中的页面置换
最优置换算法
先进先出算法
LRU算法
DNS的缓存,浏览器页面的缓存,内容分发网络CDN也是缓存。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/92823.html