redis-过期策略和内存淘汰机制

redis内存管理

在 redis 中,允许用户设置最大使用内存大小

1
server.maxmemory

默认为0,没有指定最大缓存,如果有新的数据添加,超过最大内存,则会使redis崩溃,所以一定要设置。

当内存达到上限时,Redis 将使用指定的策略清除其他键值。
如果 Redis 无法清除(或者策略不允许清除键值),将对占用内存的命令报错,但对只读的命令正常服务。

从Redis 5开始,默认情况下,副本将忽略其maxmemory设置(除非在故障转移后或手动将其提升为主设备)。 这意味着key的清除将由主服务器处理,当主服务器中的key清除时,将DEL命令发送到副本。此行为可确保主服务器和副本服务器保持一致,但是如果您的副本服务器是可写的,或者您希望副本服务器具有不同的内存设置,并且您确定对副本服务器执行的所有写操作都是幂等的,然后你可以改变这个默认值(但一定要明白你在做什么)。

1
replica-ignore-maxmemory yes

问题引出

在使用redis的过程中,可能会如下的两个问题:

  1. 往redis写入的数据为什么没了?
  2. 数据明明过期了,为什么还占着内存?

这都是有redis的过期策略内存淘汰策略来决定的。

redis过期策略

redis的过期策略是:定期删除+惰性删除

定期删除

所谓定期删除,指的是redis默认每隔100ms就随机抽取一些设置了过期时间的key,检查其是否过期,如果过期就删除。

假设 redis 里放了 10w 个 key,都设置了过期时间,你每隔几百毫秒,就检查 10w 个 key,那 redis 基本上就死了,cpu 负载会很高的,消耗在你的检查过期 key 上了。注意,这里可不是每隔 100ms 就遍历所有的设置过期时间的 key,那样就是一场性能上的灾难。实际上 redis 是每隔 100ms 随机抽取一些 key 来检查和删除的。

问题是,定期删除可能会导致很多过期 key 到了时间并没有被删除掉,那咋整呢?

答案是惰性删除

惰性删除

获取 key 的时候,如果此时 key 已经过期,就删除,不会返回任何东西。

问题是,如果定期删除漏掉了很多过期 key,然后你也没及时去查,也就没走惰性删除,此时会怎么样?如果大量过期 key 堆积在内存里,导致 redis 内存块耗尽了,咋整?

答案是内存淘汰机制

内存淘汰机制

有如下内存淘汰机制:

  • noeviction: 当内存不足以容纳新写入数据时,新写入操作会报错,这个一般没人用(默认值)。

  • allkeys-lru:当内存不足以容纳新写入数据时,在键空间中,移除最近最少使用的 key(这个是最常用的)。

  • allkeys-random:当内存不足以容纳新写入数据时,在键空间中,随机移除某个 key,这个一般没人用。

  • volatile-lru:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,移除最近最少使用的 key(这个一般不太合适)。

  • volatile-random:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,随机移除某个 key。

  • volatile-ttl:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,有更早过期时间的 key 优先移除。

简单来说,volatile和allkeys规定了是对已设置过期时间的数据集淘汰数据还是从全部数据集淘汰数据,后面的lru、ttl以及random是三种不同的淘汰策略,再加上一种no-enviction永不回收的策略。

使用策略规则:

  1. 如果数据呈现幂律分布,也就是一部分数据访问频率高,一部分数据访问频率低,则使用allkeys-lru
  2. 如果数据呈现平等分布,也就是所有的数据访问频率都相同,则使用allkeys-random

LRU算法实现

核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

设计并实现了一个最近最少使用(LRU)缓存的数据结构,它应该支持以下操作:get和set。
get(key)——如果键存在于缓存中,则获得键值(总是正数),否则返回-1。
set(key, value)——如果键不存在,则设置或插入值。当缓存达到其容量时,应在插入新项之前使最近最少使用的项无效。

分析:LRU缓存可使用一个HashMap和双向链表实现。HashMap,使得get的时间是O(1);双向链表使节点添加/删除操作O(1),也可以使用LinkedHashMap来实现。


在集合章节学过LinkedHashMap:集合-LinkedHashMap

LinkedHashMap有两种数据存储的顺序,插入顺序和访问顺序。

可以通过设置 accessOrder 属性,来进行设置。设置为 false 表示按插入顺序进行存储,设置为true表示按照访问顺序进行存储(首次插入还是尾插)。

LinkedHashMap提供了用于设置 accessOrder 的构造器方法:

1
2
3
4
5
6
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

其中关于使用的例子请参看 LinkedHashMap博文。

下面来看看如何使用 LinkedHashMap 实现LRU缓存。

LinkedHashMap实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int CACHE_SIZE;

/**
* 传递进来最多能缓存多少数据
*
* @param cacheSize 缓存大小
*/
public LRUCache(int cacheSize) {
// true 表示让 linkedHashMap 按照访问顺序来进行排序,最近访问的放在尾部,最老访问的放在头部。
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
CACHE_SIZE = cacheSize;
}

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当 map中的数据量大于指定的缓存个数的时候,就自动删除最老的数据(删除的链表头部的节点)。
return size() > CACHE_SIZE;
}
}

关键的两个点:

  1. LinkedHashMap构造器

    1
    2
    3
    4
    5
    6
    7
    //如果accessOrder为true的话,则会把访问过的元素放在链表后面,放置顺序是访问的顺序
    public LinkedHashMap(int initialCapacity,
    float loadFactor,
    boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
    }
  2. 重写removeEldestEntry方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //removeEldestEntry方法会在afterNodeInsertion中调用
    //在每次put操作末尾会调用afterNodeInsertion方法。可以利用此方法删除链表的顶端元素。
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    removeNode(hash(key), key, null, false, true);
    }
    }

HashMap和双向链表实现

定义双向链表节点:

1
2
3
4
5
6
7
8
9
10
11
class Node{
int key;
int value;
Node pre;
Node next;

public Node(int key, int value){
this.key = key;
this.value = value;
}
}
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
public class LRUCache {
int capacity;
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
Node head=null;
Node end=null;

public LRUCache(int capacity) {
this.capacity = capacity;
}

public int get(int key) {
if(map.containsKey(key)){
Node n = map.get(key);
remove(n);
setHead(n);
return n.value;
}

return -1;
}

public void remove(Node n){
if(n.pre!=null){
n.pre.next = n.next;
}else{
head = n.next;
}

if(n.next!=null){
n.next.pre = n.pre;
}else{
end = n.pre;
}

}

public void setHead(Node n){
n.next = head;
n.pre = null;

if(head!=null)
head.pre = n;

head = n;

if(end ==null)
end = head;
}

public void set(int key, int value) {
if(map.containsKey(key)){
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old);
}else{
Node created = new Node(key, value);
if(map.size()>=capacity){
map.remove(end.key);
remove(end);
setHead(created);

}else{
setHead(created);
}

map.put(key, created);
}
}
}

文章出处

jsbintask的简书

Hacker_Jp的简书

0%