高新网站建设,东莞网络优化公司排名,湖南省建设厅官网查询证书,做动画 的 网站有哪些内容作者 | 码哥呀来源 | CSDN博客在《Redis 数据缓存满了怎么办#xff1f;》我们知道 Redis 缓存满了之后能通过淘汰策略删除数据腾出空间给新数据。淘汰策略如下所示#xff1a;redis内存淘汰设置过期时间的 keyvolatile-ttl、volatile-random、volatile-lru、volatile-lfu 这… 作者 | 码哥呀来源 | CSDN博客在《Redis 数据缓存满了怎么办》我们知道 Redis 缓存满了之后能通过淘汰策略删除数据腾出空间给新数据。淘汰策略如下所示redis内存淘汰设置过期时间的 keyvolatile-ttl、volatile-random、volatile-lru、volatile-lfu 这四种策略淘汰的数据范围是设置了过期时间的数据。所有的 keyallkeys-lru、allkeys-random、allkeys-lfu 这三种淘汰策略无论这些键值对是否设置了过期时间当内存不足都会进行淘汰。这就意味着即使它的过期时间还没到也会被删除。当然如果已经过了过期时间即使没有被淘汰策略选中也会被删除。volatile-ttl 和 volatile-randon 很简单重点在于 volatile-lru 和 volatile-lfu他们涉及到 LRU 算法 和 LFU 算法。今天带大家一起搞定 Redis 的 LRU 算法…近似 LRU 算法❝ 什么是 LRU 算法呢LRU 算法的全程是 Least Rencently Used顾名思义就是按照最近最久未使用的算法进行数据淘汰。核心思想「如果该数据最近被访问那么将来被访问的几率也更高」。我们把所有的数据组织成一个链表MRU表示链表的表头代表着最近最常被访问的数据LRU表示链表的表尾代表最近最不常使用的数据。LRU 算法可以发现LRU 更新和插入新数据都发生在链表首删除数据都发生在链表尾。被访问的数据会被移动到 MRU 端被访问的数据之前的数据则相应往后移动一位。❝ 使用单链表可以么如果选用单链表删除这个结点需要 O(n) 遍历一遍找到前驱结点。所以选用双向链表在删除的时候也能 O(1) 完成。❝ Redis 使用该 LRU 算法管理所有的缓存数据么不是的由于 LRU 算法需要用链表管理所有的数据会造成大量额外的空间消耗。除此之外大量的节点被访问就会带来频繁的链表节点移动操作从而降低了 Redis 性能。所以 Redis 对该算法做了简化Redis LRU 算法并不是真正的 LRURedis 通过对少量的 key 采样并淘汰采样的数据中最久没被访问过的 key。这就意味着 Redis 无法淘汰数据库最久访问的数据。Redis LRU 算法有一个重要的点在于可以更改样本数量来调整算法的精度使其近似接近真实的 LRU 算法同时又避免了内存的消耗因为每次只需要采样少量样本而不是全部数据。配置如下maxmemory-samples 50运行原理大家还记得么数据结构 redisObject 中有一个 lru 字段 用于记录每个数据最近一次被访问的时间戳。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 值。如果新数据进入候选集合的个数达到了 maxmemory-samples 设定的值那就把候选集合中 lru 最小的数据淘汰。这样就大大减少链表节点数量同时不用每次访问数据都移动链表节点大大提升了性能。Java 实现 LRU CahceLinkedHashMap 实现完全利用 Java 的LinkedHashMap实现可以采用组合或者继承的方式实现在这里使用组合的形式完成。public class LRUCacheK, V {private MapK, V map;private final int cacheSize;public LRUCache(int initialCapacity) {map new LinkedHashMapK, V(initialCapacity, 0.75f, true) {Overrideprotected boolean removeEldestEntry(Map.EntryK, V eldest) {return size() cacheSize;}};this.cacheSize initialCapacity;}
}重点在于 LinkedHashMap的第三个构造函数上要把这个构造参数accessOrder设为 true代表LinkedHashMap内部维持访问顺序。另外还需要重写removeEldestEntry()这个函数如果返回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 MapInteger, 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;}
}参考文献https://redis.io/docs/manual/eviction/http://antirez.com/news/109https://time.geekbang.org/column/article/294640 https://halfrost.com/lru_lfu_interview/https://blog.csdn.net/csdlwzy/article/details/95635083往期推荐Kubernetes 上调试 distroless 容器Kubernetes 上容器的启动顺序如何把控Redis 内存满了怎么办这样置才正确用 Spring boot 简单搭建一个微服务项目点分享点收藏点点赞点在看
