This article is about 5300 words. It will take you about 13 minutes to read it completely.

Introduction to the

We know that Redis is a very common in-memory database, and reading data from in-memory is one of the reasons why it is very efficient, so what if one day, “Redis allocated memory is full”? Don’t panic. There are two ways to answer this interview question:

  • “What will Redis do”?
  • “What can we do?”

Increase redis available memory

This method is very violent and very useful. We can increase the available memory of Redis directly. There are two ways to do this

  • “Through the configuration file“
    • Set the memory size by adding the following configuration to the redis.conf configuration file under the redis installation directory
    // Set the maximum memory used by Redis to 1000 MB

    maxmemory 1000mb 

    Copy the code
  • “Modify by running commands“
    • Redis supports dynamic memory size changes at run time through commands
    // Set the maximum memory used by Redis to 1000 MB

    127.0.0.1:6379 > configset maxmemory 1000mb  

    Copy the code

Reids memory is always limited by the machine’s memory and cannot grow indefinitely, so what if there is no way to increase the available memory of Redis?

Memory flushing strategy

In fact, Redis defines “8 memory flushing strategies” to handle Redis running out of memory:

    1. Noeviction: Directly returns bugs without disporting any existing Redis keys
    1. Allkeys-lru: allkeys are eliminated using the lru algorithm
    1. Volatile – LRU: The lRU algorithm is used to eliminate expired items
    1. Allkeys-random: deletes the Redis key randomly
    1. Volatile -random: deletes redis keys with expiration time randomly
    1. Volatile – TTL: deletes the redis key that is about to expire
    1. Volatile – lFU: Deletes keys with expiration time based on the LFU algorithm
    1. Allkeys-lfu: deletes allkeys based on the lfu algorithm

These memory flushing strategies are easy to understand. Let’s focus on how lRU, LFU, and TTL are implemented

Best practices for LRU?

A: I haven’t Used lRU Recently. B: I haven’t Used lRU Recently. If you’ve used it recently, you’re more likely to use it later. Since memory is very expensive, the amount of data we can store in the cache is limited. For example, we can only store 1W data, and when memory is full, for every new data inserted in the cache, the longest unused data is discarded. Let’s sort through the above, we can get the following requirements:

  • “1. Ensure the read and write efficiency, such as the complexity of the read and write is O(1).“
  • “2. When a piece of data is read, update the last time it was used“
  • “3. When inserting a new piece of data, delete the data that has not been used for the longest time“

So we want to make sure that queries are as efficient as possible, inserts are as efficient as possible, and we know that if query efficiency is the only consideration, then the hash table is probably the best choice, and if insert efficiency is the only consideration, then linked lists must have a place.

However, both of these two data structures have their drawbacks when used alone. Is there a data structure that can guarantee both query efficiency and insert efficiency? The hash+ linked list structure emerged

The hash table is used to query the location of data in the linked list. The linked list is responsible for data insertion. When new data is inserted into the head of the linked list, two things happen.

  • 1. When the list is full, discard the data at the end of the list.
    • This is easier, just erase the pointer to the end of the list and clear the information in the hash
  • 2. Whenever a cache hit (that is, cached data is accessed), the data is moved to the head of the list;
    • In this case, what we find is that if we hit the middle of the list, what we need to do is
    • 1). Move the node to the first node
    • 2). “Set the next node of the previous node of this node to the next node of this node”, there will be a problem, we can not find the last node of this node, because it is a one-way linked list, so, a new model is generated.

At this point, the role of bidirectional linked lists also emerged. Can locate directly to the parent node. That’s very efficient. And because the bidirectional list has tail Pointers, it is very convenient and fast to remove the last tail node

So the final solution is to use the “hash table + bidirectional linked list” structure

Best practices for LFU?

LFU: The data that is “Least Frequently Used” in a period of time is preferred to be eliminated. Least-used (LFU) is a caching algorithm for managing computer memory. It records and tracks the number of blocks used, and when the cache is full and more space is needed, the system will clear the memory at the lowest block usage rate. The simplest way to use the LFU algorithm is to assign a counter to each block loaded into the cache. Each time the block is referenced, the counter increases by one. When the cache reaches its capacity and a new block of memory is waiting to be inserted, the system searches for the block with the lowest counter and removes it from the cache.

Here we propose an O(1) time complexity LFU implementation that supports insert, access, and delete operations

As shown in figure:

It consists of two bidirectional lists + hash tables. The top bidirectional list is used to count, and the bottom bidirectional list is used to record stored data. The head node of the list stores numbers, and the value object of the hash table records the data of the bottom bidirectional list.

  • Insert the data that needs to be stored
  • In the hash table“There are“, find the corresponding lower bidirectional linked list, connect the previous node of this node to the next node of this node (there may be only yourself here, just remove it directly), and then determine whether the count of the bidirectional linked list above you is 1 larger than the current count
    • “If it is”, it moves itself to the upper bidirectional list and “determines whether there are any elements under the bidirectional list”. If not, it deletes the node
    • “If it is not or there is no next node in the bidirectional list above”, a new node is added and the count is set to the current count +1
  • To “not exist” in the hash table, store the data to the hash table, concatenate the data to the head node of the two-way list (it is possible that the list is not initialized).

So that the efficiency of finding and inserting is order one

How is redis TTL implemented?

TTL Stores the data structure

Redis stores a dedicated dict for TTL time, namely the dict * Expires field in redisDb. Dict is a hashtable as its name implies, with the corresponding Rediskey and value being the corresponding TTL time. The dict data structure contains two Dictht objects, which are mainly used to rehash data in the process of resolving hash conflicts.





TTL Sets the expiration time

