“ 在计算机世界里,缓存可以说无处不在,无论是硬件,还是软件,缓存都是一种最使用的优化手段,可以在操作系统读取磁盘数据时、也可以在应用访问数据库数据时,还可以是本地程序访问网络数据时……”
在开发一个应用时候,一般我们使用缓存先请求缓存,缓存不存在再请求数据库,当从数据库取到后,需要先更新缓存,再返回。这样一来,下次便可以直接从缓存中获取数据,不需要再访问数据库,避免数据直接访问磁盘而从内存直接读取,就是缓存真正的使用价值。
01
—
缓存淘汰算法
FIFO(First in First out)
比较容易实现的一种缓存淘汰策略,思想就是先进先出,是最简单、最公平的思想。即,最先进入缓存的数据,在空间不够的情况下,会被优先清理掉。
缺点:可能不符合数据的动态特征,比如某些热点数据会被频繁使用,但没有响应的机制来存储,直接使用缓存进入时间来淘汰缓存有点太暴力。
适用场景:优先保障最新数据可用
# 实现
# 每次插入链表,插入链表一端(头部),当超过长度时,将另一端(尾部)清除掉;
#LinkedHashMap实现
# 构造的 accessOrder 为false,表示每次访问元素时,不将被访问的元素移动到tail位置
public class FifoCache<K, V> extends LinkedHashMap<K, V> {
// 容量
private final int maxCapacity;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private final Lock lock = new ReentrantLock();
public FifoCache(int maxCapacity) {
super(maxCapacity, DEFAULT_LOAD_FACTOR, false);
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return this.size() > maxCapacity;
}
@Override
public V get(Object key) {
try {
lock.lock();
return super.get(key);
} finally {
lock.unlock();
}
}
@Override
public V put(K key, V value) {
try {
lock.lock();
return super.put(key, value);
} finally {
lock.unlock();
}
}
public int size() {
try {
lock.lock();
return super.size();
} finally {
lock.unlock();
}
}
public void clear() {
try {
lock.lock();
super.clear();
} finally {
lock.unlock();
}
}
}
# Belady现象 https://www.jianshu.com/p/bcf2efe81eed
LRU(Least Recently Used)
最近最少使用策略,根据元素最后一次被使用的时间戳,清除最远使用时间戳的元素来释放空间。
缺点:当缓存经历一次大批量的顺序读写,就会将原本比较有价值的缓存,替换出去,缓存中都会被新的、无用的缓存数据填满;
使用场景:热点访问数据使用
# 实现
#每次插入链表,插入链表一端(头部),当超过长度时,将另一端(尾部)清除掉;
#当访问元素时,需要将被访问的元素移动到头部,保证最近访问的元素始终处在不被淘汰的位置,而最久未被使用的元素则会被淘汰;
# LinkedHashMap实现
# 构造的 accessOrder 为true,表示每次访问元素时,将被访问的元素移动到tail位置
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxCapacity;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private final Lock lock = new ReentrantLock();
public LRUCache(int maxCapacity) {
super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return this.size() > maxCapacity;
}
@Override
public V get(Object key) {
try {
lock.lock();
return super.get(key);
} finally {
lock.unlock();
}
}
@Override
public V put(K key, V value) {
try {
lock.lock();
return super.put(key, value);
} finally {
lock.unlock();
}
}
public int size() {
try {
lock.lock();
return super.size();
} finally {
lock.unlock();
}
}
public void clear() {
try {
lock.lock();
super.clear();
} finally {
lock.unlock();
}
}
}
LFU(least frequently used)
最少使用策略,根据元素使用次数为依据,清除使用次数最少的元素。
使用场景:按照数据使用频率优先的场景
# 实现
# 使用小顶堆实现,每次插入堆,根据元素的hitCount(命中次数)来移动堆内元素;
# 每次访问数据,需要更新元素的命中次数,并且也要重新移动堆内元素。
# 双向链表 + HashMap 实现
# HashMap记录链表节点,每个链表节点也保存在一个以频率为key,value为双向链表的Mao中
# 双向链表记录元素访问频次,头尾节点,移除元素在频率最低的双向链表中
class LFUCache {
// 容量
final int maxCapacity;
// 元素长度
int size;
// 最小频率
int minFreq;
Map<Integer, Node> cache;
// 存储每个频次对应的双向链表
Map<Integer, DoublyLinkedList> freqMap;
public LFUCache(int capacity) {
cache = new HashMap<>(capacity);
freqMap = new HashMap<>();
this.maxCapacity = capacity;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
updateFreq(node);
return node.value;
}
public void put(int key, int value) {
if (maxCapacity == 0) {
return;
}
Node node = cache.get(key);
if (node != null) {
node.value = value;
updateFreq(node);
} else { // 不存在
if (size == maxCapacity) { // 只有添加的元素,原来不存在才涉及到 移除元素,否则修改原容器的元素
Node deadNode = removeNode();
cache.remove(deadNode.key);
size--;
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
addNode(newNode);
size++;
}
}
void updateFreq(Node node) {
// 从原freq对应的链表里移除, 并更新min
int freq = node.freq;
DoublyLinkedList linkedList = freqMap.get(freq);
linkedList.update(node);
if (freq == minFreq && linkedList.isEmpty()) {
// 最小频率 为 仍未 当前元素 频率
minFreq = freq + 1;
}
// 加入新freq对应的链表
node.freq++;
DoublyLinkedList newLinkedList = freqMap.get(freq + 1);
if (newLinkedList == null) {
newLinkedList = new DoublyLinkedList();
freqMap.put(freq + 1, newLinkedList);
}
newLinkedList.put(node);
}
/**
* 新增一个新节点
*
* @param node
*/
void addNode(Node node) {
DoublyLinkedList linkedList = freqMap.get(1);
if (linkedList == null) {
linkedList = new DoublyLinkedList();
freqMap.put(1, linkedList);
}
linkedList.put(node);
minFreq = 1;
}
/**
* 移除双向链表中的,最小访问次数中的一个元素
* <p>
* - 更新最小频率个数?
* 当得到当前元素为 最小元素 里唯一一个元素,则将 min 更新为当前元素 频率+1
* - 如何保证双向中元素顺序?
* 最小频率元素
* 按照插入顺序,遍历
*
* @return
*/
Node removeNode() {
DoublyLinkedList linkedList = freqMap.get(minFreq);
Node deadNode = linkedList.poll();
linkedList.take(deadNode);
return deadNode;
}
}
class Node {
Integer key;
Integer value;
Node last;
Node next;
int freq = 1;
Node() {
}
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
class DoublyLinkedList {
int size;
Node head;
Node tail;
DoublyLinkedList() {
head = new Node();
tail = new Node();
tail.last = head;
head.next = tail;
}
/**
* 每次插入都插到表头
* 1、头的原来后继节点的前驱为 node
* 2、node 的前驱 为 头
* node的后继 为 头的原理后继
* 3、头的后继为 node
*
* @param node
*/
void put(Node node) {
head.next.last = node;
node.next = head.next;
node.last = head;
head.next = node;
size++;
}
/**
* 每次移除 表尾部节点
*/
Node poll() {
if (size == 0) {
return null;
}
return tail.last;
}
void update(Node node) {
Node last = node.last;
Node next = node.next;
// 清空
node.last = null;
node.next = null;
last.next = next;
next.last = last;
size--;
}
void take(Node node) {
node.last.next = tail;
tail.last = node.last;
// 清空
node.last = null;
node.next = null;
size--;
}
boolean isEmpty() {
return size == 0;
}
}
其他淘汰策略:
02
—
缓存使用常见问题
缓存穿透:
描述:不过有时候,有可能存在缓存和数据库都没有的情况,而用户不断发起这种不合逻辑(多半是攻击)的请求,这会导致频繁的返回缓存和数据库,导致数据库压力过大;
解决:缓存和数据库中都不存在的数据,在缓存中设置一个默认的空值,并且设置过期时间,可以有效避免频繁发生缓存未命中,而访问数据库;
缓存击穿:
描述:一般指缓存中的热点数据,通常热点数据为了抗住大量的并发访问,不过,有可能这些热点key在失效的瞬间,导致大量请求访问到了数据库;
解决:使热点数据永不过期;设置查询数据库时增加互斥锁,尽量保护数据库不会受到,大的并发而压垮;
缓存雪崩:
描述:可能由于缓存失效,或者缓存大面积失效,导致并发压力都集中到数据库,而使数据库负载过高;
解决:通过互斥锁机制,保证真实到数据库访问量不会过高;丢掉一部分请求(如随机数访问);限流(如:令牌桶、漏洞桶等);缓存不过期或者避免缓存同时失效;缓存服务器灾备;
03
—
其他
应用场景
其他相关