每日一题：聊聊 Redis 过期键的删除策略

聊聊 Redis 过期键的删除策略

答案

• 惰性删除 ：只会在取出 key 的时候才对数据进行过期检查；这样对 CPU 最友好，但是可能会造成太多过期 key 没有被删除（占用内存）。

  • 通过定时器实现（时间事件），时间事件是通过无序链表实现的，查询复杂度为 O(N)

  • 数据到达过期时间，不做处理；每次访问该数据时，我们需要实时判断

  • 源码路径：db.c/expireIfNeeded()，本质上 expireIfNeeded 方法类似于过滤器

    • 7.2 版本只会返回 0/1 ， 0： 有效 1： 过期

• 定时删除 ： 每隔一段时间抽取一批 key 执行删除过期 key 操作。并且，Redis 底层会通过限制删除操作执行的时长和频率来减少删除操作对 CPU 时间的影响。

  • 默认情况下 Redis 定期检查的频率是每秒扫描 10 次，用于定期清除过期键。当然此值还可以通过配置文件进行设置，在 redis.conf 中修改配置 hz 即可，默认的值为 hz 10，官方注释范围为 1~500，但建议最大 100 即可

  • 定时删除的扫描并不是遍历所有的键值对，这样的话比较费时且太消耗系统资源。Redis 服务器采用的是随机抽取形式，每次从过期字典中，取出 20 个键进行过期检测，过期字典中存储的是所有设置了过期时间的键值对。如果这批随机检查的数据中有 25% 的比例过期，那么会再抽取 20 个随机键值进行检测和删除，并且会循环执行这个流程，直到抽取的这批数据中过期键值小于 25%，此次检测才算完成

  • Redis 服务器为了保证过期删除策略不会导致线程卡死，会给过期扫描增加了最大执行时间为 25ms

  • 定期删除对内存更加友好，惰性删除对 CPU 更加友好

• 总结：所以 Redis 采用的是 定时删除+惰性删除 可以简称为 定期删除 源码路径：server.c/activeExpireCycle()

• ps: 本文源码内容基于 7.2 版本

引申内容：源码解析

• 内存数据库：redisDb

/* 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;                 /* The keyspace for this DB 所有数据的键值对 */
    dict *expires;              /* Timeout of keys with a timeout set 设置了超时时间的相关键值对数据 */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)  阻塞的 dict */
    dict *blocking_keys_unblock_on_nokey;   /* Keys with clients waiting for
                                             * data, and should be unblocked if key is deleted (XREADEDGROUP).
                                             * This is a subset of blocking_keys 解除阻塞的dict */
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS  监控的dict （事务前可以加watch） */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
    clusterSlotToKeyMapping *slots_to_keys; /* Array of slots to keys. Only used in cluster mode (db 0). */
} redisDb;

• 键值对：dict

struct dict {
    dictType *type; /* 键值对的类型 */

    dictEntry **ht_table[2]; /* 两张哈希表，目的为了 rehash */
    unsigned long ht_used[2]; /* 上面两张哈希表中，分别使用了多少 */
	/* rehash 的目的是重新进行扩展或收缩 */
    long rehashidx; /* rehashing not in progress if rehashidx == -1，记录 rehash 进度的标志，每移动一个桶,rehashidx++ */

    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) rehash是否暂停 */
    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) 目的： 加快运算速度*/

    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as defined
                                 * by dictType's dictEntryBytes. */
};

• 键值对实体：dictEntry
• 存放键值对

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. 哈希值相同的key/val对出现哈希冲突时通过链表存储起来 */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
};

• 哈希数据类型 dictType

  • 存放函数的结构体，定义了一些函数指针
  • 目的: 通过设置自定义函数，使得 dict 的 key 和 value 能够存储任何类型的数据

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(dict *d, const void *key);
    void *(*valDup)(dict *d, const void *obj);
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    void (*keyDestructor)(dict *d, void *key);
    void (*valDestructor)(dict *d, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Flags */
    /* The 'no_value' flag, if set, indicates that values are not used, i.e. the
     * dict is a set. When this flag is set, it's not possible to access the
     * value of a dictEntry and it's also impossible to use dictSetKey(). Entry
     * metadata can also not be used. */
    unsigned int no_value:1;
    /* If no_value = 1 and all keys are odd (LSB=1), setting keys_are_odd = 1
     * enables one more optimization: to store a key without an allocated
     * dictEntry. */
    unsigned int keys_are_odd:1;
    /* TODO: Add a 'keys_are_even' flag and use a similar optimization if that
     * flag is set. */

    /* Allow each dict and dictEntry to carry extra caller-defined metadata. The
     * extra memory is initialized to 0 when allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
    size_t (*dictMetadataBytes)(void);
    /* Optional callback called after an entry has been reallocated (due to
     * active defrag). Only called if the entry has metadata. */
    void (*afterReplaceEntry)(dict *d, dictEntry *entry);
} dictType;