标签：缓存 hash Cache 选型 LRU 内存 key 淘汰

背景

tcp网关出现了内存泄漏的现象，经排查后发现是一个java原生内存缓存导致的。
Map<String, String> belongCache = new ConcurrentHashMap<>();
该内存缓存作为兜底缓存使用，主要逻辑是读取redis用户身份信息后，有则更新到内存缓存，没有则从内存缓存中获取缓存数据。

该内存缓存直接使用了ConcurrentHashMap实现，寻找效率较高，而且线程安全。但是功能比较简单，且无过期和淘汰能力只能手动淘汰，存在内存泄露问题。

因此，需要对内存缓存进行一次升级，添加淘汰策略，以解决内存泄漏问题，故收集了市面上三种常用的内存缓存组件/框架信息，以做选型参考。

GuavaCache

前面说到，ConcurrentHashMap主要的缺点是功能简单没有过期和淘汰机制，那么为了解决这些问题，Google提供了一套JVM本地缓存框架GuavaCache，底层实现的数据结构类似于ConcurrentHashMap，但是进行了更多的能力拓展，包括缓存过期时间、缓存容量设置、多种淘汰策略、缓存监控统计等。

被动淘汰

过期机制

① 基于创建时间expireAfterWrite

public Cache<String, User> createUserCache() {
    return CacheBuilder.newBuilder()
        .expireAfterWrite(30L, TimeUnit.MINUTES)
        .build();
}

② 基于最后一次访问时间expireAfterAccess

public Cache<String, User> createUserCache() {
    return CacheBuilder.newBuilder()
        .expireAfterAccess(30L, TimeUnit.MINUTES)
        .build();
}

注: 基于过期机制的被动淘汰，其实现类似redis的惰性删除（无独立清理线程），在get请求时触发一次cleanUp操作（tryLock佛系抢锁以应对高并发场景）。

注: GuavaCache底层也采用了ConcurrentHashMap一样的分段锁机制，执行清理时，会且仅会针对当前查询记录所在的Segment分片执行清理操作。

刷新机制

public LoadingCache<String, User> createUserCache() {
    return CacheBuilder.newBuilder().refreshAfterWrite(30L, TimeUnit.MINUTES)
        .build(newCacheLoader<String, User>() {
            @Override
            public User load(String key) throwsException {
                log.info(key + "用户缓存更新，尝试CacheLoader回源查找并回填...");
                returnuserDao.getUser(key);
            }
        });
}

过期机制和刷新机制对比

① expire
优势: 有效防止缓存击穿问题，且阻塞等待的方式可以保证业务层面获取到的缓存数据的强一致性。
劣势: 高并发场景下，如果回源的耗时较长，会导致多个读线程被阻塞等待，影响整体的并发效率
适用场景: 数据极少变更，或者对变更的感知诉求不强，且并发请求同一个key的竞争压力不大

② refresh(异步refresh)
优势: 可以最大限度的保证查询操作的执行效率，避免过多的线程被阻塞等待。
劣势: 多个线程并发请求同一个key对应的缓存值拿到的结果可能不一致，在对于一致性要求特别严苛的业务场景下可能会引发问题
适用场景: 数据无需过期，但是可能会被修改，需要及时感知并更新缓存数据

结合使用: 数据需要过期，也需要在有效期内尽可能保证数据的更新一致性
均不使用: 数据需要永久存储，且不会变更

注: expire和refresh不是互斥关系，其实是互补关系，即同时设置expire和refresh。不过需要注意的是，refresh的时间设置应小于expire。

引用机制

核心是利用JVM虚拟机的GC机制来达到数据清理的目的。按照JVM的GC原理，当一个对象不再被引用之后，便会执行一系列的标记清除逻辑，并最终将其回收释放。实际使用的较少，下面是三种支持的回收机制。
① weakKeys
采用弱引用方式存储key值内容，当key对象不再被引用的时候，由GC进行回收
② weakValues
采用弱引用方式存储value值内容，当value对象不再被引用的时候，由GC进行回收
③ softValues
采用软引用方式存储value值内容，当内存容量满时基于LRU策略进行回收

容量限制机制

淘汰条件

① 基于缓存记录条数maximumSize

public Cache<String, User> createUserCache() {
    return CacheBuilder.newBuilder()
        .maximumSize(10000L)
        .build();
}

