缓存介绍

缓存是分布式系统中的重要组件，主要解决高并发，大数据场景下，热点数据访问的性能问题。提供高性能的数据快速访问。缓存主要分类：

  • 本地缓存：指的是在应用中的缓存组件，其最大的优点是应用和cache是在同一个进程内部，请求缓存非常快速，没有过多的网络开销等，在单应用不需要集群支持或者集群情况下各节点无需互相通知的场景下使用本地缓存较合适；同时，它的缺点也是应为缓存跟应用程序耦合，多个应用程序无法直接的共享缓存，各应用或集群的各节点都需要维护自己的单独缓存，对内存是一种浪费。

  • 分布式缓存：指的是与应用分离的缓存组件或服务，其最大的优点是自身就是一个独立的应用，与本地应用隔离，多个应用可直接的共享缓存。

Caffeine介绍

Caffeine简介

Caffeine是基于JDK8的高性能本地缓存库，提供了几乎完美的命中率。它有点类似JDK中的ConcurrentMap，实际上，Caffeine中的LocalCache接口就是实现了JDK中的ConcurrentMap接口，但两者并不完全一样。最根本的区别就是，ConcurrentMap保存所有添加的元素，除非显示删除之（比如调用remove方法）。而本地缓存一般会配置自动剔除策略，为了保护应用程序，限制内存占用情况，防止内存溢出。

性能对比

读 (75%) / 写 (25%)

在这个基准测试中，对一个配置了最大容量的缓存，6 线程进行并发读，2 线程进行并发写。

avatar

写 (100%)

在这个基准测试中，8 线程对一个配置了最大容量的缓存进行并发写。

avatar

Caffeine特性

  1. 自动把数据加载到本地缓存中，并且可以配置异步。

  2. 基于频率和近期的数量/容量淘汰策略。

  3. 基于失效时间剔除策略，这个时间是从最后一次访问或者写入算起。

  4. 异步刷新（当entry的第一个过时请求时,进行异步刷新）。

  5. Key会被包装成Weak引用；

  6. Value会被包装成Weak或者Soft引用，从而能被GC掉，而不至于内存泄漏；

  7. 数据剔除提醒；

  8. 写入广播机制；

  9. 缓存访问可以统计；

加载策略

Caffeine 为我们提供了4种填充策略：手动、自动同步、手动异步、异步自动。

1.Cache 手动加载

1
2
3
4
5
6
7
8
9
10
11
12
Cache<Key, UserInfo> cache = Caffeine.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .maximumSize(10_000)
    .build();
// 查找一个缓存元素，没有查找到的时候返回null
UserInfo userInfo = cache.getIfPresent(key);
// 查找缓存，如果缓存不存在则生成缓存元素,  如果无法生成则返回null（注意上一行代码两种方法对比）
userInfo = cache.get(key, k -> getUserInfoByDB(key));
// 添加或者更新一个缓存元素
cache.put(key, userInfo);
// 移除一个缓存元素
cache.invalidate(key);

Cache接口允许显式的去控制缓存的获取，更新和删除。

我们可以通过cache.getIfPresent(key) 方法来获取一个key的值，通过cache.put(key, value)方法显式的将数据放入缓存，但是会覆盖缓原来key的数据。更加建议使用cache.get(key，k – > value) 的方式，get 方法将一个参数为 key 的 Function (getUserInfoByDB) 作为参数传入。如果缓存中不存在该Key，则调用这个 Function 函数，并将返回值作为该缓存的值插入缓存中。get 方法是以阻塞方式执行调用，即使多个线程同时请求该值也只会调用一次Function方法。这样可以避免与其他线程的写入竞争，这也是为什么使用 get 优于 getIfPresent 的原因。

注意：如果调用该方法返回NULL（如上面的 getUserInfoByDB 方法），则cache.get返回null，如果调用该方法抛出异常，则get方法也会抛出异常。

也可以使用 Cache.asMap() 所暴露出来的 ConcurrentMap 的方法直接对缓存进行操作。

