redis源码之惰性删除策略分析(一)
2021/6/19 19:27:18
本文主要是介绍redis源码之惰性删除策略分析(一)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
本文浅显的谈谈redis删除key的源码部分，希望本篇文章对于学习redis并且看源码的你能够起到抛砖引玉的作用，并在此记下自己阅读源码的足迹。
本文主要由以下几个部分组成
一、为什么要删除key？
二、内存淘汰的策略主要有哪些？
三、删除key的时机或者说手段有哪些？
四、删除key的源码整体脉络
五、源码的阅读
ANSWER 一
首先，为什么要删除key呢？这是因为redis是基于内存的数据库，计算机的内存容量是有限的，试想你一直往里面写入数据而没有一定的策略去删除你写的数据，内存早晚会被用完的，所以有必要删除删除那些老的数据，给新插入的数据腾挪地方。有的同学可能会说redis集群是可以扩展的，这样我就不用删除旧数据，我可以一直加机器解决内存不足的问题。这种方式显然是行不通的，因为你基于hash的方法分发数据，可能会导致数据失衡，从而导致某台服务器过载。所以就有必要对旧数据(过期key)进行删除。
ANSWER 二
既然要对key进行删除，我们就要有一定的策略进行删除，而不是随意的进行删除。redis中给出了以下策略用于淘汰key
// 根据lru算法删除带有过期时间的key
1】volatile-lru -> remove the key with an expire set using an LRU algorithm
// 根据lru算法删除任意的key
2】allkeys-lru -> remove any key accordingly to the LRU algorithm
// 随机删除带有过期时间的key
3】volatile-random -> remove a random key with an expire set
// 随机删除任何一个key
4】 allkeys-random -> remove a random key, any key
// 删除ttl最近的key
5】 volatile-ttl -> remove the key with the nearest expire time (minor TTL)
// 不删
6】noeviction -> don’t expire at all, just return an error on write operations
问题：你所在的公司用了哪种策略进行key的删除，为什么要用这种策略呢？可以探讨一番。
ANSWER 三
以上说了key的淘汰策略有哪些，也就是我们要删除key的时候要遵守的规则，并按照这个规则执行的key删除。那么策略有了，删除key的时机或者方式有哪些呢？在redis中有三个时机删除key。1、定时删除 2、定期删除 3、惰性删除。 redis目前删除的时机是 定期删除+惰性删除。至于这三个时机有什么优缺点，自己查阅相关书籍就能找到答案【redis设计与实现 P107】
ANSWER 四
本篇文章只讲惰性删除，也就是当执行命令时进行key的删除。这里给出执行命令时删除key的一个大致脉络，也就是函数的调用流程
客户端发送请求，redis服务端最终会调用这个函数处理客户端的命令请求
------------processCommand(redisClient *c)
在处理命令时，会调用这个函数进行内存释放，也就是进行key的删除，返回删除成功or失败
--------------freeMemoryIfNeeded（）
------------evictionPoolPopulate（dict, db->dict, db->eviction_pool）得到要删除的key
---------estimateObjectIdleTime(o) 计算key的过期时间
在对key惰性删除的时候，基本上调用上述四个函数。在讲解具体函数之前，我们还是来熟悉下几个数据结构
/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
typedef struct redisObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 引用计数
int refcount;
// 指向实际值的指针
void *ptr;
} robj;
typedef struct redisDb {
// 数据库键空间，保存着数据库中的所有键值对
dict *dict; /* The keyspace for this DB */
// 键的过期时间，字典的键为键，字典的值为过期事件 UNIX 时间戳
dict *expires; /* Timeout of keys with a timeout set */
// 正处于阻塞状态的键
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */
// 可以解除阻塞的键
dict *ready_keys; /* Blocked keys that received a PUSH */
// 正在被 WATCH 命令监视的键
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */
// 数据库号码
int id; /* Database ID */
// 数据库的键的平均 TTL ，统计信息
long long avg_ttl; /* Average TTL, just for stats */
} redisDb;
这个就是存储要删除key的数据结构
struct evictionPoolEntry {
unsigned long long idle; /* Object idle time. */
sds key; /* Key name. */
};
ANSWER 五
下面我们依次讲解上述的几个函数
/* If this function gets called we already read a whole
* command, arguments are in the client argv/argc fields.
* processCommand() execute the command or prepare the
* server for a bulk read from the client.
*
* 这个函数执行时，我们已经读入了一个完整的命令到客户端，
* 这个函数负责执行这个命令，
* 或者服务器准备从客户端中进行一次读取。
*
* If 1 is returned the client is still alive and valid and
* other operations can be performed by the caller. Otherwise
* if 0 is returned the client was destroyed (i.e. after QUIT).
*
* 如果这个函数返回 1 ，那么表示客户端在执行命令之后仍然存在，
* 调用者可以继续执行其他操作。
* 否则，如果这个函数返回 0 ，那么表示客户端已经被销毁。
*/
int processCommand(redisClient *c) {
/*
* 我在这里删了一些和本次分享无关的一些代码，让我们直接来到这里
* Handle the maxmemory directive.
*
* First we try to free some memory if possible (if there are volatile
* keys in the dataset). If there are not the only thing we can do
* is returning an error. */
// 如果设置了最大内存，那么检查内存是否超过限制，并做相应的操作
// 其中 maxmemory是我们在配置文件中可以设置的，在C语言中只要不等于0就是真
@1 if (server.maxmemory) {
// 如果内存已超过限制，那么尝试通过删除过期键来释放内存
int retval = freeMemoryIfNeeded();
// 如果即将要执行的命令可能占用大量内存（REDIS_CMD_DENYOOM）
// 并且前面的内存释放失败的话
// 那么向客户端返回内存错误
if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
flagTransaction(c);
addReply(c, shared.oomerr);
return REDIS_OK;
}
}
return REDIS_OK;
}
processCommand()这个函数在处理命令时在@1处如果说我们设置了maxmemory那么会调用freeMemoryIfNeeded()这个方法进行内存释放[也就是删除key的操作]，如果释放失败，返回错误。在我们没有分析freeMemoryIfNeeded()之前，如果让我们自己设计一个删除key的函数，想一想都有哪些步骤？我想无非是这样几个步骤：
1、计算目前已经使用了多少内存，需要释放多少内存？假设需要释放的内存为x。
2、遍历redis的每一个库，根据一定的策略【ANSWER2中的6个策略】找出要删除的key
3.删除key，释放内存，计算一下释放的内存是否已经大于等于步骤1中需要释放的内存x，如果达到这个条件本次删除key的任务结束【这里我觉得是考虑到服务性能的问题，想一想步骤1中不设置一个释放内存的阈值会出现什么问题？】。等分析完这个函数后，我会绘制一张流程图。我们现在只分析一种策略，那就是all-keys-lru这种内存淘汰策略
现在让我进入freeMemoryIfNeeded()这个重磅函数
int freeMemoryIfNeeded(void) {
/*
mem_used:已经使用的内存
mem_tofree：需要释放的内存
mem_freed:已经释放的内存
*/
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
// 计算出 Redis 目前占用的内存总数，但有两个方面的内存不会计算在内：
// 1）从服务器的输出缓冲区的内存
// 2）AOF 缓冲区的内存
mem_used = zmalloc_used_memory();
// @1 这部分计算内存的逻辑我们可以略过，无非就是 已经使用的内存-最大内存=需要释放的内存
if (slaves) {
listIter li;
listNode *ln;
listRewind(server.slaves,&li);
while((ln = listNext(&li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
if (server.aof_state != REDIS_AOF_OFF) {
mem_used -= sdslen(server.aof_buf);
mem_used -= aofRewriteBufferSize();
}
/* Check if we are over the memory limit. */
// 如果目前使用的内存大小比设置的 maxmemory 要小，那么无须执行进一步操作
if (mem_used <= server.maxmemory) return REDIS_OK;
// 如果占用内存比 maxmemory 要大，但是 maxmemory 策略为不淘汰，那么直接返回
if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
return REDIS_ERR; /* We need to free memory, but policy forbids. */
/* Compute how much memory we need to free. */
// 计算需要释放多少字节的内存
mem_tofree = mem_used - server.maxmemory;
// 初始化已释放内存的字节数为 0
mem_freed = 0;
// 根据 maxmemory 策略，
// 遍历每个数据库，释放内存【删除key】并记录被释放内存的字节数
// @2已经释放的内存如果>=需要释放的内存 wilie循环终止，释放内存工作【惰性删key工作结束】
while (mem_freed < mem_tofree) {
int j, k, keys_freed = 0;
// @3 遍历所有数据库找出要删除的key，释放内存
for (j = 0; j < server.dbnum; j++) {
long bestval = 0; /* just to prevent warning */
sds bestkey = NULL; // 要删除的最合适的key
dictEntry *de;
redisDb *db = server.db+j; // 第j个数据库
dict *dict; // 数据库的词典，redis数据是键值对，存储在词典中
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
// 如果策略是 allkeys-lru 或者 allkeys-random
// 那么淘汰的目标为所有数据库键
// @4 我们目前就是分析这个策略 all-keys-lru,所以词典就是第j个数据库中全部键值对
dict = server.db[j].dict;
} else {
// 如果策略是 volatile-lru 、 volatile-random 或者 volatile-ttl
// 那么淘汰的目标为带过期时间的数据库键
dict = server.db[j].expires;
}
// 跳过空字典，接着下一次for循环
if (dictSize(dict) == 0) continue;
/* volatile-random and allkeys-random policy */
// 如果使用的是随机策略，那么从目标字典中随机选出键，我们暂时略过个if
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
{
de = dictGetRandomKey(dict);
bestkey = dictGetKey(de);
}
/* volatile-lru and allkeys-lru policy */
// 如果使用的是 LRU 策略，
// @5 那么从一个sample 键中选出 IDLE 时间最长的那个键， 让我重点分析这个分支
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
// @6 pool是一个数组，所有要删除的key按照idle time从小到大排序
// 这个数组在服务启动时进行初始化
struct evictionPoolEntry *pool = db->eviction_pool;
// @7 这个while循环就是要找出第j个数据库中要删除的最合适的key，也就是idle time
// 最长的那个key
while(bestkey == NULL) {
// @8 这个方法就是要找出词典中要删除的key，这些要删除的key
// 以idle time递增的方式保存在 eviction_pool
// 因为我们分析的是 all-keys-lru,它的 sampledict和dict是一样的，这里先不
// 详细解释解释这个函数，稍后我们再分析，只需要记住，他填充eviction_pool，里面是 //字典中需要删除的 key就行了
evictionPoolPopulate(dict, db->dict, db->eviction_pool);
/* Go backward from best to worst element to evict. */
for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
if (pool[k].key == NULL) continue;
de = dictFind(dict,pool[k].key);
/* Remove the entry from the pool. */
// 从数组中删除这个key
sdsfree(pool[k].key);
/* Shift all elements on its right to left. */
// 这个可以忽略，就是调整数组
memmove(pool+k,pool+k+1,
sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
/* Clear the element on the right which is empty
* since we shifted one position to the left. */
pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;
/* If the key exists, is our pick. Otherwise it is
* a ghost and we need to try the next element. */
if (de) {
// @9 返回指定节点的键，说明在第j个数据库中找到这个要删除的最合适的key了
bestkey = dictGetKey(de);
break;
} else {
/* Ghost... */
// 继续遍历
continue;
}
} // 遍历 pool数组的for循环结束
}// 找 第j个数据中最合适的key结束
/* Finally remove the selected key. */
// @10 这一步是真正的删除被选中的键
if (bestkey) {
long long delta;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
// 忽略
propagateExpire(db,keyobj);
/* We compute the amount of memory freed by dbDelete() alone.
* It is possible that actually the memory needed to propagate
* the DEL in AOF and replication link is greater than the one
* we are freeing removing the key, but we can't account for
* that otherwise we would never exit the loop.
*
* AOF and Output buffer memory will be freed eventually so
* we only care about memory used by the key space. */
// 计算删除键所释放的内存数量
delta = (long long) zmalloc_used_memory();
dbDelete(db,keyobj);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
// 对淘汰键的计数器增一
server.stat_evictedkeys++;
// 忽略
notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
keyobj, db->id);
decrRefCount(keyobj);
keys_freed++;
// 忽略
/* When the memory to free starts to be big enough, we may
* start spending so much time here that is impossible to
* deliver data to the slaves fast enough, so we force the
* transmission here inside the loop. */
if (slaves) flushSlavesOutputBuffers();
}
}
// 如果遍历完所有的数据库，删除key的个数为0，则返回错误，这个是快速失败
if (!keys_freed) return REDIS_ERR; /* nothing to free... */
} // end 最外层的while，删除key的工作结束
return REDIS_OK;
}
流程图如下：
至此我们分析完了freeMemoryIfNeeded（），还不算太复杂吧。在分析过程中我删掉了一些无用代码和分支。大家再比照着源码分析一下，相信很快就能掌握它。现在，我们总结下这个函数所做的事情是不是和我们开头所列举的吻合呢？我想应该吻合吧。在分析freeMemoryIfNeeded()这个函数的时候，大家是否还记得有一个pool数组用来盛放要删除的key，还有一个函数evictionPoolPopulate()用来填充pool数组。那它究竟是怎样计算的呢？我们在下篇文章接着进行分析。
总结
学好redis，并用好redis并非那么容易。有时候学习源码并非为了装逼，而是学习作者的思路和其优秀思想并能借鉴之。的确，学习源码能让我们对其内部实现了解一二，在平时看来神秘的东西，通过阅读源码感觉“也不过尔尔”。在信息轰炸和科技日新月异的今天，我们需要自己冷静，需要自己思考，需要自己有独特的判断力，我们不能被别人裹挟着前进，我们更不可能把所有计算机的技术都了如指掌，我们只需要有一方面技术的沉淀就行了，知识都是相似相通的。
这篇关于redis源码之惰性删除策略分析(一)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-18Redis安装入门：新手必读指南
- 2024-11-08阿里云Redis项目实战入门教程
- 2024-11-08阿里云Redis资料：新手入门与初级使用指南
- 2024-11-08阿里云Redis教程：新手入门及实用指南
- 2024-11-07阿里云Redis学习入门：新手必读指南
- 2024-11-07阿里云Redis学习入门：从零开始的操作指南
- 2024-11-07阿里云Redis学习：初学者指南
- 2024-11-06阿里云Redis入门教程：轻松搭建与使用指南
- 2024-11-02Redis项目实战：新手入门教程
- 2024-10-22Redis入门教程：轻松掌握数据存储与操作
