0%

redis的过期删除策略及淘汰机制

redis的过期删除策略

​ redis是以K-V键值对存放的。如果给key设置了存活时间,假设是2分钟,如果2分钟以后,redis是怎么删除这些key的。redis的过期删除策略有两种。

​ 一种是惰性删除,一种是定期删除。

惰性删除

​ 见名知义,当我们取出这些key的时候再进行删除。当我们使用到这些key时,会对key进行检查,是否已经过期,如果过期了就会进行删除。这种删除策略对CPU是比较友好的,因为不需要专门来处理过期的key。但是这样也会导致由于使用到才会检查并删除,所以会有很多过期的key还存放在内存中,比较耗内存。

定期删除

​ 定期删除是每隔一段时间就会执行一次对过期key的删除。不是对所有的key,是抽取一部分的key进行删除。并且redis底层会限制删除操作的时长,以免对CPU造成太大负担的同时,也可以缓解内存空间的压力。


​ 但是,以上两种方法都有弊端,惰性删除会导致内存空间浪费,当积压到一定量之后,很有可能会内存溢出。而定期删除虽然可以解决内存问题,但是由于定期的抽取也会导致有大量的key遗留在内存空间中,内存溢出也只是时间问题。为了解决这一问题,redis有一个内存淘汰机制。

内存淘汰机制

​ 打开redis的配置文件 redis.conf, 可以看到有8种内存淘汰机制。在配置文件中的975行。

1
2
3
4
5
6
7
8
volatile-lru -> Evict using approximated LRU, only keys with an expire set #从已经过期了的key中挑选最近最少使用的键进行淘汰
allkeys-lru -> Evict any key using approximated LRU #从所有key中挑选最近最少使用的键进行淘汰
volatile-lfu -> Evict using approximated LFU, only keys with an expire set #从已经过期了的key中挑选使用最不频繁的(即不经常使用的)进行淘汰
allkeys-lfu -> Evict any key using approximated LFU #从所有key中挑选使用最不频繁的键进行淘汰
volatile-random # 从已经过期的key中随机淘汰
allkeys-random # 从所有key中随机淘汰
volatile-ttl -> remove the key with nearest expire time # 删除过期时间最近的key
noeviction -> don't evict anything,just return error on wirte operations. #什么都不做,直接返回异常

​ 一般使用比较多的是LRU,对最近最少使用的key进行淘汰。使用allkeys-lru较多。通过内存淘汰机制可以很好的解决内存问题以及CPU问题。那么LRU是一种什么算法呢?

LRU算法

​ LRU前面提到过是redis内存淘汰的一种方式,即对最近最少使用的key进行淘汰。怎么实现?

​ 我们可以通过一个node节点来存放K-V键值对。表示一个一个的key以及数据。并把这些node通过双向链表的方式串联起来。怎么来得到这些key-value键值对呢? 我们可以使用一个hashmap来存储。这样我们可以根据双向链表的有序性,将最近使用的放在头部。接下来就是模拟LRU。当我们访问某一个key时,我们可以将这个key所对应的node从原先位置删除,并且将这个node添加到链表的头部。当我们添加node时,如果key存在,则更新数据,并把这个node放到链表头部,如果不存在,则判断是否已经达到内存容量,如果没有,则添加到头部,如果满了,则删除尾部元素。因为链表尾部的就是最近最少使用的。

​ 根据以上的分析,我们可以得到,我们需要一个由双向链表实现的map,其实jdk中已经有这样的结构了,那就是LinkedHashMap。LinkedHashMap 通过特有底层双向链表的支持,使得LinkedHashMap可以保存元素之间的顺序,例如插入顺序或者访问顺序。并且在其类的注释中可以看到这么一行话。使用LinkedHashMap是十分适合左LRU算法的。

1
2
3
4
5
public class LinkedHashMap {
/**
* This kind of map is well-suited to building LRU caches.
*/
}

LRU算法实现 demo

​ 这里不使用LinkedHashMap来创建,自己来构建双向链表来创建,具体如下

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//这里我们先创建一个node类,来封装redis中的key-value键值对
class Node<K,V> {
K key; //redis中的key
V value; // value
Node<K,V> next; //指向下一个节点的指针
Node<K,V> prev; //指向前一个节点的指针

//构造器
public Node(K key, V value) {
//初始化
this.key = key;
this.value = value;
next = prev = null;
}

public Node() {
next = prev = null;
}
}

//在构建一个双向链表,用来保证顺序
class DoubleLinkedList<K,V> {
Node<K,V> head; //双向链表的头结点
Node<K,V> tail; //双向链表的尾节点

//构造器初始化
public DoubleLinkedList() {
head = new Node<>();
tail = new Node<>();
head.next = tail;
tail.prev = head;
}

//因为规定链表头部的节点是最近最多使用的,所以我们编写一个方法可以在头部添加节点
public void addHead(Node<K,V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}

//删除节点,如果访问一个节点后,我们需要把这个被访问的节点添加到头部,并且删除该节点的原有位置
public void removeNode(Node<K,V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
}

//当添加节点时,当容量达到最大值时,需要删除最后一个节点,因此,我们编写方法获取最后一个节点
public Node<K,V> getLastNode() {
return this.tail.prev;
}
}

//LRU算法
class LRUDemo {
private int capacity; //容量
private Map<Integer, Node<Integer,Integer>> map; //存放节点
private DoubleLinkedList<Integer,Integer> list; //串联节点

//构造器
public LRUDemo(int capacity) {
this.capacity = capacity;
map = new HashMap<Integer, Node<Integer,Integer>>();
list = new DoubleLinkedList<Integer,Integer>();
}

//获取某一key对应的value
public int get(int key) {
//先判断是否存在这个key
if (! map.containsKey(key)) return -1;
Node<Integer,Integer> node = map.get(key);
//得到这个节点之后,如前面所说,删除它,添加到头部
list.remove(node);
list.addHead(node);
return node.value;
}

//添加节点
public void put(int key, int value) {
//同样,判断添加的key是否已经存在
if (map.containsKey(key)) { //如果存在
Node<Integer> node = map.get(key);
node.value = value;
map.put(key,node);
list.removeNode(node);
list.addHead(node);
} else {
//判断此时是否容量满了
if (map.size() == capacity) {
//得到最后一个节点,并删除
Node<Integer,Integer> lastNode = list.getLast();
list.removeNode(lastNode);

}

//封装成node并添加到最前面
Node<Integer,Integer> newNode = new Node<>(key,value);
map.put(key,node);
list.addHead(newNode);
}
}
}

​ 这只是一个简单的demo,有很多不同的方式实现,怕自己忘记,所以我记录一下。


over

-------------本文结束感谢您的阅读-------------