We have explained the 5 basic Redis data types in detail in the previous article, which are string (string), list (list), hash (set), zset (ordered set) and Redis Stream structure in detail in version 5.0. So how are the underlying types implemented? In fact, each object of Redis is composed of object structure (redisObject) combined with the corresponding coding data structure. This paper mainly introduces the object structure (redisObject) part.

Introduction: Where do you start learning the lower levels?

When I sorted out the underlying design of Redis, I found that there were a lot of information on the Internet, but there was a lack of top-down connection. Here I will collect and reorganize a lot of material from the web to help you better understand the underlying design of Redis. @pdai

So how are the underlying types implemented? With this in mind, let’s begin to understand the underlying design, starting with the following image:

It reflects that each object of Redis is actually composed of object structure (redisObject) and corresponding encoding data structure, and each object type corresponds to several encoding methods, and different encoding methods correspond to different underlying data structures.

Therefore, we need to approach the underlying research from several perspectives:

  • Object Design Mechanism: Object Structure (redisObject)
  • Encoding type and underlying data structure: data structure corresponding to encoding

Why does Redis design a redisObject

Why does Redis design a redisObject?

The commands used to process keys make up a large portion of redis commands, and the commands that keys can execute vary depending on the type of value they hold (the type of the key). For example, LPUSH and LLEN can only be used for list keys, SADD and SRANDMEMBER can only be used for collection keys, etc. Others, such as DEL, TTL, and TYPE, can be used with any TYPE of key; But to implement these commands correctly, different types of keys must be handled differently: deleting a list key, for example, is not the same as deleting a string key.

As described above, Redis must have type information for each key so that the program can check the type of the key and choose the appropriate treatment for it.

For example, a collection type can be implemented by two different data structures, a dictionary and a collection of integers. However, when a user executes ZADD, he or she should not care what encoding the collection uses, as long as Redis can add new elements to the collection as instructed by ZADD.

This means that in addition to checking for the type of the key, commands that operate on data types also need to be polymorphic depending on the encoding of the data type.

In order to solve the above problems, Redis built its own type system. The main functions of this system include:

  • RedisObject object.
  • Type check based on redisObject.
  • An explicit polymorphic function based on redisObject.
  • Mechanism for allocating, sharing, and destroying redisObjects.

RedisObject Data structure

RedisObject is the core of the Redis type system. Every key, value, and parameter processed by Redis itself is represented as this type of data.

/* * Redis object */ typedef struct redisObject {// type unsigned type:4; // Unsigned encoding:4; // lru-24 bits, record the last access time (relative to lru_clock); Or LFU (least-used data: 8-bit frequency, 16-bit access time) unsigned LRU :LRU_BITS; // LRU_BITS: 24 // int refcount; // point to an instance of the underlying data structure void * PTR; } robj;Copy the code

The following figure corresponds to the structure above

Type, Encoding, and PTR are the three most important attributes.

  • Type records the type of value the object holds. Its value may be one of the following constants:
/* * Object type */ #define OBJ_STRING 0 // string #define OBJ_LIST 1 // list #define OBJ_SET 2 // set #define OBJ_ZSET 3 // ordered set #define OBJ_HASH 4Copy the code
  • Encoding records the encoding of the value held by the object, which may be one of the following constants:
/ #define OBJ_ENCODING_RAW representation */ #define OBJ_ENCODING_INT 1 /* Encoded as INTEGER */ #define OBJ_ENCODING_ZIPMAP 2 /* Encoded as hash table */ #define OBJ_ENCODING_ZIPMAP 3 / */ #define OBJ_ENCODING_LINKEDLIST 4 No longer in use, */ #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 */Copy the code
  • The PTR is a pointer to the data structure that actually holds the value, as determined by the Type and Encoding attributes. For example, if the type attribute of a redisObject is OBJ_LIST and the encoding attribute is OBJ_ENCODING_QUICKLIST, then the object is a Redis List, Its value is stored in a QuickList data structure, and the PTR pointer points to QuickList objects;

The following diagram shows the relationships between redisObject, all Redis data types, all Redis encoding methods, and the underlying data structures (PDAI: from version 6.0) :

Note: OBJ_ENCODING_ZIPMAP does not appear in the diagram because, as of Redis2.6, it is no longer the underlying structure of any data type (although there is zipmap.c code as well); OBJ_ENCODING_LINKEDLIST is also unsupported and the code has been removed.

  • Lru property: Records the last time an object was accessed by a command program

Idle time: The current time minus the LRU time of the key’s value object, which is the idle time of the key. The Object idletime command displays the idling duration of a given key

If maxMemory is enabled and the algorithm used by the server to reclaim memory is volatile- lRU or allkeys-lRU, then the key with the higher idle time will be freed first when the server’s memory usage exceeds the maxMemory threshold. To reclaim memory.

Type checking and polymorphism of commands

So how does Redis handle a command?

When executing a command to process data types, Redis performs the following steps

  • Returns NULL if the redisObject corresponding to the given key is found in the database dictionary.
  • Check whether the type attribute of redisObject is consistent with the required type of the command. If not, an error type is returned.
  • Select the appropriate operation function to process the underlying data structure, according to the encoding specified in the Encoding property of the redisObject;
  • Returns the result of the operation on the data structure as the return value of the command.

For example, now execute the LPOP command:

Objects share

Redis usually puts some common values into a shared object, which saves the application from the trouble of double allocation and some CPU time.

Redis preallocates the value object as follows:

  • The return values of various commands, such as OK on success, ERROR on ERROR, QUEUE on failure, and so on
  • All integers, including 0, less than REDIS_SHARED_INTEGERS (the default value for REDIS_SHARED_INTEGERS is 10000)

Note: Shared objects can only be used by data structures that can have Pointers, such as dictionaries and two-way lists. In-memory data structures like integer collections and compressed lists can only hold self-explanatory strings, integers, and so on

Why doesn’t Redis share list objects, hash objects, collection objects, ordered collection objects, only string objects?

  • List objects, hash objects, collection objects, ordered collection objects, itself can contain string objects, high complexity.
  • If the shared object is a save string object, the complexity of the validation operation is O(1)
  • If the shared object is a string object that holds a string value, the complexity of the validation operation is O(N)
  • If the shared object is an object that contains multiple values, and the value itself is a string object, that is, a string object is nested in other objects, such as a list object or a hash object, then the complexity of the validation operation will be O(N squared).

If creating shared objects for complex objects consumes a lot of CPU, it is not appropriate to exchange this consumption for memory space

Reference counting and object destruction

RedisObject has the refCount property, which is the reference count of the object, and obviously counts 0 to be recyclable.

  • Each redisObject structure has a refCount property that indicates how many times the object has been referenced;
  • When a new object is created, its refCount property is set to 1;
  • When an object is shared, Redis increments the refcount of that object by one;
  • When an object is used up or references to an object are removed, the refcount of the object is reduced by one.
  • When the refcount of the object drops to 0, the memory of the RedisObject structure, and the data structure it references, is freed.

summary

  • Redis uses its own object mechanism (redisObject) to implement type determination, command polymorphism, and garbage collection based on number of references.
  • Redis preallocates some commonly used data objects and shares these objects to reduce memory footprint and avoid frequently allocating memory for small objects.