17 Will Lazy Free Affect Cache Replacement #
The purpose of the Redis cache eviction algorithm is to select some cold data and delete them from the Redis server when the memory usage exceeds the limit, in order to ensure that the memory usage of the server does not exceed the limit. In the previous two lessons, we have studied the implementation of the LRU algorithm and the LFU algorithm in the Redis source code. When these algorithms eliminate data, they both delete the data being eliminated.
However, whether it is the LRU algorithm or the LFU algorithm, when deleting the eliminated data, they actually determine whether to use Lazy Free based on the lazyfree-lazy-eviction configuration item of the Redis server. Lazy Free is a feature provided in Redis 4.0 and later versions, which uses a background thread to execute the task of deleting data, avoiding the blocking of the main thread by the delete operation. However, can the background thread asynchronously delete data and release memory in a timely manner? Will it affect the normal use of the Redis cache?
In today’s lesson, I will introduce the application of Lazy Free in cache eviction. By understanding this part, you will be able to understand the possible impacts of enabling Lazy Free on cache eviction and memory release in Redis. This way, when you encounter issues with the memory capacity of the Redis cache in practical applications, you will have another troubleshooting approach.
Alright, now let’s take a look at the basic process of data deletion during cache eviction. However, before understanding this deletion process, we need to first understand the configuration of enabling Lazy Free in the Redis server. Because in the Redis source code, many places will execute different branching operations based on whether the server has enabled Lazy Free.
Setting for lazy eviction #
First, when the Redis server wants to enable lazy eviction, it needs to set the corresponding configuration items related to lazy eviction in the redis.conf file. There are four configuration items, which correspond to the following four scenarios.
- lazyfree-lazy-eviction : Corresponds to the deletion of data during cache eviction.
- lazyfree-lazy-expire : Corresponds to the deletion of expired keys.
- lazyfree-lazy-server-del : Corresponds to the deletion operations implicitly performed by server commands.
- replica-lazy-flush : Corresponds to the scenario where old data is deleted after a replica completes full synchronization.
The default values for these four configuration items are all “no”. So, if you want to enable it during cache eviction, you need to set lazyfree-lazy-eviction to “yes”. At the same time, during the initialization of configuration parameters in the Redis server startup process, the global variable server’s lazyfree_lazy_eviction member variable will be set based on the configuration information in redis.conf.
In this way, in the Redis source code, if you see a conditional judgment based on the value of server.lazyfree_lazy_eviction variable, it actually means Redis determines whether to perform lazy eviction based on the configuration item lazyfree-lazy-eviction.
Alright, now that we have learned how to set up lazy eviction in the cache eviction scenario, let us take a look at the process of deleting the evicted data.
Deletion Process of Eliminated Data #
In fact, through the study of the previous two lessons, we already know that the freeMemoryIfNeeded function in the Redis source code (in the evict.c file) is responsible for the data eviction process. After filtering out the eliminated key-value pairs, the function starts the deletion process of the eliminated data, which can be divided into two steps.
Step 1: The freeMemoryIfNeeded function first creates an SDS object for the eliminated key and then calls the propagateExpire function, as shown below:
int freeMemoryIfNeeded(void) {
...
if (bestkey) {
db = server.db+bestdbid;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
...
}
The propagateExpire function is implemented in the db.c file. It first creates an array of redisObject structures, where the first element of the array is the command object corresponding to the delete operation, and the second element is the key object to be deleted. Because Redis server may enable lazy deletion for cache eviction scenarios, the propagateExpire function determines which command the delete operation corresponds to based on the value of the lazyfree_lazy_eviction member variable of the global variable server.
If lazyfree_lazy_eviction is set to 1, indicating that lazy deletion is enabled when caching eviction, then the command corresponding to the delete operation is UNLINK; otherwise, the command is DEL. Because these commands are frequently used, Redis source code creates shared objects for these commands. The data structure for these shared objects is the sharedObjectsStruct structure, represented by the global variable shared. This structure contains pointers to the shared objects, including the unlink and del command objects.
The code below shows the definition of the shared global variable and the sharedObjectsStruct structure. The shared variable is defined in the server.c file, and the sharedObjectsStruct structure is defined in the server.h file.
struct sharedObjectsStruct shared;
struct sharedObjectsStruct {
...
robj *del, *unlink,
...
}
Then, when creating the command object for the delete operation, the propagateExpire function uses the unlink or del object from the shared variable. This part of the code is shown below:
void propagateExpire(redisDb *db, robj *key, int lazy) {
robj *argv[2];
argv[0] = lazy ? shared.unlink : shared.del; // If server enables lazyfree-lazy-evict, then the value of argv[0] is the unlink object; otherwise, it is the del object
argv[1] = key; // The eliminated key object
...
}
Next, the propagateExpire function checks whether AOF logging is enabled in Redis server. If it is enabled, the propagateExpire function first records the delete operation of the eliminated key in the AOF file to ensure consistency when using the AOF file for database recovery. This step is implemented by calling the feedAppendOnlyFile function (in the aof.c file).
Then, the propagateExpire function calls the replicationFeedSlaves function (in the replication.c file) to synchronize the delete operation to the slave nodes to ensure data consistency between the master and slave nodes.
The code below shows the basic process of the propagateExpire function. Take a look:
...
// If AOF logging is enabled, write the delete operation to the AOF file
if (server.aof_state != AOF_OFF)
feedAppendOnlyFile(server.delCommand,db->id,argv,2);
// Synchronize the delete operation to the slave nodes
replicationFeedSlaves(server.slaves,db->id,argv,2);
...
With this, the freeMemoryIfNeeded function will start the deletion operation.
Step 2: The freeMemoryIfNeeded function performs different operations based on whether the server enables lazy deletion.
- Branch 1: If the server enables lazy deletion, the
freeMemoryIfNeededfunction calls thedbAsyncDeletefunction to perform asynchronous deletion. - Branch 2: If the server does not enable lazy deletion, the
freeMemoryIfNeededfunction calls thedbSyncDeletefunction to perform synchronous deletion.
Whether performing asynchronous deletion or synchronous deletion, the freeMemoryIfNeeded function calls the zmalloc_used_memory function (in the zmalloc.c file) before calling the deletion function. This function calculates the current memory usage. Then, after calling the deletion function, the freeMemoryIfNeeded function calls the zmalloc_used_memory function again to calculate the memory usage at that time. It calculates the difference in memory usage caused by the deletion operation, which is the amount of memory freed by the deletion operation.
Therefore, the freeMemoryIfNeeded function adds this freed memory amount to the already freed memory amount to get the latest amount of memory freed. The execution logic of this part is shown in the following code:
delta = (long long) zmalloc_used_memory(); // Get the current memory usage
if (server.lazyfree_lazy_eviction)
dbAsyncDelete(db,keyobj); // Perform asynchronous deletion if lazy deletion is enabled
else
dbSyncDelete(db,keyobj); // Perform synchronous deletion otherwise
delta -= (long long) zmalloc_used_memory(); // Calculate the amount of memory freed before and after the deletion based on the current memory usage
mem_freed += delta; // Update the amount of memory freed
So far, we know that the freeMemoryIfNeeded function, after selecting the key-value pairs to be deleted, can perform the actual deletion of the data through asynchronous or synchronous operations. But how exactly are the data asynchronously and synchronously deleted?
Next, let’s take a closer look.
Data Deletion Operation #
Before studying asynchronous or synchronous data deletion, you first need to know that the deletion operation actually includes two sub-operations.
- Sub-operation 1: Remove the key-value pair to be eliminated from the hash table. The hash table here may be a hash table with expired keys or a global hash table.
- Sub-operation 2: Release the memory space occupied by the eliminated key-value pair.
In other words, if these two sub-operations are done together, it is synchronous deletion; if only sub-operation 1 is done and sub-operation 2 is executed by a background thread, it is asynchronous deletion.
For Redis source code, it uses the dictGenericDelete function to implement these two sub-operations. The dictGenericDelete function is implemented in the dict.c file, and we will now understand its specific execution process.
First, the dictGenericDelete function will first search for the key to be deleted in the hash table. It calculates the hash value of the key to be deleted, and then finds the hash bucket where the key is located based on the hash value.
Because different keys may have the same hash value, and Redis’ hash table uses chain hashing (you can review the chain hashing introduced in [Lesson 3]), even if we locate the hash bucket where a key is based on its hash value, we still need to compare and find whether this key really exists in this hash bucket.
It is precisely because of this reason that the dictGenericDelete function will then compare and find the key to be deleted in the hash bucket. If it is found, it first removes this key from the hash table, which means removing this key from the linked list in the hash bucket.
Then, the dictGenericDelete function determines whether to actually free the memory space of the key and value based on the value of the nofree parameter passed in. The execution logic of this part in the dictGenericDelete function is as follows:
h = dictHashKey(d, key); // Calculate the hash value of the key
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask; // Get the bucket number where the key is located based on the hash value of the key
he = d->ht[table].table[idx]; // Get the first hash entry in the hash bucket where the key is located
prevHe = NULL;
while(he) { // Compare and find whether the key to be deleted exists in the hash bucket
if (key==he->key || dictCompareKeys(d, key, he->key)) {
// If the key to be deleted is found, remove it from the linked list in the hash bucket
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) { // If synchronous deletion is required, free the memory space of the key and value
dictFreeKey(d, he); // Call dictFreeKey to free
dictFreeVal(d, he);
zfree(he);
}
d->ht[table].used--;
return he;
}
prevHe = he;
he = he->next; // If the current key is not the key to be found, continue to find the next one
}
...
}
From the implementation of the dictGenericDelete function, you can see that the dictGenericDelete function actually determines whether to perform synchronous deletion or asynchronous deletion based on the value of the nofree parameter. In addition to the dictGenericDelete function, Redis source code also encapsulates two functions: dictDelete and dictUnlink.
The difference between these two functions lies in the value of the nofree parameter passed to the dictGenericDelete function, whether it is 0 or 1. If the value of nofree is 0, it indicates synchronous deletion, and if the value of nofree is 1, it indicates asynchronous deletion.
The following code shows the prototype of the dictGenericDelete function, as well as the implementations of the dictDelete and dictUnlink functions. You can see them below.
// Prototype of dictGenericDelete function, parameters are the hash table to be searched, the key to be searched, and the synchronous/asynchronous deletion flag
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree)
// Synchronous deletion function, nofree value passed to dictGenericDelete function is 0
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
// This is an asynchronous delete function, with the nofree parameter set to 1 when passing it to the dictGenericDelete function.
dictEntry *dictUnlink(dict *ht, const void *key) { return dictGenericDelete(ht,key,1); }
Okay, now we have a basic understanding of the code implementation for synchronous and asynchronous deletion. Next, let’s take a look at how the dbAsyncDelete and dbSyncDelete functions, which are called in the freeMemoryIfNeeded function, actually use dictDelete and dictUnlink to delete the evicted data.
Evicting Data Using Asynchronous Deletion #
Let’s first look at the process of evicting data using asynchronous deletion. This process is executed by the dbAsyncDelete function, which is implemented in the lazyfree.c file. The logic of this function is actually not complicated and can be divided into three steps.
Step 1: The dbAsyncDelete function calls the dictDelete function to synchronously delete the evicted key-value pair in the expires hash table for expired keys, as shown below:
if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);
Step 2: The dbAsyncDelete function calls the dictUnlink function to asynchronously delete the evicted key-value pair in the global hash table, as shown below:
dictEntry *de = dictUnlink(db->dict,key->ptr);
At this point, the evicted key-value pair is only removed from the global hash table, and the memory space it occupies has not been freed yet. Therefore, the dbAsyncDelete function calls the lazyfreeGetFreeEffort function to calculate the cost of freeing the memory space occupied by the evicted key-value pair. If the cost is small, the dbAsyncDelete function directly performs synchronous deletion in the main IO thread. Otherwise, the dbAsyncDelete function creates a lazy deletion task and hands it over to a background thread to complete.
Here, you need to note that although the dbAsyncDelete function performs lazy deletion, it actually uses the lazyfreeGetFreeEffort function mentioned earlier to evaluate the deletion cost.
The lazyfreeGetFreeEffort function is implemented in the lazyfree.c file, and its evaluation logic for deletion cost is simple. It calculates the deletion cost based on the type of the key-value pair to be deleted. If the key-value pair type belongs to one of the four collection types, List, Hash, Set, and Sorted Set, and it is not stored using a compact memory structure, then the deletion cost of this key-value pair is equal to the number of elements in the collection. Otherwise, the deletion cost is 1.
Let me give you a simple example. The following code demonstrates how the lazyfreeGetFreeEffort function calculates the deletion cost for List and Set type key-value pairs. You can see that if the key-value pair is of Set type and it uses a hash table structure instead of an intset to store data, then the deletion cost is equal to the number of elements in the Set.
size_t lazyfreeGetFreeEffort(robj *obj) {
if (obj->type == OBJ_LIST) {
quicklist *ql = obj->ptr;
return ql->len;
} else if (obj->type == OBJ_SET && obj->encoding == OBJ_ENCODING_HT) {
dict *ht = obj->ptr;
return dictSize(ht);
}
...
}
In this way, after the dbAsyncDelete function obtains the deletion cost of the evicted key-value pair through the lazyfreeGetFreeEffort function, in the Step 3, it compares the deletion cost with the macro definition LAZYFREE_THRESHOLD (defined in the lazyfree.c file), which has a default value of 64.
Therefore, only when the evicted key-value pair is a collection type containing more than 64 elements, the dbAsyncDelete function calls the bioCreateBackgroundJob function to create a background task for lazy deletion. I have already introduced the purpose and working mechanism of the bioCreateBackgroundJob function in Lecture 12, so you can review it again.
However, if the evicted key-value pair is not a collection type or a collection type with fewer than or equal to 64 elements, the dbAsyncDelete function directly calls the dictFreeUnlinkedEntry function (in the dict.c file) to free the memory space occupied by the key-value pair.
The following code shows the logic for the dbAsyncDelete function to release memory space using background tasks or the main IO thread. You can take a look.
// If the evicted key-value pair contains more than 64 elements
if (free_effort > LAZYFREE_THRESHOLD && val->refcount == 1) {
atomicIncr(lazyfree_objects,1);
bioCreateBackgroundJob(BIO_LAZY_FREE,val,NULL,NULL); // Create a background task for lazy deletion and hand it over to a background thread for execution
dictSetVal(db->dict,de,NULL); // Set the value of the evicted key-value pair to NULL
}
if (de) {
dictFreeUnlinkedEntry(db->dict,de);
...
return 1;
}
In addition, you can also review the execution process as a whole based on the following image.
Okay, now we have understood the process of data eviction based on asynchronous deletion. In fact, the actual deletion operation is performed either by the background thread or the main thread, depending on the number of elements in the key-value pair to be deleted.
However, if the background thread is used to free memory, a problem arises: How does the main thread know that the memory space freed by the background thread has already satisfied the size of the space to be released?
In fact, the freeMemoryIfNeeded function itself will calculate the amount of memory used before and after calling the dbAsyncDelete or dbSyncDelete function and calculate the difference to obtain the size of the freed memory space.
In addition, after calling the dbAsyncDelete function, the freeMemoryIfNeeded function will also actively check the current memory usage to see if it has met the maximum memory capacity requirements. Once it is satisfied, the freeMemoryIfNeeded function will stop the process of evicting data. You can refer to the following code for the execution logic of this step:
int freeMemoryIfNeeded(void) {
...
// Perform the loop process and delete the evicted data
while (mem_freed < mem_tofree) {
...
// If lazy eviction is used and 16 keys are deleted, check the current memory usage
if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {
// Check if the current memory usage does not exceed the maximum memory capacity
if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
mem_freed = mem_tofree; // If the maximum capacity requirement is met, let the freed memory equal to the memory to be freed to end the loop
}
}
...
}}
So far, we have learned about the implementation process of data eviction based on asynchronous deletion. Next, let’s take a look at the implementation process of data eviction based on synchronous deletion.
Data Eviction Based on Synchronous Deletion #
In fact, compared to the data eviction process based on asynchronous deletion, the data eviction process based on synchronous deletion is relatively simple. This process is implemented by the dbSyncDelete function in the db.c file.
The dbSyncDelete function mainly performs two operations. First, it calls the dictDelete function to delete the evicted key-value pair from the expired keys hash table. Then, it calls the dictDelete function again to delete the evicted key-value pair from the global hash table. With these two steps, the basic operations of synchronous deletion are completed.
However, you need to pay attention here. When the dictDelete function synchronously frees the memory space occupied by the key-value pair, it ultimately calls the dictFreeKey, dictFreeVal, and zfree functions separately to free the memory space occupied by the key, value, and hash entry corresponding to the key-value pair.
The zfree function is implemented in the zmalloc.c file. The dictFreeKey and dictFreeVal functions are two macro definitions defined in the dict.h file. Their specific implementations call the valDestructor function and keyDestructor function, respectively, based on the type of the hash table being operated. You can see the code below, which shows the macro definitions of dictFreeKey and dictFreeVal:
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
(d)->type->valDestructor((d)->privdata, (entry)->v.val)
#define dictFreeKey(d, entry) \
if ((d)->type->keyDestructor) \
(d)->type->keyDestructor((d)->privdata, (entry)->key)
So, to help you find the functions that perform the final memory deallocation operation, let’s take the global hash table as an example and look at the functions corresponding to the dictFreeVal and dictFreeKey macro definitions when operating the global hash table.
First of all, the global hash table is created in the initServer function. When it is created, the type of the global hash table is dbDictType, as shown below:
void initServer(void) {
...
for (j = 0; j < server.dbnum; j++) {
server.db[j].dict = dictCreate(&dbDictType,NULL);
server.db[j].expires = dictCreate(&keyptrDictType,NULL);
...
}
...
}
In the code snippet above, dbDictType is a dictType struct of type dictType, which is defined in the dict.h file. Its last two member variables are keyDestructor function pointer and valDestructor function pointer, as shown below:
typedef struct dictType {
...
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
Next, for dbDictType, it is defined in the server.c file. Since it is a global hash table, it stores keys of type SDS and values of various data types. Therefore, the key and value destruction functions for the dbDictType hash table are actually dictSdsDestructor function and dictObjectDestructor function respectively, as shown below:
dictType dbDictType = {
...
dictSdsDestructor, // key destruction function
dictObjectDestructor // value destruction function
};
Both of these functions are implemented in the server.c file.
The dictSdsDestructor function mainly calls the sdsfree function (defined in the sds.c file) to free the memory occupied by the SDS string. The dictObjectDestructor function calls the decrRefCount function (defined in the object.c file) to perform the release operation, as shown below:
void dictObjectDestructor(void *privdata, void *val)
{
...
decrRefCount(val);
}
Here, it is worth noting that when executing the decrRefCount function, it checks the reference count of the object to be released. Only when the reference count is 1, it will call the specific release function of the object type to free the memory space. Otherwise, the decrRefCount function only decreases the reference count of the object to be released by 1.
Now let’s take an example. If the reference count of the object to be released is 1 and its type is String, then the decrRefCount function will call the freeStringObject function to perform the final memory release operation. If the object is of type List, then the decrRefCount function will call the freeListObject function to release the memory. The relevant code is as follows:
void decrRefCount(robj *o) {
if (o->refcount == 1) {
switch(o->type) {
case OBJ_STRING: freeStringObject(o); break;
case OBJ_LIST: freeListObject(o); break;
...
}
zfree(o);
} else {
...
if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount--;
}
}
I have also created an illustration to show the basic execution logic of the decrRefCount function. You can take a look at it.
Therefore, the data eviction process based on synchronous deletion is actually accomplished by removing the evicted key-value pair from the global hash table using dictDelete function, and releasing the memory space using three functions: dictFreeKey, dictFreeVal, and zfree. Through the above understanding, you now know that the function responsible for freeing the value space is decrRefCount, which calls the release function of the specific data type based on the reference count and type of the value to finalize the memory release.
In addition, it is worth noting that for data eviction based on asynchronous deletion, the function executed by the background thread is the lazyfreeFreeObjectFromBioThread function (defined in the lazyfree.c file), which actually calls the decrRefCount function to release the memory space.
Summary #
In today’s lesson, I introduced to you the data deletion process performed by Redis cache when eliminating data. Since Redis version 4.0, lazy deletion functionality has been provided, so when Redis caches eliminate data, they will decide whether to perform synchronous deletion or asynchronous lazy deletion based on whether lazy deletion is enabled.
You should know that whether it is synchronous deletion or asynchronous lazy deletion, they will first remove the eliminated key-value pair from the hash table. Then, synchronous deletion will immediately call the dictFreeKey, dictFreeVal, and zfree functions to release the memory space of the key, value, and key-value pair hash item, respectively. Asynchronous lazy deletion delegates the task of releasing space to a background thread.
Note that although lazy deletion is asynchronously completed by a background thread, once the background thread starts, it listens to the task queue for lazy deletion. Once a lazy deletion task is available, the background thread will execute it and release the memory space. So, from the perspective of releasing memory space when eliminating data, lazy deletion does not affect the space release requirement during cache elimination.
However, I would also like to remind you that the background thread needs to obtain tasks through synchronous mechanisms, which introduces some additional time overhead and may cause memory release to not be as timely as synchronous deletion. In fact, this is also a design consideration for Redis to use the main thread for memory release when eliminating small sets of data (with no more than 64 elements).
One question per lesson #
Please take a moment to think about whether the main thread can still handle external requests while the freeMemoryIfNeeded function is using a background thread to delete discarded data.
Feel free to write your answer and thoughts in the comments section. If you find it helpful, you can also share today’s content with more friends.