【过期策略和内存淘汰机制】三种过期策略、八种淘汰机制、手写lru算法_Redis04

1、redis过期策略

前言

redis默认使用惰性删除+定期删除。（其中定期删除是每隔 100ms就随机抽取一些设置了过期时间的key）

1. 定时删除流程是：

• 时时刻刻遍历所有被设置了生存时间的key，来检测数据是否已经到达过期时间，然后对它进行删除。
• 这会产生大量的性能消耗，同时也会影响数据的读取操作。

2. 惰性删除流程是：

• 在进行get或setnx等操作时，先检查key是否过期，
• 若过期，删除key，然后执行相应操作；
• 若没过期，直接执行相应操作

3. 定期删除流程是：

• for（遍历每个数据库（就是redis.conf中配置的"database"数量，默认为16））
  • for（检查当前库中的指定个数个key（默认是每个库检查20个key，注意相当于该循环执行20次，循环体时下边的描述））{
    • 如果当前库中没有一个key设置了过期时间，直接执行下一个库的遍历
    • 随机获取一个设置了过期时间的key，检查该key是否过期，如果过期，删除key
    • 判断定期删除操作是否已经达到指定时长，若已经达到，直接退出定期删除。
  • }

4. 对比三种不同的删除策略：

• 定时删除 - 总结：对CPU不友好，用处理器性能换取存储空间（拿时间换空间）
• 惰性删除 - 总结：对memory不友好，用存储空间换取处理器性能（拿空间换时间）
• 上面两种方案都走极端 - 定期删除： 定期抽样key，判断是否过期（存在漏网之鱼）

上述步骤都过堂了，还有漏洞吗？

• 定期删除时，从来没有被抽查到
• 惰性删除时，也从来没有被点中使用过
• 上述2步骤====>大量过期的key堆积在内存中，导致redis内存空间紧张或者很快耗尽
• 我们看到，通过过期删除策略，对于某些永远使用不到的键，并且多次定期删除也没选定到并删除，那么这些键同样会一直驻留在内存中，又或者在Redis中存入了大量的键，这些操作可能会导致Redis内存不够用，这时候就需要Redis的内存淘汰策略了。

---

2、Redis内存淘汰策略登场（Redis 6.0.8版本）

1. 总结一下：

• Redis过期删除策略是采用惰性删除和定期删除这两种方式组合进行的。
• 惰性删除存在从来没有被点中使用过。
• 定期删除存在从来没有被抽查到过。
• Redis是部署在物理机上的，内存不可能无限扩充的，当内存达到我们设定的界限后，便自动触发Redis内存淘汰策略（默认是：noeviction），而具体的策略方式要根据实际业务情况进行选取。

2. 内存淘汰触发时机：

在配置文件redis.conf 中，可以通过参数 maxmemory 来设定最大内存。
如果不设定该参数默认是无限制的，但是通常会设定其为物理内存的四分之三。

• 当现有内存大于 maxmemory 时，便会触发redis主动淘汰内存方式，通过设置 maxmemory-policy来确定内存淘汰策略；
  • noeviction：不会驱逐任何key
  • volatile-lfu：对所有设置了过期时间的key使用LFU算法进行删除
  • volatile-Iru：对所有设置了过期时间的key使用LRU算法进行删除
  • volatile-random：对所有设置了过期时间的key随机删除
  • volatile-ttl：删除马上要过期的key
  • allkeys-lfu：对所有key使用LFU算法进行删除
  • allkeys-Iru：对所有key使用LRU算法进行删除
  • allkeys-random：对所有key随机删除

上面总结（2*4得8）

• 2个维度
  • 过期键中筛选
  • 所有键中筛选
• 4个方面
  • LRU
  • LFU
  • random
  • ttl（Time To Live）
• 8个选项
  • noeviction。（都不删）
  • volatile-lfu、volatile-Iru、volatile-random、volatile-ttl。（设置了过期时间）
  • allkeys-lfu、allkeys-Iru、allkeys-random。（全部key）

---

3、内存淘汰策略算法lru

1）概念：

• 选择最近最久未使用的数据予以淘汰。

2）实现思路：

• 总体思路：所谓缓存，必须要有读+写两个操作，按照命中率的思路考虑，写操作+读操作时间复杂度都需要为O(1)
• 基本要求：
  • 必须要有顺序之分，一区分最近使用的和很久没有使用的数据排序。
  • 写和读操作一次搞定。
  • 如果容量(坑位)满了要删除最不常用的数据，每次新访问还要把新的数据插入到队头(按照业务你自己设定左右那一边是队头)
• 查找快、插入快、删除快，且还需要先后排序---------->什么样的数据结构可以满足这个问题？
  • 你是否可以在O(1)时间复杂度内完成这两种操作？
  • 如果一次就可以找到，你觉得什么数据结构最合适？
    • 答案：LRU的算法核心是哈希链表
  • 编码手写如何实现LRU?
    • 本质就是HashMap + DoubleLinkedList
    • 时间复杂度是O(1)，哈希表+双向链表的结合体