② 基于缓存记录权重maximumWeight+weigher

public Cache<String, User> createUserCache() {
    return CacheBuilder.newBuilder()
        .maximumWeight(10000L)
        .weigher((key, value) -> (int) Math.ceil(instrumentation.getObjectSize(value) / 1024L))
        .build();
}

我们通过计算value对象的字节数（byte）来计算其权重信息，每1kb的字节数作为1个权重，整个缓存容器的总权重限制为1w，这样就可以实现将缓存内存占用控制在10000*1k≈10M左右

淘汰策略

① FIFO: 先进先出: First In First Out
② LRU: 最近最久未使用: Least Recent Used
③ LFU: 最近最少频率使用: Least Frequency Used

注: 淘汰策略在此先不做展开，下文讨论Caffeine时W-TinyLFU将会进行详细分析

主动淘汰

接口	含义
invalidate(key)	删除指定的记录
invalidateAll(keys)	批量删除给定的记录
invalidateAll()	清空整个缓存容器

其他

支持集成数据源

① Callable模式 -> Cache

cache.get(userId, () -> {
    log.info(userId + "用户缓存不存在，尝试回源查找并回填...");
    return userDao.getUser(userId);
});

② CacheLoader模式 -> LoadingCache

CacheBuilder.newBuilder().build(newCacheLoader<String, User>() {
    @Override
    publicUserload(Stringkey) throwsException {
        log.info(key + "用户缓存不存在，尝试CacheLoader回源查找并回填...");
        return userDao.getUser(key);
    }
});

注: 两种模式可以同时存在 -> Callable优先级高，作为特定场景使用，CacheLoader作为通用场景使用，也可以任务是兜底场景。

支持更新锁定

缓存击穿: 高并发量场景下，少量缓存恰好失效遭遇大量请求，导致这些请求全部涌入数据库
一般解决方案: 分布式锁
Guava Cache解决方案: 并发锁定机制 -> 同一时刻仅允许一个请求回源获取数据并回填到缓存中，其余请求则阻塞等待。

支持监控

为什么要监控 -> 关注缓存的命中率
监控关键指标 -> 缓存数据的加载或者命中情况统计
如何开启监控 -> 缓存容器创建时，通过recordStats()开启
如何查看统计 -> 使用cache.stats()获取统计数据CacheStats

指标含义	说明
hitCount	命中缓存次数
missCount	没有命中缓存次数（查询时内存中没有）
loadSuccessCount	回源加载的时候加载成功次数
loadExceptionCount	回源加载但是加载失败的次数
totalLoadTime	回源加载操作总耗时
evictionCount	删除记录的次数

Caffeine

Caffeine是基于Google Guava Cache设计经验上改进的成果，众多的特性与设计思路都完全沿用了Guava Cache相同的逻辑，且提供的接口与使用风格也与Guava Cache无异。因此，以上GuavaCache提供的能力Caffeine基本都有，在此不做赘述，以下主要探讨Caffeine相较于GuavaCache的改进之处。

基础数据结构层面优化

Caffeine基于java8开发，Caffeine参照java8对ConcurrentHashMap底层由链表切换为红黑树、以及废弃分段锁逻辑的优化，提升了Hash冲突时的查询效率以及并发场景下的处理性能。

异步并行能力的全面支持

完美适配java8的并行编程场景，提供了全套的Async异步处理机制，可以支持业务在异步并行流水线处理场景中使用以获得更好的体验。
① 异步Callable -> AsyncCache

public static void main(String[] args) {
    AsyncCache<String, User> asyncCache = Caffeine.newBuilder().buildAsyn();
    CompletableFuture<User> userCompletableFuture = asyncCache.get("123", s -> userDao.getUser(s));
}

② 异步CacheLoader -> AsyncLoadingCache

public static void main(String[] args) {
    try {
        AsyncLoadingCache<String, User> asyncLoadingCache =
                Caffeine.newBuilder().maximumSize(1000L).buildAsync(key -> userDao.getUser(key));
        CompletableFuture<User> userCompletableFuture = asyncLoadingCache.get("123");
    } catch (Exception e) {
        e.printStackTrace();
    }
}

③ 异步AsyncCacheLoader -> AsyncLoadingCache

