玩转Redis-8种数据淘汰策略及近似LRU、LFU原理

2022-10-27 12:31:13

  《玩转Redis》系列文章主要讲述Redis的基础及中高级应用。本文是《玩转Redis》系列第【14】篇，最新系列文章请前往公众号“zxiaofan”（点我点我）查看，或百度搜索“玩转Redis zxiaofan”（点我点我）即可。

本文关键字：玩转Redis、Redis数据淘汰策略、8种数据淘汰策略、Redis缓存满了怎么办、Redis近似LRU算法、Redis的LFU算法；

往期精选：《玩转Redis-生产环境如何导入、导出及删除大量数据》

大纲

  • 为什么Redis需要数据淘汰机制？
  • Redis的8种数据淘汰策略
  • Redis的近似LRU算法
    • LRU算法原理
    • 近似LRU算法原理（approximated LRU algorithm）
  • Redis的LFU算法
    • LFU与LRU的区别
    • LFU算法原理
  • 小知识
    • 为什么Redis要使用自己的时钟？
    • 如何发现热点key？

1、为什么Redis需要数据淘汰机制？

  众所周知，Redis作为知名内存型NOSQL，极大提升了程序访问数据的性能，高性能互联网应用里，几乎都能看到Redis的身影。为了提升系统性能，Redis也从单机版、主从版发展到集群版、读写分离集群版等等，业界也有诸多著名三方扩展库（如Codis、Twemproxy）。

  阿里云的企业版Redis（Tair）的性能增强型集群版更是“[豪]无人性”，内存容量高达4096 GB 内存，支持约61440000 QPS。Tair混合存储版更是使用内存和磁盘同时存储数据的集群版Redis实例，最高规格为1024 GB内存8192 GB磁盘（16节点）。【援引：https://help.aliyun.com/document_detail/26350.html】

  既然Redis这么牛，那我们就使劲把数据往里面存储吗？

  32G DDR4 内存条大约 900 元，1TB 的 SSD 硬盘大约 1000 元，价格实在悬殊。此外，即使数据量很大，但常用数据其实相对较少，全放内存性价比太低。“二八原则”在这里也是适用的。

  既然内存空间有限，为避免内存写满，就肯定需要进行内存数据淘汰了。

  • 性价比；
  • 内存空间有限；

2、Redis的8种数据淘汰策略

  redis.conf中可配置Redis的最大内存量 maxmemory，如果配置为0，在64位系统下则表示无最大内存限制，在32位系统下则表示最大内存限制为 3 GB。当实际使用内存 mem_used 达到设置的阀值 maxmemory 后，Redis将按照预设的淘汰策略进行数据淘汰。

# redis.conf 最大内存配置示例，公众号 zxiaofan
# 不带单位则 单位是 字节<bytes>

maxmemory 1048576
maxmemory 1048576B
maxmemory 1000KB
maxmemory 100MB
maxmemory 1GB
maxmemory 1000K
maxmemory 100M
maxmemory 1G

  除了在配置文件中修改配置，也可以使用 config 命令动态修改maxmemory。

# redis maxmemory 动态设置及查看命令示例，公众号 zxiaofan

# 动态修改 maxmemory
config set maxmemory 10GB

# 查看 maxmemory
config get maxmemory
info memory | grep maxmemory

redis-cli -h 127.0.01 -p 6379 config get maxmemory

  接下来我们讲讲8种数据淘汰策略，Redis 4.0开始，共有8种数据淘汰机制。

淘汰策略名称 策略含义
noeviction 默认策略，不淘汰数据；大部分写命令都将返回错误（DEL等少数除外）
allkeys-lru 从所有数据中根据 LRU 算法挑选数据淘汰
volatile-lru 从设置了过期时间的数据中根据 LRU 算法挑选数据淘汰
allkeys-random 从所有数据中随机挑选数据淘汰
volatile-random 从设置了过期时间的数据中随机挑选数据淘汰
volatile-ttl 从设置了过期时间的数据中，挑选越早过期的数据进行删除
allkeys-lfu 从所有数据中根据 LFU 算法挑选数据淘汰（4.0及以上版本可用）
volatile-lfu 从设置了过期时间的数据中根据 LFU 算法挑选数据淘汰（4.0及以上版本可用） 
// redis.conf，Redis 6.0.6版本
// 默认策略 是 noeviction，在生产环境建议修改。
# The default is:
#
# maxmemory-policy noeviction

