简单网站建设 有教程视频杭州知名设计公司有哪些

简单网站建设 有教程视频,杭州知名设计公司有哪些,一键生成ppt,乐清市宏杉网络科技有限公司面试都背过道八股题#xff1a;Redis 的内存淘汰策略 LRU 和 LFU 是什么#xff1f;怎么选好#xff1f;很多同学对这两个算法的理解#xff0c;只停留在都是缓存淘汰#xff0c;但说不清它们具体区别#xff0c;概念混淆#xff0c;更不知道实际场景该怎么选#xff1…面试都背过道八股题Redis 的内存淘汰策略LRU和LFU是什么怎么选好很多同学对这两个算法的理解只停留在都是缓存淘汰但说不清它们具体区别概念混淆更不知道实际场景该怎么选而且 Redis 的 key 淘汰算法其实还不是正统的LRU和LFU算法而是基于 LRU/LFU 的一个变种。所以我们先了解下 LRU/LFU 基础算法再看看它和变种的 Redis LRU 算法有何不同。一、什么是 LRU 算法LRU 的全称是 Least Recently Used最近最少使用核心逻辑特别好记最近没被用过的下次也大概率用不上。举个例子你电脑桌面上放着常用的软件图标微信、IDE这些是最近常用的而几个月没打开过的压缩工具会被你拖到文件夹里。这就是 LRU 的思路保留最近使用的淘汰最近最少使用的。❝假设缓存容量只有 3依次存入 A、B、C此时缓存是 [A,B,C]若此时访问 AA 变成最近使用缓存顺序变为 [B,C,A]若再存入D缓存满了需要淘汰最近最少使用的 B最终缓存是 [C,A,D]LRU 的优缺点优点逻辑简单只关注使用时间实现成本低容易理解响应快插入、删除、查询的时间复杂度可以做到 O (1)用链表 哈希表实现贴合短期局部性很多业务场景中最近用的数据确实接下来更可能用比如你刚打开的文档接下来大概率会继续编辑。缺点突发访问误淘汰如果突然有大量一次性数据访问会把原本常用的缓存挤掉。比如缓存容量 3原本缓存 [A,B,C]A 是高频使用突然连续访问 D、E、F此时会淘汰 A、B、C缓存变成 [D,E,F]但后续再访问 A 时A 已经被淘汰需要重新从数据库加载导致缓存命中率骤降。不考虑使用频率如果 A 每天用 100 次B 每天用 1 次但 B 是 1 分钟前刚用A 是 2 分钟前用LRU 会优先淘汰 A这显然不合理高频使用的 A 不该被淘汰。实现 LRU 两种方案方案 1基于 LinkedHashMapJava 的LinkedHashMap自带按访问顺序排序的功能只需重写removeEldestEntry方法就能实现 LRU 缓存。这是最简洁的实现方式适合业务中不需要极致性能的场景快速开发。import java.util.LinkedHashMap; import java.util.Map; publicclass LRUCacheK, V extends LinkedHashMapK, V { // 缓存最大容量 privatefinalint maxCapacity; // 构造函数accessOrdertrue 表示“按访问顺序排序”核心 public LRUCache(int maxCapacity) { super(maxCapacity, 0.75f, true); this.maxCapacity maxCapacity; } // 核心当缓存大小超过maxCapacity时自动删除“最老的 entry”最近最少使用的 Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() maxCapacity; } // 测试 public static void main(String[] args) { LRUCacheInteger, String cache new LRUCache(3); cache.put(1, A); cache.put(2, B); cache.put(3, C); System.out.println(cache); // 输出{1A, 2B, 3C}插入顺序 cache.get(1); // 访问11变成最近使用 System.out.println(cache); // 输出{2B, 3C, 1A}按访问顺序排序 cache.put(4, D); // 缓存满了淘汰最老的2 System.out.println(cache); // 输出{3C, 1A, 4D} } }方案 2基于双向链表 哈希表LinkedHashMap本质是哈希表 双向链表但如果想深入理解 LRU 的实现原理建议自己手写一个核心是用哈希表保证 O (1) 查询用双向链表保证 O (1) 插入、删除维护访问顺序。适用于高并发场景和面试。import java.util.HashMap; import java.util.Map; publicclass LRUCache2K, V { // 双向链表节点存储key、value以及前后指针 staticclass NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; public Node(K key, V value) { this.key key; this.value value; } } privatefinalint maxCapacity; privatefinal MapK, NodeK, V map; // 哈希表key→NodeO(1)查询 privatefinal NodeK, V head; // 虚拟头节点简化链表操作 privatefinal NodeK, V tail; // 虚拟尾节点 public LRUCache2(int maxCapacity) { this.maxCapacity maxCapacity; this.map new HashMap(); // 初始化虚拟头尾节点避免处理null指针 this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } // 1. 获取缓存命中则把节点移到链表头部标记为最近使用 public V get(K key) { NodeK, V node map.get(key); if (node null) { returnnull; // 未命中 } // 移除当前节点 removeNode(node); // 移到头部 addToHead(node); return node.value; } // 2. 存入缓存不存在则新增存在则更新并移到头部满了则删除尾部节点 public void put(K key, V value) { NodeK, V node map.get(key); if (node null) { // 新增节点 NodeK, V newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); // 缓存满了删除尾部节点最近最少使用 if (map.size() maxCapacity) { NodeK, V tailNode removeTail(); map.remove(tailNode.key); // 同步删除哈希表中的key } } else { // 更新节点值并移到头部 node.value value; removeNode(node); addToHead(node); } } // 辅助把节点添加到链表头部 private void addToHead(NodeK, V node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 辅助移除指定节点 private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } // 辅助移除尾部节点最近最少使用 private NodeK, V removeTail() { NodeK, V tailNode tail.prev; removeNode(tailNode); return tailNode; } // 测试 public static void main(String[] args) { LRUCache2Integer, String cache new LRUCache2(3); cache.put(1, A); cache.put(2, B); cache.put(3, C); System.out.println(cache.get(1)); // 输出A此时1移到头部 cache.put(4, D); // 淘汰3 System.out.println(cache.get(3)); // 输出null已被淘汰 } }LRU 的使用场景LRU 适合短期高频场景比如:浏览器缓存浏览器缓存网页时会优先淘汰最近最少打开”的页面比如你一周没打开的网页会被优先清理Redis 默认内存淘汰策略Redis 的allkeys-lru和volatile-lru是基于 LRU 的实际是 “近似 LRU”性能更高适合 “缓存访问具有短期局部性” 的场景比如电商商品详情页用户打开后短时间内可能再次刷新本地缓存基础版如果业务中没有突发大量一次性访问用 LRU 实现本地缓存足够满足需求比如用 LinkedHashMap 快速开发。二、什么是 LFU 算法LFU的全称是Least Frequently Used最不经常使用核心逻辑和 LRU 完全不同用得少的下次也大概率用不上它关注的是使用频率而不是使用时间。还是用生活例子你手机里的 APP微信、抖音是高频使用的每天打开几十次而指南针是低频使用的几个月打开一次。当手机内存不足时系统会优先卸载指南针这类低频 APP这就是 LFU 的思路。❝假设缓存容量 3初始存入 A使用 1 次、B使用 1 次、C使用 1 次频率都是 1访问 AA 频率变成 2此时频率A2B1C1访问 AA 频率变成 3此时频率A3B1C1存入 D缓存满了需要淘汰 “频率最低” 的 B 或 C若频率相同淘汰 “最近最少使用” 的即 LFULRU 结合最终缓存是 A、C、D频率分别为 3、1、1。LFU 的优缺点优点更贴合长期高频场景能保留使用频率高的数据即使它不是 最近使用的比如 A 每天用 100 次即使 10 分钟前没⽤也不该被淘汰避免突发访问误淘汰面对一次性突发访问比如访问 D、E、F因为这些数据的频率低不会把高频的 A、B、C 挤掉缓存命中率更稳定。缺点实现复杂需要维护使用频率还需要处理频率相同的情况通常结合 LRU时间复杂度比 LRU 高插入、删除约 O (log n)冷启动问题新存入的缓存频率低容易被淘汰。比如一个新功能的接口刚开始访问频率低会被 LFU 优先淘汰但其实后续会变成高频接口频率老化问题一个数据过去高频但现在不再使用比如活动结束后的活动页面它的高频率会一直占用缓存导致新的高频数据无法进入。实现 LFU基于哈希表 优先级队列LFU 的实现比 LRU 复杂核心需要两个哈希表cachekey→Node存储 value 和使用频率、最后使用时间freqMap频率→LinkedHashSet存储该频率下的所有 keyLinkedHashSet 保证插入顺序用于处理频率相同的情况再用一个变量minFreq记录当前最小频率快速找到最该淘汰的 key。import java.util.*; publicclass LFUCacheK, V { // 缓存节点存储key、value、使用频率、最后使用时间处理频率相同时的淘汰 staticclass NodeK, V { K key; V value; int freq; // 使用频率 long lastUseTime; // 最后使用时间毫秒 public Node(K key, V value) { this.key key; this.value value; this.freq 1; // 初始频率1 this.lastUseTime System.currentTimeMillis(); } } privatefinalint maxCapacity; privatefinal MapK, NodeK, V cache; // key→Node privatefinal MapInteger, LinkedHashSetK freqMap; // 频率→key集合LinkedHashSet保证顺序 privateint minFreq; // 当前最小频率快速定位要淘汰的key public LFUCache(int maxCapacity) { this.maxCapacity maxCapacity; this.cache new HashMap(); this.freqMap new HashMap(); this.minFreq 1; } // 1. 获取缓存命中则更新频率和最后使用时间 public V get(K key) { NodeK, V node cache.get(key); if (node null) { returnnull; } // 更新节点频率 updateNodeFreq(node); return node.value; } // 2. 存入缓存不存在则新增存在则更新满了则淘汰最小频率的key public void put(K key, V value) { if (maxCapacity 0) { return; } NodeK, V node cache.get(key); if (node ! null) { // 存在更新value、频率、最后使用时间 node.value value; node.lastUseTime System.currentTimeMillis(); updateNodeFreq(node); } else { // 不存在检查缓存是否满 if (cache.size() maxCapacity) { // 淘汰最小频率的key频率相同则淘汰最早使用的 evictMinFreqKey(); } // 新增节点 NodeK, V newNode new Node(key, value); cache.put(key, newNode); // 加入freqMap频率1的集合 freqMap.computeIfAbsent(1, k - new LinkedHashSet()).add(key); // 新节点频率是1minFreq重置为1 minFreq 1; } } // 辅助更新节点频率 private void updateNodeFreq(NodeK, V node) { K key node.key; int oldFreq node.freq; int newFreq oldFreq 1; // 1. 从旧频率的集合中移除key LinkedHashSetK oldFreqSet freqMap.get(oldFreq); oldFreqSet.remove(key); // 如果旧频率是minFreq且集合为空minFreq1 if (oldFreq minFreq oldFreqSet.isEmpty()) { minFreq newFreq; } // 2. 加入新频率的集合 freqMap.computeIfAbsent(newFreq, k - new LinkedHashSet()).add(key); // 3. 更新节点的频率和最后使用时间 node.freq newFreq; node.lastUseTime System.currentTimeMillis(); } // 辅助淘汰最小频率的key频率相同则淘汰最早使用的 private void evictMinFreqKey() { // 1. 获取最小频率的key集合 LinkedHashSetK minFreqSet freqMap.get(minFreq); // 2. 淘汰集合中第一个keyLinkedHashSet按插入顺序即最早使用的 K evictKey minFreqSet.iterator().next(); minFreqSet.remove(evictKey); // 3. 同步删除cache和freqMap如果集合为空 cache.remove(evictKey); if (minFreqSet.isEmpty()) { freqMap.remove(minFreq); } System.out.println(淘汰key evictKey); } // 测试 public static void main(String[] args) { LFUCacheInteger, String cache new LFUCache(3); cache.put(1, A); cache.put(2, B); cache.put(3, C); System.out.println(cache.get(1)); // 输出A频率变成2minFreq还是1 cache.put(4, D); // 缓存满淘汰minFreq1的2B System.out.println(cache.get(2)); // 输出null已淘汰 cache.get(3); // 3频率变成2minFreq变成2 cache.get(4); // 4频率变成2 cache.put(5, E); // 缓存满淘汰minFreq2的3C最早使用 }三、Redis 中的 LRU 和 LFU实现与区别Redis 作为缓存数据库当内存达到内存maxmemory限制时会触发内存淘汰策略其中LRU和LFU是最常用的两种。但 Redis 的实现并非 “严格版”而是做了性能优化的 “近似版”这一点尤其需要注意。Redis 的 LRU 实现Redis 的 LRU 实现近似 LRU性能优先Redis 没有采用 “双向链表 哈希表” 的标准 LRU 实现因为会增加内存开销和操作复杂度而是用随机采样 时间戳实现近似 LRU核心原理每个 key 在内存中记录lru字段最后一次访问的时间戳当需要淘汰 key 时Redis 会从所有候选 key 中随机采样 N 个默认 5 个可通过maxmemory-samples配置然后淘汰这 N 个中lru值最小最久未使用的 key。为什么近似严格 LRU 需要维护全量 key 的访问顺序在 Redis 高并发场景下会成为性能瓶颈近似 LRU 通过控制采样数N 越大越接近严格 LRU但性能稍差在 “命中率” 和 “性能” 之间做了平衡。相关配置# 淘汰所有key中最久未使用的 maxmemory-policy allkeys-lru # 只淘汰设置了过期时间的key中最久未使用的 maxmemory-policy volatile-lru # 采样数默认5范围3-10 maxmemory-samples 5Redis 的 LFU 实现Redis 的 LFU 实现结合频率与时间衰减。Redis 4.0 引入了 LFU 策略解决了标准 LFU 的频率老化问题实现更贴合实际业务核心改进频率计数用lfu_count记录访问频率但不是简单累加而是用对数计数访问次数越多lfu_count增长越慢避免数值过大时间衰减用lfu_decay_time控制频率衰减单位分钟如果 key 在lfu_decay_time内没有被访问lfu_count会随时间减少避免过去高频但现在不用的 key 长期占用缓存。淘汰逻辑当需要淘汰时同样随机采样 N 个 key淘汰lfu_count最小的频率最低若频率相同淘汰最久未使用的结合 LRU 逻辑。相关配置# 淘汰所有key中访问频率最低的 maxmemory-policy allkeys-lfu # 只淘汰设置了过期时间的key中访问频率最低的 maxmemory-policy volatile-lfu # 频率衰减时间默认1分钟0表示不衰减 lfu-decay-time 1 # 初始频率新key的lfu_count默认5避免新key被立即淘汰 lfu-log-factor 10Redis 中 LRU 和 LFU 的核心区别维度Redis LRURedis LFU判断依据最后访问时间越久未用越可能被淘汰访问频率频率越低越可能被淘汰结合时间衰减适用场景短期局部性访问如用户会话、临时数据长期高频访问如热点商品、基础配置应对突发访问弱易被一次性访问挤掉常用 key强低频的突发访问 key 不会淘汰高频 key冷启动友好度较好新 key 只要最近访问就不会被淘汰需配置lfu-log-factor避免新 key 因初始频率低被淘汰内存 overhead低只存时间戳稍高存频率和时间衰减信息典型业务案例新闻 APP 的最近浏览列表电商首页的热销商品缓存怎么选看业务访问模式选 LRU如果你的缓存访问具有短期集中性比如用户打开一个页面后短时间内会频繁刷新但过几天可能再也不看比如会话缓存用户登录后 1 小时内频繁操作之后可能下线临时活动页面活动期间访问集中活动结束后很少访问。选 LFU如果你的缓存访问具有 “长期高频性”比如某些基础数据每天都被大量访问比如商品类目、地区编码等基础配置数据首页 banner、热销榜单等高频访问数据。排查技巧可以先开启 Redis 的INFO stats监控keyspace_hits缓存命中和keyspace_misses缓存未命中如果切换策略后keyspace_hits提升说明更适合当前业务。总结LRU 和 LFU 的本质区别与选择从本质上看LRU 和 LFU 的核心差异是判断价值的维度不同LRU 用最近是否被使用衡量价值适合短期热点LFU 用使用频率高低衡量价值适合长期热点。在 Redis 中两者都做了性能优化近似实现选择时不用纠结 理论完美性先看业务访问模式短期集中访问用 LRU长期高频访问用 LFU。如果实在不确定不妨先试 LRU实现更简单兼容性更好再根据监控数据调整。看完等于学会点个赞吧