数据淘汰机制

过期机制

redis 的根对象是一个 redisDb 结构体。

里面有个 expire 字段，存储了所有设置了过期时间的 key。其中，key 是指向 redisObject 的指针，value 是该键的过期时间

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 <bytes> 配置项来设置允许用户使用的最大内存大小，当内存数据集大小达到一定的大小时，就会根据 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。

/* 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<<REDIS_LRU_BITS)-1) /* Max value of obj->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 的对象。淘汰数据时，根据策略从这两个哈希表里挑选对象删除

/* 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 为止。

源码

这段建议跳过

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数据淘汰机制

Previous数据类型-ZsetNext通信协议-RESP

Last updated