面试时 Redis 内存淘汰总被问，但是总答不好，怎么解决-CSDN博客

本文链接：https://blog.csdn.net/code8889/article/details/136726187

3.1处，不是本节点处理，直接返回ask，指示客户端转向
4处，判断是否设置了maxMemory，这里就是本文重点：设置了maxMemory时，内存淘汰策略
4.1处，调用了下方的 freeMemoryIfNeeded

接下来，深入4.1处：

int freeMemoryIfNeeded(void) {

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();

if (slaves) {

…

}

if (server.aof_state != REDIS_AOF_OFF) {

mem_used -= sdslen(server.aof_buf);

mem_used -= aofRewriteBufferSize();

}

/* Check if we are over the memory limit. */

//1 如果目前使用的内存大小比设置的 maxmemory 要小，那么无须执行进一步操作

if (mem_used <= server.maxmemory) return REDIS_OK;

//2 如果占用内存比 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. */

// 3 计算需要释放多少字节的内存

mem_tofree = mem_used - server.maxmemory;

// 初始化已释放内存的字节数为 0

mem_freed = 0;

// 根据 maxmemory 策略，

//4 遍历字典，释放内存并记录被释放内存的字节数

while (mem_freed < mem_tofree) {

int j, k, keys_freed = 0;

// 遍历所有字典

for (j = 0; j < server.dbnum; j++) {

long bestval = 0; /* just to prevent warning */

sds bestkey = NULL;

dictEntry *de;

redisDb *db = server.db + j;

dict *dict;

if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||

server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM) {

// 如果策略是 allkeys-lru 或者 allkeys-random

//5 那么淘汰的目标为所有数据库键

dict = server.db[j].dict;

} else {

// 如果策略是 volatile-lru 、 volatile-random 或者 volatile-ttl

//6 那么淘汰的目标为带过期时间的数据库键

dict = server.db[j].expires;

}

/* volatile-random and allkeys-random policy */

// 如果使用的是随机策略，那么从目标字典中随机选出键

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 */

//7

else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||

server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU) {

struct evictionPoolEntry *pool = db->eviction_pool;

while (bestkey == NULL) {

// 8

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;

// 8.1

de = dictFind(dict, pool[k].key);

/* 8.2 Remove the entry from the pool. */

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. */

// 8.3

if (de) {

bestkey = dictGetKey(de);

break;

} else {

/* Ghost… */

continue;

}

/* volatile-ttl */

// 策略为 volatile-ttl ，从一集 sample 键中选出过期时间距离当前时间最接近的键

else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {

…

}

/* Finally remove the selected key. */

// 8.4 删除被选中的键

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++;

…

}

if (!keys_freed) return REDIS_ERR; /* nothing to free… */

}

return REDIS_OK;

}

1处，如果目前使用的内存大小比设置的 maxmemory 要小，那么无须执行进一步操作
2处，如果占用内存比 maxmemory 要大，但是 maxmemory 策略为不淘汰，那么直接返回
3处，计算需要释放多少字节的内存
4处，遍历字典，释放内存并记录被释放内存的字节数
5处，如果策略是 allkeys-lru 或者 allkeys-random 那么淘汰的目标为所有数据库键
6处，如果策略是 volatile-lru 、 volatile-random 或者 volatile-ttl ，那么淘汰的目标为带过期时间的数据库键
7处，如果使用的是 LRU 策略，那么从 sample 键中选出 IDLE 时间最长的那个键
8处，调用evictionPoolPopulate，该函数在下面讲解,该函数的功能是，传入一个链表，即这里的db->eviction_pool，然后在函数内部，随机找出n个key，放入传入的链表中，并按照空闲时间排序，空闲最久的，放到最后。

当该函数，返回后，db->eviction_pool这个链表里就存放了我们要淘汰的key。

8.1处，找到这个key，这个key，在后边会被删除
8.2处，下面这一段，从db->eviction_pool将这个已经处理了的key删掉
8.3处，如果这个key，是存在的，则跳出循环，在后面8.4处，会被删除
8.4处，删除这个key

选择哪些key作为被淘汰的key

前面我们看到，在7处，如果为lru策略，则会进入8处的函数：

evictionPoolPopulate。

该函数的名称为：填充(populate)驱逐(eviction)对象池(pool)。驱逐的意思，就是现在达到了maxmemory，没办法，只能开始删除掉一部分元素，来腾空间了，不然新的put类型的命令，根本没办法执行。

该方法的大概思路是，使用lru的时候，随机找n个key，类似于抽样，然后放到一个链表，根据空闲时间排序。

具体看看该方法的实现：

