Redis has high performance in large part because each of its data structures is specially designed to deal with different scenarios
Redis's data structure can be essentially divided into two layers, the exposed data structure and the underlying internal data structure
1. Redis data structure hierarchy
1.1 External data structure
The data structures exposed to the outside are the String, list, hash, set, zset, etc. we use
1.2 Internal data structure
Redis has more refined implementations, in general, there are the following:
SDS, hashtable, ziplist, linkedlist, quicklist, intset, skiplist, etc.
2. Redis underlying implementation
2.1 The underlying implementation of String string type
The underlying implementation of string type mainly relies on the data structure of SDS. Compared with the string expressed in traditional C language, SDS has made changes internally, including len (the true length of the string), buf[] (an array that stores string data), alloc (the actual length of the buf array), and flags.
Different string lengths will use the same structure but different lengths of SDS data structures (internal buf, alloc will be different). Flags is used to specify which one you are using.
Except for the different structures caused by length, the specific encoding modes will also vary with the transmission value. Generally speaking, it is divided into three types: RAW, EMBSTR, and INT (write int type but actually stores long).
When a value of string type is transmitted outside, redis will first use RAW to receive it, and then convert it into INT or EMBSTR type encoding for memory saving.
The advantage of this is that when we try to increment the string, the int type will automatically add 1, and str will try to convert it to int, and then add 1. When we perform append operations, the int type will try to convert it to str and then execute it, and str will execute it directly. Otherwise, the encoding method will be different, and the command results will be different in some cases.
2.2 The underlying implementation of Hash type
The underlying implementation of hash type is mainly divided into two types, ziplist and hashtable
Ziplist is a linked list stored in continuous memory. It is based on memory continuity and has high reading efficiency. It traverses directly when looking for elements, and does not store data such as front and back nodes internally. However, because of memory continuity, it will also receive some restrictions. In fact, ziplist must meet the following two conditions before it will be used.
- Length less than 512
- A single value is less than 64 bytes
If it is not satisfied and forced use, it will lead to a high memory copy cost involving insertion and modification, which will affect performance.
When it is not satisfied, we will use hashtable to implement it. The hash search in the hash table can ensure that the time complexity is close to O(1), and resolve hash conflicts in the form of a linked list array. When the hash table needs to be expanded, in order to avoid the sharp increase in response time caused by a single expansion, it distributes the rehash required for a single expansion into subsequent addition, deletion, modification and search operations of the hash table, and performs hash expansion step by step.
2.3 The underlying implementation of list type
The list type is implemented using ziplist or linkedlist before redis3.2, and using quicklist after 3.2.
quicklist is a linked list data structure that combines both ziplist and linkedlist. Each node inside is a ziplist. This design is actually a kind of space and time.
For a bidirectional list, it is necessary to save internal data, but also to maintain front and back pointers to occupy space. When the list length is too long, fragmentation problems will also occur. Therefore, we encapsulate part of the data in a ziplist to reduce the number of pointers and reduce memory crisps. Of course, the ziplist itself should not be set too long. If you cannot find a large enough continuous space for the ziplist, the storage efficiency will also decrease. The specific length setting depends on the business scenario.
2.4 The underlying implementation of set type
Set type is mainly implemented by hashtable and intset
When all internal data are integers and the amount of internal data is less than 512, intset is used to implement it. Intset is essentially an ordered set implemented by integers. It uses binary search internally. Like ziplist, it is also a continuous memory space, and different encodings are performed for the certificate size to achieve memory optimization.
When the condition is not met, it will be implemented using hashtable. The key is to store data. Because we don’t care about the value of the value, the value is generally stored as a null value.
2.5 The underlying implementation of zset type
The zset type is implemented by skiplist. Taking 7 in 1 2 3 4 5 6 7 8 9 10 as an example, according to the linked list, you need to traverse one by one to find. For the jump table, each node will randomly store the next target and the number of skipped layers, such as starting from 1, jumping to 4, 4<7, so you don’t need to care about the data between 1-4, 4 jumping to 8, 8>7, so you go back to 4, 4 jumping to 6, and then 6 jumping to 8, and find 8>7, so go back to 6, 6 jumping to 7, this is the basic principle of jumping tables. Each node will store the next node and the nodes that can jump.
So how do you set which nodes each node can jump to?
When each node is initialized, a level array will be randomly set to indicate its own level (the random probability p is set by the developer). The lowest layer stores the next node, the second layer stores the next node with the second layer array, and the third layer stores the next node with the third layer array, and finally hit the tail node.
Summarize
The above is personal experience. I hope you can give you a reference and I hope you can support me more.