18 Redis Expiration Strategy and Source Code Analysis #

In Redis, we can set expiration time for some elements. How does Redis handle these expired keys when they expire?

Expiration Key Execution Process #

Redis is able to determine which keys have expired because it maintains a dictionary in Redis that stores all the keys with expiration time, which we call the expiration dictionary.

The process of determining expired keys is shown in the following diagram:

Source Code Analysis for Expiration Keys #

Expired keys are stored in the redisDb structure and the source code can be found in the src/server.h file:

/* 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;                 /* Database key space, where all the keys are stored */
    dict *expires;              /* Keys' expiration time */
    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 */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

Tip: All the source code in this article is based on Redis 5.

The data structure for expired keys is shown in the following diagram:

Expiration Policies #

Redis deletes expired keys to reduce the memory usage. However, since Redis is single-threaded, if the deletion operation affects the execution of the main business, it will be counterproductive. Therefore, Redis needs to implement multiple (expiration) deletion policies to ensure that bad things do not happen.

The common expiration policies are as follows:

• Timed deletion
• Lazy deletion
• Periodic deletion

Let’s take a look at each policy.

Timed Deletion #

When setting an expiration time for a key, a timed event is created. When the expiration time is reached, the event handler automatically deletes the key.

• Advantages: Ensures memory can be freed as soon as possible.
• Disadvantages: In high-load situations or when there are many expired keys to process at the same time, the Redis server may hang, affecting the execution of the main business.

Lazy Deletion #

Expired keys are not actively deleted. Each time a key-value pair is retrieved from the database, it is checked if the key has expired. If it has, the key-value pair is deleted and null is returned.

• Advantages: Since the expiration check is performed only when accessing a key, this policy uses very few system resources.
• Disadvantages: The system may occupy space for expired keys that have not been deleted in a timely manner, resulting in reduced space utilization and some space wastage.

Source Code Analysis

The source code for lazy deletion is in the expireIfNeeded method in the src/db.c file. The source code is as follows:

int expireIfNeeded(redisDb *db, robj *key) {
    // Check if the key has expired
    if (!keyIsExpired(db,key)) return 0;
    if (server.masterhost != NULL) return 1;
    /* Delete the expired key */
    // Increase the number of expired keys
    server.stat_expiredkeys++;
    // Propagate the expired key message
    propagateExpire(db,key,server.lazyfree_lazy_expire);
    notifyKeyspaceEvent(NOTIFY_EXPIRED,
        "expired",key,db->id);
    // server.lazyfree_lazy_expire is 1 for asynchronous deletion (lazy free),
    // and 0 for synchronous deletion
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}
// Check if the key has expired
int keyIsExpired(redisDb *db, robj *key) {
    mstime_t when = getExpire(db,key);
    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;
    mstime_t now = server.lua_caller ? server.lua_time_start : mstime();
    return now > when;
}
// Get the expiration time of the key
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);
}

The expireIfNeeded method is called before executing any read or write commands on the database to check if the key has expired. If it has, it will be deleted from the database; otherwise, no action will be taken.

The execution process of lazy deletion is shown in the following diagram:

Periodic Deletion #

Check the database at regular intervals and randomly delete some expired keys.

By default, Redis performs 10 expiration scans per second. This configuration can be modified in the Redis configuration file redis.conf, with the configuration key hz (default value is hz 10).

Note that Redis does not scan all keys in the expired dictionary each time, but randomly selects and deletes expired keys.

Flow of Periodic Deletion

1. Randomly select 20 keys from the expired dictionary.
2. Delete the expired keys among the 20 selected keys.
3. If the proportion of expired keys exceeds 25%, repeat step 1.

In order to avoid excessive scanning during periodic deletion, which can lead to thread deadlock, the algorithm also sets a time limit for the scan, which is set to a maximum of 25ms by default.

The execution flow of periodic deletion is shown in the following diagram:

• Advantages: By limiting the duration and frequency of deletion operations, it reduces the impact of deletion operations on the primary business of Redis, and also deletes some expired data to reduce the ineffective occupation of expired keys.
• Disadvantages: The memory cleaning effect of periodic deletion is not as good as that of timed deletion, and it consumes less system resources than lazy deletion.

Source Code Analysis

The core source code of periodic deletion can be found in the activeExpireCycle function in the src/expire.c file, as shown below:

void activeExpireCycle(int type) {
    static unsigned int current_db = 0; /* ID of the last database processed in a cycle. */
    static int timelimit_exit = 0;      /* Time limit hit in previous call? */
    static long long last_fast_cycle = 0; /* Time we started the last fast cycle. */
    int j, iteration = 0;
    int dbs_per_call = CRON_DBS_PER_CALL; // Number of databases to process per call.
    long long start = ustime(), timelimit, elapsed;
    if (clientsArePaused()) return;
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        if (!timelimit_exit) return;
        if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
        last_fast_cycle = start;
    }
    if (dbs_per_call > server.dbnum || timelimit_exit)
        dbs_per_call = server.dbnum;
    timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
    timelimit_exit = 0;
    if (timelimit <= 0) timelimit = 1;
    if (type == ACTIVE_EXPIRE_CYCLE_FAST)
        timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION;
    long total_sampled = 0;
    long total_expired = 0;
    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        int expired;
        redisDb *db = server.db+(current_db % server.dbnum);
        current_db++;
        do {
            // .......
            expired = 0;
            ttl_sum = 0;
            ttl_samples = 0;
            if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
                num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
            while (num--) {
                dictEntry *de;
                long long ttl;
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                ttl = dictGetSignedInteger
                if (activeExpireCycleTryExpire(db,de,now)) expired++;
                if (ttl > 0) {
                    /* We want the average TTL of keys yet not expired. */
                    ttl_sum += ttl;
                    ttl_samples++;
                }
                total_sampled++;
            }
            total_expired += expired;
            if (ttl_samples) {
                long long avg_ttl = ttl_sum/ttl_samples;
                if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
                db->avg_ttl = (db->avg_ttl/50)*49 + (avg_ttl/50);
            }
            if ((iteration & 0xf) == 0) { /* check once every 16 iterations. */
                elapsed = ustime()-start;
                if (elapsed > timelimit) {
                    timelimit_exit = 1;
                    server.stat_expired_time_cap_reached_count++;
                    break;
                }
            }
            /* Only delete expired keys every 1/4 of the iterations. */
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }
    // .......
}

The activeExpireCycle function randomly checks the expiration time of some keys in the expired dictionary and deletes the expired keys within a specified time frame. This function has two execution modes: fast mode and slow mode, which are determined by the timelimit variable in the code. In fast mode, the timelimit value is fixed and equal to the predefined constant ACTIVE_EXPIRE_CYCLE_FAST_DURATION; while in slow mode, the timelimit value is calculated using the formula 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100.

Redis Expiration Policy #

Redis uses a combination of lazy deletion and periodic deletion as its expiration policy.

Summary #

From this article, we can see that Redis uses an expired dictionary to determine expired keys. Redis deletes expired keys using a combination of lazy deletion and periodic deletion. Redis’s periodic deletion strategy does not delete every expired key by traversing, but randomly selects expired keys for deletion. In order to ensure that expiration scanning does not affect the primary business of Redis, the periodic deletion strategy also provides a maximum execution time to ensure that Redis can run normally and efficiently.