Redis缓存淘汰算法详解

news/2024/12/22 20:42:34/

文章目录

    • Redis缓存淘汰算法
      • 1. Redis缓存淘汰策略分类
      • 2. 会进行淘汰的7种策略
        • 2.1 基于过期时间的淘汰策略
        • 2.2 基于所有数据范围的淘汰策略
      • 3. LRU与LFU算法详解
      • 4. 配置与调整
      • 5. 实际应用场景
    • LRU算法以及实现样例
    • LFU算法实现
      • 1. 数据结构选择
      • 2. 访问频率更新
      • 3. 缓存淘汰
      • 4. 缓存插入
      • 5. 优化和变种
      • 6. 注意事项
      • 7. 算法的python实现

Redis缓存淘汰算法

Redis缓存淘汰算法是Redis内存管理机制中的重要组成部分，用于在Redis达到内存使用上限时，通过不同的策略选择部分数据进行删除，以腾出内存空间。Redis提供了多种缓存淘汰策略，这些策略可以根据业务需求和数据特点进行灵活配置。以下是对Redis缓存淘汰算法的详细解析：

1. Redis缓存淘汰策略分类

Redis的缓存淘汰策略可以分为两大类：

  • 不进行数据淘汰的策略：仅有一种，即noeviction。当缓存数据满了，有新的写请求进来时，Redis不再提供服务，而是直接返回错误。
  • 会进行淘汰的策略：共有7种，包括基于数据是否设置过期时间的两类策略。

2. 会进行淘汰的7种策略

2.1 基于过期时间的淘汰策略
  • volatile-random：在设置了过期时间的键值对中，进行随机删除。
  • volatile-ttl：根据过期时间的先后进行删除，越早过期的越先被删除。
  • volatile-lru：使用LRU（Least Recently Used，最近最少使用）算法筛选设置了过期时间的键值对。
  • volatile-lfu：使用LFU（Least Frequently Used，最近最少使用）算法选择设置了过期时间的键值对（Redis 4.0后新增）。
2.2 基于所有数据范围的淘汰策略
  • allkeys-random：从所有键值对中随机选择并删除数据。
  • allkeys-lru：使用LRU算法在所有数据中进行筛选。
  • allkeys-lfu：使用LFU算法在所有数据中进行筛选（Redis 4.0后新增）。

3. LRU与LFU算法详解

  • LRU（Least Recently Used）：最近最少使用算法，它的基本思想是淘汰最近最少访问的数据。Redis实现的LRU算法是近似LRU，通过随机选择一定数量的键，并从中选择最不常使用的键进行淘汰。这种方式避免了遍历所有键的开销，但可能会牺牲一定的精确度。
  • LFU（Least Frequently Used）：最近最少使用频率算法，它基于数据的访问频率进行淘汰。Redis使用近似计数器为每个键记录访问次数，当内存达到上限时，会优先淘汰访问次数较少的键。LFU算法通过log-log计数器实现，能够以较低的内存开销记录键的访问次数。

4. 配置与调整

  • 设置内存使用上限：通过maxmemory参数来设定Redis的内存使用上限。
  • 配置淘汰策略：通过maxmemory-policy参数来配置淘汰策略。
  • 调整采样数量：对于LRU和LFU算法，可以通过maxmemory-samples参数来控制每次随机选择的键的数量，以提高算法的精确度，但也会增加CPU开销。
  • 监控与评估：通过定期监控Redis的内存使用情况和命中率，可以评估当前的淘汰策略是否合适，并根据需要进行调整。

5. 实际应用场景

  • 缓存数据的重要性较高：适合使用LRU或LFU策略，以保留访问频繁的数据。
  • 数据具有明确的过期时间：适合使用volatile-ttl、volatile-random、volatile-lru或volatile-lfu策略。
  • 数据访问频率不均：适合使用allkeys-lfu或volatile-lfu策略，以提升缓存的命中率。
  • 对数据一致性要求非常高：适合使用noeviction策略，以确保不会随意删除数据。

综上所述，Redis的缓存淘汰算法为Redis的内存管理提供了灵活且强大的支持，通过合理的配置和调整，可以显著提高缓存的效率和性能。

LRU算法以及实现样例

LRU（Least Recently Used，最近最少使用）缓存淘汰算法是一种常用的页面置换算法，用于管理缓存中的数据，确保最近最少使用的数据被优先淘汰。在双向链表中实现LRU缓存是一种高效的方式，因为双向链表可以让我们在O(1)时间复杂度内完成节点的插入和删除操作。

下面是一个使用Python实现的基于双向链表的LRU缓存的简单示例：

class ListNode:def __init__(self, key=0, value=0):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):self.capacity = capacity# 初始化头尾节点self.head = ListNode()self.tail = ListNode()self.head.next = self.tailself.tail.prev = self.headself.cache = {}def get(self, key: int) -> int:if key not in self.cache:return -1node = self.cache[key]# 将节点移动到链表头部self._move_to_head(node)return node.valuedef put(self, key: int, value: int) -> None:if key in self.cache:# 如果key已存在，更新值并移动到头部node = self.cache[key]node.value = valueself._move_to_head(node)else:# 如果key不存在，创建新节点newNode = ListNode(key, value)# 添加到哈希表中self.cache[key] = newNode# 添加到链表头部self._add_node(newNode)# 如果超出容量，删除链表尾部节点if len(self.cache) > self.capacity:tail = self.pop_tail()del self.cache[tail.key]def _move_to_head(self, node):# 移除节点self._remove_node(node)# 添加到头部self._add_node(node)def _remove_node(self, node):prev = node.prevnext_node = node.nextprev.next = next_nodenext_node.prev = prevdef _add_node(self, node):node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef pop_tail(self):res = self.tail.prevself._remove_node(res)return res# 使用示例
lru_cache = LRUCache(2)
lru_cache.put(1, 1)
lru_cache.put(2, 2)
print(lru_cache.get(1))  # 返回 1
lru_cache.put(3, 3)      # 淘汰 key 2
print(lru_cache.get(2))  # 返回 -1 (未找到)
lru_cache.put(4, 4)      # 淘汰 key 1
print(lru_cache.get(1))  # 返回 -1 (未找到)
print(lru_cache.get(3))  # 返回 3
print(lru_cache.get(4))  # 返回 4

这个实现中，LRUCache 类维护了一个双向链表和一个哈希表。哈希表用于快速查找节点，而双向链表则用于维护节点的使用顺序。每次访问或添加节点时，都会将其移动到链表的头部，表示最近使用过。当缓存达到容量上限时，会删除链表尾部的节点，即最近最少使用的节点。

LFU算法实现

LFU（Least Frequently Used）算法是一种基于访问频率的缓存淘汰算法，其核心思想是优先淘汰那些访问频率最低的数据项。以下是LFU算法实现的基本步骤和关键点：

1. 数据结构选择

LFU算法的实现通常需要结合多种数据结构来高效地管理缓存项及其访问频率。常见的组合包括哈希表（HashMap）和双向链表（Doubly Linked List）或优先队列（如最小堆Min-Heap）：

  • 哈希表：用于存储缓存项及其对应的访问频率信息。键为缓存项的键，值为指向双向链表节点或堆中元素的指针，以及访问频率计数器。
  • 双向链表或优先队列：用于按访问频率排序缓存项。在双向链表中，相同访问频率的节点可以通过额外的链表组织在一起；在优先队列中，则可以直接根据频率进行排序。

2. 访问频率更新

每次缓存项被访问时，需要更新其访问频率：

  • 在哈希表中查找缓存项，获取其当前的访问频率和对应的双向链表节点或堆元素。
  • 将访问频率加1，并更新哈希表中的记录。
  • 如果使用双向链表，可能需要将节点从当前频率的链表中移除，并插入到更高频率的链表中（如果频率增加）。
  • 如果使用优先队列，则可能需要重新调整队列中的位置。

3. 缓存淘汰

当缓存达到容量上限且需要插入新数据时，执行缓存淘汰：

  • 如果使用双向链表，遍历最低频率的链表，找到最久未被访问或访问频率最低的节点进行淘汰。
  • 如果使用优先队列，则直接从队列中取出最小频率的节点进行淘汰。
  • 从哈希表中删除被淘汰的缓存项，并释放相应的内存。

4. 缓存插入

新数据插入时，首先检查缓存是否已满：

  • 如果未满，直接在哈希表中添加新项，并初始化其访问频率为1。如果使用双向链表，将其添加到最低频率的链表中；如果使用优先队列，则将其插入到适当的位置。
  • 如果已满，则执行缓存淘汰操作，然后插入新数据。

