Redis 精通系列——LRU 算法详述 (Least Recently Used - 最近最少使用)
默认情况 maxmemory 配置项并未启用，Redis 官方介绍 64 位操作系统默认无内存限制，32 位操作系统默认 3GB 隐式内存配置，如果 maxmemory 为 0，代表内存不受限。
因此我们在做缓存架构时，要根据硬件资源+业务需求做合适的 maxmemory 配置。
?
3、内存达到 maxmemory 怎么办
很显然配置了最大内存，当 maxmemory 达到了最大上限之后 Redis 不可能不干活了，那么 Redis 是怎么来处理这个问题的呢？这就是本文的重点，Redis 提供了 maxmemory-policy 淘汰策略（本文只讲述 LRU 不涉及 LFU，LFU 在下一篇文章讲述），对满足条件的 key 进行删除，辞旧迎新。
maxmemory-policy 淘汰策略：
**noeviction：**当达到内存限制并且客户端尝试执行可能导致使用更多内存的命令时返回错误，简单来说读操作仍然允许，但是不准写入新的数据，del（删除）请求可以。
**allkeys-lru：**从全体 key 中，通过 lru（Least Recently Used - 最近最少使用）算法进行淘汰
**allkeys-random：**从全体 key 中，随机进行淘汰
**volatile-lru：**从设置了过期时间的全部 key 中，通过 lru（Least Recently Used - 最近最少使用）算法进行淘汰，这样可以保证未设置过期时间需要被持久化的数据，不会被选中淘汰
**volatile-random：**从设置了过期时间的全部 key 中，随机进行淘汰
**volatile-ttl：**从设置了过期时间的全部 key 中，通过比较 key 的剩余过期时间 TTL 的值，TTL 越小越先被淘汰
还有 volatile-lfu/allkeys-lfu 这个留到下文一起探讨，两个算法不一样！
random 随机淘汰只需要随机取一些 key 进行删除，释放内存空间即可；ttl 过期时间小先淘汰也可以通过比较 ttl 的大小，将 ttl 值小的 key 进行删除，释放内存空间即可。
那么 LRU 是怎么实现的呢？Redis 又是如何知道哪个 key 最近被使用了，哪个 key 最近没有被使用呢？
?
4、LRU 算法实现
我们先用 Java 的容器实现一个简单的 LRU 算法，我们使用 ConcurrentHashMap 做 key-value 结果存储元素的映射关系，使用 ConcurrentLinkedDeque 来维持 key 的访问顺序。
LRU 实现代码：
package?com.lizba.redis.lru;
import?java.util.Arrays;
import?java.util.List;
import?java.util.concurrent.ConcurrentHashMap;
import?java.util.concurrent.ConcurrentLinkedDeque;
/**
*?<p>
*??????LRU 简单实现
*?</p>
*?@Author:?Liziba
*?@Date:?2021/9/17?23:47
*/
public?class?SimpleLru?{
/**?数据缓存?*/
private?ConcurrentHashMap<String,?Object>?cacheData;
/**?访问顺序记录?*/
private?ConcurrentLinkedDeque<String>?sequence;
/**?缓存容量?*/
private?int?capacity;
public?SimpleLru(int?capacity)?{
this.capacity?=?capacity;
cacheData?=?new?ConcurrentHashMap(capacity);
sequence?=?new?ConcurrentLinkedDeque();
}
/**
*?设置值
*?@param?key
*?@param?value
*?@return
*/
public?Object?setValue(String?key,?Object?value)?{
//?判断是否需要进行 LRU 淘汰
this.maxMemoryHandle();
//?包含则移除元素，新访问的元素一直保存在队列最前面
if?(sequence.contains(key))?{
sequence.remove();
}
sequence.addFirst(key);
cacheData.put(key,?value);
return?value;
}
/**
*?达到最大内存，淘汰最近最少使用的 key
*/
private?void?maxMemoryHandle()?{
while?(sequence.size()?>=?capacity)?{
String?lruKey?=?sequence.removeLast();
cacheData.remove(lruKey);
System.out.println("key:?"?+?lruKey?+?"被淘汰！");
}
}
/**
*?获取访问 LRU 顺序
*?@return
*/
public?List<String>?getAll()?{
return?Arrays.asList(sequence.toArray(new?String[]?{}));
}
}
测试代码：
package?com.lizba.redis.lru;
/
**
*?<p>
*??????测试最近最少使用
*?</p>
*?@Author:?Liziba
*?@Date:?2021/9/18?0:00
*/
public?class?TestSimpleLru?{
public?static?void?main(String[]?args)?{
SimpleLru?lru?=?new?SimpleLru(8);
for?(int?i?=?0;?i?<?10;?i++)?{
lru.setValue(i+"",?i);
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论