void evictionPoolPopulate(dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {

其中，传入的第三个参数，是要被填充的对象，在c语言中，习惯传入一个入参，然后在函数内部填充或者修改入参对象的属性。

该属性，就是前面说的那个链表，用来存放收集的随机的元素，该链表中节点的结构如下：

struct evictionPoolEntry {

unsigned long long idle; /* Object idle time. */

sds key; /* Key name. */

};

该结构共2个字段，一个存储key，一个存储空闲时间。

该链表中，共maxmemory-samples个元素，会按照idle时间长短排序，idle时间长的在链表尾部，（假设头在左，尾在右）。

void evictionPoolPopulate(dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {

int j, k, count;

dictEntry *_samples[EVICTION_SAMPLES_ARRAY_SIZE];

dictEntry **samples;

/* Try to use a static buffer: this function is a big hit…

Note: it was actually measured that this helps. */

if (server.maxmemory_samples <= EVICTION_SAMPLES_ARRAY_SIZE) {

samples = _samples;

} else {

samples = zmalloc(sizeof(samples[0]) * server.maxmemory_samples);

}

/* 1 Use bulk get by default. */

count = dictGetRandomKeys(sampledict, samples, server.maxmemory_samples);

// 2

for (j = 0; j < count; j++) {

unsigned long long idle;

sds key;

robj *o;

dictEntry *de;

de = samples[j];

key = dictGetKey(de);

/* If the dictionary we are sampling from is not the main

dictionary (but the expires one) we need to lookup the key
again in the key dictionary to obtain the value object. */

if (sampledict != keydict) de = dictFind(keydict, key);

// 3

o = dictGetVal(de);

// 4

idle = estimateObjectIdleTime(o);

/* 5 Insert the element inside the pool.

First, find the first empty bucket or the first populated
bucket that has an idle time smaller than our idle time. */

k = 0;

while (k < REDIS_EVICTION_POOL_SIZE &&

pool[k].key &&

pool[k].idle < idle)

k++;

…

// 6

pool[k].key = sdsdup(key);

pool[k].idle = idle;

}

if (samples != _samples) zfree(samples);

}

1处，获取 server.maxmemory_samples个key，这里是随机获取的，（dictGetRandomKeys），这个值，默认值为5，放到samples中
2处，遍历返回来的samples
3处，调用如下宏，获取val

he的类型为dictEntry：

哈希表节点

typedef struct dictEntry {

// 键

void *key;

// 值

union {

// 1

void *val;

uint64_t u64;

int64_t s64;

} v;

// 指向下个哈希表节点，形成链表

struct dictEntry *next;

} dictEntry;

所以，这里去

Copy

robj *o;

o = dictGetVal(de);

实际就是获取其v属性中的val,(1处)：

robj *o;

o = dictGetVal(de);

4处，准备计算该val的空闲时间

我们上面3处，看到，获取的o的类型为robj。我们现在看看怎么计算对象的空闲时长：

/* Given an object returns the min number of milliseconds the object was never

requested, using an approximated LRU algorithm. */

unsigned long long estimateObjectIdleTime(robj *o) {

//4.1 获取系统的当前时间

unsigned long long lruclock = LRU_CLOCK();

// 4.2

if (lruclock >= o->lru) {

// 4.3

return (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;

} else {

return (lruclock + (REDIS_LRU_CLOCK_MAX - o->lru)) *

REDIS_LRU_CLOCK_RESOLUTION;

}

这里，4.1处，获取系统的当前时间；

4.2处，如果系统时间，大于对象的lru时间

4.3处，则用系统时间减去对象的lru时间，再乘以单位,换算为毫秒，最终返回的单位，为毫秒(可以看注释。)

#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */

5处，这里拿当前元素，和pool中已经放进去的元素，从第0个开始比较，如果当前元素的idle时长，大于pool中指针0指向的元素，则和pool中索引1的元素比较；直到条件不满足为止。

这句话意思就是，类似于冒泡，把当前元素一直往后冒，直到idle时长小于被比较的元素为止。

6处，把当前元素放进pool中。

经过上面的处理后，链表中存放了全部的抽样元素，且ide时间最长的，在最右边。

对象还有字段存储空闲时间？

前面4处，说到，用系统的当前时间，减去对象的lru时间。

大家看看对象的结构体

typedef struct redisObject {

// 类型

unsigned type:4;

// 编码

unsigned encoding:4;

//1 对象最后一次被访问的时间

unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

// 引用计数

int refcount;

// 指向实际值的指针

void *ptr;

} robj;

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Java工程师，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Java开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频

如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注Java）

架构学习资料

准备两个月，面试五分钟，Java中高级岗面试为何越来越难？

由于篇幅限制小编，pdf文档的详解资料太全面，细节内容实在太多啦，所以只把部分知识点截图出来粗略的介绍，每个小节点里面都有更细化的内容！

robj;

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Java工程师，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Java开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
[外链图片转存中…(img-HKD1yQQm-1710439069771)]
[外链图片转存中…(img-EJKuq6Yt-1710439069773)]
[外链图片转存中…(img-Nit0bbT5-1710439069774)]

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频

如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注Java）
[外链图片转存中…(img-6tqqs2HR-1710439069774)]