闲来无事，动手写一个LRU本地缓存

学习java并发的时候，书上的例子是基于缓存展开的，于是就想可以写一个通用的本地缓存

写在前面

写一个缓存，需要考虑缓存底层存储结构、缓存过期、缓存失效、并发读写等问题，因此自己动手写的本地缓存将围绕这几点进行设计

缓存失效

缓存失效指的是缓存过期了，需要对过期的缓存数据进行删除。删除可以分为主动删除和被动删除两种

主动删除

• 定时删除
  在设置键值对过期时间的同时，创建一个定时器，让定时器在键过期时间来临时，立即执行对键的删除操作
  优点：对内存最友好，保证过期的键值对尽可能地被删除，释放过期键值对所占用的内存
  缺点：对CPU不友好，如果过期键值对比较多，删除过期键值对会占用相当一部分CPU执行时间
• 定期删除
  每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响【难点，执行时长和频率比较难设置】

被动删除

• 惰性删除
  只有在取出键的时候才会对键进行过期检查 优缺点和定时删除相反
  优点：对CPU友好
  缺点：对内存不友好 同时使用惰性删除+定期删除，可以取得CPU和内存的平衡，因此本地缓存的缓存失效采用惰性删除+定期删除两种

缓存淘汰

缓存淘汰指的是缓存的数量达到一定值时按照某种规则删除某个数据，不考虑该数据是否过期。常见的缓存淘汰算法有：

• 先进先出算法【FIFO】
  最先存入缓存的数据将最先被淘汰
• 最不经常使用算法【LFU】
  淘汰使用次数最少的数据，一般实现是对每个数据进行计数，每使用一次就进行计算一次，淘汰计数次数最少的
• 最近最少使用算法【LRU】
  最近不使用的数据最先被淘汰，一般实现是通过链表，将最新访问、新插入的元素移到链表头部，淘汰链表最后一个元素 本地缓存将选择LRU算法实现缓存淘汰

缓存结构定义

选择好了缓存失效和缓存淘汰的算法以后就可以确定缓存结构了，原先考略的是线程安全的K-V结构的ConcurrentHashMap再加+双向链表的结构，但何甜甜最近沉迷记英语单词，同时了解到LinkedHashMap可以实现LRU，偷懒使用了LinkedHashMap。LinkedHashMap可以基于插入顺序存储【默认】，也可以根据访问顺序存储【最近读取的会放在最前面，最最不常读取的会放在最后】，将插入顺序存储改为访问顺序存储只需将accssOrder设置为true即可，默认为false。同时LinkedHashMap提供了一个用于判断是否需要移除最不常读取数据的方法【removeEldestEntry(Map.Entry<K, CacheNode<K, V>> eldest)默认返回false不移除】，需要移除重写该方法就可以了

缓存节点的定义

public class CacheNode<K, V> {
    /**
     * 保存的键
     */
    private K key;

    /**
     * 保存的值
     */
    private V value;

    /**
     * 保存时间
     */
    private long gmtCreate;

    /**
     * 过期时间，单位为毫秒，默认永久有效
     */
    private long expireTime = Long.MAX_VALUE;
}

缓存结构初始化

    /**
     * 底层缓存结构
     */
    private LinkedHashMap<K, CacheNode<K, V>> localCache;

    /**
     * 负载因子
     */
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 缓存过期清理策略
     */
    private ExpireStrategy<K, V> lazyExpireStrategy = new LazyExpireStrategy<>();

    private ExpireStrategy<K, V> regularExpireStrategy;

    private int maxCacheSie;

    /**
     * 构造函数
     *
     * @param expireStrategy 缓存失效策略实现类，针对的是定期失效缓存，传入null，定期失效缓存类为默认配置值
     * @param maxCacheSie    缓存最大允许存放的数量，缓存失效策略根据这个值触发
     */
    public LocalCache(int maxCacheSize, ExpireStrategy<K, V> expireStrategy) {
        //缓存最大容量为初始化的大小
        this.maxCacheSize = maxCacheSize;
        //缓存最大容量 => initialCapacity * DEFAULT_LOAD_FACTOR，避免扩容操作
        int initialCapacity = (int) Math.ceil(maxCacheSie / DEFAULT_LOAD_FACTOR) + 1;
        //accessOrder设置为true，根据访问顺序而不是插入顺序
        this.localCache = new LinkedHashMap<K, CacheNode<K, V>>(initialCapacity, DEFAULT_LOAD_FACTOR, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, CacheNode<K, V>> eldest) {
                return size() > maxCacheSie;
            }
        };
        this.regularExpireStrategy = (expireStrategy == null ? new RegularExpireStrategy<>() : expireStrategy);
        //启动定时清除过期键任务
        regularExpireStrategy.removeExpireKey(localCache, null);
    }

