先说论断:本地缓存优先选用 caffeine,因为性能比 guava cache 快,api 格调与之兼容、能轻松地平滑迁徙,并且在 spring/spring boot 最新版本中曾经是默认本地缓存了。上面开展讲讲本地缓存和 Spring cache。
本文探讨堆内缓存,暂不探讨堆外缓存。堆内缓存是指缓存与应用程序在一个 JVM 利用中,会受 GC 影响,个别业务层面的利用开发用不到堆外缓存。
1、什么场景应用本地缓存
并非所有的缓存场景,redis 都实用,以下状况该当优先思考本地缓存。
- 数据量不大
- 批改频率低、甚至是动态的数据
- 查问 qps 极高:通过纯内存操作,防止网络申请
- 对性能有极致要求,速度比 redis 更快
如:秒杀热点商品缓存、地区信息缓存。
2、缓存基本原理
先简略回顾一下缓存的基本原理。
语义
- get:依据 key 查问 value,缓存未命中时查问底层数据并设置缓存
- put:设置缓存
- evict:删除 key
- ttl:kv 键值对过期生效
淘汰策略
缓存有大小下限,超过后须要淘汰掉冷数据,保留真正的热数据,以确保缓存命中率。有 2 种常见算法:LRU 和 LFU。
LRU(Least Recently Used)
优先淘汰掉最近起码应用的数据,该算法假如最近拜访的数据,未来也会频繁地应用。
-
长处
- 容易了解和实现
- 链表占用空间小
-
毛病
- 长期批量数据,会把真正的热数据冲掉,而造成缓存命中率急剧下降,影响性能
上面给出 LRU 算法的 2 种伪代码实现:
-
LinkedHashMap 实现:LinkedHashMap 底层数据结构就是一个 HashMap 和双向链表的结合体,能够借助它疾速实现 LRU 算法。
public class LRUCache extends LinkedHashMap { // 缓存最大条目数 private int maxSize; public LRUCache(int maxSize) { // 初始大小为 16,loadFactor 为 0.75,accessOrder 按拜访顺序排列为 true super(16, 0.75f, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { // 大小超过 maxSize 时,删除最长远的数据 return size() > maxSize;} }
-
Map+Deque 实现:
- Deque 双端队列队尾是最新数据,队首是最长远数据
- 最新拜访的元素,如果已存在,则挪动至队尾,否则直接插入队尾
- put 时如果已满,则删除队首元素
// 泛型反对
public class LRUCache<K, V> {
private int maxSize;
private Map<K, V> map = new HashMap<>();
// 双端队列,用于记录拜访的远近;LinkedList 是 Deque 的子类
private LinkedList<K> recencyList = new LinkedList<>();
public LRUCache(int maxSize) {this.maxSize = maxSize;}
public V get(K key) {if (map.containsKey(key)) {moveToTail(key);
return map.get(key);
} else {return null;}
}
public void put(K key, V value) {if (map.containsKey(key)) {moveToTail(key);
} else {addToTail(key);
}
map.put(key, value);
if (map.size() > maxSize) {removeEldest();
}
}
private void moveToTail(K key) {recencyList.remove(key);
recencyList.add(key);
}
private void addToTail(K key) {recencyList.add(key);
}
private void removeEldest(K key) {recencyList.removeFirst(key);
}
}
LFU(Least Frequently Used)
优先淘汰掉最不常常应用的数据,该算法假如最近应用频率高的数据,未来也会频繁地应用。
-
长处
- 统计了 key 的拜访频率,淘汰掉的数据大概率是冷数据
- 不会受长期批量数据的影响
-
毛病
- 占用更大的内存,须要额定记录 key 的拜访频率的数据结构
- 统计周期难以确定,新拜访的数据频率值较低,即便后续常常拜访,也可能先被淘汰
- 伪代码实现
public class LFUCache {
// 容量大小
int cap;
// 最小的频次
int minFreq;
// key 到 val 的映射
HashMap<Integer, Integer> key2Val;
// key 到 freq 的映射
HashMap<Integer, Integer> key2Freq;
// freq 到 key 列表的映射
HashMap<Integer, LinkedHashSet<Integer>> freq2Keys;
public LFUCache(int capacity) {
this.cap = capacity;
this.minFreq = 0;
key2Val = new HashMap<>();
key2Freq = new HashMap<>();
freq2Keys = new HashMap<>();}
public int get(int key) {if (!key2Val.containsKey(key)) {return -1;}
// 减少拜访频次
increaseFreq(key);
return key2Val.get(key);
}
public void put(int key, int value) {if (this.cap == 0) {return;}
// 判断是否蕴含 key,蕴含间接减少拜访频次,更新值
if (key2Val.containsKey(key)) {
// 减少拜访频次
increaseFreq(key);
key2Val.put(key, value);
return;
}
// 不蕴含,判断是否达到容量,达到容量删除起码频次,最先拜访的元素
if (key2Val.size() >= this.cap) {removeMinFreqKey();
}
// 保留数据,更新频次
key2Val.put(key, value);
// 设置 key 热度
key2Freq.put(key, 1);
freq2Keys.putIfAbsent(1, new LinkedHashSet<>());
// 热度与 key 关联
freq2Keys.get(1).add(key);
this.minFreq = 1;
}
private void increaseFreq(Integer key) {int freq = key2Freq.get(key);
// 减少热度
key2Freq.put(key, freq + 1);
freq2Keys.putIfAbsent(freq + 1, new LinkedHashSet<>());
freq2Keys.get(freq + 1).add(key);
// 调整热度与 key 关系的数据
freq2Keys.get(freq).remove(key);
if (freq2Keys.get(freq).size() == 0) {freq2Keys.remove(freq);
if (freq == this.minFreq) {this.minFreq++;}
}
}
private void removeMinFreqKey() {
// 查看最小的热度
// 找到最先拜访的 key
int oldKey = freq2Keys.get(this.minFreq).iterator().next();
// 删除 key 及 val
key2Val.remove(oldKey);
key2Freq.remove(oldKey);
// 删除热度与 key 的关系
freq2Keys.get(this.minFreq).remove(oldKey);
if (freq2Keys.get(this.minFreq).size() == 0) {freq2Keys.remove(this.minFreq);
}
}
}
3、Guava cache 大抵原理
- 淘汰策略应用 LRU 算法
- 应用了 2 个队列 accessQueue、writeQueue,别离记录读、写缓存时数据拜访和写入的程序,更加精密
- 惰性删除:拜访缓存的时候判断数据是否过期,如果过期才将其删除,并没有专门的后盾线程来删除过期数据
- 并发:map 数据结构相似 ConcurrentHashMap,有多个 segment,不同 segment 之间的读写可并发;
4、caffeine 大抵原理
- 淘汰策略应用 window tiny-lfu 算法,是一种高效的近似 LFU 算法
- 应用 3 个队列:WindowDeque 作为前置的 LRU,ProbationDeque(试用期队列)、ProtectedDeque(受爱护队列),当 WindowDeque 满时,会进入 Segmented LRU 中的 ProbationDeque,在后续被拜访到时,它会被晋升到 ProtectedDeque。当 ProtectedDeque 满时,会有数据降级到 ProbationDeque
- 异步淘汰数据
上面是从 github wiki 和 [高性能缓存 Caffeine 原理及实战
](https://zhuanlan.zhihu.com/p/…) 摘抄的。
一、近似统计频率,而非准确:采纳 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,队首数据是最先进入队列的,称为受害者,队尾的数据称为攻击者,比拟两者频率大小,大胜小汰。
5、Spring cache 应用示例
通过 Spring 能够很不便地集成本地缓存,先介绍基本概念。有 2 个外围类,Cache、CacheManager。
Cache 是缓存的形象接口,提供 put、putIfAbsent(不存在时才设置 kv)、get、evict(删除 kv)、clear(清空所有 kv)、getName(获取缓存名称)等操作。
CacheManager 是一个蕴含了一至多个雷同配置的 Cache 的汇合,提供 getCache(获取 Cache 对象),getCacheNames(获取蕴含的所有 Cache 对象的名称)操作。
配置
以 Caffeine 为例,Guava cache 相似。
需注意:在 @Configuration 润饰的 Spring 配置类上,加上 @EnableCaching,相当于 Spring cache 的总开关。
@Configuration
@EnableCaching
public class CacheConfig {
@Bean
public Caffeine cacheConfig() {return Caffeine.newBuilder() // 默认配置,kv 强援用类型(strong reference,绝对于软援用、弱援用)// 写入 10 秒后过期
.expireAfterWrite(10, TimeUnit.SECONDS)
// 缓存 kv 个数下限
.maximumSize(10000)
// 统计
.recordStats();}
@Bean
public CacheManager cacheManager() {
// 该 CacheManager 包含 2 个缓存 userCache、orderCache
CaffeineCacheManager cacheManager = new CaffeineCacheManager("userCache", "orderCache");
// 应用 cacheConfig bean 的配置
cacheManager.setCaffeine(cacheConfig());
return cacheManager;
}
}
注解申明
- @Cacheable:优先查缓存,如果查不到再通过执行办法逻辑查问,最初塞到缓存中。key 用 SpEL 表达式,如果不指定默认是所有参数作为整体的 key
- @CachePut:立刻更新缓存,而不是期待 key 生效
- @CacheEvict:显式删除 kv
// 应用的 cache 名为 userCache,cacheManager 是 cacheManager,key 为 userDetail 拼上 user 对象的 id 字段
@Cacheable(value="userCache", cacheManager="cacheManager", key="'userDetail' + #user.id")
public UserDetail queryUserDetail(User user) {
// 查问理论逻辑
return userDetailResult;
}