In depth analysis of redis object structure

We have already explained that Redis 5 Detailed explanation of three basic data types , They are strings (string)、 list (list)、 Hash (hash)、 aggregate (set)、 Ordered set (zset), as well as 5.0 In the version Redis Stream The structure, ; So how is the bottom layer of these basic types realized ？Redis Each kind of object of is actually composed of an object structure (redisObject) And The data structures corresponding to the codes are combined , This article mainly introduces the object structure (redisObject) part .

introduce : Where to start learning from the bottom ？

I'm sorting out Redis Bottom design , I found that there are a lot of information on the Internet , But it lacks a top-down undertaking . Here I will collect a lot of online information and reorganize , To help you better understand Redis Bottom design [email protected]

So how is the bottom layer of these basic types realized ？ With this in mind, let's begin to understand the underlying design , First look at the figure below ：

It reflects. Redis In fact, every kind of object is made up of Object structure (redisObject)  And   The data structure of the corresponding code It's a combination of , Each object type corresponds to several coding methods , Different coding methods correspond to different underlying data structures .

therefore , We need to start the underlying research from several perspectives ：

• Object design mechanism : Object structure (redisObject)
• Coding type and underlying data structure : The data structure of the corresponding code

Why? Redis Can design redisObject object

Why? Redis Can design redisObject object ？

stay redis In command , The commands used to process keys make up a large part , For the type of value saved by the key （ Type of key ）, The commands that keys can execute are different . Such as ： LPUSH  and  LLEN  Can only be used for list keys , and  SADD  and  SRANDMEMBER  Can only be used for collection keys , wait ; Other commands , such as  DEL、 TTL  and  TYPE, Can be used for any type of key ; But to implement these commands correctly , Different processing methods must be set for different types of keys : for instance , Deleting a list key is different from deleting a string key .

The above description , Redis Each key must have type information , Enables the program to check the type of key , And choose the appropriate treatment for it .

for instance , The set type can be realized by two different data structures: dictionary and integer set , however , When the user executes ZADD On command , He / She shouldn't have to care about what code the collection uses , as long as Redis Can follow ZADD Command instructions , Just add the new element to the collection .

This explanation ,  Commands that manipulate data types, in addition to checking the type of key , Polymorphic processing is also required according to different codes of data types .

To solve the above problems , Redis Build your own type system , The main functions of this system include :

• redisObject object .
• be based on redisObject Object type check .
• be based on redisObject Object's explicit polymorphic function .
• Yes redisObject Distribute 、 Mechanisms for sharing and destruction .

redisObject data structure

redisObject yes Redis The core of the type system , Every key in the database 、 value , as well as Redis Parameters handled by itself , Are expressed as this data type .

/*
 * Redis  object 
 */
typedef struct redisObject {

    //  type 
    unsigned type:4;

    //  Encoding mode 
    unsigned encoding:4;

    // LRU - 24 position ,  Record the last visit time （ be relative to lru_clock）;  perhaps  LFU（ Least used data ：8 Bit frequency ,16 Bit visit time ）
    unsigned lru:LRU_BITS; // LRU_BITS: 24

    //  Reference count 
    int refcount;

    //  Point to the underlying data structure instance 
    void *ptr;

} robj;  

The following figure corresponds to the above structure

among type、encoding and ptr These are the three most important attributes .

• type Records the type of value that the object holds , Its value may be one of the following constants ：

/*
*  object type 
*/
#define OBJ_STRING 0 //  character string 
#define OBJ_LIST 1 //  list 
#define OBJ_SET 2 //  aggregate 
#define OBJ_ZSET 3 //  Ordered set 
#define OBJ_HASH 4 //  Hashtable  

• encoding It records the code of the value saved by the object , Its value may be one of the following constants ：

/*
*  Object code 
*/
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /*  Be careful ： edition 2.6 No longer use . */
#define OBJ_ENCODING_LINKEDLIST 4 /*  Be careful ： No longer use , The old version 2.x in String One of the bottom layers of . */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

• ptr It's a pointer , Point to the data structure that actually holds the value , This data structure consists of type and encoding Attribute decision . for instance , If one redisObject Of type The attribute is OBJ_LIST , encoding The attribute is OBJ_ENCODING_QUICKLIST , Then this object is a Redis list （List), Its value is saved in a QuickList Within the data structure , and ptr The pointer points to quicklist The object of ;

The following figure shows redisObject 、Redis All data types 、Redis The relationship between all coding methods and the underlying data structure （pdai： from 6.0 From the version ）：

Be careful ：OBJ_ENCODING_ZIPMAP It's not in the picture , Because in redis2.6 Start , It is no longer the underlying structure of any data type ( Although there are zipmap.c Code for ); OBJ_ENCODING_LINKEDLIST It doesn't support , Relevant codes have also been deleted .

• lru attribute : It records the time when the object was last accessed by the command program

Idle time ： Subtract the value of the key object from the current time lru Time , Is the idle time of the key .Object idletime The command can print out the idle time of a given key

If the server is turned on maxmemory Options , And the algorithm that the server uses to reclaim memory is volatile-lru perhaps allkeys-lru, So when the server takes up more memory than maxmemory When the upper value set by the option , The key with higher idle time will be released by the server first , To reclaim memory .

Type checking and polymorphism of commands

that Redis How do you handle a command ？

When executing a command to process data types ,redis Follow these steps

• According to the given key, Find the corresponding... In the database dictionary redisObject, If not , Just go back to NULL;
• Check redisObject Of type Does the property match the type required to execute the command , If it doesn't match , Return type error ;
• according to redisObject Of encoding The code specified by the property , Choose the appropriate operation function to deal with the underlying data structure ;
• Return the operation result of the data structure as the return value of the command .

For example, now execute LPOP command ：

Object sharing

redis Generally, some common values are put into a shared object , In this way, the program can avoid the trouble of repeated allocation , It also saves some CPU Time .

redis The pre assigned value objects are as follows ：

• Return values of various commands , For example, it is returned when it is successful OK, Error returned ERROR, Return when the command fails to join the team QUEUE, wait
• Include 0 , , Less than REDIS_SHARED_INTEGERS All integers of （REDIS_SHARED_INTEGERS The default value of is 10000）

Be careful ： Shared objects can only be used by data structures with pointers such as dictionaries and bi-directional linked lists . Things like integer sets and compressed lists can only hold strings 、 Memory data structures such as integers

Why? redis Do not share list objects 、 Hash object 、 A collection of objects 、 An orderly collection of objects , Share only string objects ？

• List objects 、 Hash object 、 A collection of objects 、 An orderly collection of objects , Itself can contain string objects , High complexity .
• If the shared object is a saved string object , So the complexity of the verification operation is O(1)
• If the shared object is a string object that holds string values , So the complexity of the verification operation is O(N)
• If the shared object is an object that contains multiple values , Where the value itself is a string object , That is, string objects are nested in other objects , For example, list objects 、 Hash object , So the complexity of the validation operation would be O(N The square of )

If you create shared objects for objects with high complexity , It takes a lot of CPU, Use this consumption in exchange for memory space , It's not appropriate

Reference count and object destruction

redisObject There is refcount attribute , Is the reference count of the object , Apparent count 0 Then it can be recycled .

• Every redisObject All structures have a refcount attribute , Indicates how many times this object has been referenced ;
• When you create a new object , its refcount Property is set to 1;
• When sharing an object ,redis Put this object's refcount Add one ;
• After using an object , Or after eliminating the reference to an object , The program will the of the object refcount Minus one ;
• Be the object of refcount Down to 0 when , This RedisObject structure , And the memory of the data structure it references will be released .

Summary

• redis Use your own object mechanism （redisObject) To realize type judgment 、 Command polymorphism and reference based garbage collection ;
• redis Some common data objects will be pre allocated , And reduce memory consumption by sharing these objects , And avoid frequent memory allocation for small objects .