Redis键过期策略

1.1 过期检查方式

定时删除是集中处理,惰性删除是零散处理。

redis 会将每个设置了过期时间的 key 放入到一个独立的字典中,以后会定时遍历这个字典来删除到期的 key。

惰性策略

在客户端访问这个 key 的时候,redis 对 key 的过期时间进行检查,如果过期了就立即删除。

定时扫描策略

Redis 默认会每秒进行十次过期扫描,过期扫描不会遍历过期字典中所有的 key,而是采用了一种简单的贪心策略。

1、从过期字典中随机 20 个 key;

2、删除这 20 个 key 中已经过期的 key;

3、如果过期的 key 比率超过 1/4,那就重复步骤 1;

同时,为了保证过期扫描不会出现循环过度,导致线程卡死现象,扫描时间的上限,默认不会超过 25ms。

从库的过期策略

从库不会进行过期扫描的。主库在 key 到期时,会在 AOF文件里增加一条 del 指令,同步到所有的从库,从库通过执行这条 del 指令来删除过期的key。

指令同步是异步进行的,会出现主从数据的不一致,主库没有的数据在从库里还存在,比如集群环境分布式锁的算法漏洞就是因为这个同步延迟产生的。

1.2 LRU

maxmemory-policy

redis的默认内存淘汰策略为noenviction,当实际内存超出 maxmemory 时,Redis 提供了几种可选策略 (maxmemory-policy) 来让用户自己决定该如何腾出新的空间以继续提供读写服务。此时应该同步修改 maxmemory 和 maxmemory-policy 参数。

1. noeviction 不会继续 写请求 (DEL 请求可以继续服务),读请求可以进行。这样可以保证不会丢失数据,但是会让线上的业务不能持续进行。这是默认的淘汰策略。

2. volatile-lru 尝试淘汰设置了过期时间的 key,最少使用的 key 优先被淘汰。没有设置过期时间的 key 不会被淘汰,这样可以保证需要持久化的数据不会突然丢失。

3.volatile-ttl 跟上面一样,除了淘汰的策略不是 LRU,而是 key 的剩余寿命 ttl 的值,ttl越小越优先被淘汰。

4.volatile-random 跟上面一样,不过淘汰的 key 是过期 key 集合中随机的 key。

5.allkeys-lru 区别于 volatile-lru,这个策略要淘汰的 key 对象是全体的 key 集合,而不只是过期的 key 集合。这意味着没有设置过期时间的 key 也会被淘汰。

6.allkeys-random 跟上面一样,不过淘汰的策略是随机的 key。

volatile-xxx 策略只会针对带过期时间的 key 进行淘汰,allkeys-xxx 策略会对所有的key 进行淘汰。如果你只是拿 Redis 做缓存,那应该使用 allkeys-xxx,客户端写缓存时不必携带过期时间。如果你还想同时使用 Redis 的持久化功能,那就使用 volatile-xxx策略,这样可以保留没有设置过期时间的 key,它们是永久的 key 不会被 LRU 算法淘汰。

LRU 算法

实现 LRU 算法除了需要 key/value 字典外,附加一个链表,链表元素按照一定的顺序排列。

当空间满的时候,会踢掉链表尾部的元素。

当字典的某个元素被访问时,它在链表中的位置会被移动到表头。

链表尾部元素是不被重用的元素,被踢掉。表头的元素就是最近刚刚用过的元素,暂时不会被踢。

近似 LRU 算法

Redis 使用一种近似 LRU 算法,它跟 LRU 算法还不太一样。

原因

LRU算法需要消耗大量的额外的内存,需要对现有的数据结构进行较大的改造。

近似LRU 算法很简单,在现有数据结构的基础上使用随机采样法来淘汰元素,能达到和 LRU算法非常近似的效果。

实现原理

Redis 为实现近似 LRU 算法,它给每个 key 增加了一个额外的小字段,长度是 24 个 bit,也就是最后一次被访问的时间戳。上一节提到处理 key 过期方式分为集中处理和懒惰处理,LRU 淘汰不一样,它的处理方式只有懒惰处理。当 Redis 执行写操作时,发现内存超出 maxmemory,就会执行一次LRU 淘汰算法。这个算法也很简单,就是随机采样出 5(可以配置) 个 key,然后淘汰掉最旧的 key,如果淘汰后内存还是超出 maxmemory,那就继续随机采样淘汰,直到内存低于maxmemory 为止。

如何采样就是看 maxmemory-policy 的配置,如果是 allkeys 就是从所有的 key 字典中随机,如果是 volatile 就从带过期时间的 key 字典中随机。每次采样多少个 key 看的是maxmemory_samples 的配置,默认为 5。

同时 Redis3.0 在算法中增加了淘汰池,进一步提升了近似 LRU 算法的效果。淘汰池是一个数组,它的大小是 maxmemory_samples,在每一次淘汰循环中,新随机出来的 key 列表会和淘汰池中的 key 列表进行融合,淘汰掉最旧的一个 key 之后,保留剩余较旧的 key 列表放入淘汰池中留待下一个循环。

1.3 相关函数

freeMemoryIfNeeded

/* 根据当前的maxmemory设置,定期调用此函数以查看是否有可用的内存。如果超出了内存限制,该函数将尝试释放一些内存以在该限制下返回*。 如果处于内存限制之下或超过了限制,则函数返回C_OK,但是释放内存的尝试成功了。 如果我们超出了内存限制,但是没有足够的内存被释放以在该限制下返回,该函数将返回C_ERR。. */

int freeMemoryIfNeeded(void) {

int keys_freed = 0;

// 副本忽略

if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;

size_t mem_reported, mem_tofree, mem_freed;

mstime_t latency, eviction_latency, lazyfree_latency;

long long delta;

int slaves = listLength(server.slaves);

int result = C_ERR;

 

if (clientsArePaused()) return C_OK;

if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)

return C_OK;

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

 

latencyStartMonitor(latency);

if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)

goto cant_free; // maxmemory 策略为不淘汰,那么直接返回

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

while (mem_freed < mem_tofree) { //每次循环删除一个节点, 循环直到达到水位线以下

int j, k, i;

static unsigned int next_db = 0;

sds bestkey = NULL;

int bestdbid;

redisDb *db;

dict *dict;

dictEntry *de;

 

if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||

server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)

{

struct evictionPoolEntry *pool = EvictionPoolLRU;

 

while(bestkey == NULL) {

unsigned long total_keys = 0, keys;

 

/* 遍历所有字典 dbnum为字典总数 */

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

db = server.db+i;

// 这里需要先指定要进行删除的字典是超时字典还是主字典

dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ?

db->dict : db->expires;

if ((keys = dictSize(dict)) != 0) {

//帮助函数,key过期时用一些条目填充evictionPool。添加了空闲时间小于当前key之一的键。

//如果有空闲条目,则始终添加key。按升序插入键,因此空闲时间较小的键在左侧,而空闲时间较长的键在右侧。

evictionPoolPopulate(i, dict, db->dict, pool);

total_keys += keys;

}

}

if (!total_keys) break; /* No keys to evict. */

 

/* 在eviction_pool找到一个可以删除的的节点 即退出 . */

for (k = EVPOOL_SIZE-1; k >= 0; k--) {

if (pool[k].key == NULL) continue;

bestdbid = pool[k].dbid;

 

if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {

de = dictFind(server.db[pool[k].dbid].dict,

pool[k].key);

} else {

de = dictFind(server.db[pool[k].dbid].expires,

pool[k].key);

}

 

/* Remove the entry from the pool. */

if (pool[k].key != pool[k].cached)

sdsfree(pool[k].key);

pool[k].key = NULL;

pool[k].idle = 0;

 

/* 显然优先删除LRU时间最长的,此时bestkey使我们要删除的元素 */

if (de) {

bestkey = dictGetKey(de);

break;

} else {

/* Ghost... Iterate again. */

}

}

}

}

 

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

else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||

server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)

{

/* When evicting a random key, we try to evict a key for

* each DB, so we use the static 'next_db' variable to

* incrementally visit all DBs. */

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

j = (++next_db) % server.dbnum;

db = server.db+j;

dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ?

db->dict : db->expires;

if (dictSize(dict) != 0) {

de = dictGetRandomKey(dict);

bestkey = dictGetKey(de);

bestdbid = j;

break;

}

}

}

 

/* 删除选择的key */

if (bestkey) {

db = server.db+bestdbid;

robj *keyobj = createStringObject(bestkey,sdslen(bestkey));

propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);

//计算删除键所释放的内存数量

delta = (long long) zmalloc_used_memory();

latencyStartMonitor(eviction_latency);

if (server.lazyfree_lazy_eviction)

dbAsyncDelete(db,keyobj);

else

dbSyncDelete(db,keyobj);

signalModifiedKey(NULL,db,keyobj);

latencyEndMonitor(eviction_latency);

latencyAddSampleIfNeeded("eviction-del",eviction_latency);

delta -= (long long) zmalloc_used_memory();

mem_freed += delta;

// 对淘汰键的计数器增一

server.stat_evictedkeys++;

notifyKeyspaceEvent(NOTIFY_EVICTED, "evicted",

keyobj, db->id);

decrRefCount(keyobj);

keys_freed++;

 

if (slaves) flushSlavesOutputBuffers();

 

