Detailed explanation of data structure in Redis

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:

##HashCompressed list
Hash table Sorted SetCompressed List
Skip ListSetHash Table
Integer Array

The corresponding characteristics of the data type are similar to the underlying data structure of its implementation, and the properties are the same, and

String is implemented based on SDS and is suitable for simple key-valueStorage, setnx key valueImplement distributed locks, counters (atomicity), and distributed global unique IDs.

List, is sorted according to the order in which the elements enter List , following the FIFO (first in, first out) rule, and is generally used in sorting statistics and simple message queues.

Hash is the mapping between the string key and the string value. It is very suitable for representing an object information. Features are added. And the deletion operation complexity is O(1).

Set is an unordered collection of String type elements. The members of the collection are unique, which means that duplicate data cannot appear in the collection. It is implemented based on a hash table, so the complexity of adding, deleting, and searching is O(1).

Sorted Set is an upgrade of the Set type. The difference is that each element is associated with a double type score. By sorting the score, range query is possible.

Then let’s take a look at these data types, Redis Geo, HyperLogLog, BitMap?

Redis Geo, treats the earth as an approximate sphere, and converts two-dimensional longitude and latitude into strings based on GeoHash to implement location division and specified distance query. Features are generally used in location-related applications.

HyperLogLog is a probabilistic data structure that uses probabilistic algorithms to count the approximate cardinality of a set, with an error rate of approximately 0.81%. When the number of set elements is very large, the space required to calculate the cardinality is always fixed and very small, making it suitable for UV statistics.

BitMap uses one bit to map the state of an element. There are only two states: 0 and 1. It is a very typical binary state, and it uses the String type as the underlying layer. A data type of statistical binary state implemented by the data structure. It has the advantage of saving a lot of memory space and can be used in binary statistics scenarios.

After understanding the above knowledge, let's discuss which strategies are used to select the Redis data type in the corresponding application scenario?

Choose the appropriate RedisData type strategy

In actual development applications, Redis can be applied to many business scenarios, but what do we need? What about choosing data type storage?

The main basis is time/space complexity. In actual development, the following points can be considered:

• Amount of data, the size of the data itself
• Collection type Statistical mode
• Supports single point query/range query
• Special usage scenarios

Amount of data, the size of the data itself

When the amount of data is relatively large and the data itself is relatively small, using String will greatly increase the use of extra space, because a hash table is used to save key-value pairs, and dictEntry is used Structure saving will result in the overhead of saving three additional pointers of dictEntry when saving each key-value pair. This will cause the data itself to be smaller than the additional space overhead, which will eventually lead to a much larger storage space data size. than the original data storage size.

Can be implemented using List, Hash and Sorted Set# based on integer arrays and compressed lists ##, because integer array and compressed list allocate a space with continuous addresses in the memory, and then place the elements in the set one by one in this space, It is very compact, and there is no need to use extra pointers to connect elements together, which avoids the space overhead caused by extra pointers. Moreover, when using a collection type, one key corresponds to the data of a collection, and a lot more data can be saved, but only one dictEntry is used, thus saving memory.

Collection type statistical mode

RedisCommon collection type statistical modes include:

• Aggregation statistics (intersection, difference set, union statistics): When performing aggregation calculations on multiple sets, you can choose Set;
• Sorting statistics (requires set type The order of elements can be preserved): List and Sorted Set in Redis are ordered collections, and List is entered according to the elements List is sorted in the order, Sorted Set can be sorted according to the weight of the elements;
• Binary state statistics (the values ​​of set elements are only 0 and 1) : Bitmap itself is a statistical binary state data type implemented using the String type as the underlying data structure. Bitmap is used after BITOP bitwise AND, OR, and XOR operations. BITCOUNT counts the number of 1's.
• Cardinality statistics (counting the number of unique elements in a set): HyperLogLog is a data collection type used to count cardinality. The statistical results have a certain error. Standard The error rate is 0.81%. If you need accurate statistical results, use Set or Hash type.

Set type, suitable for statistical users/friends/follows/fans/interested people collection aggregation operations, such as

• Statistics of the number of new users of mobile APP every day
• Common friends of two users

Redis中List and Sorted Set are ordered sets, used to deal with the sorting requirements of set elements, such as

• Latest comments list
• Ranking

BitmapBinary status statistics are suitable for statistics with a large amount of data and can be represented by binary status, such as:

• Sign-in and clock-in, the number of user check-ins on the day
• User Weekly Active
• User Online Status

HyperLogLog is a data collection type used to count cardinality, counting non-repeating elements in a collection Number, for example,

• counts the UV of a web page. Multiple visits by a user in a day can only be counted once.

Supports single point query/range query

RedisList and Sorted Set are ordered collections that support range queries, but Hash is

Special usage scenarios that do not support range query

Message queue, use Redis as the implementation of the message queue, to Basic requirements for messages Preserve message order , Handle duplicate messages and Ensure message reliability , the solutions are as follows:

• Based on List's message queue solution
• Streams-based message queue solution

Data type	Data structure
String	SDS (Simple Dynamic String)
List	Doubly linked list Compressed list

##Blocking readUse Use Duplicate message processingProducers implement global unique IDs by themselvesStreams automatically generates globally unique IDsMessage reliabilityUse Use Applicable scenariosThe total amount of messages is smallThe total amount of messages is large and data needs to be read in the form of consumer groups

	Based on List	Based on Strems
Message order preservation	Use LPUSH/RPOP	Use XADD/XREAD
	BRPOP	XREAD block
	BRPOPLPUSH	PENDING List to automatically retain messages

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.

For more programming related knowledge, please visit:

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!