> For the complete documentation index, see [llms.txt](https://wtifs.gitbook.io/diva-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wtifs.gitbook.io/diva-notes/redis/shu-ju-tao-tai-ji-zhi.md). # 数据淘汰机制 ## 过期机制 `redis` 的根对象是一个 `redisDb` 结构体。里面有个 `expire` 字段，存储了所有设置了过期时间的 `key`。其中，`key` 是指向 `redisObject` 的指针，`value` 是该键的过期时间 ```c typedef struct redisDb { dict *dict; // 保存所有 kv dict *expires; // 设置了过期时间的 key 及其过期时间 } ``` 因此当我们使用 `EXPIRE key duration` 命令对一个 `key` 设置过期时间时，会将该 `key` 保存到 `expires` 这个字典中，就是说一个 `key` 存了两次，额外占用内存。但这个 `key` 的 `value` 不是实际数据的 `value`，而是过期时间。 ### 过期删除 * 定时过期：给每个设置过期时间的 `key` 都创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好；但是会占用大量的 `CPU` 资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。 * 惰性过期：只有当访问一个 `key` 时，才会判断该 `key` 是否已过期，过期则清除。该策略可以最大化地节省 `CPU` 资源，却对内存非常不友好。 * 定期过期：每隔一定的时间，会扫描一定数量的数据库的 `expires` 字典中一定数量的 `key`，并清除其中已过期的 `key`。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得 `CPU` 和内存资源达到最优的平衡效果。 * `expires` 字典会保存所有设置了过期时间的 `key` 的过期时间数据，扫描时是随机抽样 * 驱逐时检查：`redis` 空间满时，会触发数据淘汰，也会检查过期的 `key` 并将其删除。 `redis` 使用的是惰性过期 + 定期过期 + 驱逐时检查的三种策略。 ## 数据淘汰机制 ### 简介 `redis` 可以通过 `maxmemory ` 配置项来设置允许用户使用的最大内存大小，当内存数据集大小达到一定的大小时，就会根据 `maxmemory-policy noeviction` 配置项配置的策略来进行数据淘汰/驱逐。 `redis 5.0` 提供了 8 种数据淘汰策略： * `volatile-lfu` 从已设置过期时间的数据集（server.db\[i].expires）中挑选使用频率最低的数据淘汰 * `volatile-lru` 从已设置过期时间的数据集中挑选最近最少使用的数据淘汰 * `volatile-random` 从已设置过期时间的数据集中任意选择数据淘汰 * `volatile-ttl` 从已设置过期时间的数据集中挑选将要过期的数据淘汰 * `allkeys-lfu` 从所有数据（server.db\[i].dict）中挑选最近最少使用的数据淘汰 * `allkeys-lru` 从所有数据中挑选使用频率最低的数据淘汰 * `allkeys-random` 从所有数据中任意选择数据淘汰 * `noeviction` 禁止驱逐数据，永远不过期。此时会拒绝写操作，对写操作返回一个错误，默认为该项 ### 淘汰机制在 `redisobject` 中都会为每个 `redis` 对象设置最近访问时间，每次访问的时候都会更新 `redisObject.lru`。 ```c /* A redis object, that is a type able to hold a string / list / set */ /* The actual Redis Object */ #define REDIS_LRU_BITS 24 #define REDIS_LRU_CLOCK_MAX ((1<lru */ #define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */ 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; ``` 而 `redisDb` 中，`dict` 字段保存了所有对象，`expires` 字段保存了所有设置了 `TTL` 的对象。淘汰数据时，根据策略从这两个哈希表里挑选对象删除 ```c /* Redis database representation. There are multiple databases identified * by integers from 0 (the default database) up to the max configured * database. The database number is the 'id' field in the structure. */ typedef struct redisDb { dict *dict; // 保存所有 key dict *expires; // 设置了过期时间的 key 及其过期时间 dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */ dict *ready_keys; /* Blocked keys that received a PUSH */ dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */ struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */ int id; /* Database ID */ long long avg_ttl; /* Average TTL, just for stats */ } redisDb; ``` #### LRU数据淘汰机制该淘汰机制是这样的：在数据集中随机挑选几个键值对，取出其中 `lru` 最大的键值对进行淘汰。 `redis` 并不是保证取得所有数据集中最近最少使用（LRU）的键值对，而只是随机挑选的几个键值对中的。以下是定时任务,每秒调用 `server.hz` 次，主要异步做一些相应的操作，例如： * 淘汰过期 key * 软件监控 * 更新一些统计信息 * 如果有哈希表在搬迁，协助搬迁 * 触发 `BGSAVE/AOF` 写等持久化操作 * 不同种类的客户端超时 * 复制同步重连接 #### TTL数据淘汰机制和 `LRU` 数据淘汰机制类似，`TTL` 数据淘汰机制是这样的：从过期时间 `redisDB.expires` 表中随机挑选几个键值对，取出其中 `TTL` 最近的键值对淘汰。同样你会发现，`redis` 并不是保证取得所有过期时间的表中最快过期的键值对，而只是从中随机挑选几个选 `TTL` 最近的。 #### 数据淘汰过程 `redis` 每次执行写命令的时候，都会检测使用的内存是否超额，如果超额则进行数据淘汰，即在执行读写的时间才会进行数据淘汰。 `processCommand()` 函数在执行命令的时候会检测内存使用情况，这时会调用 `freeMemoryIfNeeded()` 函数来进行淘汰，该函数主要是释放足够的内存来保持 `redis` 在其配置内存限制之内，他计算需要释放多少内存，然后进入循环选择最合适的键进行删除，不断删除，直到空间占用小于 `maxmemory` 为止。 ### 源码这段建议跳过 ```c int freeMemoryIfNeeded(void) { if (mem_used <= server.maxmemory) return REDIS_OK; // 如果已经使用的没有达到上限，则直接返回ok if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION) // NO EVICTION 策略，直接报错返回 return REDIS_ERR; mem_tofree = mem_used - server.maxmemory; // 计算需要释放多少内存 mem_freed = 0; latencyStartMonitor(latency); while (mem_freed < mem_tofree) { // 选择最合适的key释放内存直到达到了需要的内存为止 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; // 判断淘汰策略是否与过期key有关,即从哪个哈希表找相应的key if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU || server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM) { dict = server.db[j].dict; // ALLKEYS 类的策略查 dict } else { dict = server.db[j].expires; // VOTILE 类的策略查 expires } if (dictSize(dict) == 0) continue; // RANDOM 类策略，就随机选 key 出来删除 if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM || server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM) { de = dictGetRandomKey(dict); bestkey = dictGetKey(de); } // LRU 类的策略 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) { 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. */ 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) { bestkey = dictGetKey(de); break; } else { /* Ghost... */ continue; } } } } // TTL 类的策略 else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) { for (k = 0; k < server.maxmemory_samples; k++) { sds thiskey; long thisval; de = dictGetRandomKey(dict); thiskey = dictGetKey(de); thisval = (long) dictGetVal(de); /* Expire sooner (minor expire unix timestamp) is better * candidate for deletion */ if (bestkey == NULL || thisval < bestval) { bestkey = thiskey; bestval = thisval; } } } // 最后删除选择的key /* Finally remove the selected key. */ 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(); latencyStartMonitor(eviction_latency); dbDelete(db,keyobj); latencyEndMonitor(eviction_latency); latencyAddSampleIfNeeded("eviction-del",eviction_latency); latencyRemoveNestedEvent(latency,eviction_latency); 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(); } } if (!keys_freed) { latencyEndMonitor(latency); latencyAddSampleIfNeeded("eviction-cycle",latency); return REDIS_ERR; /* nothing to free... */ } } latencyEndMonitor(latency); latencyAddSampleIfNeeded("eviction-cycle",latency); return REDIS_OK; } ``` **问题** 注意，使用 `SET key val` 命令修改数据会清除原数据的过期时间 **参考** > [bingbo - Redis数据淘汰机制](https://github.com/bingbo/blog/wiki/Redis%E6%95%B0%E6%8D%AE%E6%B7%98%E6%B1%B0%E6%9C%BA%E5%88%B6)