TTL Sets the key expiration time using the following methods:

  • Expire Expire policy based on relative time in seconds
  • Expireat Indicates an expiration policy based on absolute time in seconds
  • Pexpire Expire policy in milliseconds in relative time
  • Pexpireat Expiration policy in milliseconds in absolute time
{"expire",expireCommand,3."w".0,NULL,1.1.1.0.0},

{"expireat",expireatCommand,3."w".0,NULL,1.1.1.0.0},

{"pexpire",pexpireCommand,3."w".0,NULL,1.1.1.0.0},

{"pexpireat",pexpireatCommand,3."w".0,NULL,1.1.1.0.0},

Copy the code

expire expireat pexpire pexpireat

From the implementation function that actually sets the expiration time, the relative time policy will have a current time as the base time, and the absolute time policy will “take 0 as a base time.”

void expireCommand(redisClient *c) {

    expireGenericCommand(c,mstime(),UNIT_SECONDS);

}



void expireatCommand(redisClient *c) {

    expireGenericCommand(c,0,UNIT_SECONDS);

}



void pexpireCommand(redisClient *c) {

    expireGenericCommand(c,mstime(),UNIT_MILLISECONDS);

}



void pexpireatCommand(redisClient *c) {

    expireGenericCommand(c,0,UNIT_MILLISECONDS);

}

Copy the code

The entire expiration time is finally converted to the absolute time for storage, which is calculated by the formula baseline time + expiration time. For relative time the base time is the current time, and for absolute time the relative time is zero. Consider whether the set expiration time has expired. If it has, the master will delete the data and synchronize the deletion action to the slave. The normal way to set an expiration time is to store it in a dict * Expires object through the setExpire method.

/ *

*

* This function is the underlying implementation of the EXPIRE, PEXPIRE, EXPIREAT, and PEXPIREAT commands.

*

* The second argument to the command may be absolute or relative.

* When the *AT command is executed, baseTime is 0, otherwise it stores the current absolute time.

*

* Unit is used to specify the format of argv[2] (passed expiration time),

* It can be UNIT_SECONDS or UNIT_MILLISECONDS,

The baseTime parameter is always in millisecond format.

* /

void expireGenericCommand(redisClient *c, long long basetime, int unit) {

   robj *key = c->argv[1], *param = c->argv[2];

   long long when; /* unix time in milliseconds when the key will expire. */



// Retrieve the when parameter

   if(getLongLongFromObjectOrReply(c, param, &when, NULL) ! = REDIS_OK)

       return;



// If the expiration time passed is in seconds, convert it to milliseconds

   if (unit == UNIT_SECONDS) when *= 1000;

   when += basetime;



   /* No key, return zero. */

/ / remove the key

   if (lookupKeyRead(c->db,key) == NULL) {

       addReply(c,shared.czero);

       return;

   }



/ *

* When loading data, or when the server is an affiliate node,

* Even if the TTL of EXPIRE is negative, or the timestamp provided by EXPIREAT has expired,

* The server also does not actively remove the key, but waits for an explicit DEL command from the master node.

    *

* The program will continue to set (a TTL that may have expired) to the expiration time of the key,

* And wait for the DEL command from the master node.

* /

   if(when <= mstime() && ! server.loading && ! server.masterhost) {



// The time provided by when has expired, the server is the primary node, and no data is being loaded



       robj *aux;



       redisAssertWithInfo(c,key,dbDelete(c->db,key));

       server.dirty++;



       /* Replicate/AOF this as an explicit DEL. */

// Propagate the DEL command

       aux = createStringObject("DEL", 3);



       rewriteClientCommandVector(c,2,aux,key);

       decrRefCount(aux);



       signalModifiedKey(c->db,key);

       notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",key,c->db->id);



       addReply(c, shared.cone);



       return;

   } else {



// Set the expiration time of the key

// If the server is a subordinate node, or the server is loading,

// When is out of date

       setExpire(c->db,key,when);



       addReply(c,shared.cone);



       signalModifiedKey(c->db,key);

       notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"expire",key,c->db->id);



       server.dirty++;



       return;

   }

}



The setExpire function mainly sets an expiration time for the dictEntry corresponding to the key in db-> Expires.



/ *

* Set the expiration time of key key to when

* /

void setExpire(redisDb *db, robj *key, long long when) {



   dictEntry *kde, *de;



   /* Reuse the sds from the main dict in the expire dict */

/ / remove the key

   kde = dictFind(db->dict,key->ptr);



redisAssertWithInfo(NULL,key,kde ! = NULL);



// Retrieve key expiration time based on key

   de = dictReplaceRaw(db->expires,dictGetKey(kde));



// Set the expiration time of the key

// The expiration date is stored as an integer value instead of a String encoded with an INT

   dictSetSignedIntegerVal(de,when);

}

Copy the code

When does Redis implement the elimination strategy?

There are three types of deletion operations in Redis for this strategy

  • Scheduled deletion: For a key with an expiration time, the timer task deletes the key immediately when the expiration time expires
    • Because of the need to maintain a timer, so will consume CPU resources, especially the redis keys with expiration time more and more loss of performance will increase linearly
  • Lazy deletion: The system checks the expiration time of the key only when the key is accessed again. If the key has expired, the system deletes it.
    • This will only be deleted when accessed, so it is possible that some of the expired Redis keys will never be accessed and will continue to occupy Redis memory
  • Periodically delete: Delete expired keys every once in a while.
    • This solution is equivalent to a compromise between the preceding two solutions. The key is deleted by controlling the deletion interval to reduce CPU resource consumption and rationalize the deletion operation.

The shoulders of giants TTL principle lru lfu https://zhuanlan.zhihu.com/p/265597517 https://www.jianshu.com/p/53083f5f2ddc https://tech.ipalfish.com/blog/2020/03/25/lfu/