Implementation of Redis database and key expiration

Implementation of Redis database and key expiration

Original address: www.xilidou.com/2018/03/20/...

The previous article explained the data structure of Redis. This time you can look at how Redis stores data as an in-memory database. And how the key expired.

Reading this article you will know:

  • Redis database implementation
  • Redis key expiration strategy

Implementation of the database

Let's look at the code first server.h/redisServer

struct redisServer{
    ...

    // db  
    redisDb *db;
    
    //db  
    int dbnum;

    ...
}

 

Look at the code of redisDb:

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 *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 */
} redisDb;

 

Generally speaking, the redis server contains several (default 16) redisDb databases.

Redis is a key-value pair database stored by kv. Dictionary dict which holds all key database right, this place is called the keyspaceliteral translation is "key space."

So we can think so, in redisDb we use dict (dictionary) to maintain the key space.

  • The kay of the keyspace is the key of the database, and each key is a string object. Note that it is not a string, but a string object.

  • The value of the keyspace is the value of the database. This value can be one of redis, string object, list object, hash table object, collection object or ordered object.

Database read and write operations

Therefore, the addition, deletion, modification, and check of data is the addition, deletion, modification, and check of the large map of keyspace.

When we execute:

>redis SET mobile "13800000000"
 

In fact, a key is added to the keyspace, which is a string object containing the string "mobile", and the value is a string object containing the character "13800000000".

Look at the picture:

There is nothing to say about deleting, modifying, and checking. The map operation similar to java should be understood by most programmers.

It is important to note that when performing key read and write operations, Redis needs to do some additional maintenance actions:

  • Maintain hit and miss counters. Used to count Redis cache hit rate.
  • Update the LRU time of the key and record the last active time of the key.
  • If the key is found to have expired when reading, Redis deletes the expired key and then performs the remaining operations.
  • If a customer performs a WATCH operation on this key, this key will be marked as dirty, so that the transaction notices that this key has been changed.
  • If dirty is not modified once, it will increase by 1.
  • If the server has enabled the database notification function, after the key is modified, the notification will be sent according to the configuration.

Key expiration realization

One of the most important features of Redis as a cache is that you can set the expiration time for key-value pairs. Just look at how Redis realizes this most important feature?

Commands related to expiration time in Redis

  • EXPIRE sets the survival time of the key in seconds
  • EXPIREAT Set the expiration time of the key in seconds
  • PEXPIRE sets the survival time of the key in milliseconds
  • PEXPIREAT Set the expiration time of the key in milliseconds

In fact, these commands and the underlying commands are all implemented by REXPIREAT.

The dict *expires is used in redisDb to store the expiration time. The key points to the key in the keyspace (the pointer in the C language), and the value is a long long type timestamp. The time point when the key expires is calibrated in milliseconds.

If we add an expiration time to the mobile above.

>redis PEXPIREAT mobile 1521469812000
 

At this time, a key-value pair will be added to the expired dictionary. As shown below:

The judgment logic for expiration is very simple:

  1. Whether the key exists in the dictionary expires.
  2. If the key exists, whether the timestamp of value is less than the current system timestamp.

Next, we need to discuss the deletion strategy of expired keys.

There are three strategies for key deletion:

  1. Timed deletion, Redis regularly deletes all expired key-value pairs in the memory, which can ensure memory friendliness, and expired keys will be deleted. However, if the number of keys is large, one deletion requires CPU operations, which is not CPU friendly.
  2. Lazy deletion, only when the key is called does it check whether the key-value pair expires, but it will cause a large number of expired key-value pairs to be stored in the memory, which is not memory friendly, but it greatly reduces the burden on the CPU.
  3. Partially deleted regularly, Redis scans the expired keys regularly, but only deletes some of them. As for the number of keys to be deleted, it is determined according to the current Redis state.

These three strategies have different tendencies towards time and space. In order to balance time and space, Redis adopts the latter two strategies for lazy deletion and regular partial deletion.

Lazy deletion is relatively simple, so I won't introduce too much. Mainly discuss the timing part deletion.

The strategy of timed deletion of expired keys is implemented by expire.c/activeExpireCycle() function, and server.c/serverCron() is called regularly activieExpireCycle().

The big operating principle of activeExpireCycle is that if there are fewer expired keys, the number of deleted keys is also conservative. If there are many expired keys, the key deletion strategy will be very aggressive.

static unsigned int current_db = 0; /* Last DB tested. */
static int timelimit_exit = 0;      /* Time limit hit in previous call? */
static long long last_fast_cycle = 0; /* When last fast cycle ran. */
 
  • First three staticglobal parameters were recorded current traversal db subscript, delete if timeout exit, the last time when quick operation is carried out.

  • Calculated timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;to be understood that 25% of the cpu time.

  • If the size of expire in db is 0, do not operate

  • expire accounted for less than 1% of the total key do not operate

  • num = dictSize(db->expires); num is the number of keys used by expire.

  • slots = dictSlots(db->expires); slots is the size of the expire dictionary.

  • The used key (num) is greater than ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP, then set to ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP. This means that only ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP keys are checked each time.

  • Randomly get expired keys. Calculate whether it has expired, and delete it if it expires.

  • Then various statistics, including the number of times the key was deleted, and the average expiration time.

  • Every sixteen times of traversal, the operation time is calculated, and if it exceeds the timelimit, it will end and return.

  • If the deleted expiration key is greater than 1\4 of ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP, it will jump out of the loop and end.

The steps are more complicated, to summarize: (here are described with the default configuration)

  1. Redis will use up to 25% of the cpu time to process key expiration.
  2. Traverse all redisDb
  3. In each redisDb, if there are no expired keys in the data or the proportion of expired keys is too low, go directly to the next redisDb.
  4. Otherwise, traverse the expired keys in redisDb. If the deleted key reaches 25% of the key with expiration time, or the operation time is greater than 25% of the cpu time, the current cycle is ended and the next redisDb is entered.

postscript

This article mainly explains how the Redis database is implemented, and at the same time introduces the logic of Redis processing expired keys. The more you look at the Redis code, the more you discover it. In fact, one thing Redis has been doing is balancing, balancing the space and time of the program. In fact, the usual business design is to balance the system in terms of time and space. So what I want to say is that looking at the source code allows us to learn the system architecture from the microcosm, which is the only way for every architect. Come on, everybody.

The link addresses of my three previous articles about the basic data structure of Redis are welcome to read.

The basic data structure of Redis (1) Variable strings, linked lists, and dictionaries

Redis basic data structure (two) integer set, skip table, compressed list

Redis basic data structure (three) objects

Welcome to follow my WeChat public account: