Redis 为何使用近似 LRU 算法淘汰数据,而不是真实 LRU?

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis 为何使用近似 LRU 算法淘汰数据,而不是真实 LRU?

在《Redis 数据缓存满了怎么办?》我们知道 Redis 缓存满了之后能通过淘汰策略删除数据腾出空间给新数据。

淘汰策略如下所示:

redis内存淘汰

设置过期时间的 key

volatile-ttl、volatile-random、volatile-lru、volatile-lfu 这四种策略淘汰的数据范围是设置了过期时间的数据。

所有的 key

allkeys-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 算法并不是真正的 LRU,Redis 通过对少量的 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 Cahce

LinkedHashMap 实现

完全利用 Java 的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;
    }
}

重点在于 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 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;
    }
}

不要吝啬赞美,当别人做的不错,就给予他正反馈。少关注用「赞美」投票的事情,而应该去关注用「交易」投票的事情。

判断一个人是否牛逼,不是看网上有多少人夸赞他,而是要看有多少人愿意跟他发生交易或赞赏、支付、下单。

因为赞美太廉价,而愿意与他发生交易的才是真正的信任和支持。

码哥到现在已经写了近 23+ 篇 Redis 文章,赠送了很多书籍,收到过许多赞美和少量赞赏,感谢曾经赞赏过我的读者,谢谢。


相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
4天前
|
NoSQL Redis
05- Redis的数据淘汰策略有哪些 ?
Redis 提供了 8 种数据淘汰策略:挥发性 LRU、LFU 和 TTL(针对有过期时间的数据),挥发性随机淘汰,以及全库的 LRU、LFU 随机淘汰,用于在内存不足时选择删除。另外,还有不淘汰策略(no-eviction),允许新写入操作报错而非删除数据。
9 1
|
27天前
|
机器学习/深度学习 算法 Oracle
ICLR 2024:近似最优的最大损失函数量子优化算法
【2月更文挑战第27天】ICLR 2024:近似最优的最大损失函数量子优化算法
26 3
ICLR 2024:近似最优的最大损失函数量子优化算法
C4.
|
1月前
|
算法 程序员 C语言
C语言的选择结构与数据算法
C语言的选择结构与数据算法
C4.
17 0
|
1月前
|
NoSQL 算法 安全
Redlock 算法-主从redis分布式锁主节点宕机锁丢失的问题
Redlock 算法-主从redis分布式锁主节点宕机锁丢失的问题
148 0
|
2月前
|
机器学习/深度学习 数据采集 搜索推荐
Paper Digest | 突破个性化推荐数据稀疏性:长尾增强的图对比学习算法研究
本文提出了一种新的长尾增强的图对比学习方法(LAGCL),该方法促使模型同时兼顾头部节点与尾部节点之间的知识,并通过长尾增强技术来使模型产出更均匀更准确的节点表征,从而改进基于 GNN 的推荐任务。
|
2月前
|
编解码 算法 定位技术
GEE时序——利用sentinel-2(哨兵-2)数据进行地表物候学分析(时间序列平滑法估算和非平滑算法代码)
GEE时序——利用sentinel-2(哨兵-2)数据进行地表物候学分析(时间序列平滑法估算和非平滑算法代码)
58 3
|
5天前
|
NoSQL 安全 Redis
redis内存限制与淘汰策略
Redis内存管理包括限制和淘汰策略。`maxmemory`配置参数决定内存上限,无设置时64位系统默认不限制,可能导致系统资源耗尽,生产环境建议设定合理值。当内存满时,未设置淘汰策略会导致写入错误。Redis提供8种淘汰策略,如LRU(最近最少使用)和LFU(最不经常使用),以及随机或基于过期时间的删除。需根据数据重要性、访问频率和一致性选择合适策略。
10 0
|
12天前
|
存储 缓存 NoSQL
Redis的内存淘汰策略是什么?
【4月更文挑战第2天】Redis内存淘汰策略在内存满时,通过删除旧数据为新数据腾空间。策略包括:volatile-lru/LFU(基于LRU/LFU算法淘汰有过期时间的键),volatile-random/ttl(随机/按TTL淘汰),allkeys-lru/LFU(所有键的LRU/LFU),allkeys-random(随机淘汰所有键),以及noeviction(不淘汰,返回错误)。选择策略要考虑访问模式、数据重要性和性能需求。
|
1月前
|
存储 缓存 算法
从0开始回顾数据结构---LRU,LFU算法
题意解释 请为LFU缓存设计一个数据结构。支持两种操作:get和set。 ● get(key) : 如果key在缓存中,则返回key对应的值;否则返回-1; ● put(key, value): 如果key在缓存中,则更新key对应的值;否则插入(key, value),如果缓存已满,则先删除使用频率最小的key,如果有多个key具有相同的使用频率,则应该删除最久未使用的key。 C++代码 class LFUCache { public: struct Node { Node *left, *right; int key, val;
|
2月前
|
机器学习/深度学习 算法 搜索推荐
【实操】数据扩增:Retinex算法用于图像颜色恢复和对比度增强
【实操】数据扩增:Retinex算法用于图像颜色恢复和对比度增强
29 0
【实操】数据扩增:Retinex算法用于图像颜色恢复和对比度增强