缓存之算法探究与实现.md

缓存之算法探究与实现

0. Overview

1. 全部缓存

• Overview

  将从数据库里面查出来的数据保存到内存中，如果请求下次来就直接从内存中返回。

• 使用 HashMap 来替代数据库查询

  @Service
  public class HashMapCacheService {
  
      private HashMap<String, String> hashMap = new HashMap<>();
  
      @Resource
      private TestDbMapper dbMapper;
  
      public String getValue(String key) {
          String value = hashMap.get(key);
          if (value == null) {
              value = dbMapper.get(key);
              hashMap.put(key, value);
          }
          return value;
      }
  }
  

• 优点

  实现简单方便，能够有效的减少对于DB的请求

• 缺点

  HashMap 无法进行数据淘汰，内存会无限制的增长，如果是数据 key 比较恒定，但是访问频繁的类型，可以避免此缺点。

2. 数据淘汰

• Overview

  担心内存会无限制的增长，那我们直接采用算法淘汰一些数据不就行了么？

2.1. FIFO 算法

• Overview

  先进先出算法，先进入缓存的会先被淘汰。

• 实现

• 优点

  实现简单

• 缺点

  命中率会很低，没法区分高频访问的缓存和低频访问的缓存。

2.2. LRU 算法

• Overview

  最近最少使用算法，每次访问数据都会将其重新放在我们的队尾，如果需要淘汰数据，就只需要淘汰队首即可

• 实现

  在 LinkedHashMapMap 中，所有 put 进来的 Entry 都保存在哈希表（entry 链表）中，但由于它又额外定义了一个以 head 为头结点的双向链表，因此对于每次 get 或者 put的时候，除了将其保存到哈希表中对应的位置上之外，还会将其插入到双向链表的尾部。

  必须实现 removeEldestEntry ，否则不会发生淘汰，具体参考 LinkedHashMap 的实现。

  在构造方法中，设置的大小特意设置到 max*1.1 ，避免 LinkedHashMap 的自动扩容逻辑。

  public class LRUHashMapCacheService {
  
  
      class LRULinkedHashMap extends LinkedHashMap {
  
          private final int max;
          private Object lock;
  
          public LRULinkedHashMap(int max, Object lock) {
              super((int) (max * 1.1f), 0.75f, true);
              this.max = max;
              this.lock = lock;
          }
  
  
          @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;
          }
      }
  
  
  }
  

• 优点

  避免了 FIFO 的问题，高频词汇会延后淘汰。

• 缺点

  1. 无法避免时间段问题：比如在10分钟的前9分钟，高频数据被访问了1w次，但是接下来1分钟，高频词汇没有被访问，则高频词汇缓存会慢慢被移动到队首然后被淘汰。

  2. 锁竞争严重

  3. 不支持过期时间

  4. 不支持自动刷新

  5. 命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

2.3. LFU 算法

• Overview

  最近最少频率使用算法，对 LRU 算法进行了优化，利用额外的空间记录每个数据的使用频率，然后选出频率最低进行淘汰。

• 实现

  缓存之LFU算法

• 优点

  避免了 LRU 的问题，可以处理时间段的问题。

• 缺点

  实现成本较高，需要额外的空间消耗。

3. Guava cache

• Overview

  缓存之GuavaCache

4. Caffeine

• Overview

  缓存之Caffeine