public static void main(String[] args) {
    try {
        AsyncLoadingCache<String, User> asyncLoadingCache =
                Caffeine.newBuilder().maximumSize(1000L).buildAsync(
                        (key, executor) -> CompletableFuture.supplyAsync(() -> userDao.getUser(key), executor)
                );
        CompletableFuture<User> userCompletableFuture = asyncLoadingCache.get("123");
    } catch (Exception e) {
        e.printStackTrace();
    }
}

注: 异步AsyncCacheLoader是异步CacheLoader的另一个版本，区别在于异步AsyncCacheLoader使用的是 buildAsync的重载版本，允许传入一个支持异步并行处理的AsyncCacheLoader对象。

数据淘汰策略的优化

W-TinyLFU算法，提供了更佳的热点数据留存效果，提供了近乎完美的热点数据命中率，以及更低消耗的过程维护，接下来将重点介绍这一部分。

其他淘汰策略

FIFO: First In First Out

先进先出: 先进去的缓存最先淘汰
优点: 实现非常简单
缺点: 缓存命中率（hit rate）并不理想，通用缓存基本上不考虑。

LRU: Least Recent Used

最近最久未使用: 把最近访问过的缓存项保留了下来
优点:
实现简单，根据局部性原理，一般情况下LRU的命中率不错，而针对访问频繁的热点数据，命中率非常好。
缺点:
对于周期性、偶发性的访问数据，有大概率可能造成缓存污染，也就是置换出去了热点数据，把这些偶发性数据留下了，从而导致LRU的数据命中率急剧下降，因此无法处理大量的稀疏流量。
稀疏流量: sparse burst: 即短时间内使用几次后面就不被使用了

LFU:Least Frequency Used

最近最少频率使用: 把访问频率高的缓存项保留下来，同时考虑时间因素
优点:
可以有效地保护缓存，相对于LRU来说有更好的缓存命中率。
缺点:
1、需要为每一个缓存项维护其频率统计信息，每一次访问都需要更新相应的统计信息，因此需要额外的空间和时间开销。
2、无法处理稀疏流量（sparse burst）场景。因为稀疏流量只有少量的访问次数，在比较访问频率决定去留时处于劣势，可能导致稀疏流量缓存项频繁被淘汰，造成缓存污染，进而导致访问稀疏流量经常无法命中。

W-TinyLFU: Window Cache - Tiny Least Frequency Used

结合了LRU和LFU的优点, 实现了高命中、低内存占用的效果。
主要结构
① TinyLFU: 用于估算统计各个key值的请求频率
② Window Cache: 其本质就是一个LRU缓存
③ SLRU（Segmented LRU，即分段 LRU）: 包括一个名为 protected 和一个名为 probation 的缓存区，通过增加一个缓存区（即 Window Cache），当有新的记录插入时，会先在 window Cache区呆一下，就可以避免 sparse bursts 问题。

TinyLFU上文提到了LFU的两个缺点，为了解决LFU的两个缺点提出了对应的两个解决方案。
问题
① 如何减少访问频率的保存和记录的更新，所带来的空间和时间的开销
② 如果提升对局部热点数据的算法命中率
方案
① Count–Min Sketch 算法
② “新鲜度”机制（Freshness Mechanism）

核心算法: Count–Min Sketch

Caffeine采用Count-Min Sketch算法来统计LFU频率，该算法借鉴了boomfilter的思想，只不过hash key对应的value不是表示存在的true或false标志，而是一个计数器。
它会对缓存key进行四次hash（seed不同），将hash值对应的计数器加一。计数器只有4bit，所以计数器最大只能计数到15，超过15则不再往上增加计数。
因为bloomfilter存在positive false的问题（hash冲突），缓存项的频率值取四个计数器的最小值（Count-Min的含义）。当所有计数器值的和超过设定的阈值（默认是缓存项最大数量的10倍），所有计数器值减半。

// FrequencySketch源码（caffenie版本: 2.9.3）
// 预设的4个种子
static final long[] SEED = { // A mixture of seeds from FNV-1a, CityHash, and Murmur3
      0xc3a5c85c97cb3127L, 0xb492b66fbe98f273L, 0x9ae16a3b2f90404fL, 0xcbf29ce484222325L};