if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {

if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {

/* Let's satisfy our stop condition. */

mem_freed = mem_tofree;

}

}

} else {

goto cant_free; /* nothing to free... */

}

}

result = C_OK;

 

cant_free:

....

return result;

}

 

evictionPoolEntry结构

/* 为了提高LRU近似的质量,采用了一组键,它们是在freeMemoryIfNeeded()调用中淘汰的很好的候选者。

eviciton池中的条目按空闲时间排序,将更大的空闲时间放在右边(升序)。

当使用LFU策略时,将使用倒序频率指示而不是空闲时间,因此我们仍会以较大的值退出(*较大的倒序频率意味着将访问频率最低的按键退出)。*/

#define EVPOOL_SIZE 16

#define EVPOOL_CACHED_SDS_SIZE 255

struct evictionPoolEntry {

unsigned long long idle; /* 对象空闲时间(LFU的倒频)*/

sds key; /* Key name. */

sds cached; /* Cached SDS object for key name. */

int dbid; /* Key DB number. */

};

 

evictionPoolPopulate

//以下函数所做的事情就是在sampledict中随机挑选元素,计算LRU,以升序插入pool中

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

int j, k, count;

dictEntry *samples[server.maxmemory_samples];

// 此函数对字典进行采样,以从随机位置返回一些键。

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

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

unsigned long long idle;

sds key;

robj *o;

dictEntry *de;

de = samples[j];

key = dictGetKey(de);

/* 要从中采样的字典不是主字典(而是过期的字典),则需要在密钥字典中再次查找该密钥以获得值对象*/

if (server.maxmemor2y_policy != MAXMEMORY_VOLATILE_TTL) {

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

o = dictGetVal(de);

}

 

/* 根据策略计算空闲时间。仅仅因为代码最初处理LRU,就将其称为"闲置",实际上它只是一个分数,分数越高意味着候选者越好。 */

if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {

idle = estimateObjectIdleTime(o); //计算给定对象的闲置时长

} else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {

/* 当使用LRU策略时,按空闲时间对key进行排序,以便从更长的空闲时间开始使key过期。

但是,当该策略是LFU策略时,有一个频率估计,并且先驱逐频率较低的密钥。因此,在池中,我们使用倒转频率减去实际频率到最大255来放置对象。 */

idle = 255-LFUDecrAndReturn(o);

} else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {

/*在TTL策略下情况下,越早过期越好 */

idle = ULLONG_MAX - (long)dictGetVal(de);

} else {

serverPanic("Unknown eviction policy in evictionPoolPopulate()");

}

 

/* 将元素插入池中。(要根据idle找到合适的位置)

首先,找到第一个空桶或第一个填充的空桶,它们的空闲时间小于我们的空闲时间。*/

k = 0;

while (k < EVPOOL_SIZE &&

pool[k].key &&

pool[k].idle < idle) k++; //找到一个可以插入的位置 保证以LRU时间升序排列

if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {

/* 不需要插入, LRU时间比里面最小的还大 */

continue;

} else if (k < EVPOOL_SIZE && pool[k].key == NULL) {

/*插入到空位置。插入之前无需设置。 */

} else {

/* 插入中间。现在k指向第一个元素大于要插入的元素 */

if (pool[EVPOOL_SIZE-1].key == NULL) {

/* 插入以后我们需要向后移动元素 */

sds cached = pool[EVPOOL_SIZE-1].cached;

memmove(pool+k+1,pool+k,

sizeof(pool[0])*(EVPOOL_SIZE-k-1));

pool[k].cached = cached;

} else {

/*右边没有可用空间, 在k-1处插入 */

k--;

/*将k(包括)左侧的所有元素向左移,因此我们丢弃空闲时间较短的元素。. */

sds cached = pool[0].cached; /* Save SDS before overwriting. */

if (pool[0].key != pool[0].cached) sdsfree(pool[0].key);

memmove(pool,pool+1,sizeof(pool[0])*k);

pool[k].cached = cached;

}

}

 

/* 尝试重用在池条目中分配的缓存的SDS字符串,因为分配和取消分配该对象的成本很高 */

int klen = sdslen(key);

if (klen > EVPOOL_CACHED_SDS_SIZE) {

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

} else {

memcpy(pool[k].cached,key,klen+1);

sdssetlen(pool[k].cached,klen);

pool[k].key = pool[k].cached;

}

pool[k].idle = idle;

pool[k].dbid = dbid;

}

}

 

参考:

<<Redis 深度历险 :核心原理和 和应用实践>> ,

https://blog.csdn.net/weixin_43705457/article/details/105087813

上一篇:Redis过期策略和内存淘汰机制(手写LRU算法)


下一篇:redis的淘汰机制的分享