高性能缓存 Caffeine 原理及实战
时间:2021-08-19 15:51:26
手机看文章
扫描二维码
随时随地手机看文章
[导读]一、简介Caffeine是基于Java8开发的、提供了近乎最佳命中率的高性能本地缓存组件,Spring5开始不再支持GuavaCache,改为使用Caffeine。下面是Caffeine官方测试报告。由上面三幅图可见:不管在并发读、并发写还是并发读写的场景下,Caffeine的性...
一、简介
Caffeine 是基于Java 8 开发的、提供了近乎最佳命中率的高性能本地缓存组件,Spring5 开始不再支持 Guava Cache,改为使用 Caffeine。
下面是 Caffeine 官方测试报告。
由上面三幅图可见:不管在并发读、并发写还是并发读写的场景下,Caffeine 的性能都大幅领先于其他本地开源缓存组件。
本文先介绍 Caffeine 实现原理,再讲解如何在项目中使用 Caffeine 。
二、Caffeine 原理
2.1 淘汰算法
2.1.1 常见算法
对于 Java 进程内缓存我们可以通过 HashMap 来实现。不过,Java 进程内存是有限的,不可能无限地往里面放缓存对象。这就需要有合适的算法辅助我们淘汰掉使用价值相对不高的对象,为新进的对象留有空间。常见的缓存淘汰算法有 FIFO、LRU、LFU。
FIFO(First In First Out):先进先出。它是优先淘汰掉最先缓存的数据、是最简单的淘汰算法。缺点是如果先缓存的数据使用频率比较高的话,那么该数据就不停地进进出出,因此它的缓存命中率比较低。
LRU(Least Recently Used):最近最久未使用。它是优先淘汰掉最久未访问到的数据。缺点是不能很好地应对偶然的突发流量。比如一个数据在一分钟内的前59秒访问很多次,而在最后1秒没有访问,但是有一批冷门数据在最后一秒进入缓存,那么热点数据就会被冲刷掉。
LFU(Least Frequently Used):最近最少频率使用。它是优先淘汰掉最不经常使用的数据,需要维护一个表示使用频率的字段。主要有两个缺点:一、如果访问频率比较高的话,频率字段会占据一定的空间;二、无法合理更新新上的热点数据,比如某个歌手的老歌播放历史较多,新出的歌如果和老歌一起排序的话,就永无出头之日。
2.1.2 W-TinyLFU 算法
Caffeine 使用了 W-TinyLFU 算法,解决了 LRU 和LFU上述的缺点。W-TinyLFU 算法由论文《TinyLFU: A Highly Efficient Cache Admission Policy》提出。
它主要干了两件事:一、采用 Count–Min Sketch 算法降低频率信息带来的内存消耗;二、维护一个PK机制保障新上的热点数据能够缓存。
如下图所示,Count–Min Sketch 算法类似布隆过滤器 (Bloom filter)思想,对于频率统计我们其实不需要一个精确值。存储数据时,对key进行多次 hash 函数运算后,二维数组不同位置存储频率(Caffeine 实际实现的时候是用一维 long 型数组,每个 long 型数字切分成16份,每份4bit,默认15次为最高访问频率,每个key实际 hash 了四次,落在不同 long 型数字的16份中某个位置)。读取某个key的访问次数时,会比较所有位置上的频率值,取最小值返回。对于所有key的访问频率之和有个最大值,当达到最大值时,会进行reset即对各个缓存key的频率除以2。
如下图缓存访问频率存储主要分为两大部分,即 LRU 和 Segmented LRU 。新访问的数据会进入第一个 LRU,在 Caffeine 里叫 WindowDeque。当 WindowDeque 满时,会进入 Segmented LRU 中的 ProbationDeque,在后续被访问到时,它会被提升到 ProtectedDeque。当 ProtectedDeque 满时,会有数据降级到 ProbationDeque 。数据需要淘汰的时候,对 ProbationDeque 中的数据进行淘汰。具体淘汰机制:取ProbationDeque 中的队首和队尾进行 PK,队首数据是最先进入队列的,称为受害者,队尾的数据称为攻击者,比较两者 频率大小,大胜小汰。
总的来说,通过 reset 衰减,避免历史热点数据由于频率值比较高一直淘汰不掉,并且通过对访问队列分成三段,这样避免了新加入的热点数据早早地被淘汰掉。
2.2 高性能读写
Caffeine 认为读操作是频繁的,写操作是偶尔的,读写都是异步线程更新频率信息。
2.2.1 读缓冲
传统的缓存实现将会为每个操作加锁,以便能够安全的对每个访问队列的元素进行排序。一种优化方案是将每个操作按序加入到缓冲区中进行批处理操作。读完把数据放到环形队列 RingBuffer 中,为了减少读并发,采用多个 RingBuffer,每个线程都有对应的 RingBuffer。环形队列是一个定长数组,提供高性能的能力并最大程度上减少了 GC所带来的性能开销。数据丢到队列之后就返回读取结果,类似于数据库的WAL机制,和ConcurrentHashMap 读取数据相比,仅仅多了把数据放到队列这一步。异步线程并发读取 RingBuffer 数组,更新访问信息,这边的线程池使用的是下文实战小节讲的 Caffeine 配置参数中的 executor。
2.2.2 写缓冲
与读缓冲类似,写缓冲是为了储存写事件。读缓冲中的事件主要是为了优化驱逐策略的命中率,因此读缓冲中的事件完整程度允许一定程度的有损。但是写缓冲并不允许数据的丢失,因此其必须实现为一个安全的队列。Caffeine 写是把数据放入MpscGrowableArrayQueue 阻塞队列中,它参考了JCTools里的MpscGrowableArrayQueue ,是针对 MPSC- 多生产者单消费者(Multi-Producer
Caffeine 是基于Java 8 开发的、提供了近乎最佳命中率的高性能本地缓存组件,Spring5 开始不再支持 Guava Cache,改为使用 Caffeine。
下面是 Caffeine 官方测试报告。
由上面三幅图可见:不管在并发读、并发写还是并发读写的场景下,Caffeine 的性能都大幅领先于其他本地开源缓存组件。
本文先介绍 Caffeine 实现原理,再讲解如何在项目中使用 Caffeine 。
二、Caffeine 原理
2.1 淘汰算法
2.1.1 常见算法
对于 Java 进程内缓存我们可以通过 HashMap 来实现。不过,Java 进程内存是有限的,不可能无限地往里面放缓存对象。这就需要有合适的算法辅助我们淘汰掉使用价值相对不高的对象,为新进的对象留有空间。常见的缓存淘汰算法有 FIFO、LRU、LFU。
FIFO(First In First Out):先进先出。它是优先淘汰掉最先缓存的数据、是最简单的淘汰算法。缺点是如果先缓存的数据使用频率比较高的话,那么该数据就不停地进进出出,因此它的缓存命中率比较低。
LRU(Least Recently Used):最近最久未使用。它是优先淘汰掉最久未访问到的数据。缺点是不能很好地应对偶然的突发流量。比如一个数据在一分钟内的前59秒访问很多次,而在最后1秒没有访问,但是有一批冷门数据在最后一秒进入缓存,那么热点数据就会被冲刷掉。
LFU(Least Frequently Used):最近最少频率使用。它是优先淘汰掉最不经常使用的数据,需要维护一个表示使用频率的字段。主要有两个缺点:一、如果访问频率比较高的话,频率字段会占据一定的空间;二、无法合理更新新上的热点数据,比如某个歌手的老歌播放历史较多,新出的歌如果和老歌一起排序的话,就永无出头之日。
2.1.2 W-TinyLFU 算法
Caffeine 使用了 W-TinyLFU 算法,解决了 LRU 和LFU上述的缺点。W-TinyLFU 算法由论文《TinyLFU: A Highly Efficient Cache Admission Policy》提出。
它主要干了两件事:一、采用 Count–Min Sketch 算法降低频率信息带来的内存消耗;二、维护一个PK机制保障新上的热点数据能够缓存。
如下图所示,Count–Min Sketch 算法类似布隆过滤器 (Bloom filter)思想,对于频率统计我们其实不需要一个精确值。存储数据时,对key进行多次 hash 函数运算后,二维数组不同位置存储频率(Caffeine 实际实现的时候是用一维 long 型数组,每个 long 型数字切分成16份,每份4bit,默认15次为最高访问频率,每个key实际 hash 了四次,落在不同 long 型数字的16份中某个位置)。读取某个key的访问次数时,会比较所有位置上的频率值,取最小值返回。对于所有key的访问频率之和有个最大值,当达到最大值时,会进行reset即对各个缓存key的频率除以2。
如下图缓存访问频率存储主要分为两大部分,即 LRU 和 Segmented LRU 。新访问的数据会进入第一个 LRU,在 Caffeine 里叫 WindowDeque。当 WindowDeque 满时,会进入 Segmented LRU 中的 ProbationDeque,在后续被访问到时,它会被提升到 ProtectedDeque。当 ProtectedDeque 满时,会有数据降级到 ProbationDeque 。数据需要淘汰的时候,对 ProbationDeque 中的数据进行淘汰。具体淘汰机制:取ProbationDeque 中的队首和队尾进行 PK,队首数据是最先进入队列的,称为受害者,队尾的数据称为攻击者,比较两者 频率大小,大胜小汰。
总的来说,通过 reset 衰减,避免历史热点数据由于频率值比较高一直淘汰不掉,并且通过对访问队列分成三段,这样避免了新加入的热点数据早早地被淘汰掉。
2.2 高性能读写
Caffeine 认为读操作是频繁的,写操作是偶尔的,读写都是异步线程更新频率信息。
2.2.1 读缓冲
传统的缓存实现将会为每个操作加锁,以便能够安全的对每个访问队列的元素进行排序。一种优化方案是将每个操作按序加入到缓冲区中进行批处理操作。读完把数据放到环形队列 RingBuffer 中,为了减少读并发,采用多个 RingBuffer,每个线程都有对应的 RingBuffer。环形队列是一个定长数组,提供高性能的能力并最大程度上减少了 GC所带来的性能开销。数据丢到队列之后就返回读取结果,类似于数据库的WAL机制,和ConcurrentHashMap 读取数据相比,仅仅多了把数据放到队列这一步。异步线程并发读取 RingBuffer 数组,更新访问信息,这边的线程池使用的是下文实战小节讲的 Caffeine 配置参数中的 executor。
2.2.2 写缓冲
与读缓冲类似,写缓冲是为了储存写事件。读缓冲中的事件主要是为了优化驱逐策略的命中率,因此读缓冲中的事件完整程度允许一定程度的有损。但是写缓冲并不允许数据的丢失,因此其必须实现为一个安全的队列。Caffeine 写是把数据放入MpscGrowableArrayQueue 阻塞队列中,它参考了JCTools里的MpscGrowableArrayQueue ,是针对 MPSC- 多生产者单消费者(Multi-Producer