static final long RESET_MASK = 0x7777777777777777L;
static final long ONE_MASK = 0x1111111111111111L;

// sampleSize = (maximumSize == 0) ? 10 : (10 * maximum);
int sampleSize;
// tableMask = Math.max(0, table.length - 1)
// table长度一般为2的n次方, tableMask值为tabel数组长度-1（掩码）
// 可以通过&操作来模拟取余操作，进而根据hash值快速得到table对应的index值
int tableMask;
// 存储计数频率的一维数组
long[] table;
int size;

/**
   * Increments the popularity of the element if it does not exceed the maximum (15). The popularity
   * of all elements will be periodically down sampled when the observed events exceeds a threshold.
   * This process provides a frequency aging to allow expired long term entries to fade away.
   *
   * @param e the element to add
   */
  public void increment(@NonNull E e) {
    if (isNotInitialized()) {
      return;
    }

    // 怕一次hash不够均匀, 调用spread方法再打散一次
    int hash = spread(e.hashCode());
    // 取低2位作为随机值，往左移动两位得到一个小于16的值（0000、0100、1000、1100）
    int start = (hash & 3) << 2;

    // Loop unrolling improves throughput by 5m ops/s
    // 根据hash值和4个不同种子（SEED）得到table的下标index
    int index0 = indexOf(hash, 0);
    int index1 = indexOf(hash, 1);
    int index2 = indexOf(hash, 2);
    int index3 = indexOf(hash, 3);

    // 根据index和start(+1, +2, +3)的值，把table[index]对应的等分追加1
    // 前两位: 0000、0100、1000、1100 -> 补全后两位: 00、01、10、11
    boolean added = incrementAt(index0, start);
    added |= incrementAt(index1, start + 1);
    added |= incrementAt(index2, start + 2);
    added |= incrementAt(index3, start + 3);

    // size是所有记录的频率统计和，即每个记录加1，这个size都会加1
    // sampleSize是一个阈值，值为maximumSize的10倍
    if (added && (++size == sampleSize)) {
      reset();
    }
  }

/**
   * Applies a supplemental hash function to a given hashCode, which defends against poor quality
   * hash functions.
   */
  int spread(int x) {
    x = ((x >>> 16) ^ x) * 0x45d9f3b;
    x = ((x >>> 16) ^ x) * 0x45d9f3b;
    return (x >>> 16) ^ x;
  }

/**
   * Returns the table index for the counter at the specified depth.
   *
   * @param item the element's hash
   * @param i the counter depth
   * @return the table index
   */
  int indexOf(int item, int i) {
    long hash = (item + SEED[i]) * SEED[i];
    hash += (hash >>> 32);
    return ((int) hash) & tableMask;
  }

/**
   * Increments the specified counter by 1 if it is not already at the maximum value (15).
   *
   * @param i the table index (16 counters)
   * @param j the counter to increment
   * @return if incremented
   */
  boolean incrementAt(int i, int j) {
    // j表示16个等分的下标，offset相当于在64位中的下标
    // 4位: 0~15 -> 6位: 0~63 -> 实际offset取值: 0~60(预留了4位给mask掩码)
    int offset = j << 2;
    // Caffeine把频率统计最大定为15，即0xfL
    // mask是在64位中的掩码 -> 1111+0000...(0~60个0)
    long mask = (0xfL << offset);
    // 如果table[index]要计算的4bit不等于15，就追加1，否则不追加
    if ((table[i] & mask) != mask) {
      table[i] += (1L << offset);
      return true;
    }
    return false;
  }

/** Reduces every counter by half of its original value. */
  void reset() {
    int count = 0;
    for (int i = 0; i < table.length; i++) {
      // 16个counter中频次为奇数的个数
      // 最低一位为1 -> (下面>>>1再&RESET_MASK) -> 被抹掉的1的个数
      count += Long.bitCount(table[i] & ONE_MASK);
      // table[i] >>> 1，整体右移1位，相当于除2，每个counter的高位是上一个bit的低位，可能为1
      // & RESET_MASK，抹去新counter的最高位，保留低三位。最终实现每个counter除2
      table[i] = (table[i] >>> 1) & RESET_MASK;
    }
    // 新size = 老size/2 - 奇数数据/4
    // 除以4是因为每增加1个频次 -> 实际加了4次1
    // 结合reset方法和incrementAt可以发现，size的值并不完全准确，可能会有误差，就像boomfilter一样并不追求百分百的准确
    size = (size >>> 1) - (count >>> 2);
  }

