Redis 数据缓存满了怎么办？我们知道 Redis 缓存满了之后能通过淘汰策略删除数据腾出空间给新数据。
设置过期时间的 key
所有的 key
这就意味着，即使它的过期时间还没到，也会被删除。当然，如果已经过了过期时间，即使没有被淘汰策略选中，也会被删除。
今天码哥带大家一起搞定 Redis 的 LRU 算法…
近似 LRU 算法
算法的全程是，顾名思义就是按照最近最久未使用的算法进行数据淘汰。
核心思想「如果该数据最近被访问，那么将来被发放稳的几率也更高」。
-
MRU
：表示链表的表头，代表着最近最常被访问的数据；
LRU：表示链表的表尾，代表最近最不常使用的数据。
LRU 更新和插入新数据都发生在链表首，删除数据都发生在链表尾。
使用单链表可以么？
Redis 使用该 LRU 算法管理所有的缓存数据么？
除此之外，大量的节点被访问就会带来频繁的链表节点移动操作，从而降低了 Redis 性能。
对少量的 key 采样，并淘汰采样的数据中最久没被访问过的 key。
Redis LRU 算法有一个重要的点在于可以更改样本数量来调整算法的精度，使其近似接近真实的 LRU 算法，同时又避免了内存的消耗，因为每次只需要采样少量样本，而不是全部数据。
maxmemory-samples 50运行原理
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
/* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time).
*/
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;Redis 在淘汰数据时，第一次随机选出 N 个数据放到候选集合，将 lru 字段值最小的数据淘汰。
再次需要淘汰数据时，会重新挑选数据放入第一次创建的候选集合，不过有一个挑选标准：进入该集合的数据的 lru 的值必须小于候选集合中最小的 lru 值。
这样就大大减少链表节点数量，同时不用每次访问数据都移动链表节点，大大提升了性能。
Java 实现 LRU Cahce
LinkedHashMap 实现
public class LRUCache<K, V> {
private Map<K, V> map;
private final int cacheSize;
public LRUCache(int initialCapacity) {
map = new LinkedHashMap<K, V>(initialCapacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
};
this.cacheSize = initialCapacity;
}
}重点在于 的第三个构造函数上，要把这个构造参数设为true，代表内部维持访问顺序。
自己实现
其中代码是从 LeetCode 146. LRU Cache 上摘下来的。代码里面有注释。
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
/**
* 在链头放最久未被使用的元素，链尾放刚刚添加或访问的元素
*/
class LRUCache {
class Node {
int key, value;
Node pre, next;
Node(int key, int value) {
this.key = key;
this.value = value;
pre = this;
next = this;
}
}
private final int capacity;// LRU Cache的容量
private Node dummy;// dummy节点是一个冗余节点，dummy的next是链表的第一个节点，dummy的pre是链表的最后一个节点
private Map<Integer, Node> cache;//保存key-Node对，Node是双向链表节点
public LRUCache(int capacity) {
this.capacity = capacity;
dummy = new Node(0, 0);
cache = new ConcurrentHashMap<>();
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) return -1;
remove(node);
add(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node == null) {
if (cache.size() >= capacity) {
cache.remove(dummy.next.key);
remove(dummy.next);
}
node = new Node(key, value);
cache.put(key, node);
add(node);
} else {
cache.remove(node.key);
remove(node);
node = new Node(key, value);
cache.put(key, node);
add(node);
}
}
/**
* 在链表尾部添加新节点
*
* @param node 新节点
*/
private void add(Node node) {
dummy.pre.next = node;
node.pre = dummy.pre;
node.next = dummy;
dummy.pre = node;
}
/**
* 从双向链表中删除该节点
*
* @param node 要删除的节点
*/
private void remove(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
}不要吝啬赞美，当别人做的不错，就给予他正反馈。少关注用「赞美」投票的事情，而应该去关注用「交易」投票的事情。
因为赞美太廉价，而愿意与他发生交易的才是真正的信任和支持。
少量赞赏，感谢曾经赞赏过我的读者，谢谢。