Java电商项目面试--缓存(Guava Cache)

xiaoxiao2021-03-01  14

面试题:手写LRU(今日头条面试题) 面试题:手撕LFU,要求get和put都为O(1)

一、Guava Cache适用场景 1、你愿意消耗一部分内存来提升速度; 2、你已经预料某些值会被多次调用; 3、缓存数据不会超过内存总量; Guava Cache是一个全内存的本地缓存实现,它提供了线程安全的实现机制。整体上来说Guava cache 是本地缓存的不二之选,简单易用,性能好。 二、Guava Cache有以下两种创建方式 Guava提供两种不同的方法来加载数据: CacheLoader:在build cache的时候定义一个CacheLoader来获取数据,适用的情况:有固定的方式可以根据key来加载或计算value的值,比如从数据库中获取数据 Callable:在get的时候传入一个Callable对象,适用的情况:如果从缓存中获取不到数据,则另外计算一个出来,并把计算结果加入到缓存中 本项目采用的是第一种方式:

public class TokenCache { private static Logger logger = LoggerFactory.getLogger(TokenCache.class); public static final String TOKEN_PREFIX = "token_"; //生成本地缓存,初始化为1000,最大为10000,当超过10000时就会使用LRU算法(最小使用算法)进行清除,有效期是12小时 private static LoadingCache<String,String> localCache = CacheBuilder.newBuilder().initialCapacity(1000).maximumSize(10000).expireAfterAccess(12, TimeUnit.HOURS) //缓存有效期12小时 .build(new CacheLoader<String, String>() { //默认的数据加载实现,当调用get取值的时候,如果key没有对应的值,就调用这个方法进行加载. @Override public String load(String s) throws Exception { return "null"; } }); public static void setKey(String key,String value){ localCache.put(key,value); } public static String getKey(String key){ String value = null; try { value = localCache.get(key); if("null".equals(value)) return null; return value; }catch (Exception e){ logger.error("localCache get error",e); } return null; } }

三、缓存回收方式 1、基于容量的回收(size-based eviction),有两种方式,接近最大的size或weight时回收: 基于maximumSize(long):一个数据项占用一个size单位,适用于value是固定大小的情况 基于maximumWeight(long):对不同的数据项计算weight,适用于value不定大小的情况,比如value为Map类型时,可以把map.size()作为weight 回收算法采用的是LRU算法。 2、定时回收(Timed Eviction): expireAfterAccess(long, TimeUnit):缓存项在给定时间内没有被读/写,则回收。 expireAfterWrite(long, TimeUnit):缓存项在给定时间内没有被写访问(创建或覆盖),则回收。 3、基于引用的回收(Reference-based Eviction),通过使用弱引用的键或值、或软引用的值,把缓存设置为允许垃圾回收器回收: CacheBuilder.weakKeys():使用弱引用存储键。当键没有其它(强或软)引用时,缓存项可以被GC回收 CacheBuilder.weakValues():使用弱引用存储值。当值没有其它(强或软)引用时,缓存项可以被GC回收 CacheBuilder.softValues():使用软引用存储值。软引用只有在响应内存需要时,才按照全局最近最少使用的顺序回收。影响性能,不推荐使用。 4、显式清除(invalidate) 个别清除:Cache.invalidate(key) 批量清除:Cache.invalidateAll(keys) 清除所有缓存项:Cache.invalidateAll() 四、什么时候发生缓存清理: 也许这个问题有点奇怪,如果设置的存活时间为一分钟,难道不是一分钟后这个key就会立即清除掉吗?我们来分析一下如果要实现这个功能,那Cache中就必须存在线程来进行周期性地检查、清除等工作,很多cache如redis、ehcache都是这样实现的。 但在GuavaCache中,并不存在任何线程!它实现机制是在写操作时顺带做少量的维护工作(如清除),偶尔在读操作时做(如果写操作实在太少的话),也就是说在使用的是调用线程,参考如下示例: 这在GuavaCache被称为“延迟删除”,即删除总是发生得比较“晚”,这也是GuavaCache不同于其他Cache的地方!这种实现方式的问题:缓存会可能会存活比较长的时间,一直占用着内存。如果使用了复杂的清除策略如基于容量的清除,还可能会占用着线程而导致响应时间变长。但优点也是显而易见的,没有启动线程,不管是实现,还是使用起来都让人觉得简单(轻量)。 如果你还是希望尽可能的降低延迟,可以创建自己的维护线程,以固定的时间间隔调用Cache.cleanUp(),ScheduledExecutorService可以帮助你很好地实现这样的定时调度。不过这种方式依然没办法百分百的确定一定是自己的维护线程“命中”了维护的工作。 总结: 请一定要记住GuavaCache的实现代码中没有启动任何线程!!Cache中的所有维护操作,包括清除缓存、写入缓存等,都是通过调用线程来操作的。这在需要低延迟服务场景中使用时尤其需要关注,可能会在某个调用的响应时间突然变大。 GuavaCache毕竟是一款面向本地缓存的,轻量级的Cache,适合缓存少量数据。如果你想缓存上千万数据,可以为每个key设置不同的存活时间,并且高性能,那并不适合使用GuavaCache。 五、缓存失效策略 当缓存需要被清理时(比如空间占用已经接近临界值了),需要使用某种淘汰算法来决定清理掉哪些数据。常用的淘汰算法有下面几种: FIFO:First In First Out,先进先出。判断被存储的时间,离目前最远的数据优先被淘汰。 LRU:Least Recently Used,最近最少使用。判断最近被使用的时间,目前最远的数据优先被淘汰。 LFU:Least Frequently Used,最不经常使用。在一段时间内,数据被使用次数最少的,优先被淘汰。 FIFO FIFO按照“先进先出(First In,First Out)”的原理淘汰数据,正好符合队列的特性,数据结构上使用队列Queue来实现。 1、新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动; 2、淘汰FIFO队列头部的数据; LRU 算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。 最常见的实现是使用一个链表保存缓存数据,详细算法实现如下: 1、新数据插入到链表头部; 2、每当缓存命中(即缓存数据被访问),则将数据移到链表头部; 3、当链表满的时候,将链表尾部的数据丢弃。 LFU 算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。 LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。 具体实现如下: 1、新加入数据插入到队列尾部(因为引用计数为1); 2、队列中的数据被访问后,引用计数增加,队列重新排序; 3、当需要淘汰数据时,将已经排序的列表最后的数据块删除。 六、LRU和LFU实现 利用LinkedHashMap。 用这个类有两大好处:一是它本身已经实现了按照访问顺序的存储,也就是说,最近读取的会放在最前面,最最不常读取的会放在最后(当然,它也可以实现按照插入顺序存储)。 第二,LinkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数,但是,原始方法默认不需要移除(这是,LinkedHashMap相当于一个linkedlist),所以,我们需要override这样一个方法,使得当缓存里存放的数据个数超过规定个数后,就把最不常用的移除掉。

import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private static final long serialVersionUID = 1L; private int cacheSize; //缓存大小 public LRUCache(int cacheSize) { super(10, 0.75f, true); //第三个参数true是关键 this.cacheSize = cacheSize; } //缓存是否已满 @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { boolean r = size() > cacheSize; if(r) System.out.println("清除缓存key:"+eldest.getKey()); return r; } //测试 public static void main(String[] args) { LRUCache<String, String> cache = new LRUCache<String, String>(5); cache.put("1", "1"); cache.put("2", "2"); cache.put("3", "3"); cache.put("4", "4"); cache.put("5", "5"); System.out.println("初始化:"); System.out.println(cache.keySet()); System.out.println("访问3:"); cache.get("3"); System.out.println(cache.keySet()); System.out.println("访问2:"); cache.get("2"); System.out.println(cache.keySet()); System.out.println("增加数据6,7:"); cache.put("6", "6"); cache.put("7", "7"); System.out.println(cache.keySet()); } } //运行结果 初始化: [1, 2, 3, 4, 5] 访问3: [1, 2, 4, 5, 3] 访问2: [1, 4, 5, 3, 2] 增加数据6,7: 清除缓存key:1 清除缓存key:4 [5, 3, 2, 6, 7]

手撕LFU,要求get和put都为O(1) LeetCode算法题解:LFU Cache O(1)


Java面试的完整博客目录如下:Java笔试面试目录

转载请标明出处,原文地址:https://blog.csdn.net/weixin_41835916 如果觉得本文对您有帮助,请点击支持一下,您的支持是我写作最大的动力,谢谢。

转载请注明原文地址: https://www.6miu.com/read-4050001.html

最新回复(0)