说明：

• 重写了removeEldestEntry方法，当缓存大小超过了设置的maxCacheSize才会移除不常使用的元素
• 构造函数中设置accessOrder为true，根绝访问顺序存储
• 缓存容量大小由(int) Math.ceil(maxCacheSie / DEFAULT_LOAD_FACTOR) + 1计算得到，这样即使达到设置的maxCacheSize也不会触发扩容操作
• regularExpireStrategy.removeExpireKey(localCache, null);启动定期删除任务

定期删除策略实现：

public class RegularExpireStrategy<K, V> implements ExpireStrategy<K, V> {
    Logger logger = LoggerFactory.getLogger(getClass());
    /**
     * 定期任务每次执行删除操作的次数
     */
    private long executeCount = 100;

    /**
     * 定期任务执行时常 【1分钟】
     */
    private long executeDuration = 1000 * 60;

    /**
     * 定期任务执行的频率
     */
    private long executeRate = 60;

    //get and set
    public long getExecuteCount() {
        return executeCount;
    }

    public void setExecuteCount(long executeCount) {
        this.executeCount = executeCount;
    }

    public long getExecuteDuration() {
        return executeDuration;
    }

    public void setExecuteDuration(long executeDuration) {
        this.executeDuration = executeDuration;
    }

    public long getExecuteRate() {
        return executeRate;
    }

    public void setExecuteRate(long executeRate) {
        this.executeRate = executeRate;
    }

    /**
     * 清空过期Key-Value
     *
     * @param localCache 本地缓存底层使用的存储结构
     * @param key 缓存的键
     * @return 过期的值
     */
    @Override
    public V removeExpireKey(LinkedHashMap<K, CacheNode<K, V>> localCache, K key) {
        logger.info("开启定期清除过期key任务");
        ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);
        //定时周期任务，executeRate分钟之后执行，默认1小时执行一次
        executor.scheduleAtFixedRate(new MyTask(localCache), 0, executeRate, TimeUnit.MINUTES);
        return null;
    }

    /**
     * 自定义任务
     */
    private class MyTask<K, V> implements Runnable {
        private LinkedHashMap<K, CacheNode<K, V>> localCache;

        public MyTask(LinkedHashMap<K, CacheNode<K, V>> localCache) {
            this.localCache = localCache;
        }

        @Override
        public void run() {
            long start = System.currentTimeMillis();
            List<K> keyList = localCache.keySet().stream().collect(Collectors.toList());
            int size = keyList.size();
            Random random = new Random();

            for (int i = 0; i < executeCount; i++) {
                K randomKey = keyList.get(random.nextInt(size));
                if (localCache.get(randomKey).getExpireTime() - System.currentTimeMillis() < 0) {
                    logger.info("key:{}已过期，进行定期删除key操作", randomKey);
                    localCache.remove(randomKey);
                }

                //超时执行退出
                if (System.currentTimeMillis() - start > executeDuration) {
                    break;
                }
            }
        }
    }
}

说明：

• 使用ScheduledExecutorService的scheduleAtFixedRate实现定时周期任务
• 默认1小时执行一次，每次执行的时间为1分钟，每次随机尝试删除100个元素【如果时间允许、键过期】

懒加载删除策略实现：LazyExpireStrategy.java

public class LazyExpireStrategy<K, V> implements ExpireStrategy<K, V> {
    private final Logger logger = LoggerFactory.getLogger(getClass());

