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 # 删除过期时间最近的keynoeviction -> 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 { }
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 class Node <K ,V > { K key; V 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; } } 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>(); } public int get (int 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) { 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<Integer,Integer> newNode = new Node<>(key,value); map.put(key,node); list.addHead(newNode); } } }
这只是一个简单的demo,有很多不同的方式实现,怕自己忘记,所以我记录一下。
over