3）现成的LinkedHashMap完成lru算法

import java.util.LinkedHashMap;

public class LRUCache {
	
	private LinkedHashMap<Integer, Integer> cache;
	
    public LRUCache(int capacity) {
        cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
        	
			  	private static final long serialVersionUID = 1L;
			
             /**
             * 此方法为钩子方法，map插入元素时会调用此方法
             * 此方法返回true则证明删除最老的因子
             *
             * 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
             * @param eldest
             * @return
             */
            @Override
            protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest){
               return size() > capacity;
            }
        	
        };
    }
    
    public int get(int key) {
    	return cache.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        cache.put(key, value);
    }
    
    @Override
    public String toString() {
    	return cache.toString();
    }
    
}
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

4）手写一个LRU

• 哈希表 + 双向链表

  //双向链表的节点对象
	class Node<K, V>{
		K key;
		V value;
		Node<K, V> prev;
		Node<K, V> next;
		
		public Node() {
			this.prev = this.next = null;
		}
		public Node(K key, V value) {
			super();
			this.key = key;
			this.value = value;
		}
	}
  
	-------------------	-------------------	-------------------	-------------------
    //新的插入头部，旧的从尾部移除
    //有两个属性链表的头和尾，通过头或者尾就能找到这个链表的其他成员（prev，next）
    //
	class DoublyLinkedList<K, V>{
		Node<K, V> head;
		Node<K, V> tail;
		
		public DoublyLinkedList() {
            //头尾哨兵节点
			this.head = new Node<K, V>();
			this.tail = new Node<K, V>();
			this.head.next = this.tail;
			this.tail.prev = this.head;
		}
    //node
		//star-aa-bb-cc-end
    
		public void addHead(Node<K, V> node) {
			node.next = this.head.next;
			node.prev = this.head;
			this.head.next.prev = node;
			this.head.next = node;
		}
		
		public void removeNode(Node<K, V> node) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
			node.prev = null;
			node.next = null;

		}
		
		public Node<K, V> getLast() {
			if(this.tail.prev == this.head)
				return null;
			return this.tail.prev;
		}

	}

class LRUCache2{
	private int cacheSize;//缓存的大小
	private Map<Integer, Node<Integer, Integer>> map;//map负责保存节点
	private DoublyLinkedList<Integer, Integer> doublyLinkedList;//链表负责节点顺序、删除节点等
	
	//redis确定缓存大小的有参构造方法
	public LRUCache2(int cacheSize) {
		this.cacheSize = cacheSize;
		map = new HashMap<>();
		doublyLinkedList = new DoublyLinkedList<>();
	}
  
	//redis缓存的获取get方法
	public int get(int key) {
		if(!map.containsKey(key)) {
			return -1;
		}
		
		Node<Integer, Integer> node = map.get(key);
        
        //更新节点位置，将节点移置链表头
		doublyLinkedList.removeNode(node);
		doublyLinkedList.addHead(node);
		
		return node.value;
	}
  
	//redis缓存的新增put方法
	public void put(int key, int value) {
		
		if(map.containsKey(key)) {
			
			Node<Integer, Integer> node = map.get(key);
			node.value = value;
			map.put(key, node);
			
            
			doublyLinkedList.removeNode(node);
			doublyLinkedList.addHead(node);
		}else {
			
			if(map.size() == cacheSize) {//已达到最大容量了，把旧的移除，让新的进来
				Node<Integer, Integer> lastNode = doublyLinkedList.getLast();
				map.remove(lastNode.key);//node.key主要用处，反向连接map
				doublyLinkedList.removeNode(lastNode);
			}
			
			Node<Integer, Integer> newNode = new Node<>(key, value);
			map.put(key, newNode);
			doublyLinkedList.addHead(newNode);
		}
	}	
}

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
105
106
107
108
109
110
111
112

5）实现方式：

• 1.用LinkedHashMap完成lru算法。
• 2.手写lru的get()，save()思路：HashMap + DoubleLinkedList

  • save(key， value)：首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。

  • get(key)：通过 HashMap 找到 LRU 链表节点，把节点插入到队头，返回缓存的值。
    

  • 上面展示了，预设大小是 3 的，LRU存储的在存储和访问过程中的变化。

  • 为了简化图复杂度，图中没有展示 HashMap部分的变化，仅仅演示了上图 LRU 双向链表的变化。

  • 我们对这个LRU缓存的操作序列如下：

    save(“key1”， 7);
    
    save(“key2”， 0);
    
    save(“key3”， 1);
    
    save(“key4”， 2);
    
    get(“key2”);
    
    save(“key5”， 3);
    
    get(“key2”);
    
    save(“key6”， 4);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15