    /**
     * 清空过期Key-Value
     *
     * @param localCache 本地缓存底层使用的存储结构
     * @param key 缓存的键
     * @return 过期的值
     */
    @Override
    public V removeExpireKey(LinkedHashMap<K, CacheNode<K, V>> localCache, K key) {
        CacheNode<K, V> baseCacheValue = localCache.get(key);
        //值不存在
        if (baseCacheValue == null) {
            logger.info("key:{}对应的value不存在", key);
            return null;
        } else {
            //值存在并且未过期
            if (baseCacheValue.getExpireTime() - System.currentTimeMillis() > 0) {
                return baseCacheValue.getValue();
            }
        }

        logger.info("key:{}已过期，进行懒删除key操作", key);
        localCache.remove(key);
        return null;
    }
}

说明：

• 判断键是否存在，不存在返回null值
• 如果键存在，判断是否过期，不过期返回，过期删除并返回null值

缓存操作方法的实现

• 删除

  public synchronized V removeKey(K key) {
    CacheNode<K, V> cacheNode = localCache.remove(key);
    return cacheNode != null ? cacheNode.getValue() : null;
  }
  

• 查找

  public synchronized V getValue(K key) {
    return lazyExpireStrategy.removeExpireKey(localCache, key);
  }
  

  查找的时候会走懒删除策略
• 存入
  存入的值不失效：

  public synchronized V putValue(K key, V value) {
      CacheNode<K, V> cacheNode = new CacheNode<>();
      cacheNode.setKey(key);
      cacheNode.setValue(value);
      localCache.put(key, cacheNode);
      // 返回添加的值
      return value;
  }
  

  存入的值失效：

  public synchronized V putValue(K key, V value, long expireTime) {
    CacheNode<K, V> cacheNode = new CacheNode<>();
    cacheNode.setKey(key);
    cacheNode.setValue(value);
    cacheNode.setGmtCreate(System.currentTimeMillis() + expireTime);
    localCache.put(key, cacheNode);
    // 返回添加的值
    return value;
  }
  

• 设置缓存失效时间

  public synchronized void setExpireKey(K key, long expireTime) {
    if (localCache.get(key) != null) {
      localCache.get(key).setExpireTime(System.currentTimeMillis() + expireTime);
    }
  }
  

• 获取缓存大小

  public synchronized int getLocalCacheSize() {
          return localCache.size();
  }
  

所有方法为了保证线程安全都使用了synchronize关键字【线程安全，何甜甜只会synchronize，没有想到其他更好的加锁方式、考虑了读写锁但是行不通、、、】

使用姿势

• 创建LocalCache对象
  • 姿势一

    LocalCache<Integer, Integer> localCache = new LocalCache<>(4, null);
    

    第一个参数缓存的大小，允许存放缓存的数量 第二个参数定期删除对象，如果为null，使用默认的定期删除对象【执行周期、执行时间、执行次数都为默认值】
  • 姿势二

    RegularExpireStrategy<Integer, Integer> expireStrategy = new RegularExpireStrategy<>();
    expireStrategy.setExecuteRate(1); //每隔1分钟执行一次
    LocalCache<Integer, Integer> localCache = new LocalCache<>(4, expireStrategy);
    

    传入自定义的定期删除对象
• 存入缓存

  for (int i = 0; i < 16; i++) {
    localCache.putValue(i, i);
  }
  

• 存入缓存并设置失效时间

   localCache.putValue(i, i,1000);
  

• 从缓存中读取值

  localCache.getValue(i)
  

• 设置已有缓存中数据的过期时间

  localCache.setExpireKey(i, 1000)
  

• 获取缓存的大小

  localCache.getLocalCacheSize()
  

• 删除缓存

  localCache.removeKey(i)
  

基于学习的目的写了一个本地缓存，实际应用中还是推荐使用Google的Guava Cache，如果你对我的代码足够自信，当然也欢迎使用提Bug

优化点

• 使用ConcurrentHashMap再加+双向链表
• 缓存失效、定时任务时间选择多样性，目前使用缓存失效单位默认为毫秒，定时任务默认单位为分钟，通过在方法中加入TimeUnit参数时间选择更多样性
• 并发支持较差，实现的是同步【何甜甜太菜了！！！】

TODO

• 上传私服，提供依赖的方式在其他项目中使用，顺便学习一下如何上传私服

最后附：项目完整代码，欢迎fork，star
如有错误，欢迎指正交流【何甜甜真的太菜了！！！】