玩转Redis-8种数据淘汰策略及近似LRU、LFU原理
此⽂转载⾃：my.oschina/zxiaofan/blog/4765393
>  《玩转Redis》系列⽂章主要讲述Redis的基础及中⾼级应⽤。本⽂是《玩转Redis》系列第【14】篇，最新系列⽂章请前往查看，或即可。
本⽂关键字：玩转Redis、Redis数据淘汰策略、8种数据淘汰策略、Redis缓存满了怎么办、Redis近似LRU算法、Redis的LFU算法；
往期精选：
⼤纲
为什么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这么⽜，那我们就使劲把数据往⾥⾯存储吗？
  32G DDR4 内存条⼤约 900 元，1TB 的 SSD 硬盘⼤约 1000 元，价格实在悬殊。此外，即使数据量很⼤，但常⽤数据其实相对较少，全放内存性价⽐太低。“⼆⼋原则”在这⾥也是适⽤的。
  既然内存空间有限，为避免内存写满，就肯定需要进⾏内存数据淘汰了。
性价⽐；
内存空间有限；
2、Redis的8种数据淘汰策略
  f中可配置Redis的最⼤内存量 maxmemory，如果配置为0，在64位系统下则表⽰⽆最⼤内存限制，在32位系统下则表⽰最⼤内存限制为 3 GB。当实际使⽤内存 mem_used 达到设置的阀值 maxmemory 后，Redis将按照
预设的淘汰策略进⾏数据淘汰。
# f 最⼤内存配置⽰例， 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及以上版本可⽤）
// f，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 ⼏种。
让我们⽤⼀张图来概括：
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 算法底层结构伪代码， 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+双向链表】结构⽰意图
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 注册为时间事件（serverCr
on 是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：由 f 配置的 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算法redis支持的五种数据类型
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 数据淘汰⽰意图：
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 ...
【玩转Redis系列⽂章近期精选 @zxiaofan】
扫码关注【@zxiaofan】查阅最新⽂章。Life is all about choices！
将来的你⼀定会感激现在拼命的⾃⼰！
【】【】【】【】【】
</integer,></bytes>

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。