5. 优化和变种

  • LFU-Aging：在LFU的基础上增加“老化”机制，即定期降低所有缓存项的访问频率，以便更快地适应访问模式的变化。
  • Window-LFU：只记录过去一段时间内的访问历史，而不是所有数据的历史访问记录，以减少内存消耗和提高效率。
  • LFU*：只淘汰访问次数为1的缓存项，以减少缓存污染问题。

6. 注意事项

  • LFU算法在访问模式稳定时表现良好，但在访问模式频繁变化时可能会出现缓存污染问题。
  • 相比LRU算法，LFU算法需要更多的内存来记录访问频率信息，并且在访问频率更新和排序时可能会有更高的性能开销。

7. 算法的python实现

在Python中实现LFU（Least Frequently Used）缓存算法，我们可以使用collections模块中的OrderedDict来模拟双向链表的功能（虽然它实际上是一个有序字典），以及一个哈希表来记录每个键的访问频率。不过，为了更准确地实现LFU算法，特别是当需要频繁地根据访问频率进行排序时，我们可能需要一个更复杂的结构，比如使用heapq（最小堆）来优化查找最小频率项的过程。

然而，为了简化说明，这里我将提供一个基于OrderedDict和额外哈希表的LFU缓存实现，该实现将模拟LFU的行为，但可能不是最高效的（特别是在处理大量数据和频繁更新时）。

from collections import OrderedDict, defaultdictclass LFUCache:def __init__(self, capacity: int):self.capacity = capacityself.cache = OrderedDict()  # 存储键和对应的值以及频率self.frequency = defaultdict(OrderedDict)  # 存储每个频率对应的键的集合def get(self, key: int) -> int:if key not in self.cache:return -1# 更新访问频率freq = self.cache[key][1]self.frequency[freq].pop(key)if not self.frequency[freq]:del self.frequency[freq]freq += 1self.cache[key] = (self.cache[key][0], freq)if freq not in self.frequency:self.frequency[freq] = OrderedDict()self.frequency[freq][key] = None# 将键移到OrderedDict的末尾，模拟最近访问self.cache.move_to_end(key)return self.cache[key][0]def put(self, key: int, value: int) -> None:if self.capacity <= 0:returnif key in self.cache:# 更新现有键的值和频率self.cache[key] = (value, self.cache[key][1] + 1)freq = self.cache[key][1]self.frequency[self.cache[key][1] - 1].pop(key)if not self.frequency[self.cache[key][1] - 1]:del self.frequency[self.cache[key][1] - 1]if freq not in self.frequency:self.frequency[freq] = OrderedDict()self.frequency[freq][key] = Noneself.cache.move_to_end(key)else:# 插入新键if len(self.cache) >= self.capacity:# 淘汰最少使用的项min_freq = min(self.frequency.keys())oldest_key = next(iter(self.frequency[min_freq]))del self.cache[oldest_key]del self.frequency[min_freq][oldest_key]if not self.frequency[min_freq]:del self.frequency[min_freq]# 插入新项self.cache[key] = (value, 1)if 1 not in self.frequency:self.frequency[1] = OrderedDict()self.frequency[1][key] = None# 示例用法
lfu = LFUCache(2)
lfu.put(1, 1)
lfu.put(2, 2)
print(lfu.get(1))  # 返回 1
lfu.put(3, 3)      # 淘汰键 2
print(lfu.get(2))  # 返回 -1 (未找到)
lfu.put(4, 4)      # 淘汰键 1
print(lfu.get(1))  # 返回 -1 (未找到)
print(lfu.get(3))  # 返回 3
print(lfu.get(4))  # 返回 4

注意：这个实现虽然模拟了LFU的行为，但在处理大量数据和频繁更新时可能不是最高效的。特别是，它使用OrderedDict来模拟双向链表的行为，这在每次更新频率时都需要进行字典的插入和删除操作，这些操作的时间复杂度都是O(1)平均情况下，但在最坏情况下（即哈希冲突严重时）可能会退化。

为了获得更好的性能，特别是在需要频繁更新频率和根据频率进行排序时，可以考虑使用更复杂的数据结构，如平衡树或自定义的双向链表与哈希表的组合。然而，这些实现将更加复杂，并且可能需要更多的内存和代码来实现。


http://www.ppmy.cn/news/1532710.html

相关文章

Jenkins本地安装配置与远程访问管理本地服务详细流程

Jenkins本地安装配置与远程访问管理本地服务详细流程

文章目录 前言1. 安装Jenkins2. 局域网访问Jenkins3. 安装 cpolar内网穿透软件4. 配置Jenkins公网访问地址5. 公网远程访问Jenkins6. 固定公网地址 前言 本文主要介绍如何在Linux CentOS 7中安装Jenkins并结合cpolar内网穿透工具实现远程访问管理本地部署的Jenkins服务. Jenk…
阅读更多...
VMware复制Ubuntu虚拟机后网卡失效的问题

VMware复制Ubuntu虚拟机后网卡失效的问题

为了在个人电脑上搭建集群&#xff0c;我使用了多台VMware虚拟机来模拟集群主机。之前虚拟机的操作系统是Redhat时&#xff0c;我复制虚拟机后网卡功能没有问题&#xff0c;但这次换成Ubuntu操作系统&#xff0c;我复制了虚拟机后同时启动这两台虚拟机&#xff0c;其中一台虚拟…
阅读更多...
ArduSub程序学习（11）--EKF实现逻辑②

ArduSub程序学习（11）--EKF实现逻辑②

1.InitialiseFilter(void) 扩展卡尔曼滤波器2 (EKF2) 的初始化流程。这个函数的核心功能是设置并启动 EKF2 滤波器&#xff0c;包括内存分配、滤波器核心设置以及与惯性测量单元 (IMU) 的关联。 //EKF2初始化 bool NavEKF2::InitialiseFilter(void) {//通过 start_frame 函数…
阅读更多...
第十章 【后端】商品分类管理微服务 ＞ 分类列表查询接口（10.8.3）——MyBatis-Plus 逻辑删除

第十章 【后端】商品分类管理微服务 ＞ 分类列表查询接口（10.8.3）——MyBatis-Plus 逻辑删除

10.8.3 MyBatis-Plus 逻辑删除 参考：https://baomidou.com/pages/6b03c5/ powerdesigner 修改数据库设计 按11.5节重新创建数据表或直接修改数据表结构 修改 com.glc.etms.goods.entity.Category package com.yumi.etms.goods.entity;import</
阅读更多...
docker学习笔记（1.0）

docker学习笔记（1.0）

docker命令 下载镜像相关命令 检索&#xff1a;docker search 比如&#xff1a;docker search nginx 是查看有没有nginx镜像 后面的OK表示是不是官方镜像&#xff0c;如果有就是官方镜像&#xff0c;如果没有就是第三方的。 下载&#xff1a;docker pull 比如&#xff1a…
阅读更多...
【STM32】江科大STM32笔记汇总(已完结)

【STM32】江科大STM32笔记汇总(已完结)

STM32江科大笔记汇总 STM32学习笔记课程简介(01)STM32简介(02)软件安装(03)新建工程(04)GPIO输出(05)LED闪烁& LED流水灯& 蜂鸣器(06)GPIO输入(07)按键控制LED 光敏传感器控制蜂鸣器(08)OLED调试工具(09)OLED显示屏(10)EXTI外部中断(11)对射式红外传感器计次 旋转编码器…
阅读更多...
《应急通信产业发展研究报告》蓝皮书解读

《应急通信产业发展研究报告》蓝皮书解读

近日&#xff0c;中国信通院发布了《应急通信产业发展研究报告》蓝皮书&#xff0c;该报告是对中国应急通信产业现状、发展趋势及其政策环境的综合分析&#xff0c;旨在为行业发展提供参考与指导。以下是小编对该蓝皮书的一些内容解读&#xff1a; 1.应急通信的重要性 应急通信…
阅读更多...
SpringBoot与MyBatis-Plus的整合与综合实例

SpringBoot与MyBatis-Plus的整合与综合实例

MyBatis 是一款优秀的持久层框架&#xff0c;它支持定制化SQL、存储过程、以及高级映射。MyBatis3 提供的注解可以取代 XML。例如&#xff0c;使用注解 Select 直接编写 SQL 完成数据查询。MyBatis-Plus 是一个对 MyBatis 进行增强的工具&#xff0c;在 MyBatis 的基础上只做增…
阅读更多...
最新文章

Copyright @ 2022~2023