redis_内存淘汰策略
介绍
Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时，怎么处理需要新写入且需要申请额外空间的数据。
全局的键空间选择性移除
noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。
allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。（这个是最常用的）
allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。
设置过期时间的键空间选择性移除
volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。
volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。
volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。
LRU算法
LRU（Least Recently Used）是一种常见的页面置换算法，在计算中，所有的文件操作都要放在内存中进行，然而计算机内存大小是固定的，所以我们不可能把所有的文件都加载到内存，因此我们需要制定一种策略对加入到内存中的文件进项选择。
常见的页面置换算法有如下几种：
- LRU 最近最久未使用
- FIFO 先进先出置换算法 类似队列
- OPT 最佳置换算法 （理想中存在的）
- NRU Clock置换算法
- LFU 最少使用置换算法
- PBA 页面缓冲算法
原理
当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。
正如上面图所表示的意思：每次访问的数据都会放在栈顶，当访问的数据不在内存中，且栈内数据存储满了，我们就要选择移除栈底的元素，因为在栈底部的数据访问的频率是比较低的。所以要将其淘汰。
实现
如何来设计一款LRU算法呢？对于这种类似序列的结构我们一般可以选择链表或者是数组来构建。
差异对比：
数组 查询比较快，但是对于增删来说是一个不是一个好的选择
链表 查询比较慢，但是对于增删来说十分方便O(1)时间复杂度内搞定
有没有办法既能够让其搜索快，又能够快速进行增删操作。
我们可以选择链表+hash表，hash表的搜索可以达到0(1)时间复杂度，这样就完美的解决我们搜索时间慢的问题了
- 基于链表+Hash表
Hash表，在Java中HashMap是我们的不二选择
链表，Node一个双向链表的实现，Node中存放的是数结构如下：
构建双向链表节点ListNode，应包含key,value,prev,next这几个基本属性
对于Cache对象来说，我们需要规定缓存的容量，所以在初始化时，设置容量大小，然后实例化双向链表的head,tail，并让head.next->tail tail.prev->head，这样我们的双向链表构建完成
对于get操作,我们首先查阅hashmap，如果存在的话，直接将Node从当前位置移除，然后插入到链表的首部，在链表中实现删除直接让node的前驱节点指向后继节点，很方便.如果不存在，那么直接返回Null
对于put操作，比较麻烦。
[图片上传失败...(image-f70fab-1644827709973)]
代码实现
/**
* @description: redis内存淘汰策略算法LRU
* @author: li
*/
public class LRUCache<V> {
/**容量*/
private int capacity = 1024;
/**Node 记录表 相当于缓存记录表*/
private Map<String, ListNode<String, V>> table = new ConcurrentHashMap<>();
/**双向链头部*/
private ListNode<String, V> head;
/**双向链表尾部*/
private ListNode<String, V> tail;
/**有参构造函数*/
public LRUCache(int capacity) {
this();
this.capacity = capacity;
}
public LRUCache() {
head = new ListNode<>();
tail = new ListNode<>();
head.next = tail;
head.prev = null;
tail.prev = head;
tail.next = null;
}
/**
* get操作
* 1. 先判断访问的key是否在map记录表中，如果存在，把之前存在链表给删除掉，然后把新的key插入到最前面。反之，返回null
* */
public V get(String key) {
ListNode<String, V> cur_node = table.get(key);
if(cur_node == null) {//不在缓存里
return null;
}
cur_node.prev.next = cur_node.next;
cur_node.next.prev = cur_node.prev;
//当前节点移动到链表首位
cur_node.prev = head;
head.next = cur_node;
cur_node.next = head.next;
head.next.prev = cur_node;
//记录hash表
table.put(key, cur_node);
return cur_node.value;
}
/**
* put操作
* 1. 先判断新增的key是否在hash表中，如果存在 把新增的node插入到链表的首位，同时记录hash表
* 2. 如果不存在，并且容量够，则也需要新增的key的插入到两边首位，同时记录hash表
* 3. 如果不存在，并且容量也不够，则移除尾部节点，把新的节点插入到首位，同时记录hash表
* */
public void put(String key, V value) {
ListNode<String, V> cur_node = table.get(key);
if(cur_node == null) {
if(table.size() == this.capacity) {
//把尾部的节点删除掉
table.remove(tail.prev.key);
tail.prev = tail.next;
tail.next = null;
tail = tail.prev;
}
cur_node = new ListNode<>();
cur_node.key = key;
cur_node.value = value;
table.put(key, cur_node);
}
// 存在还是不存在 都要把新的节点移动到首位
cur_node.prev = head;
head.next.prev = cur_node;
cur_node.next = head.next;
head.next = cur_node;
}
/**双向链表内部类*/
public static class ListNode<K, V> {
private K key;
private V value;
public ListNode<K, V> prev;
public ListNode<K, V> next;
public ListNode(K key, V value) {
this.key = key;
this.value = value;
}
public ListNode() {
}
}
public static void main(String[] args) {
LRUCache<ListNode> cache = new LRUCache<>(4);
ListNode<String, Integer> node1 = new ListNode<>("key1", 1);
ListNode<String, Integer> node2 = new ListNode<>("key2", 2);
ListNode<String, Integer> node3 = new ListNode<>("key3", 3);
ListNode<String, Integer> node4 = new ListNode<>("key4", 4);
ListNode<String, Integer> node5 = new ListNode<>("key5", 5);
cache.put("key1", node1);
cache.put("key2", node2);
cache.put("key3", node3);
cache.put("key4", node4);
cache.get("key2");
cache.put("key5", node5);
cache.get("key2");
System.out.println(cache);
}
}
