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

以你之姓@ 2021-09-27 08:10 386阅读 0赞

> **面试题：手写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来实现。  
![这里写图片描述][70]  
1、新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；  
2、淘汰FIFO队列头部的数据；  
**LRU**  
算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。  
最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：  
![这里写图片描述][70 1]  
1、新数据插入到链表头部；  
2、每当缓存命中（即缓存数据被访问），则将数据移到链表头部；  
3、当链表满的时候，将链表尾部的数据丢弃。  
**LFU**  
算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。  
LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。  
具体实现如下：  
![这里写图片描述][70 2]  
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)][LeetCode_LFU Cache O_1]**

--------------------

**Java面试的完整博客目录如下：[Java笔试面试目录][Java]**

> **转载请标明出处，原文地址：[https://blog.csdn.net/weixin\_41835916][https_blog.csdn.net_weixin_41835916] 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。  
> ![这里写图片描述][70 3]**

[70]: /images/20210923/e42f85c6589d4bf8a4c9a8a1445b40c0.png
[70 1]: /images/20210923/95a3236c6b4f484083a35b403dc9e55b.png
[70 2]: /images/20210923/992db530c7d641f19fe081690aed0c4d.png
[LeetCode_LFU Cache O_1]: https://www.cnblogs.com/charlesblc/p/6096144.html
[Java]: https://blog.csdn.net/weixin_41835916/article/details/81413498
[https_blog.csdn.net_weixin_41835916]: https://blog.csdn.net/weixin_41835916
[70 3]: /images/20210923/5342e23ca9854b848a08a974ec9ae605.png