// 在线设置数据淘汰策略 maxmemory-policy

config set maxmemory-policy volatile-lfu

noeviction 涉及的返回错误的写命令包含：
set,setnx,setex,append,incr,decr,rpush,lpush,rpushx,lpushx,linsert,lset,rpoplpush,sadd,sinter,sinterstore,sunion,sunionstore,sdiff,sdiffstore,zadd,zincrby,zunionstore,zinterstore,hset,hsetnx,hmset,hincrby,incrby,decrby,getset,mset,msetnx,exec,sort。

  我们可以看到，除 noeviction 比较特殊外，allkeys 开头的将从所有数据中进行淘汰，volatile 开头的将从设置了过期时间的数据中进行淘汰。淘汰算法又核心分为 lru、random、ttl、lfu 几种。

让我们用一张图来概括：
玩转Redis-8种数据淘汰策略及近似LRU、LFU原理

3、Redis的近似LRU算法

  在了解Redis近似LRU算法前，我们先来了解下原生的LRU算法。

3.1、LRU算法

  LRU（Least Recently Used）最近最少使用。优先淘汰最近未被使用的数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

  LRU底层结构是 hash 表 + 双向链表。hash 表用于保证查询操作的时间复杂度是O(1)，双向链表用于保证节点插入、节点删除的时间复杂度是O(1)。

  为什么是 双向链表而不是单链表呢？单链表可以实现头部插入新节点、尾部删除旧节点的时间复杂度都是O(1)，但是对于中间节点时间复杂度是O(n)，因为对于中间节点c，我们需要将该节点c移动到头部，此时只知道他的下一个节点，要知道其上一个节点需要遍历整个链表，时间复杂度为O(n)。

  LRU GET操作：如果节点存在，则将该节点移动到链表头部，并返回节点值；
  LRU PUT操作：①节点不存在，则新增节点，并将该节点放到链表头部；②节点存在，则更新节点，并将该节点放到链表头部。

  LRU算法源码可参考Leetcode：https://www.programcreek.com/2013/03/leetcode-lru-cache-java/ 。

# LRU 算法 底层结构 伪代码，公众号 zxiaofan

class Node{
    int key;
    int value;
    Node prev;
    Node next;
}

class LRUCache {
    Node head;
    Node tail;
    HashMap<Integer, Node> map = null;
    int cap = 0;
 
    public LRUCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<>();
    }
 
    public int get(int key) {
    }
 
    public void put(int key, int value) {
        // 此处代码注释的 move/add to tail，应该是 to head。
    }
 
    private void removeNode(Node n){
    }
 
    private void offerNode(Node n){
    }
}

【LRU缓存】【hash+双向链表】结构示意图
玩转Redis-8种数据淘汰策略及近似LRU、LFU原理

3.2、近似LRU算法原理（approximated LRU algorithm）

  Redis为什么不使用原生LRU算法？

  • 原生LRU算法需要 双向链表 来管理数据，需要额外内存；
  • 数据访问时涉及数据移动，有性能损耗；
  • Redis现有数据结构需要改造；

  以上内容反过来就可以回答另一个问题：Redis近似LRU算法的优势？

  在Redis中，Redis的key的底层结构是 redisObject，redisObject 中 lru:LRU_BITS 字段用于记录该key最近一次被访问时的Redis时钟 server.lruclock（Redis在处理数据时，都会调用lookupKey方法用于更新该key的时钟）。

  不太理解Redis时钟的同学，可以将其先简单理解成时间戳（不影响我们理解近似LRU算法原理），server.lruclock 实际是一个 24bit 的整数，默认是 Unix 时间戳对 2^24 取模的结果，其精度是毫秒。

# Redis的key的底层结构，源码位于：server.h，公众号 zxiaofan

typedef struct redisObject {
    unsigned type:4; // 类型
    unsigned encoding:4; // 编码
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount; // 引用计数
    void *ptr; // 指向存储实际值的数据结构的指针，数据结构由 type、encoding 决定。
} robj;

server.lruclock 的值是如何更新的呢？

  Redis启动时，initServer 方法中通过 aeCreateTimeEvent 将 serverCron 注册为时间事件（serverCron 是Redis中最核心的定时处理函数）， serverCron 中 则会 触发 更新Redis时钟的方法 server.lruclock = getLRUClock() 。

