溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Redis中的過期刪除策略和內存淘汰機制是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Redis中的過期刪除策略和內存淘汰機制是什么”吧！
Redis 中提供了三種過期刪除的策略
在設置某個 key 的過期時間同時，我們創建一個定時器，讓定時器在該過期時間到來時，立即執行對其進行刪除的操作。
優點：
通過使用定時器，可以保證過期 key 可以被盡快的刪除，并且釋放過期 key 所占用的內存
缺點：
對 CPU 是不友好的，當過期鍵比較多的時候，刪除過期 key 會占用相當一部分的 CPU 資源，對服務器的響應時間和吞吐量造成影響。
惰性刪除，當一個鍵值對過期的時候，只有再次用到這個鍵值對的時候才去檢查刪除這個鍵值對，也就是如果用不著，這個鍵值對就會一直存在。
優點：
對 CPU 是友好的，只有在取出鍵值對的時候才會進行過期檢查，這樣就不會把 CPU 資源花費在其他無關緊要的鍵值對的過期刪除上。
缺點：
如果一些鍵值對永遠不會被再次用到，那么將不會被刪除，最終會造成內存泄漏，無用的垃圾數據占用了大量的資源，但是服務器卻不能去刪除。
看下源碼
// https://github.com/redis/redis/blob/6.2/src/db.c#L1541
// 當訪問到 key 的時候，會調用這個函數，因為有的 key 雖然已經過期了，但是還可能存在于內存中
// key 仍然有效，函數返回值為0，否則，如果 key 過期，函數返回1。
int expireIfNeeded(redisDb *db, robj *key) {
// 沒有過期
if (!keyIsExpired(db,key)) return 0;
// 從庫的過期是主庫控制的，是不會進行刪除操作的
// 上面已經判斷過是否到期了，所以這里的 key 肯定是過期的 key ,不過如果是主節點創建的 key 從節點就不刪除，只會返回已經過期了
if (server.masterhost != NULL) return 1;
...
/* Delete the key */
// 刪除 key
deleteExpiredKeyAndPropagate(db,key);
return 1;
}可以看到每次操作對應的 key 是會檢查 key 是否過期，如果過期則會刪除對應的 key 。
如果過期鍵是主庫創建的，那么從庫進行檢查是不會進行刪除操作的,只是會根據 key 的過期時間返回過期或者未過期的狀態。
定期刪除是對上面兩種刪除策略的一種整合和折中
每個一段時間就對一些 key 進行采樣檢查，檢查是否過期，如果過期就進行刪除
1、采樣一定個數的key，采樣的個數可以進行配置，并將其中過期的 key 全部刪除；
2、如果過期 key 的占比超過可接受的過期 key 的百分比，則重復刪除的過程，直到過期key的比例降至可接受的過期 key 的百分比以下。
優點：
定期刪除，通過控制定期刪除執行的時長和頻率，可以減少刪除操作對 CPU 的影響，同時也能較少因過期鍵帶來的內存的浪費。
缺點：
執行的頻率不太好控制
頻率過快對 CPU 不友好，如果過慢了就會對內存不太友好，過期的鍵值對不能及時的被刪除掉
同時如果一個鍵值對過期了，但是沒有被刪除，這時候業務再次獲取到這個鍵值對，那么就會獲取到被刪除的數據了，這肯定是不合理的。
看下源碼實現
// https://github.com/redis/redis/blob/6.2/src/server.c#L1853
// 這個函數處理我們需要在Redis數據庫中增量執行的“后臺”操作，例如活動鍵過期，調整大小，重哈希。
void databasesCron(void) {
// 通過隨機抽樣來過期
// 這里區分了主節點和從節點的處理
if (server.active_expire_enabled) {
if (iAmMaster()) {
activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
} else {
expireSlaveKeys();
}
}
...
}
// https://github.com/redis/redis/blob/6.2/src/expire.c#L113
void activeExpireCycle(int type) {
// 根據配置的超時工作調整運行參數。默認工作量為1，最大可配置工作量為10
unsigned long
effort = server.active_expire_effort-1, /* Rescale from 0 to 9. */
// 采樣的 key 的數量
config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
// 占比CPU時間，默認是25%，最大43%，如果是100%，那除了定時刪除其他的工作都做不了了，所以要做限制
config_cycle_slow_time_perc = ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC +
2*effort,
// 可接受的過期 key 的百分比
config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE-
effort;
...
//慢速定期刪除的執行時長
timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;
timelimit_exit = 0;
...
// 在 key 過期時積累一些全局統計信息，以便了解邏輯上已經過期但仍存在于數據庫中的 key 的數量
long total_sampled = 0;
long total_expired = 0;
for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
...
// 如果超過 config_cycle_acceptable_stale 的key過期了，則重復刪除的過程，直到過期key的比例降至 config_cycle_acceptable_stale 以下。
// 存儲在 config_cycle_acceptable_stale 中的百分比不是固定的，而是取決于Redis配置的“expire efforce”
do {
/* If there is nothing to expire try next DB ASAP. */
if ((num = dictSize(db->expires)) == 0) {
db->avg_ttl = 0;
break;
}
...
// 采樣的 key 的數量
if (num > config_keys_per_loop)
num = config_keys_per_loop;
...
while (sampled < num && checked_buckets < max_buckets) {
for (int table = 0; table < 2; table++) {
...
while(de) {
/* Get the next entry now since this entry may get
* deleted. */
dictEntry *e = de;
de = de->next;
ttl = dictGetSignedIntegerVal(e)-now;
// 過期檢查，并對過期鍵進行刪除
if (activeExpireCycleTryExpire(db,e,now)) expired++;
...
}
}
db->expires_cursor++;
}
...
// 判斷過期 key 的占比是否大于 config_cycle_acceptable_stale，如果大于持續進行過期 key 的刪除
} while (sampled == 0 ||
(expired*100/sampled) > config_cycle_acceptable_stale);
}
...
}
// 檢查刪除由從節點創建的有過期的時間的 key
void expireSlaveKeys(void) {
// 從主庫同步的 key，過期時間由主庫維護，主庫同步 DEL 操作到從庫。
// 從庫如果是 READ-WRITE 模式，就可以繼續寫入數據。從庫自己寫入的數據就需要自己來維護其過期操作。
if (slaveKeysWithExpire == NULL ||
dictSize(slaveKeysWithExpire) == 0) return;
...
}惰性刪除過程
1、固定的時間執行一次定期刪除；
2、采樣一定個數的key，采樣個數可以進行配置，并將其中過期的key全部刪除；
3、如果過期 key 的占比超過可接受的過期 key 的百分比，則重復刪除的過程，直到過期key的比例降至可接受的過期 key 的百分比以下；
4、對于從庫創建的過期 key 同樣從庫是不能進行刪除的。
上面討論的三種策略，都有或多或少的問題。Redis 中實際采用的策略是惰性刪除加定期刪除的組合方式。
組合方式的使用
定期刪除，獲取 CPU 和 內存的使用平衡，針對過期的 KEY 可能得不到及時的刪除，當 KEY 被再次獲取的時候，通過惰性刪除再做一次過期檢查，來避免業務獲取到過期內容。
從上面惰性刪除和定期刪除的源碼閱讀中，我們可以發現，從庫對于主庫的過期鍵是不能主動進行刪除的。如果一個主庫創建的過期鍵值對，已經過期了，主庫在進行定期刪除的時候，沒有及時的刪除掉，這時候從庫請求了這個鍵值對，當執行惰性刪除的時候，因為是主庫創建的鍵值對，這時候是不能在從庫中刪除的，那么是不是就意味著從庫會讀取到已經過期的數據呢？
答案肯定不是的
how-redis-replication-deals-with-expires-on-keys
How Redis replication deals with expires on keys
Redis expires allow keys to have a limited time to live. Such a feature depends on the ability of an instance to count the time, however Redis slaves correctly replicate keys with expires, even when such keys are altered using Lua scripts.
To implement such a feature Redis cannot rely on the ability of the master and slave to have synchronized clocks, since this is a problem that cannot be solved and would result into race conditions and diverging data sets, so Redis uses three main techniques in order to make the replication of expired keys able to work:
1.Slaves don’t expire keys, instead they wait for masters to expire the keys. When a master expires a key (or evict it because of LRU), it synthesizes a DEL command which is transmitted to all the slaves.
2.However because of master-driven expire, sometimes slaves may still have in memory keys that are already logically expired, since the master was not able to provide the DEL command in time. In order to deal with that the slave uses its logical clock in order to report that a key does not exist only for read operations that don’t violate the consistency of the data set (as new commands from the master will arrive). In this way slaves avoid to report logically expired keys are still existing. In practical terms, an HTML fragments cache that uses slaves to scale will avoid returning items that are already older than the desired time to live.
3.During Lua scripts executions no keys expires are performed. As a Lua script runs, conceptually the time in the master is frozen, so that a given key will either exist or not for all the time the script runs. This prevents keys to expire in the middle of a script, and is needed in order to send the same script to the slave in a way that is guaranteed to have the same effects in the data set.
Once a slave is promoted to a master it will start to expire keys independently, and will not require any help from its old master.
上面是官方文檔中針對這一問題的描述
大概意思就是從節點不會主動刪除過期鍵，從節點會等待主節點觸發鍵過期。當主節點觸發鍵過期時，主節點會同步一個del命令給所有的從節點。
因為是主節點驅動刪除的，所以從節點會獲取到已經過期的鍵值對。從節點需要根據自己本地的邏輯時鐘來判斷減值是否過期，從而實現數據集合的一致性讀操作。
我們知道 Redis 中的過期策略是惰性刪除和定期刪除，所以每個鍵值的操作，都會使用惰性刪除來檢查是否過期，然后判斷是否可以進行刪除
// https://github.com/redis/redis/blob/6.2/src/db.c#L1541
// 當訪問到 key 的時候，會調用這個函數，因為有的 key 雖然已經過期了，但是還可能存在于內存中
// key 仍然有效，函數返回值為0，否則，如果 key 過期，函數返回1。
int expireIfNeeded(redisDb *db, robj *key) {
// 檢查 key 是否過期
if (!keyIsExpired(db,key)) return 0;
// 從庫的過期是主庫控制的，是不會進行刪除操作的
// 上面已經判斷過是否到期了，所以這里的 key 肯定設計過期的 key ,不過如果是主節點創建的 key 從節點就不刪除，只會返回已經過期了
if (server.masterhost != NULL) return 1;
...
/* Delete the key */
// 刪除 key
deleteExpiredKeyAndPropagate(db,key);
return 1;
}
// https://github.com/redis/redis/blob/6.2/src/db.c#L1485
/* Check if the key is expired. */
int keyIsExpired(redisDb *db, robj *key) {
// 過期時間
mstime_t when = getExpire(db,key);
mstime_t now;
// 沒有過期
if (when < 0) return 0; /* No expire for this key */
/* Don't expire anything while loading. It will be done later. */
if (server.loading) return 0;
// lua 腳本執行的過程中不過期
if (server.lua_caller) {
now = server.lua_time_snapshot;
}
// 如果我們正在執行一個命令，我們仍然希望使用一個不會改變的引用時間:在這種情況下，我們只使用緩存的時間，我們在每次調用call()函數之前更新。
// 這樣我們就避免了RPOPLPUSH之類的命令，這些命令可能會重新打開相同的鍵多次，如果下次調用會看到鍵過期，則會使已經打開的對象在下次調用中失效，而第一次調用沒有。
else if (server.fixed_time_expire > 0) {
now = server.mstime;
}
// 其他情況下，獲取最新的時間
else {
now = mstime();
}
// 判斷是否過期了
return now > when;
}
// 返回指定 key 的過期時間，如果沒有過期則返回-1
long long getExpire(redisDb *db, robj *key) {
dictEntry *de;
/* No expire? return ASAP */
if (dictSize(db->expires) == 0 ||
(de = dictFind(db->expires,key->ptr)) == NULL) return -1;
/* The entry was found in the expire dict, this means it should also
* be present in the main dict (safety check). */
serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
return dictGetSignedIntegerVal(de);
}上面的惰性刪除，對于主節點創建的過期 key ，雖然不能進行刪除的操作，但是可以進行過期時間的判斷，所以如果主庫創建的過期鍵，如果主庫沒有及時進行刪除，這時候從庫可以通過惰性刪除來判斷鍵值對的是否過期，避免讀取到過期的內容。
上面我們討論的 Redis 過期策略指的是 Redis 使用那種策略，來刪除已經過期的鍵值對。但是有一些 key以后永遠用不到了，那么就可能一直不能被刪除掉，還有就是 Redis 中的使用過程中，隨著寫數據的增加，Redis 中的內存不夠用了，這時候就需要 Redis 的內存淘汰策略了。
Redis 過期策略指的是 Redis 使用那種策略，來刪除已經過期的鍵值對；
Redis 內存淘汰機制指的是，當 Redis 運行內存已經超過 Redis 設置的最大內存之后，將采用什么策略來刪除符合條件的鍵值對，以此來保障 Redis 高效的運行。
Redis 中的內存只有達到了閥值，才會觸發內存淘汰算法,這個閥值就是我們設置的最大運行內存，在配置文件redis.conf中，通過參數 maxmemory <bytes> 來設置
查詢最大運行內存
127.0.0.1:6379> config get maxmemory 1) "maxmemory" 2) "0"
在 64 位操作系統中，當 maxmemory 為 0 時，表示沒有內存大小限制，32位的系統。
當現有內存大于 maxmemory 時，便會觸發redis主動淘汰內存方式，通過設置 maxmemory-policy ，有如下幾種淘汰方式：
1、volatile-lru:淘汰所有設置了過期時間的鍵值中最久未使用的鍵值；
2、allkeys-lru:淘汰整個鍵值中最久未使用的鍵值；
3、volatile-random:隨機淘汰設置了過期時間的任意鍵值；
4、allkeys-random:隨機淘汰任意鍵值;
5、volatile-ttl:優先淘汰更早過期的鍵值;
6、noeviction:不淘汰任何數據，當內存不足時，新增操作會報錯，Redis 默認內存淘汰策略；
其中 allkeys-xxx 表示從所有的鍵值中淘汰數據，而 volatile-xxx 表示從設置了過期鍵的鍵值中淘汰數據。
除了隨機刪除和不刪除之外，主要有兩種淘汰算法：LRU 算法和 LFU 算法。
LRU 全稱是Least Recently Used譯為最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。
一般 LRU 算法的實現基于鏈表結構，鏈表中的元素按照操作順序從前往后排列，最新操作的鍵會被移動到表頭，當需要內存淘汰時，只需要刪除鏈表尾部的元素即可。
Redis 使用的是一種近似 LRU 算法，目的是為了更好的節約內存，它的實現方式是給現有的數據結構添加一個額外的字段，用于記錄此鍵值的最后一次訪問時間，Redis 內存淘汰時，會使用隨機采樣的方式來淘汰數據，它是隨機取 5 個值（此值可配置），然后淘汰最久沒有使用的那個。
這里看下是如何實現的呢
Redis 在源碼中對于每個鍵值對中的值，會使用一個 redisObject 結構體來保存指向值的指針，這里先來看下 redisObject 的結構
// https://github.com/redis/redis/blob/6.2/src/server.h#L673
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
// 這里保存
// LRU時間(相對于全局LRU時鐘)
// LFU數據 (低 8 bits 作為計數器,用 24 bits 中的高 16 bits，記錄訪問的時間戳)
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;
} robj;當一個鍵值對被創建的時候，就會記錄下更新的時間
// https://github.com/redis/redis/blob/6.2/src/object.c#L41
robj *createObject(int type, void *ptr) {
robj *o = zmalloc(sizeof(*o));
o->type = type;
o->encoding = OBJ_ENCODING_RAW;
o->ptr = ptr;
o->refcount = 1;
// 如果緩存替換策略是LFU，那么將lru變量設置為LFU的計數值
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
// 如果是 lru
// 調用LRU_CLOCK函數獲取LRU時鐘值
o->lru = LRU_CLOCK();
}
return o;
}同時一個鍵值對被訪問的時候記錄的時間也會被更新，當一個鍵值對被訪問時，訪問操作最終都會調用 lookupKey 函數。
// https://github.com/redis/redis/blob/6.2/src/db.c#L63
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
/* Update the access time for the ageing algorithm.
* Don't do it if we have a saving child, as this will trigger
* a copy on write madness. */
if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
// 使用 LRU 更新 lru 的時間
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}上面我們分別看了，創建和訪問一個鍵值對的代碼，每次操作，redisObject 中記錄的 lru 時間就會被同步的更新
Redis 會判斷當前內存的使用情況，如果超過了 maxmemory 配置的值，就會觸發新的內存淘汰了
如果內存超過了 maxmemory 的值，這時候還需要去計算需要釋放的內存量，這個釋放的內存大小等于已使用的內存量減去 maxmemory。不過，已使用的內存量并不包括用于主從復制的復制緩沖區大小。
// https://github.com/redis/redis/blob/6.2/src/evict.c#L512
int performEvictions(void) {
...
while (mem_freed < (long long)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;
/* We don't want to make local-db choices when expiring keys,
* so to start populate the eviction pool sampling keys from
* every DB. */
// 根據淘汰策略，決定使用全局哈希表還是設置了過期時間的key的哈希表
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) {
// 將選擇的哈希表dict傳入evictionPoolPopulate函數，同時將全局哈希表也傳給evictionPoolPopulate函數
evictionPoolPopulate(i, dict, db->dict, pool);
total_keys += keys;
}
}
...
}
}
...
}
// 用來填充evictionPool
// 按升序插入鍵，所以空閑時間小的鍵在左邊，空閑時間高的鍵在右邊。
// https://github.com/redis/redis/blob/6.2/src/evict.c#L145
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++) {
...
// 將元素插入池中。 首先，找到第一個空閑時間小于我們空閑時間的空桶或第一個填充的桶。
k = 0;
while (k < EVPOOL_SIZE &&
pool[k].key &&
pool[k].idle < idle) k++;
if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
/* Can't insert if the element is < the worst element we have
* and there are no empty buckets. */
continue;
} else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
/* Inserting into empty position. No setup needed before insert. */
} else {
/* Inserting in the middle. Now k points to the first element
* greater than the element to insert. */
if (pool[EVPOOL_SIZE-1].key == NULL) {
/* Free space on the right? Insert at k shifting
* all the elements from k to end to the right. */
/* Save SDS before overwriting. */
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 {
/* No free space on right? Insert at k-1 */
k--;
/* Shift all elements on the left of k (included) to the
* left, so we discard the element with smaller idle time. */
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;
}
}
...
}
}處理淘汰的數據，Redis 中提供了一個數組 EvictionPoolLRU，用來保存待淘汰的候選鍵值對。這個數組的元素類型是 evictionPoolEntry 結構體，該結構體保存了待淘汰鍵值對的空閑時間 idle、對應的 key 等信息。
可以看到上面的上面會選取一定的過期鍵，然后插入到 EvictionPoolLRU 中
dictGetSomeKeys 函數采樣的 key 的數量，是由 redis.conf 中的配置項 maxmemory-samples 決定的，該配置項的默認值是 5
// https://github.com/redis/redis/blob/6.2/src/evict.c#L55
struct evictionPoolEntry {
// 待淘汰的鍵值對的空閑時間
unsigned long long idle; /* Object idle time (inverse frequency for LFU) */
// 待淘汰的鍵值對的key
sds key; /* Key name. */
// 緩存的SDS對象
sds cached; /* Cached SDS object for key name. */
// 待淘汰鍵值對的key所在的數據庫ID
int dbid; /* Key DB number. */
};
static struct evictionPoolEntry *EvictionPoolLRU;然后通過 evictionPoolPopulate 函數，進行采樣，然后將采樣數據寫入到 EvictionPoolLRU 中，插入到 EvictionPoolLRU 中的數據是按照空閑時間從小到大進行排好序的
freeMemoryIfNeeded 函數會遍歷一次 EvictionPoolLRU 數組，從數組的最后一個 key 開始選擇，如果選到的 key 不是空值，那么就把它作為最終淘汰的 key。
// https://github.com/redis/redis/blob/6.2/src/evict.c#L512
int performEvictions(void) {
if (!isSafeToPerformEvictions()) return EVICT_OK;
int keys_freed = 0;
size_t mem_reported, mem_tofree;
long long mem_freed; /* May be negative */
mstime_t latency, eviction_latency;
long long delta;
int slaves = listLength(server.slaves);
int result = EVICT_FAIL;
if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
return EVICT_OK;
...
while (mem_freed < (long long)mem_tofree) {
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;
...
/* Go backward from best to worst element to evict. */
// 從數組最后一個key開始查找
for (k = EVPOOL_SIZE-1; k >= 0; k--) {
// 當前key為空值，則查找下一個key
if (pool[k].key == NULL) continue;
bestdbid = pool[k].dbid;
// 從全局哈希表或是expire哈希表中，獲取當前key對應的鍵值對；
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. */
// 將當前key從EvictionPoolLRU數組刪除
if (pool[k].key != pool[k].cached)
sdsfree(pool[k].key);
pool[k].key = NULL;
pool[k].idle = 0;
/* If the key exists, is our pick. Otherwise it is
* a ghost and we need to try the next element. */
// 如果當前key對應的鍵值對不為空，選擇當前key為被淘汰的key
if (de) {
bestkey = dictGetKey(de);
break;
} else {
/* Ghost... Iterate again. */
}
}
}
}
...
/* Finally remove the selected 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);
...
}
}
...
}每次選中一部分過期的鍵值對，每次淘汰最久沒有使用的那個，如果釋放的內存空間還不夠，就會重復的進行采樣，刪除的過程。
除了 LRU 算法，Redis 在 4.0 版本引入了 LFU 算法，就是最不頻繁使用（Least Frequently Used，LFU）算法。
LRU 算法：淘汰最近最少使用的數據，它是根據時間維度來選擇將要淘汰的元素，即刪除掉最長時間沒被訪問的元素。
LFU 算法：淘汰最不頻繁訪問的數據，它是根據頻率維度來選擇將要淘汰的元素，即刪除訪問頻率最低的元素。如果兩個元素的訪問頻率相同，則淘汰最久沒被訪問的元素。
LFU 的基本原理
LFU（Least Frequently Used）算法，即最少訪問算法，根據訪問緩存的歷史頻率來淘汰數據，核心思想是“如果數據在過去一段時間被訪問的次數很少，那么將來被訪問的概率也會很低”。
它是根據頻率維度來選擇將要淘汰的元素，即刪除訪問頻率最低的元素。如果兩個元素的訪問頻率相同，則淘汰最久沒被訪問的元素。也就是說 LFU 淘汰的時候會選擇兩個維度，先比較頻率，選擇訪問頻率最小的元素；如果頻率相同，則按時間維度淘汰掉最久遠的那個元素。
LUF 的實現可參見LFU實現詳解
這看下 Redis 中對 LFU 算法的實現
1、鍵值對的訪問頻率記錄和更新
上面分析 LRU 的時候，聊到了 redisObject，Redis 在源碼中對于每個鍵值對中的值，會使用一個 redisObject 結構體來保存指向值的指針。里面 lru:LRU_BITS 字段記錄了 LRU 算法和 LFU 算法需要的時間和計數器。
// https://github.com/redis/redis/blob/6.2/src/server.h#L673
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
// 這里保存
// LRU時間(相對于全局LRU時鐘)
// LFU數據 (低 8 bits 作為計數器,用 24 bits 中的高 16 bits，記錄訪問的時間戳)
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;
} robj;當一個鍵值對被創建的時候，如果使用 LFU 算法，就會更新 lru 字段記錄的鍵值對的訪問時間戳和訪問次數。
// https://github.com/redis/redis/blob/6.2/src/object.c#L41
robj *createObject(int type, void *ptr) {
robj *o = zmalloc(sizeof(*o));
o->type = type;
o->encoding = OBJ_ENCODING_RAW;
o->ptr = ptr;
o->refcount = 1;
// 如果緩存替換策略是LFU，lru變量包括以分鐘為精度的UNIX時間戳和訪問次數5
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
// 如果是 lru
// 調用LRU_CLOCK函數獲取LRU時鐘值
o->lru = LRU_CLOCK();
}
return o;
}當一個鍵值對被訪問時，Redis 會調用 lookupKey 函數進行查找。當 maxmemory-policy 設置使用 LFU 算法時，lookupKey 函數會調用 updateLFU 函數來更新鍵值對的訪問頻率，也就是 lru 變量值，如下所示：
// https://github.com/redis/redis/blob/6.2/src/db.c#L63
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
// 使用LFU算法時，調用updateLFU函數更新訪問頻率
if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
// 使用 LRU 更新 lru 的時間
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}
// https://github.com/redis/redis/blob/6.2/src/db.c#L54
/* 訪問對象時更新 LFU。
* 首先，如果達到遞減時間，則遞減計數器。
* 然后對計數器進行對數遞增，并更新訪問時間。 */
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val);
counter = LFULogIncr(counter);
val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
// https://github.com/redis/redis/blob/6.2/src/evict.c#L318
unsigned long LFUDecrAndReturn(robj *o) {
// 獲取當前鍵值對的上一次訪問時間
unsigned long ldt = o->lru >> 8;
// 獲取當前的訪問次數
unsigned long counter = o->lru & 255;
unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
if (num_periods)
// 如果衰減大小小于當前訪問次數，那么，衰減后的訪問次數是當前訪問次數減去衰減大小；否則，衰減后的訪問次數等于0
counter = (num_periods > counter) ? 0 : counter - num_periods;
// 如果衰減大小為0，則返回原來的訪問次數
return counter;
}上面的代碼可以看到，當訪問一個鍵值對的時候，首先進行了訪問次數的衰減？
LFU 算法是根據訪問頻率來淘汰數據的，而不只是訪問次數。如果訪問間隔時間越長，那么訪問頻率就越低。
因為 Redis 是使用 lru 變量中的訪問次數來表示訪問頻率，所以在每次更新鍵值對的訪問頻率時，就會通過 LFUDecrAndReturn 函數對訪問次數進行衰減。
LFUDecrAndReturn 函數會調用 LFUTimeElapsed 函數（在 evict.c 文件中），計算距離鍵值對的上一次訪問已經過去的時長。這個時長也是以 1 分鐘為精度來計算的。有了距離上次訪問的時長后，LFUDecrAndReturn 函數會把這個時長除以 lfu_decay_time 的值，并把結果作為訪問次數的衰減大小。
lfu_decay_time 變量值，是由 redis.conf 文件中的配置項 lfu-decay-time 來決定的。Redis 在初始化時，會通過 initServerConfig 函數來設置 lfu_decay_time 變量的值，默認值為 1。所以，在默認情況下，訪問次數的衰減大小就是等于上一次訪問距離當前的分鐘數。
衰減之后，再來看下如何進行訪問次數的更新
// https://github.com/redis/redis/blob/6.2/src/evict.c#L298
uint8_t LFULogIncr(uint8_t counter) {
// 等于255，不在進行次數的更新
if (counter == 255) return 255;
// 計算一個隨機數
double r = (double)rand()/RAND_MAX;
// 計算當前訪問次數和初始值的差值
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
// 根據baseval和lfu_log_factor計算閾值p
double p = 1.0/(baseval*server.lfu_log_factor+1);
// 概率值小于閥值
if (r < p) counter++;
return counter;
}如果當前訪問次數小于255的時候，每次 LFULogIncr 函數會計算一個閾值 p，以及一個取值為 0 到 1 之間的隨機概率值 r。如果概率 r 小于閾值 p，那么 LFULogIncr 函數才會將訪問次數加 1。否則的話，LFULogIncr 函數會返回當前的訪問次數，不做更新。
這樣按照一定的概率增加訪問頻率，避免了訪問次數過大，8 bits 計數器對訪問次數的影響。
2、使用 LFU 算法淘汰數據
LFU 處理數據淘汰和 LRU 方式差不多，這里回顧下 LRU 處理數據淘汰的過程
1、調用 getMaxmemoryState 函數計算待釋放的內存空間；
2、調用 evictionPoolPopulate 函數隨機采樣鍵值對，并插入到待淘汰集合 EvictionPoolLRU 中；
3、遍歷待淘汰集合 EvictionPoolLRU，選擇實際被淘汰數據，并刪除。
不同的是，LFU 算法在淘汰數據時，在第二步的 evictionPoolPopulate 函數中，使用了不同的方法來計算每個待淘汰鍵值對的空閑時間。
LRU 中 idle 記錄的是它距離上次訪問的空閑時間。
LFU 中 idle 記錄的是用 255 減去鍵值對的訪問次數。也就是鍵值對訪問次數越大，它的 idle 值就越小，反之 idle 值越大。
if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
idle = estimateObjectIdleTime(o);
} else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
idle = 255-LFUDecrAndReturn(o);
}freeMemoryIfNeeded 函數按照 idle 值從大到小，遍歷 EvictionPoolLRU 數組，選擇實際被淘汰的鍵值對時，它就能選出訪問次數小的鍵值對了，也就是把訪問頻率低的鍵值對淘汰出去。
具體的源碼上面 LRU 已經展示了，這里不在啰嗦了。
Redis 中的內存可能會遇到這樣一種情況，雖然進行了數據的刪除，據量已經不大了，但是使用 top 命令，發現 Redis 還是會占用大量的內存
因為，當數據刪除后，Redis 釋放的內存空間會由內存分配器管理，并不會立即返回給操作系統。所以，操作系統仍然會記錄著給 Redis 分配了大量內存。
但是這些內存可能是不連續的，對于不連續的小內存塊，雖然是空閑內存，但是 Redis 缺不能拿來用，會造成資源的浪費。
為什么會產生內存碎片呢？
1、內存分配器的分配策略
內存分配器對于內存的分配，一般是按固定大小來分配內存，而不是完全按照應用程序申請的內存空間大小給程序分配。
Redis 可以使用 libc、jemalloc、tcmalloc 多種內存分配器來分配內存，默認使用 jemalloc。
jemalloc 的分配策略之一，是按照一系列固定的大小劃分內存空間，例如8字節、16字節、32字節、48字節，…, 2KB、4KB、8KB等。當程序申請的內存最接近某個固定值時，jemalloc會給它分配相應大小的空間。
這樣的分配方式本身是為了減少分配次數。例如，Redis申請一個20字節的空間保存數據，jemalloc 就會分配 32 字節，此時，如果應用還要寫入 10 字節的數據，Redis 就不用再向操作系統申請空間了，因為剛才分配的32字節已經夠用了，這就避免了一次分配操作。
減少了內存分配的次數，缺點就是增加了產生內存碎片的可能。
2、鍵值對的刪除更改操作
Redis 中鍵值對會被修改和刪除，這會導致空間的擴容和釋放，一方面，如果修改后的鍵值對變大或變小了，就需要占用額外的空間或者釋放不用的空間。另一方面，刪除的鍵值對就不再需要內存空間了，此時，就會把空間釋放出來，形成空閑空間。
Redis中的值刪除的時候，并沒有把內存直接釋放，交還給操作系統，而是交給了Redis內部有內存管理器。
Redis 中申請內存的時候，也是先看自己的內存管理器中是否有足夠的內存可用。Redis的這種機制，提高了內存的使用率，但是會使 Redis 中有部分自己沒在用，卻不釋放的內存，導致了內存碎片的發生。
mem_fragmentation_ratio的不同值，說明不同的情況。
大于1：說明內存有碎片，一般在1到1.5之間是正常的；
大于1.5：說明內存碎片率比較大，需要考慮是否要進行內存碎片清理，要引起重視；
小于1：說明已經開始使用交換內存，也就是使用硬盤了，正常的內存不夠用了，需要考慮是否要進行內存的擴容。
可以使用 INFO memory 命令查看內存碎片率
127.0.0.1:6379> INFO memory # Memory used_memory:865672 used_memory_human:845.38K used_memory_rss:8085504 used_memory_rss_human:7.71M used_memory_peak:865672 used_memory_peak_human:845.38K used_memory_peak_perc:100.01% used_memory_overhead:819226 used_memory_startup:802056 used_memory_dataset:46446 used_memory_dataset_perc:73.01% allocator_allocated:995552 allocator_active:1282048 allocator_resident:3690496 total_system_memory:1929736192 total_system_memory_human:1.80G used_memory_lua:37888 used_memory_lua_human:37.00K used_memory_scripts:0 used_memory_scripts_human:0B number_of_cached_scripts:0 maxmemory:0 maxmemory_human:0B maxmemory_policy:noeviction allocator_frag_ratio:1.29 allocator_frag_bytes:286496 allocator_rss_ratio:2.88 allocator_rss_bytes:2408448 rss_overhead_ratio:2.19 rss_overhead_bytes:4395008 mem_fragmentation_ratio:9.80 mem_fragmentation_bytes:7260856 mem_not_counted_for_evict:0 mem_replication_backlog:0 mem_clients_slaves:0 mem_clients_normal:16986 mem_aof_buffer:0 mem_allocator:jemalloc-5.1.0 active_defrag_running:0 lazyfree_pending_objects:0
mem_fragmentation_ratio 表示的就是內存碎片率
mem_fragmentation_ratio = used_memory_rss/ used_memory
used_memory_rss 是操作系統實際分配給 Redis 的物理內存空間，里面就包含了碎片；而 used_memory 是 Redis 為了保存數據實際申請使用的空間。
Redis服務器重啟后，Redis會將沒用的內存歸還給操作系統，碎片率會降下來；
4.0 版本的 Redis 引入了自動內存碎片清理的功能。
自動碎片清理，只要設置了如下的配置，內存就會自動清理了。
config set activedefrag yes
不過對于具體什么時候開始，受下面兩個參數的控制，只要一個不滿足就停止自動清理
active-defrag-ignore-bytes 100mb：表示內存碎片的字節數達到100MB時，開始清理；
active-defrag-threshold-lower 10：表示內存碎片空間占操作系統分配給Redis的總空間比例達到10%時，開始清理。
為了保證清理過程中對 CPU 的影響，還設置了兩個參數，分別用于控制清理操作占用的CPU時間比例的上、下限，既保證清理工作能正常進行，又避免了降低Redis性能。
active-defrag-cycle-min 25： 表示自動清理過程所用CPU時間的比例不低于25%，保證清理能正常開展；
active-defrag-cycle-max 75：表示自動清理過程所用CPU時間的比例不高于75%，一旦超過，就停止清理，從而避免在清理時，大量的內存拷貝阻塞Redis，導致響應延遲升高。 、
如果你對自動清理的效果不滿意，可以使用如下命令，直接試下手動碎片清理：
memory purge
感謝各位的閱讀，以上就是“Redis中的過期刪除策略和內存淘汰機制是什么”的內容了，經過本文的學習后，相信大家對Redis中的過期刪除策略和內存淘汰機制是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