/**
   * Returns the estimated number of occurrences of an element, up to the maximum (15).
   *
   * @param e the element to count occurrences of
   * @return the estimated number of occurrences of the element; possibly zero but never negative
   */
  @NonNegative
  public int frequency(@NonNull E e) {
    if (isNotInitialized()) {
      return 0;
    }

    int hash = spread(e.hashCode());
    int start = (hash & 3) << 2;
    int frequency = Integer.MAX_VALUE;
    for (int i = 0; i < 4; i++) {
      int index = indexOf(hash, i);
      // 读操作同写操作
      int count = (int) ((table[index] >>> ((start + i) << 2)) & 0xfL);
      // 取最小的count
      frequency = Math.min(frequency, count);
    }
    return frequency;
  }

注:
table数组每个元素大小是64bit，每个计数器大小为4bit，那么每个table元素有16个计数器。
这16个计数器分为4个group，每个group包含4个计数器，等于bloom hash函数的个数。
4个hash计数器在相应table元素内计数器的偏移不一样，也可以有效降低hash冲突。

保鲜机制

由于计数器大小只有4bit，极大地降低了LFU频率统计对存储空间的要求。
同时，计数器统计上限是15，并在计数总和达到阈值时所有计数器值减半，相当于引入计数饱和和衰减机制，可以有效解决短时间内突发大流量不能有效淘汰的问题。
比如出现了一个突发热点事件，它的访问量是其他事件的成百上千倍，但是该热点事件很快冷却下去，传统的LFU淘汰机制会让该事件的缓存长时间地保留在缓存中而无法淘汰掉，虽然该类型事件已经访问量非常小了。

Window Cache + SLRU

TinyLFU解决了LFU列出的第一个问题，但是并没有解决第二个问题。于是在TinyLFU算法基础上引入一个基于LRU的Window Cache，这个新的算法叫就叫做W-TinyLFU（Window-TinyLFU）。

W-TinyLFU将缓存存储空间分为两个大的区域：Window Cache（1%）和Main Cache（99%）
Window Cache是一个标准的LRU Cache，Main Cache则是一个SLRU（Segmemted LRU）cache。
Main Cache进一步划分为Protected Cache（保护区）（80%）和Probation Cache（观察区）（20%）两个区域，这两个区域都是基于LRU的Cache。
注: 这些cache区域的大小会动态调整

写入流程

有新的缓存项写入缓存时，会先写入Window Cache区域。
当Window Cache空间满时，最旧的缓存项会被移出Window Cache。
如果Probation Cache未满，从Window Cache移出的缓存项会直接写入Probation Cache；
如果Probation Cache已满，则会根据TinyLFU算法确定从Window Cache移出的缓存项是丢弃（淘汰）还是写入Probation Cache。

Probation Cache中的缓存项如果访问频率达到一定次数，会提升到Protected Cache；
如果Protected Cache也满了，最旧的缓存项也会移出Protected Cache，然后根据TinyLFU算法确定是丢弃（淘汰）还是写入Probation Cache。

淘汰机制

从Window Cache或Protected Cache移出的缓存项称为Candidate
Probation Cache中最旧的缓存项称为Victim
如果Candidate缓存项的访问频率大于Victim缓存项的访问频率，则淘汰掉Victim。
如果Candidate小于或等于Victim的频率，那么如果Candidate的频率小于5，则淘汰掉Candidate；
否则，则在Candidate和Victim两者之中随机地淘汰一个。

总结

caffeine综合了LFU和LRU的优势，将不同特性的缓存项存入不同的缓存区域
最近刚产生的缓存项进入Window区，不会被淘汰；
访问频率高的缓存项进入Protected区，也不会淘汰；
介于这两者之间的缓存项存在Probation区，当缓存空间满了时，Probation区的缓存项会根据访问频率判断是保留还是淘汰；

通过这种机制，平衡了【访问频率】和【访问时间新鲜程度】两个维度因素，尽量将新鲜的访问频率高的缓存项保留在缓存中。
同时在维护缓存项访问频率时，引入【计数器饱和】和【衰减机制】，即节省了存储资源，也能较好的处理稀疏流量、短时超热点流量等传统LRU和LFU无法很好处理的场景。