// Redis 核心定时任务 serverCron，源码位于sercer.c ，公众号zxiaofan

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
  ...
    /* We have just LRU_BITS bits per object for LRU information.
     * So we use an (eventually wrapping) LRU clock.
     *
     * Note that even if the counter wraps it's not a big problem,
     * everything will still work but some object will appear younger
     * to Redis. However for this to happen a given object should never be
     * touched for all the time needed to the counter to wrap, which is
     * not likely.
     *
     * Note that you can change the resolution altering the
     * LRU_CLOCK_RESOLUTION define. */
    server.lruclock = getLRUClock();
    ...
}

  当 mem_used > maxmemory 时，Redis通过 freeMemoryIfNeeded 方法完成数据淘汰。LRU策略淘汰核心逻辑在 evictionPoolPopulate（淘汰数据集合填充） 方法。

Redis 近似LRU 淘汰策略逻辑：

  • 首次淘汰：随机抽样选出【最多N个数据】放入【待淘汰数据池 evictionPoolEntry】；
    • 数据量N：由 redis.conf 配置的 maxmemory-samples 决定，默认值是5，配置为10将非常接近真实LRU效果，但是更消耗CPU；
    • samples：n.样本；v.抽样；
  • 再次淘汰：随机抽样选出【最多N个数据】，只要数据比【待淘汰数据池 evictionPoolEntry】中的【任意一条】数据的 lru 小，则将该数据填充至 【待淘汰数据池】；
    • evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
    • 详见 源码 中 evictionPoolPopulate 方法的注释；
  • 执行淘汰： 挑选【待淘汰数据池】中 lru 最小的一条数据进行淘汰；

  Redis为了避免长时间或一直找不到足够的数据填充【待淘汰数据池】，代码里（dictGetSomeKeys 方法）强制写死了单次寻找数据的最大次数是 [maxsteps = count*10; ]，count 的值其实就是 maxmemory-samples。从这里我们也可以获得另一个重要信息：单次获取的数据可能达不到 maxmemory-samples 个。此外，如果Redis数据量（所有数据 或 有过期时间 的数据）本身就比 maxmemory-samples 小，那么 count 值等于 Redis 中数据量个数。

产品、技术思想互通：市面上很多产品也有类似逻辑，列表页面不强制返回指定的分页数量，调整为人为滑动，每次返回数量并不固定，后台按需异步拉取，对用户而言是连续滑动且无感的。

// 
// 源码位于 server.c，公众号 zxiaofan。
// 1、调用lookupCommand()获取Redis命令，
// 2、检查命令是否可执行（含执行数据淘汰），
// 3、调用 call() 方法执行命令。

int processCommand(client *c) {
...
  if (server.maxmemory && !server.lua_timedout) {
        int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR;
        ...
  }
}

// 源码位于 evict.c，公众号 zxiaofan。
/* This is a wrapper for freeMemoryIfNeeded() that only really calls the
 * function if right now there are the conditions to do so safely:
 *
 * - There must be no script in timeout condition.
 * - Nor we are loading data right now.
 *
 */
int freeMemoryIfNeededAndSafe(void) {
    if (server.lua_timedout || server.loading) return C_OK;
    return freeMemoryIfNeeded();
}

// 源码位于 evict.c
int freeMemoryIfNeeded(void) {
    // Redis内存释放核心逻辑代码
    // 计算使用内存大小；
    // 判断配置的数据淘汰策略，按对应的处理方式处理；
    void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
        ...
    }
}

// 【待淘汰数据池 evictionPoolEntry】填充 evictionPoolPopulate
// 源码位于  evict.c

/* This is an helper function for freeMemoryIfNeeded(), it is used in order
 * to populate the evictionPool with a few entries every time we want to
 * expire a key. Keys with idle time smaller than one of the current
 * keys are added. Keys are always added if there are free entries.
 *
 * We insert keys on place in ascending order, so keys with the smaller
 * idle time are on the left, and keys with the higher idle time on the
 * right. */

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) { 
    // sampledict ：db->dict（从所有数据淘汰时值为 dict） 或 db->expires（从设置了过期时间的数据中淘汰时值为 expires）;
    // pool ： 待淘汰数据池
    // 获取 最多 maxmemory_samples 个数据，用于后续比较淘汰；
    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
}

