从LRU开始学习缓存
从LRU开始学习缓存
缓存相信大家已经不陌生了，用个通俗的比方来说一下就是，如果把你的家比作一个仓库，那么你每天出
门时背的包就是你的缓存，你会把最近经常使用的东西放入到背包中，如果背包中没有你需要的，就只能回家
去拿了。
这篇文章从一道Leetcode的题目开始引入缓存的设计方式，然后介绍一些常见的缓存策略，最后简单介绍
一些经典的缓存系统和经常遇到的缓存问题
一、Leetcode 146 LRU缓存机制
1.题目描述
设计一个LRU缓存机制，支持获取数据get和写入数据put，具体含义如下：
获取数据get：如果key存在于缓存中，获取key的值value并且将这个数据放到数据结构的最前面，否则返回-1
写入数据put：如果key不存在，写入数据值，并且将新写入的数据放到数据结构的最前面；如果缓存的容量已
经达到了上限，应该在写入新数据之前删除最近最少使用的数据值，这也是LRU的核心思想,这里我们可以
将排在数据结构最后的位置的元素视为最近最少使用的元素
- get和put操作的时间复杂度要求是O（1）
如果还没有明白，可以看看这个缓存是怎么工作的
//假设这个缓存的容量为2
LRUCache cache = new LRUCache(2);
//先将cache理解成一个数组，左边是头部，右边是尾部，最近使用的排在对头，最久未使用的排在队尾
cache.put(1,1); //此时缓存中的数据是[(1,1)]
cache.put(2,2); //此时缓存中的数据是[(2,2),(1,1)] 新加入的数据应该放在头部
cache.get(1); //查询key为1的值，返回1，最近访问了键1，移动到头部,缓存中的数据是[(1,1),(2,2)]
cache.put(3,3) //缓存已满，出去尾部元素(2,2)，[(3,3),(1,1)]
cache.get(2) //未找到该元素，返回-1
2.解题思路
要想在O(1)的时间复杂度内完成上述操作，存储缓存的数据结构应该具备这样的特点：查找是O(1)、插入
是O（1）、删除是O（1）、而且元素之间还要有一定的顺序；查找O(1)和删除O(1)这个比较好办，哈希表就
可以满足了，但是它没有顺序啊，实际在应用的时候需要将数据插入头部和从尾部进行删除，这是哈希表无法
做到的；这个时候就轮到链表上场了，链表是有顺序的，只需将哈希表和链表结合即可
但是这个时候又有问题了，链表是使用单向链表还是双向链表呢？我们可以从删除操作的执行过程来分析
单向链表要想删除一个节点，必须要知道它的前驱节点，也就是多用一个指针，你可以通过哈希表来找到当前
节点，但是如何找到前一个节点，但是如何找找到前一个节点呢？所以只能使用双向链表，最终我们将这种数
剧结构称为哈希链表，话不多说，赶紧上图
3.缓存使用的数据结构
Python和Java都有内置的哈希链表和类似LRU功能的库函数，比如Java中的LinkedHashMap，关于
关于它在容器数据结构这篇文章中有介绍；Python中可以使用OrderedDict实现LRU，但是推荐使用一个
装饰器functools.lru_cache。但是我们还是自己设计一个框架比较好
//双向链表节点类型
class Node{
public int key,val;
public Node next,prev;
public Node(int k,int v){
this.key = k;
this.val = v;
}
}
//双向链表节点的实现
class DoubleList{
//常用的API操作
public void addFirst(Node x); //在链表的头部添加节点 O(1)
public void remove(Node x); //移除链表中的节点 O(1)
public Node removeLast(); //删除链表中的最后一个节点 O(1)
public int size(); //返回链表的长度 O(1)
}
有了双向链表我们就可以加入HashMap了，这里给出先给出一个伪算法，再写出代码
HashMap<Integer,Node> map; //将哈希表中的key映射成双向链表的一个节点
DoubleList cache;
//get操作
int get(int key){
if(key 不存在) return -1；
else:将键值对移至开头 返回value
}
//put操作
void put(int key,int val){
Node x = new Node(key,val);
if (key已经存在) 将原先的数据删除 再将新节点插入头部
else:
if (缓存已满) 删除链表中的最后一个数据 删除map中映射到该数据中的键
else:将新节点插入开头，同时新建映射
}
4.代码实现
（1）使用伪算法的代码实现，自己造轮子
class Node{
public int key,val;
public Node(int k,int v){
this.key = k;
this.val = v;
}
}
class LRUCache{
private HashMap<Integer,Node> map;
private LinkedList<Node> cache;
private int cap; //缓存最大容量
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<>();
cache = new LinkedList<>();
}
public int get(int key) {
if(!map.containsKey(key)) return -1;
int val = map.get(key).val;
put(key,val);
return val;
}
public void put(int key, int value) {
Node node = new Node(key,value);
if(map.containsKey(key)){
cache.remove(map.get(key));
cache.addFirst(node);
map.put(key,node);
}else{
if(cap == cache.size()){
Node last = cache.removeLast();
map.remove(last.key);
}
cache.addFirst(node);
map.put(key,node);
}
}
}
（2）使用Java中的LinkedHashMap实现
Java中的LinkedHashMap已经实现了LRU缓存淘汰算法，具体使用请看代码
class LRUCache extends LinkedHashMap<Integer,Integer>{ //直接继承LinkedHashMap
private int capacity;
public LRUCache(int capacity) {
super(capacity,0.75F,true); //true表示按照使用时间排序
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key,-1); //存在就返回value,否则返回-1
}
public void put(int key, int value) {
super.put(key,value);
}
//如果map里面的元素个数大于缓存最大容量时，删除链表的顶端元素;需要重写removeEldestEntry方法
@Override
protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
//参数eldest 在映射中最早插入的条目
return size() > capacity; //方法返回true时将会删除eldest
}
}
(3) 使用Python的OrderedDict
有关OrderedDict的常见操作请查看Python高级容器数据结构这篇文章，同时也有介绍lru_cache的使用
from collections import OrderedDict
class LRUCache(OrderedDict): #继承OrderedDict
def __init__(self, capacity: int):
self.capacity = capacity
#这里我们将OrderedDict中尾部元素当做最近使用的,头部元素是最近最少使用的
def get(self, key: int) -> int:
if key not in self:
return -1
self.move_to_end(key) #将指定的键值对移至尾部
return self[key]
def put(self, key: int, value: int) -> None:
if key in self:
self.move_to_end(key) #将指定的键值对移至尾部
self[key] = value
if len(self) > self.capacity: #超出容量删除头部元素
self.popitem(last = False)
二、常见的缓存策略
从上面的几道题目就可以看到，缓存的容量是有限的，我们不会将所有的数据都缓存起来，必须依赖一定
的规则淘汰掉一部分数据，这个规则就是缓存淘汰策略，常见的缓存淘汰策略有如下几种：
- FIFO：First In First Out是最简单的算法，原理是：如果一个数据最先进入缓存中，则应该最早被淘汰掉，把缓
存中的数据看成一个队列，最先加入的数据位于队列的头部，最后加入的数据位于队列的尾部；当缓存空间
不足时需要执行缓存淘汰时，从队列的头部开始淘汰
- LRU Least Recently Used，最近最少被使用，主要思想如果数据最近被访问过，它在未来也极有可能被访问。
把缓存看做一个队列，访问一个数据时，如果缓存中不存在，则插入队列尾部；如果缓存中存在，则把该数
剧移动到队列尾部。当执行淘汰操作时，同样从队列的头部开始淘汰
- LFU Least Frequently Used ，最不经常使用，主要的思想就是如果一个数据在最近的一段时间内使用的次数
最小，那么在未来的一段时间内被使用的可能性也是比较小的，它主要是记录数据访问的次数，当需要进行
淘汰操作时，淘汰掉访问次数最少的数据
其他淘汰算法：
- Two Queues：同时采用FIFO和LRU两个队列，首次访问数据时加入到FIFO队列中，如果数据在FIFO队列移除
之前被再次访问，数据会被移动到LRU队列中
- LRU-K：LRU的增强版算法，在LRU维护队列的基础上，再新增一个队列维护数据访问的次数，由原来被访问
一次被添加到缓存中改成访问K次才会被加入缓存
- ARC：自适应缓存替换，这个缓存算法同时跟踪记录LFU和LRU，以及驱逐缓存条目，来获得可用缓存的最佳
实践
- MRU：最近最常使用算法，它最先移除最近最常被使用的条目，比较擅长处理一个条目越久，越容易被访问的
在上面的题目中我们对LRU进行了实现，这里我们使用Java中的LinkedHashMap对FIFO进行实现
//一个固定大小的FIFO替换策略的缓存实现
class FIFOCache<K,V> extends LinkedHashMap<K,V>{
private final int cacheSize;
public FIFOCache(int cacheSize){
this.cacheSize = cacheSize;
}
//重写removeEldestEntry函数，当Entry个数超过cacheSize时，删除最老的Entry
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
return size() > cacheSize;
}
}
三、典型的缓存系统
开源的缓存系统或者框架是比较多的，这里简单介绍几种常用的
- Redis：一个底层使用C语言编写的key-value存储的数据库，经常被用作缓存系统。访问速度比较快，支持
分布式分片集群。它是一个单核的缓存服务，单点的情况下更适合少量用户多次访问的场景
- Memcached：一种基于内存的key-value存储，用于存储小块的任意数据；它是一个多核的缓存服务，更加
适用于多用户并发访问次数比较少的应用场景
- Ehcache：一个Java实现的开源分布式缓存框架，它可以减轻数据库的负载，让数据保存在不同服务器的
内存中，需要的时候可以进行快速存取；支持分级缓存
其他的缓存框架像OSCache、J2Cache、JetCache等，都是各有优点，不一一介绍了
四、常见的缓存问题
1.有关缓存的名词
缓存是一种数据模型，它有自己的一些特征名词
- 命中率：返回的正确的结果数/请求的缓存次数，用来判断缓存有效性的重要指标，命中率越高，缓存的使用率
也就越高；缓存出现的出现的主要问题都会导致其命中率大幅降低
- 缓存最大空间：就是缓存的容量，如果缓存中的元素数量超过这个值，便会触发缓存清空策略，合理的缓存清空
策略可以在一定程度上提高缓存的命中率
- 缓存清空策略：也就是上面我们介绍的那几种缓存策略，当然除了一些专用算法，还有一些简单的策略：比如
根据过期时间清理过期时间最长的元素、清理最近要过期的元素、随机清理、根据元素内容长短清理
2.缓存的各种问题
（1）缓存穿透
缓存穿透是指用户查询数据时，数据库中都不存在，缓存中肯定不会存在，也就是查询不到；所以请求就
相当于直接到达了数据库，缓存没有起作用。这样的请求较多时，数据库就会直接宕掉
解决方法：
采用布隆过滤器，虽然它对于元素存在有一定的误判率，但是判断元素不存在是一定正确的
如果一个数据查询结果为空，仍然将这个结果进行缓存，并且设置较短的过期时间
（2）缓存雪崩
缓存雪崩一般会在这样的情况下出现，原有的缓存采用了相同的过期时间，在同一时刻出现大面积的缓存
过期，原本访问缓存的请求都会去查询数据库了，可能会造成数据库宕机
解决方法：
将缓存的失效时间分开，比如在设置缓存时间时可以加上一定范围内的随机值
采用加锁或者队列的方式保证不会有大量的线程对数据库进行一次性读写
（3）缓存的数据一致性问题
数据库中的数据和缓存数据是不可能一致的，使用缓存不能保证数据的强一致性，只能保证数据最终一致
性，因为读和写的操作都是并发的，可能会产生冲突
解决方法：
使用锁，但是会严重影响性能，可以进行优化
将缓存分成多个分片，每个分片分配一个锁，如果在不同的分片中更新缓存，不会相互等到
使用提交日志，可以将改动存储到日志中，不立即更新，然后一些后台进程将异步执行所有日志