Redis data structure – QuickList, SkipList, RedisObjective

Following the above, this article mainly introduces QuickList, SkipList, RedisObjective

4. Redis data structure – QuickList

Question 1: Although ZipList saves memory, the application memory must be a continuous space. If the memory occupies a lot, the application memory efficiency is very low. what to do?

? Answer: In order to alleviate this problem, we must limit the length and entry size of ZipList.

Question 2: But what should we do if we want to store a large amount of data and exceed the optimal upper limit of ZipList?

? Answer: We can create multiple ZipLists to store data in fragments.

Question 3: After the data is split, it is scattered and inconvenient to manage and search. How do these multiple ZipLists establish a relationship?

? Answer: Redis introduced a new data structure QuickList in version 3.2. It is a double-ended linked list, but each node in the linked list is a ZipList.

In order to avoid too many entries in each ZipList in QuickList, Redis provides a configuration item: list-max-ziplist-size to limit.
If the value is positive, it represents the maximum number of entries allowed in ZipList
If the value is negative, it represents the maximum memory size of ZipList, divided into 5 cases:

• -1: The memory usage of each ZipList cannot exceed 4kb.
• -2: The memory usage of each ZipList cannot exceed 8kb.
• -3: The memory usage of each ZipList cannot exceed 16kb.
• -4: The memory usage of each ZipList cannot exceed 32kb.
• -5: The memory usage of each ZipList cannot exceed 64kb.

Its default value is -2:

The following is the structure source code of QuickList and QuickListNode:

typedef struct quicklist {<!-- -->
    //head node pointer
quicklistNode *head;
    // tail node pointer
quicklistNode *tail;
//The number of entries in all ziplists
    unsigned long count; l
    //The total number of ziplists
unsigned long len;
//The entry upper limit of ziplist, the default value is -2
    int fill : QL_FILL_BITS;
//The number of nodes that are not compressed at the beginning and end
unsigned int compress : QL_COMP_BITS;
    //The number of bookmarks and arrays during memory reallocation are generally not used
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[;
} quicklist;

typedef struct quicklistNode {<!-- -->
    // previous node pointer
struct quicklistNode *prev;
    // next node pointer
struct quicklistNode *next;
    //The ZipList pointer of the current node
    unsigned char *zl;
//The byte size of the ZipList of the current node
    unsigned int sz;
//The number of entries in ZipList of the current node
    unsigned int count : 16;
//Encoding method: 1, ZipList; 2, Izf compression mode
    unsigned int encoding : 2;
//Data container type (reserved): 1, other; 2, ZipListunsigned
    int container : 2;
// Whether to be decompressed. 1: It means that it has been decompressed and will be recompressed in the future
    unsigned int recompress : 1;
unsigned int attempted_compress : 1;//for testing
    unsigned int extra : 10;/*reserved field*/
} quicklistNode;
                            

We next use a flow chart to describe the current structure

Summary:

Features of QuickList:

• It is a double-ended linked list whose nodes are ZipList.
• The node adopts ZipList, which solves the memory occupation problem of the traditional linked list.
• The size of ZipList is controlled to solve the problem of continuous memory space application efficiency.
• Intermediate nodes can be compressed, further saving memory.

5. Redis data structure-SkipList

SkipList (jump list) is a linked list first, but there are several differences compared with traditional linked lists:

• Elements are stored in ascending order.
• Nodes may contain multiple pointers with different pointer spans.

//t_zset.c
typedef struct zskiplist {<!-- -->
    //head and tail node pointer
struct zskiplistNode *header, *tail;
    //Number of nodes
unsigned long length;
//Maximum index level, the default is 1
    int level;
}zskiplist;

typedef struct zskiplistNode {<!-- -->
    sds ele; //The value stored by the node
double score;//node score, used for sorting and searching
struct zskiplistNode *backward;//The previous node pointer
    struct zskiplistLevel {<!-- -->
struct zskiplistNode *forward;//next node pointer
        unsigned long span;//index span
} leveli;//Multi-level index array
} zskiplistNode;

Small summary:

SkipList Features:

• The jump list is a doubly linked list, each node contains score and ele values.
• Nodes are sorted according to the score value, and if the score value is the same, they are sorted according to the ele dictionary.
• Each node can contain multiple layers of pointers, and the number of layers is a random number between 1 and 32.
• Different layer pointers have different spans to the next node, and the higher the layer, the larger the span.
• The efficiency of adding, deleting, modifying and checking is basically the same as that of red-black tree, but the implementation is simpler.

6. Redis data structure – RedisObject

The key and value of any data type in Redis will be encapsulated into a RedisObject, also called a Redis object. The source code is as follows:

1. What is redisObject:
From the perspective of Redis users, a Redis node contains multiple databases (the default is 16 in non-cluster mode, and only 1 in cluster mode), and a database maintains data from key space to object space Mapping relations. The key of this mapping relationship is a string type, and the value can be a variety of data types, such as: string, list, hash, set, sorted set, etc. We can see that the type of key is fixed as string, while the possible types of value are multiple.
From the perspective of Redis internal implementation, the mapping relationship in the database is maintained by a dict. It is enough to express the key of dict with a fixed data structure, which is the dynamic string sds. The value is more complicated. In order to store different types of values in the same dict, this requires a common data structure. This common data structure is robj, and its full name is redisObject.

Redis encoding method

According to the different types of data stored in Redis, different encoding methods are selected, including 11 different types in total:

Number	Coding method	Description
0	OBJ_ENCODING_RAW	raw encoded dynamic string
1	OBJ_ENCODING_INT	long type integer string
2	OBJ_ENCODING_HT	hash table (dictionary dict)
3	OBJ_ENCODING_ZIPMAP	Deprecated
4	OBJ_ENCODING_LINKEDLIST	Double-ended linked list
5	OBJ_ENCODING_ZIPLIST	Compressed list
6	OBJ_ENCODING_INTSET	Integer set
7	OBJ_ENCODING_SKIPLIST	skip list
8	OBJ_ENCODING_EMBSTR	embstr’s dynamic string
9	OBJ_ENCODING_QUICKLIST	quick list
10	OBJ_ENCODING_STREAM	Stream

Five data structures

Redis will choose different encoding methods according to the type of data stored. The encoding used for each data type is as follows:

Data Type	Encoding
OBJ_STRING	int, embstr, raw
OBJ_LIST	LinkedList and ZipList (before 3.2) , QuickList (after 3.2)
OBJ_SET	intset, HT
OBJ_ZSET	ZipList, HT, SkipList
OBJ_HASH	ZipList, HT