// // 【待淘汰数据池 evictionPoolEntry】
// 源码位于 evict.c
// EVPOOL_SIZE：【待淘汰数据池】存放的数据个数；
// EVPOOL_CACHED_SDS_SIZE：【待淘汰数据池】存放key的最大长度，大于255将单独申请内存空间，长度小于等于255的key将可以复用初始化时申请的内存空间；
// evictionPoolEntry 在 evictionPoolAlloc() 初始化，而initServer() 将调用evictionPoolAlloc()。

#define EVPOOL_SIZE 16
#define EVPOOL_CACHED_SDS_SIZE 255
struct evictionPoolEntry {
    unsigned long long idle;    /* key的空闲时间 (LFU访问频率的反频率) */
    sds key;                    /* Key name. */
    sds cached;                 /* Cached SDS object for key name. */
    int dbid;                   /* Key DB number. */
};

static struct evictionPoolEntry *EvictionPoolLRU;

4、Redis的LFU算法

LFU：Least Frequently Used，使用频率最少的（最不经常使用的）

  • 优先淘汰最近使用的少的数据，其核心思想是“如果一个数据在最近一段时间很少被访问到，那么将来被访问的可能性也很小”。

4.1、LFU与LRU的区别

  如果一条数据仅仅是突然被访问（有可能后续将不再访问），在 LRU 算法下，此数据将被定义为热数据，最晚被淘汰。但实际生产环境下，我们很多时候需要计算的是一段时间下key的访问频率，淘汰此时间段内的冷数据。

  LFU 算法相比 LRU，在某些情况下可以提升 数据命中率，使用频率更多的数据将更容易被保留。

对比项 近似LRU算法 LFU算法
最先过期的数据 最近未被访问的 最近一段时间访问的最少的
适用场景 数据被连续访问场景 数据在一段时间内被连续访问
缺点 新增key将占据缓存 历史访问次数超大的key淘汰速度取决于lfu-decay-time

4.2、LFU算法原理

  LFU 使用 Morris counter 概率计数器，仅使用几比特就可以维护 访问频率，Morris算法利用随机算法来增加计数，在 Morris 算法中，计数不是真实的计数，它代表的是实际计数的量级。

LFU数据淘汰策略下，redisObject 的 lru:LRU_BITS 字段（24位）将分为2部分存储：

  • Ldt：last decrement time，16位，精度分钟，存储上一次 LOG_C 更新的时间。
  • LOG_C：logarithmic counter，8位，最大255，存储key被访问频率。

注意：

  • LOG_C 存储的是访问频率，不是访问次数；
  • LOG_C 访问频率随时间衰减；
    • 为什么 LOG_C 要随时间衰减？比如在秒杀场景下，热key被访问次数很大，如果不随时间衰减，此部分key将一直存放于内存中。
  • 新对象 的 LOG_C 值 为 LFU_INIT_VAL = 5，避免刚被创建即被淘汰。
          16 bits      8 bits
     +----------------+--------+
     + Last decr time | LOG_C  |
     +----------------+--------+

  详细说明可在源码 evict.c 中 搜索 “LFU (Least Frequently Used) implementation”。

LFU 的核心配置：

  • lfu-log-factor：counter 增长对数因子，调整概率计数器 counter 的增长速度，lfu-log-factor值越大 counter 增长越慢；lfu-log-factor 默认10。
  • lfu-decay-time：衰变时间周期，调整概率计数器的减少速度，单位分钟，默认1。
    • N 分钟未访问，counter 将衰减 N/lfu-decay-time，直至衰减到0；
    • 若配置为0：表示每次访问都将衰减 counter；

  counter 的区间是0-255， 其增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter 增长的越来越慢。Redis 官网提供的在 不同 factor 下，不同命中率 时 counter 的值示例如下：

+--------+------------+------------+------------+------------+------------+
| factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
+--------+------------+------------+------------+------------+------------+
| 0      | 104        | 255        | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 1      | 18         | 49         | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 10     | 10         | 18         | 142        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 100    | 8          | 11         | 49         | 143        | 255        |
+--------+------------+------------+------------+------------+------------+

  不同于 LRU 算法，LFU 算法下 Ldt 的值不是在key被访问时更新，而是在 内存达到 maxmemory 时，触发淘汰策略时更新。