其他改进点

CleanUp异步处理

获取缓存请求中的惰性删除，优化后会新开一个线程异步处理，不再阻塞主线程。

新增expireAfter功能

可以基于个性化定制的逻辑来实现过期处理（可以定制基于新增、读取、更新等场景的过期策略，甚至支持为不同记录指定不同过期时间）
① expireAfterCreate
② expireAfterUpdate
③ expireAfterRead

Ehcache

支持多级缓存

① 支持堆外缓存
② 支持磁盘缓存
③ 支持集群缓存

堆内缓存 < 堆外缓存 < 磁盘缓存 < 集群缓存
组合:
堆内缓存 + 堆外缓存
堆内缓存 + 堆外缓存 + 磁盘缓存
堆内缓存 + 堆外缓存 + 集群缓存
堆内缓存 + 磁盘缓存
堆内缓存 + 集群缓存

注:
1、堆内缓存一定要有
2、磁盘缓存与集群缓存不能同时存在

注: 除了堆内缓存属于JVM堆内部，可以直接通过引用的方式进行访问，其余几种类型都属于JVM外部的数据交互，所以对这部分数据的读写时，需要先进行序列化与反序列化，因此要求缓存的数据对象一定要支持序列化与反序列化。

支持缓存持久化

支持使用磁盘来对缓存内容进行持久化保存，上面已经介绍在此不再赘述。

支持分布式缓存

Ehcache自带集群解决方案，通过相应的配置可以让本地缓存变身集群版本，以此来应付分布式场景下各个节点缓存数据不一致的问题，并且由于数据都缓存在进程内部，所以也可以避免集中是缓存频繁在业务流程中频繁网络交互的弊端。

① RMI组播方式: 一种点对点（P2P）的通信交互机制
② JMS消息方式: 基于发布订阅模式，默认使用ActiveMQ，也可以切换为Kafka或者RabbitMQ等
③ Cache Server模式: 一个独立的集中式缓存，类似Redis
④ JGroup方式: 和RMI有点类似
⑤ Terracotta方式: 一个JVM层专门负责做分布式节点间协同处理的平台框架

其他

更灵活和细粒度的过期时间设定

Ehcache不仅支持缓存容器对象级别统一的过期时间设定，还会支持为容器中每一条缓存记录设定独立过期时间，允许不同记录有不同的过期时间，类似redis。

同时支持JCache与SpringCache规范

Ehcache作为一个标准化构建的通用缓存框架，同时支持了JAVA目前业界最为主流的两大缓存标准，即官方的JSR107标准以及使用非常广泛的Spring Cache标准，这样使得业务中可以基于标准化的缓存接口去调用，避免了Ehcache深度耦合到业务逻辑中去。

总结

比较项	ConcurrentHashMap	Ehcache	Guava Cache	Caffeine
读写性能	很好，分段锁	好	好	很好
淘汰算法	无	LFU,LRU,FIFO	LFU,LRU,FIFO	W-TinyLFU
功能丰富度	功能简单	功能丰富	功能丰富	同GuavaCache
工具大小	jdk自带	一般	较小	一般
是否持久化	否	是	否	否
是否支持集群	否	是	否	否
选型建议	需要一个线程安全的键值存储，不需要缓存特性（例如淘汰策略）	①本地缓存数据量较大内存不足需要使用磁盘等缓存的 ②需要在JVM之间共享缓存数据	缓存需求不复杂，并且已经在使用Guava库	对性能有较高要求，并且需要复杂的缓存过期策略

思考

本地缓存的设计边界与定位

Ehcache的整体综合功能是最强大的，整体定位偏向于大而全，但导致在各个细分场景下表现不够极致：
相比Caffeine：略显臃肿，因为提供了很多额外的功能，比如使用磁盘缓存、比如支持多节点间集群组网等；
相比Redis：先天不足，毕竟是本地缓存，纵使支持了多种组网模式，仍无法媲美集中式缓存在分布式场景下的体验。

参考

https://juejin.cn/column/7140852038258147358

标签：缓存,hash,Cache,选型,LRU,内存,key,淘汰
From： https://www.cnblogs.com/nanzhuli/p/18285706

内存缓存选型

背景