2.LoadingCache 自动加载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LoadingCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .maximumSize(10_000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build(new CacheLoader<Key, UserInfo>() {
                    @Override
                    public UserInfo load(Key key) throws Exception {
                        return getUserInfoByDB(key);
                    }

                    @Override
                    public Map<Key, UserInfo> loadAll(@Nonnull Iterable<? extends Key> key) throws Exception {
                      return getUserInfosByDB(ists.newArrayList(key));
                    }
                });

// 查找缓存，如果缓存不存在则生成缓存元素,  如果无法生成则返回null
UserInfo userInfo = cache.get(key);
// 批量查找缓存，如果缓存不存在则生成缓存元素
Map<Key, UserInfo> userInfos = cache.getAll(keys);

和guava cache相同,LoadingCache是使用CacheLoader来构建的缓存。

批量查找可以使用getAll方法。默认情况下，getAll将会对缓存中没有值的key分别调用CacheLoader.load方法来构建缓存的值。我们可以重写CacheLoader.loadAll方法来提高getAll的效率。

3.AsyncCache 异步手动加载

1
2
3
4
5
6
7
AsyncCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .maximumSize(10_000)
    .buildAsync();

// 查找缓存元素，如果不存在，则异步生成
CompletableFuture<UserInfo> userInfo = cache.get(key, k -> getUserInfoByDB(key));

AsyncLoadingCache异步加载使用Executor去调用方法并返回一个CompletableFuture。异步加载缓存使用了响应式编程模型。

如果要以同步方式调用时，应提供CacheLoader。要以异步表示时，应该提供一个AsyncCacheLoader，并返回一个CompletableFuture。

synchronous()这个方法提供了一个阻塞缓存的视图LoadingCache,直到异步计算完成。调用该方法后就相当于将一个异步加载的缓存AsyncLoadingCache转换成了一个同步加载的缓存LoadingCache。

默认使用ForkJoinPool.commonPool()来执行异步线程，但是我们可以通过Caffeine.executor(Executor) 方法来替换为指定线程池。

4.AsyncLoadingCache 异步自动加载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
AsyncLoadingCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .maximumSize(10_000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    // 你可以选择: 去异步的封装一段同步操作来生成缓存元素
    .buildAsync(new CacheLoader<Key, UserInfo>() {
                    @Override
                    public UserInfo asyncLoad(Key key) throws Exception {
                        return getUserInfoByDB(key);
                    }

                    @Override
                    public Map<Key, UserInfo> asyncLoadAll(@Nonnull Iterable<? extends Key> key) throws Exception {
                      return getUserInfosByDB(ists.newArrayList(key));
                    }
                });

// 找缓存元素，如果其不存在，将会异步进行生成
CompletableFuture<UserInfo> userInfo = cache.get(key);
// 批量查找缓存元素，如果其不存在，将会异步进行生成
CompletableFuture<Map<Key, UserInfo>> userInfos = cache.getAll(keys);

AsyncLoadingCache是使用AsyncCacheLoader来构建的异步缓存,和同步加载的方式类似,异步自动加载需要一个AsyncCacheLoader,并返回CompletableFuture

淘汰策略

cffeine提供三种淘汰策略：基于大小（size-based），基于时间（time-based）和基于引用（reference-based）。

1.基于大小（size-based）

1
2
3
4
5
6
7
8
9
10
// 基于配置的大小淘汰缓存
LoadingCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .maximumSize(10_000)
    .build(this::load);

// 基于配置的权重淘汰缓存
LoadingCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .maximumWeight(10_000)
    .weigher((String key, UserInfo value)->key.getBytes().length + value.getBytes().length)
    .build(this::load);

基于大小淘汰，有两种方式：一种是基于缓存数量大小，一种是基于缓存的权重。

使用Caffeine.maximumSize(long)方法来指定缓存的最大容量。当缓存超出这个容量的时候，会使用Window-TinyLfu策略来删除缓存。

可以使用权重的策略来进行淘汰，可以使用Caffeine.weigher(Weigher)来指定权重函数，使用Caffeine.maximumWeight(long) 函数来指定缓存最大权重值。maximumWeight与maximumSize不可以同时使用。

当我们的缓存大小不均匀时，我们可以通过这种方式控制总大小。权重计算是在其创建或更新时发生的，此后其权重值都是静态存在的。

2.基于时间（time-based）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 基于固定的过期策略进行淘汰
// 表示自从最后一次访问（写入或者读取）后多久就会过期
LoadingCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .expireAfterAccess(5, TimeUnit.MINUTES)
    .build(this::load);

// 表示自从最后一次写入后多久就会过期
LoadingCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build(this::load);

// 基于动态的过期策略进行淘汰
LoadingCache<Key, UserInfo> cache = Caffeine.newBuilder()
    .expireAfter(new Expiry<Key, UserInfo>() {
      long expireAfterCreate(@Nonnull K var1, @Nonnull V var2, long var3) {
        // 首次创建过期时间设置
      }
    	long expireAfterUpdate(@Nonnull K var1, @Nonnull V var2, long var3, @Nonnegative long var5) {
      	// 更新过期时间设置
      }

    	long expireAfterRead(@Nonnull K var1, @Nonnull V var2, long var3, @Nonnegative long var5) {
        // 读取过期时间设置
      }
    })
    .build(key -> getUserInfoByDB(key));

Caffeine提供了三种定时驱逐策略：

1、expireAfterAccess(long, TimeUnit):在最后一次访问或者写入后开始计时，在指定的时间后过期。假如一直有请求访问该key，那么这个缓存将一直不会过期。

2、expireAfterWrite(long, TimeUnit): 在最后一次写入缓存后开始计时，在指定的时间后过期。

3、expireAfter(Expiry): 自定义策略，过期时间由Expiry实现计算。

通过在写入和偶尔在读取的期间来定期维护过期处理,过期事件的调度和触发都以O(1)进行。

对于准时过期，而不是依赖其他缓存活动来触发常规的维护，请使用调度程序接口和Caffeine.Scheduler（Scheduler）方法指定调度线程.

Caffeine的缓存清除是惰性的，可能发生在读请求后或者写请求后，比如说有一条数据过期后，不会立即删除，可能在下一次读/写操作后触发删除。如果读请求和写请求比较少，但想要尽快的删掉cache中过期的数据的话，可以通过增加定时器的方法（Caffeine.Scheduler（Scheduler）），定时执行cache.cleanUp()方法，触发缓存清除操作。

3.基于引用（reference-based）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Evict when neither the key nor value are strongly reachable
LoadingCache<Key, UserInfo> graphs = Caffeine.newBuilder()
    .weakKeys()
    .weakValues()
    .build(new CacheLoader<Key, UserInfo>() {
                   ...
                });

// 当进行GC的时候进行淘汰
LoadingCache<Key, UserInfo> graphs = Caffeine.newBuilder()
    .softValues()
    .build(new CacheLoader<Key, UserInfo>() {
                   ...
                });

java种有四种引用：强引用，软引用，弱引用和虚引用，caffeine可以将值封装成弱引用或软引用。

软引用：如果一个对象只具有软引用，则内存空间足够，垃圾回收器就不会回收它；如果内存空间不足了，就会回收这些对象的内存。

弱引用：弱引用的对象拥有更短暂的生命周期。在垃圾回收器线程扫描它所管辖的内存区域的过程中，一旦发现了只具有弱引用的对象，不管当前内存空间足够与否，都会回收它的内存

我们可以将缓存的驱逐配置成基于垃圾回收器。为此，我们可以将key 和 value 配置为弱引用或只将值配置成软引用。

注意：AsyncLoadingCache不支持弱引用和软引用。

Caffeine.weakKeys() 使用弱引用存储key。如果没有其他地方对该key有强引用，那么该缓存就会被垃圾回收器回收。由于垃圾回收器只依赖于身份(identity)相等，因此这会导致整个缓存使用身份 (==) 相等来比较 key，而不是使用 equals()。

Caffeine.weakValues() 使用弱引用存储value。如果没有其他地方对该value有强引用，那么该缓存就会被垃圾回收器回收。由于垃圾回收器只依赖于身份(identity)相等，因此这会导致整个缓存使用身份 (==) 相等来比较 key，而不是使用 equals()。

Caffeine.softValues() 使用软引用存储value。当内存满了过后，软引用的对象以将使用最近最少使用(least-recently-used ) 的方式进行垃圾回收。由于使用软引用是需要等到内存满了才进行回收，所以我们通常建议给缓存配置一个使用内存的最大值。 softValues() 将使用身份相等(identity) (==) 而不是equals() 来比较值。

注意：Caffeine.weakValues()和Caffeine.softValues()不可以一起使用。

刷新策略

1
2
3
4
5
LoadingCache<String, String> cache = Caffeine.newBuilder()
                .expireAfterWrite(10,TimeUnit.SECONDS)
                .refreshAfterWrite(2,TimeUnit.SECONDS)
                .executor(Executors.newFixedThreadPool(1))
                .build(this::load);

Caffeine和Guava cache一样，也提供了异步刷新的功能，通过refreshAfterWrite方法指定刷新的时间

刷新和淘汰是不一样的。刷新的是通过LoadingCache.refresh(key)方法来指定，并通过调用CacheLoader.load方法来执行，刷新key会异步地为这个key加载新的value，并返回旧的值（如果有的话）。淘汰会阻塞查询操作直到淘汰作完成才会进行其他操作。

refreshAfterWrite在查询数据的时候判断该数据是不是符合查询条件，如果符合条件该缓存就会去执行刷新操作。例如，可以在同一个缓存中同时指定refreshAfterWrite和expireAfterWrite，只有当数据具备刷新条件的时候才会去刷新数据，不会盲目去执行刷新操作。如果数据在刷新后就一直没有被再次查询，那么该数据也会过期。

在刷新的时候如果查询缓存元素，其旧值将仍被返回，直到该元素的刷新完毕后结束后才会返回刷新后的新值。refreshAfterWrite 将会使在写操作之后的一段时间后允许 key 对应的缓存元素进行刷新，但是只有在这个 key 被真正查询到的时候才会正式进行刷新操作。

在刷新的过程中，如果抛出任何异常，会保留旧值。异常会被 logger 打印，然后被吞掉。

此外，CacheLoader 还支持通过覆盖重写 CacheLoader.reload(K, V) 方法使得在刷新中可以将旧值也参与到更新的过程中去。

refresh 的操作将会异步执行在一个 Executor 上。默认的线程池实现是 ForkJoinPool.commonPool()。当然也可以通过覆盖 Caffeine.executor(Executor) 方法自定义线程池的实现。这个 Executor 同时负责 removalListener 的操作。

移除监听器

1
2
3
4
Cache<Key, Graph> graphs = Caffeine.newBuilder()
    .removalListener((Key key, UserInfo userInfo, RemovalCause cause) ->
        System.out.printf("Key %s was removed (%s)%n", key, cause))
    .build();

通过Caffeine.removalListener(RemovalListener) 为缓存指定一个删除监听，以便在删除数据时执行某些操作。 RemovalListener可以获取到key、value和RemovalCause（删除的原因）。

监听器的操作是使用Executor来异步执行的。默认执行程序是ForkJoinPool.commonPool()，可以通过Caffeine.executor(Executor)覆盖。注意：由RemovalListener抛出的任何异常都会被记录（使用Logger）但并不会抛出。

Writer

1
2
3
4
5
6
7
8
9
10
LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
  .writer(new CacheWriter<Key, Graph>() {
    @Override public void write(Key key, Graph graph) {
      // 持久化或者次级缓存
    }
    @Override public void delete(Key key, Graph graph, RemovalCause cause) {
      // 从持久化或者次级缓存中删除
    }
  })
  .build(this::load);

CacheWriter允许缓存充当一个底层资源的代理，当与CacheLoader结合使用时，所有对缓存的读写操作都可以通过Writer进行传递。Writer可以把操作缓存和操作外部资源扩展成一个同步的原子性操作。并且在缓存写入完成之前，它将会阻塞后续的更新缓存操作，但是读取（get）将直接返回原有的值。如果写入程序失败，那么原有的key和value的映射将保持不变，如果出现异常将直接抛给调用者。

CacheWriter可以同步的监听到缓存的创建、变更和删除操作。加载（例如LoadingCache.get）、重新加载（例如LoadingCache.refresh）和计算（例如Map.computeIfPresent）的操作不被CacheWriter监听到。

注意：CacheWriter不能与weakKeys或AsyncLoadingCache结合使用。

CacheWriter 可以用来实现 write-through 和 write-back 两种模式的缓存。也可以用来整合多级缓存，或是用来作为发布同步监听器使用。

统计

1
2
3
4
Cache<Key, UserInfo> cache = Caffeine.newBuilder()
 .maximumSize(10_000)
 .recordStats()
 .build();

使用Caffeine.recordStats()，您可以打开统计信息收集。Cache.stats() 方法返回提供统计信息的CacheStats，如：

  • hitRate()：返回命中与请求的比率

  • hitCount(): 返回命中缓存的总数

  • evictionCount()：缓存逐出的数量

  • averageLoadPenalty()：加载新值所花费的平均时间

这些统计数据对于缓存优化至关重要，我们建议在性能关键的应用程序中密切关注这些统计数据。

缓存统计信息可以使用基于pull or push的方法与报告系统集成.基于pull的方法定期调用Cache.stats()并记录最新的快照,基于pusu的方法提供一个定制的statcounter，以便在缓存操作期间直接更新度量。

Cleanup清理

Caffeine的缓存清除是惰性的，可能发生在读请求后或者写请求后，比如说有一条数据过期后，不会立即删除，可能在下一次读/写操作后触发删除。如果读请求和写请求比较少，但想要尽快的删掉cache中过期的数据的话，可以通过增加定时器的方法，定时执行cache.cleanUp()方法，触发缓存清除操作。

淘汰算法

淘汰策略是影响缓存命中率的因素之一，一般比较简单的缓存就会直接用到 LFU(Least Frequently Used，即最不经常使用) 或者LRU(Least Recently Used，即最近最少使用) ，而 Caffeine 就是使用了 W-TinyLFU 算法。

LRU（Least Recently Used）算法认为最近访问过的数据将来被访问的几率也更高。LRU通常使用链表来实现，如果数据添加或者被访问到则把数据移动到链表的头部，链表的头部为热数据，链表的尾部如冷数据，当数据满时，淘汰尾部的数据。

  • 优点：实现简单，可以有效的对访问比较频繁的数据进行保护，也就是针对热点数据的命中率提高有明显的效果。

  • 缺点：对于周期性、偶发性的访问数据，有大概率可能造成缓存污染，也就是置换出去了热点数据，把这些偶发性数据留下了，从而导致LRU的数据命中率急剧下降。

LFU（Least Frequently Used）算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。根据LFU的思想，如果想要实现这个算法，需要额外的一套存储用来存每个元素的访问次数，会造成内存资源的浪费。

  • 优点：LFU也可以有效的保护缓存，相对场景来讲，比LRU有更好的缓存命中率。因为是以次数为基准，所以更加准确，自然能有效的保证和提高命中率

  • 缺点：LFU需要额外的一套存储用来存每个元素的访问次数，会造成内存资源的浪费。对突发性的稀疏流量无力，因为前期经常访问的记录已经占用了缓存，偶然的流量不太可能会被保留下来，而且过去的一些大量被访问的记录在将来也不一定会使用上，这样就一直把“坑”占着了。

W-TinyLFU

核心实现

无论LRU还是LFU都有其各自的缺点，不过，现在已经有很多针对其缺点而改良、优化出来的变种算法。Caffeine的缓存淘汰是通过一种叫做W-TinyLFU的数据结构实现的，这是一种对LRU和LFU进行了组合优化的算法，以及结合了一些其他算法的特点，提供了一个近乎最佳的命中率。

W-TinyLFU采用了Count–Min Sketch算法，解决LFU资源浪费的问题，引入一个窗口来保存突发流量，使得新元素能有机会保留下来。

关于Count-Min Sketch算法，可以看作是布隆过滤器的同源的算法，假如我们用一个hashmap来存储每个元素的访问次数，那这个量级是比较大的，并且hash冲突的时候需要做一定处理，否则数据会产生很大的误差，Count-Min Sketch算法将一个hash操作，扩增为多个hash，这样原来hash冲突的概率就降低了几个等级，且当多个hash取得数据的时候，取最低值，也就是Count Min的含义所在。如下图：

avatar

图中不同的row对应着不同的哈希算法，depth大小代表着哈希算法的数量，width则表示数据可哈希的范围。如果需要记录一个值，那我们需要通过多种Hash算法对其进行处理hash，然后在对应的hash算法的记录中+1。使用多个哈希算法可以降低哈希碰撞带来的数据不准确的概率，宽度上的增加可以提高key的哈希范围，减少碰撞的概率，所以合理的调整算法数量和哈希的范围，可以更好的平衡空间与哈希碰撞产生的错误率。

Caffeine 对此有进一步的优化，例如Count–Min Sketch使用了二维数组，Caffeine只是用了一个一维的数组；频次如果是数值类型的话，这个数需要用 int 或 long 来存储，但是Caffeine 认为缓存的访问频率不需要用到那么大，只需要 15 就足够，一般认为达到 15 次的频率算是很高的了，而且 Caffeine 还有另外一个机制来使得这个频率进行衰退减半。如果最大是 15 的话，那么只需要 4 个 bit 就可以满足了，一个 long 有 64bit，可以存储 16 个这样的统计数，Caffeine 就是这样的设计，使得存储效率提高了 16 倍。

avatar

保新机制

为了让缓存保持“新鲜”，剔除掉过往频率很高但之后不经常的缓存，Caffeine 有一个 Freshness Mechanism。做法很简单，就是当整体的统计计数（当前所有记录的频率统计之和，这个数值内部维护）达到某一个值时，那么所有记录的频率统计除以 2。

淘汰策略

Caffeine 通过测试发现 TinyLFU 在面对突发性的稀疏流量（sparse bursts）时表现很差，因为新的记录（new items）还没来得及建立足够的频率就被剔除出去了，这就使得命中率下降。

Window TinyLFU主要结构如下：

avatar

可以看到整个W-TinyLFU由三部分构成：

  • 准入窗口（Admission Windows），由一个较小的LRU队列构成，其容量只有整个缓存大小的1%，这个窗口的作用主要是为了保护一些新进入缓存的数据，给他们一定的成长时间来积累自己的使用频率，避免被快速淘汰掉，而且LRU也能应对突发的流量。

  • 频次过滤器（TinyLFU）是W-TinyLFU核心部分，也是Caffeine精髓所在，上面核心实现的内容。

  • 主缓存区（Main Cache）用于存放大部分的缓存数据，数据结构为一个分段LRU队列（SLRU），占整个缓存容量的99%，Segmented LRU核心思想就是分段，所以整个主缓存区包括Protected和Probation两部分，其中Protected的大小占主缓存区容量的80%，Probation占20%，发生数据淘汰时，会从这部分缓存里获取数据进行淘汰。

在caffeine所有的数据都在ConcurrentHashMap中，这个和guava cache不同，guava cache是自己实现了个类似ConcurrentHashMap的结构。在caffeine中有三个记录引用的LRU队列:

  • Eden队列:在caffeine中规定只能为缓存容量的%1,如果size=100,那这个队列的有效大小就等于1。这个队列中记录的是新到的数据，防止突发流量由于之前没有访问频率，而导致被淘汰。比如有一部新剧上线，在最开始其实是没有访问频率的，防止上线之后被其他缓存淘汰出去，而加入这个区域。伊甸区，最舒服最安逸的区域，在这里很难被其他数据淘汰。

  • Probation队列:叫做缓刑队列，在这个队列就代表你的数据相对比较冷，马上就要被淘汰了。这个有效大小为size减去eden减去protected。

  • Protected队列:在这个队列中，可以稍微放心一下了，你暂时不会被淘汰，但是别急，如果Probation队列没有数据了或者Protected数据满了，你也将会被面临淘汰的尴尬局面。当然想要变成这个队列，需要把Probation访问一次之后，就会提升为Protected队列。这个有效大小为(size减去eden) X 80% 如果size =100，就会是79。

这三个队列关系如下:

avatar

  1. 所有进入缓存区的数据会首先被add进Eden区，当该队列长度达到容量限制后，会触发Eden区的淘汰操作，超出的entries会被下放至主缓存区的Probation队列。

  2. 进入Probation队列的数据如果在没有被主缓存区淘汰之前获得了一次access，该节点会被add进Protected队列。

  3. Protecte队列如果达到其容量限制会触发Node Demotion过程，队列首部的元素会被peek出并下放到Probation队列。

  4. 主缓存区的大小(Probation的大小 + Protected的大小)达到了其容量限制会触发主缓存区的数据淘汰，Probation会被优先选择为淘汰队列，如果Probation为空，则选择Protected为淘汰队列。

  5. 别选取淘汰队列的首部元素作为受害者(victim)，尾部元素作为竞争者(candidate)，通过对比两者的访问频次选择最终的淘汰者，其中访问频次通过CountMin Sketch获得。

这套机制确保了访问间隔小的热数据被保存下来，而被重复访问少的冷数据则被回收。

高性能读写

缓存进行读写之后（读的话，已经存在则直接返回，不存在则load数据，保存，再返回；写的话，则直接插入或更新），需要维护一些淘汰策略相关的额外数据，诸如：

  1. 计算和比较数据的是否过期

  2. 统计频率（像LFU或其变种）

  3. 护read queue和write queue

  4. 淘汰符合条件的数据

缓存数据的读写都伴随着缓存状态的变更，Guava Cache的做法是把缓存状态的变更和读写操作一起同步处理，在一个同步加锁的操作中完成。虽然Guava Cache巧妙地利用了JDK的ConcurrentHashMap（JDk7的分段锁或者JDK8的无锁CAS）来降低锁的密度，达到提高并发度的目的。但是，对于一些热点数据，这种做法还是避免不了频繁的锁竞争。

Caffeine借鉴了数据库系统的WAL（Write-Ahead Logging）思想，即先写日志再执行操作，这种思想同样适合缓存。在执行读写操作时，先把操作记录在缓冲区，然后在合适的时机异步、批量地执行缓冲区中的内容。但在执行缓冲区的内容时，也是需要在缓冲区加上同步锁的，不然存在并发问题，只不过这样就可以把 对锁的竞争从缓存数据转移到对缓冲区上。

Caffeine 认为读操作是频繁的，写操作是偶尔的，读写都是异步线程更新频率信息。

读缓冲

传统的缓存实现将会为每个操作加锁，以便能够安全的对每个访问队列的元素进行排序。一种优化方案是将每个操作按序加入到缓冲区中进行批处理操作。读完把数据放到环形队列 RingBuffer 中，为了减少读并发，采用多个 RingBuffer，每个线程都有对应的 RingBuffer。环形队列是一个定长数组，提供高性能的能力并最大程度上减少了 GC所带来的性能开销。数据丢到队列之后就返回读取结果，类似于数据库的WAL机制，和ConcurrentHashMap 读取数据相比，仅仅多了把数据放到队列这一步。异步线程并发读取 RingBuffer 数组，更新访问信息。

avatar

写缓冲

与读缓冲类似，写缓冲是为了储存写事件。读缓冲中的事件主要是为了优化驱逐策略的命中率，因此读缓冲中的事件完整程度允许一定程度的有损。但是写缓冲并不允许数据的丢失，因此其必须实现为一个安全的队列。Caffeine 写是把数据放入MpscGrowableArrayQueue 阻塞队列中，它参考了JCTools里的MpscGrowableArrayQueue ，是针对 MPSC- 多生产者单消费者（Multi-Producer & Single-Consumer）场景的高性能实现。多个生产者同时并发地写入队列是线程安全的，但是同一时刻只允许一个消费者消费队列。

资料：

时间轮：https://blog.csdn.net/weixin_43167418/article/details/111570240

https://km.sankuai.com/page/357451435

https://albenw.github.io/posts/a4ae1aa2/

https://km.sankuai.com/page/1001307176

https://km.sankuai.com/page/212609259#id-Performance%E6%80%A7%E8%83%BD

最后更新： 2022年03月08日 15:49

原始链接： https://jjw-story.github.io/2021/12/12/Caffeine/

赏
× 请我吃糖~
打赏二维码