Redis LFU 淘汰策略逻辑：

  • 随机抽样选出N个数据放入【待淘汰数据池 evictionPoolEntry】；
  • 再次淘汰：随机抽样选出【最多N个数据】，更新 Ldt 和 counter 的值，只要 counter 比【待淘汰数据池 evictionPoolEntry】中的【任意一条】数据的 counter 小，则将该数据填充至 【待淘汰数据池】；
    • evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
  • 执行淘汰： 挑选【待淘汰数据池】中 counter 最小的一条数据进行淘汰；

  在讲解近似LRU算法时，提及“Redis在处理数据时，都会调用lookupKey方法用于更新该key的时钟”，回过头来看，更为严谨的说法是“Redis在处理数据时，都会调用lookupKey方法，如果内存淘汰策略是 LFU，则会调用 ‘updateLFU()’ 方法计算 LFU 模式下的 lru 并更新，否则将更新该key的时钟 ‘val->lru = LRU_CLOCK()’”.

// 源码位于 db.c，公众号 zxiaofan。

/* Update LFU when an object is accessed.
 * Firstly, decrement the counter if the decrement time is reached.
 * Then logarithmically increment the counter, and update the access time. */
void updateLFU(robj *val) {
    // 首先 根据当前时间 参考 lfu-decay-time 配置 进行一次衰减；
    unsigned long counter = LFUDecrAndReturn(val);
    // 再参考 lfu_log_factor 配置 进行一次增长；
    counter = LFULogIncr(counter);
    // 更新 lru；
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

Redis 数据淘汰示意图：
玩转Redis-8种数据淘汰策略及近似LRU、LFU原理

5、小知识

5.1、为什么Redis要使用自己的时钟？

  • 获取系统时间戳将调用系统底层提供的方法；
  • 单线程的Redis对性能要求极高，从缓存中获取时间戳将极大提升性能。

5.2、如何发现热点key？

  object freq key 命令支持 获取 key 的 counter，所以我们可以通过 scan 遍历所有key，再通过 object freq 获取counter。

  需要注意的是，执行 object freq 的前提是 数据淘汰策略是 LFU。

127.0.0.1:6379> object freq key1
(error) ERR An LFU maxmemory policy is not selected, access frequency not tracked. Please note that when switching between policies at runtime LRU and LFU data will take some time to adjust.
127.0.0.1:6379> config set maxmemory-policy volatile-lfu
OK
127.0.0.1:6379> object freq key1
(integer) 0
127.0.0.1:6379> get key1
"v1"
127.0.0.1:6379> object freq key1
(integer) 1

  Redis 4.0.3版本也提供了redis-cli的热点key功能，执行"./redis-cli --hotkeys"即可获取热点key。需要注意的是，hotkeys 本质上是 scan + object freq，所以，如果数据量特别大的情况下，可能耗时较长。

>./redis-cli -p 6378 -a redisPassword--hotkeys
Warning: Using a password with '-a' or '-u' option on the command line interface may not be safe.

# Scanning the entire keyspace to find hot keys as well as
# average sizes per key type.  You can use -i 0.1 to sleep 0.1 sec
# per 100 SCAN commands (not usually needed).

[00.00%] Hot key '"key-197804"' found so far with counter 4
[00.00%] Hot key '"key-242392"' found so far with counter 4
[00.00%] Hot key '"key-123994"' found so far with counter 4
[00.00%] Hot key '"key-55821"' ...
...
[03.72%] Hot key '"key1"' found so far with counter 6

-------- summary -------

Sampled 300002 keys in the keyspace!
hot key found with counter: 6	keyname: "key1"
hot key found with counter: 4	keyname: "key-197804"
hot key found with counter: 4	keyname: "key-242392"
hot key found with counter: 4	keyname: "key-123994"
hot key found with counter: 4	keyname: "key-55821"
hot key ...

参考文档：
Using Redis as an LRU cache：https://redis.io/topics/lru-cache；

【玩转Redis系列文章 近期精选 @zxiaofan】

《玩转Redis-生产环境如何导入、导出及删除大量数据》

《玩转Redis-删除了两百万key，为什么内存依旧未释放？》

《玩转Redis-Redis中布隆过滤器的使用及原理》

《玩转Redis-HyperLogLog原理探索》

《玩转Redis-HyperLogLog统计微博日活月活》

公众号搜索【zxiaofan】查阅最新文章。

Life is all about choices！

将来的你一定会感激现在拼命的自己！

【CSDN】【GitHub】【OSCHINA】【掘金】【语雀】【微信公众号】

上一篇：阿里程序员整理的“Redis成长笔记”没学完我就跪了，已入魔


下一篇：操作系统页面置换算法（最佳置换算法，FIFO，LRU，Clock）