Detailed explanation of data structure in Redis
- 青灯夜游forward
- 2021-03-31 10:26:155482browse
In actual development, Redis will be used frequently, so how should we correctly choose the data type during use? Which data types are suitable in which scenarios. And in interviews, interviewers often ask questions about Redis data structure:
- Why is Redis fast?
- Why does the query operation slow down?
- Redis Hash rehash process
- Why use a hash table as the index of Redis
When We have analyzed and understood the Redis data structure, which can help us correctly choose the data type to use and improve system performance when using Redis. [Related recommendations: Redis video tutorial]
RedisUnderlying data structure
Redis Yes A memorykey-valuekey-value database, and the key-value pair data is stored in memory, so Redis memory-based data operations , which has high efficiency and fast speed;
Among them, Key is the String type, Redis supports the value type Including String, List, Hash, Set, Sorted Set, BitMap wait. Redis The reason why it can be widely applied to many business scenarios is based on its diverse types of value.
The data type of Value of Redis is based on the object system customized for RedisredisObject Implemented,
typedef struct redisObject{
//类型
unsigned type:4;
//编码
unsigned encoding:4;
//指向底层实现数据结构的指针
void *ptr;
…..
}
redisObjectIn addition to recording actual data, additional memory space is also required to record metadata information such as data length, space usage, etc., which contains 8 bytes of metadata and a 8-byte pointer, the pointer points to the actual data location of the specific data type:
Among them, the pointer points to the location based on The underlying data structure of Redis stores the location of data. The underlying data structure of Redis is: SDS, implemented by doubly linked lists, jump tables, hash tables, compressed lists, and integer sets. .
So how is the underlying data structure of Redis implemented?
Redis underlying data structure implementation
Let’s take a look at Redisrelatively simpleSDS, two-way Linked list, set of integers.
SDS, doubly linked list and integer set
SDS, use the len field to record The number of bytes used reduces the complexity of obtaining the string length to O(1), and SDS is lazy releasing space, you free free the space , the system records the data and can use it directly when you want to use it next time. No need to apply for new space. 
Integer collection, allocate a space with consecutive addresses in the memory, and the data elements will be stored next to each other, without the need for additional pointers to bring space overhead. Its characteristics areThe memory is compact and saves memory space, the query complexity is O(1) and the efficiency is high, and the complexity of other operations is O(N);
Doubly linked list , it can be a non-contiguous and non-sequential space in the memory, and the sequence between the elements is connected in series through the additional pointer overhead of the front-end/back-end pointer.
Its characteristics are that the complexity of inserting/updating data in the section is O(1), high efficiency, and the query complexity is O(N);
Hashha Hash table
Hash table is actually similar to an array. Each element of the array is called a hash bucket. Each hash bucket stores key-value pair data, and the hash bucket The elements in use the dictEntry structure, 
Therefore, the hash bucket element does not save the key-value pair itself, but points to A pointer to a specific value, so there will be additional space overhead when saving each key-value pair, at least 24 bytes will be added, especially Value is String key-value pairs, each key-value pair requires an additional 24 bytes of space. When the saved data is small and the additional overhead is larger than the data, in order to save space, consider changing the data structure.
Let’s take a look at the full picture of the global hash table: 
Although the hash table operation is very fast, RedisAfter the data becomes larger, A potential risk will arise: Hash table conflict problem and rehashoverhead problem, Can this explain why the hash table operation slows down?
When writing more data into the hash table, hash conflicts are an inevitable problem. The way Redis solves hash conflicts is Chained Hash , multiple elements in the same hash bucket are stored in a linked list, and they are connected with pointers in turn, as shown in the figure: 
When there are more and more hash conflicts, this will cause some hash conflict chains to be too long, which will lead to a long time-consuming search for elements on this chain and reduced efficiency.
In order to solve the problem of too long chains caused by hash conflicts, perform rehash operation to increase the number of existing hash buckets and disperse the single Number of bucket elements. So how is the rehash process performed?
Rehash
To make the rehash operation more efficient, two global hash tables are used: Hash table 1 and hash table 2, as follows:
- Allocate larger space to hash table 2,
- Remap the data in hash table 1 and copy it to the hash in Table 2;
- Release the space of hash table 1
However, due to the large data size of tables 1 and 2 during remapping and copying, if you put hash table 1 in one go After all the data has been migrated, the Redis thread will be blocked and unable to serve other requests.
In order to avoid this problem and ensure that Redis can handle client requests normally, Redis adopts progressive rehash.
Every time a request is processed, all entries at the index position are copied from hash table 1 to hash table 2, and the overhead of a large number of copies at one time is allocated to the process of processing multiple requests. , avoiding time-consuming operations and ensuring fast access to data.
After understanding the relevant knowledge points of HashHash tables, let’s take a look at the uncommon compression lists and skip tables.
Compressed list and skip table
Compressed list, based on the array, the compressed list has three fields in the header: zlbytes, zltail and zllen, respectively represents the length of the list, the offset of the end of the list and the number of entries in the list; the compressed list also has a zlend at the end of the table, indicating the end of the list. 
Advantages: The memory is compact and saves memory space. A space with continuous addresses is allocated in the memory, and the data elements will be stored next to each other without the need for additional pointers. To reduce space overhead; searching and locating the first element and the last element can be directly located through the length of the three header fields, and the complexity is O(1).
Jump list, based on the linked list, adds a multi-level index, and achieves rapid positioning of data through several jumps in the index position, as shown in the following figure:
For example, query 33
Features: When the amount of data is large, the search complexity of the skip table is O(logN).
To sum up, we can know the time complexity of the underlying data structure:
| Data structure type | Time complexity |
|---|---|
| Hash table | O(1) |
| Integer array | O(N) |
| Doubly linked list | O(N) |
| Compressed list | O( N) |
| Jump list | O(logN) |
RedisThe custom object system type is the Value data type of Redis. The data type of Redis is based on the underlying If the data structure is implemented, what are the data types?
Redis data type
String、List、Hash、Sorted Set , Set are relatively common types, and their corresponding relationship with the underlying data structure is as follows:
| Data type | Data structure | |
|---|---|---|
| String | SDS (Simple Dynamic String) | |
| List | Doubly linked list Compressed list |
|
| Compressed list | ||
| Compressed List | ||
| Hash Table |
| Based on List | Based on Strems | |
|---|---|---|
| Message order preservation | Use LPUSH/RPOP
|
Use XADD/XREAD
|
| Use | BRPOP | Use XREAD block |
| Producers implement global unique IDs by themselves | Streams automatically generates globally unique IDs | |
| Use | BRPOPLPUSH | Use PENDING List to automatically retain messages
|
| The total amount of messages is small | The total amount of messages is large and data needs to be read in the form of consumer groups |
Location-based LBS service is implemented using the specific GEO data type of Redis. GEO can record geographical location information in the form of longitude and latitude, and is widely used in LBS is in service. For example: how taxi-hailing software provides services based on location.
Summary
Redis is so fast because of its memory-based data manipulation and use of HashHash As an index, a table is highly efficient and fast, and thanks to the diversification of its underlying data, it can be applied to many scenarios. Choosing the appropriate data type in different scenarios can improve its query performance.
Programming Video! !
The above is the detailed content of Detailed explanation of data structure in Redis. For more information, please follow other related articles on the PHP Chinese website!