Detailed explanation of redis data structure knowledge with pictures and texts

This article brings you relevant knowledge about Redis, which mainly introduces related issues about data structures, including strings, lists, hashes, ordered sets, etc. Content, I hope it will be helpful to everyone.

Recommended learning: Redis learning tutorial

Redis data structure: String (string), List (list), hash (Hash), Set (set), Shorted Set (ordered set)

Underlying data structure: simple dynamic string, doubly linked list, compressed list, hash table, skip list, integer array

1. Hash table: A hash table is actually an array, and each element in the array is called a hash bucket.
Hash conflicts and rehash may cause operation blocking.
The method redis solves hash conflicts is chain hashing, while rehash is to increase the number of existing hash buckets.

Rehash operation steps: 1. Allocate larger space to the hash table, for example, twice the size of the current hash table
2. Remap the data in hash table 1 And copy it to hash table 2
3. Release the space of hash table 1
The second step involves a large number of data copy operations. If all the data in hash table 1 is migrated at once, it will cause thread blocking. , other requests cannot be serviced. In order to avoid this problem, redis uses progressive rehash

The complexity of integer arrays and doubly linked lists is O(N)
The compressed list has three data in the header, namely the list length, The offset at the end of the list and the number of entries in the list
There is also an element zlend at the end of the compressed list to represent the end of the list
Skip list: An ordered linked list can only search for elements one by one, while a jump list is A multi-level index is added on the basis of the linked list, and the data can be quickly positioned through several jumps in the index position
The time complexity of the following five structures

String Type

String type is not suitable for all scenarios. It has an obvious shortcoming that it consumes a lot of memory space when saving data. Because the String type requires additional memory space to record data length, space usage and other information, this information is also called metadata.
When the saved data contains characters, string will be saved using a simple dynamic string SDS structure

len is the used length of buf alloc is the actual allocated length of buf
Because redis There are many data types, and different data types have the same metadata to record, so redis will use a RedisObject structure to uniformly record these metadata

When saving the Long type, the RedisObject pointer Just assign the value directly to integer data, so that no extra pointer is needed to point to the integer, which saves the space overhead of the pointer.
If the saved string is less than 44 bytes, sds and metadata will be allocated to a continuous memory area, called embstr encoding
If the saved string is larger than 44 bytes, SDS and metadata will be Stored separately, called raw encoding

In addition, redis will use a global hash table to save all key-value pairs. Each item in the hash table is a dictEntry structure, which is used to point to a key-value pair. You can see the key value. next will use 24 bytes, but actually occupies 32 bytes. This is because when jemalloc allocates memory, it will find a power of 2 that is larger than N but closest to N according to the number of bytes we apply for. space, which can reduce the number of frequent allocations.

What data structure can be used to save memory?
Compressed list: zlbytes represents the length of the list, zltail represents the tail offset of the list, zllen represents the number of entries in the list, zlend represents the end of the list, perv_len represents the length of the previous entry, encoding represents the encoding method, and len represents The length of itself, the key is the actual stored data. Redis implements list, hash and Sorted Set based on compressed list

How to save single-value key-value pairs using set types?
When saving single-value key-value pairs, you can use Hash's secondary encoding, which is to split the single-value value into two parts. The first part is used as the Hash key, and the latter part is used as the Hash value.

以图片 ID 1101000060 和图片存储对象 ID 3302000080 为例，我们可以把图片 ID 的前 7 位（1101000）作为 Hash 类型的键，把图片 ID 的最后 3 位（060）和图片存储对象 ID 分别作为 Hash 类型值中的 key 和 value。127.0.0.1:6379> info memory# Memoryused_memory:1039120127.0.0.1:6379> hset 1101000 060 3302000080(integer) 1127.0.0.1:6379> info memory# Memoryused_memory:1039136

The Hash type has two underlying implementation structures: 1. Compressed list 2. Hash table
There are two thresholds in the hash list. Once these two thresholds are exceeded, it will be converted from the compressed list to Hash Table
hash-max-ziplist-entries indicates the maximum number of elements in the hash list set when saved in a compressed list
hash-max-ziplist-value indicates the maximum length of a single element of the hash set when saved in a compressed list

Set statistics mode
1. Aggregation statistics
2. Sorting statistics
3.Binary state statistics
4. Cardinality statistics

Three extended data types of redis

1.Bitmap:
2.HyperLogLog
3.GEO:
GEO data type for LBS applications
The underlying structure of GEO is implemented based on Sorted Set. Sorted Set can be sorted according to the weight of elements and supports range query
The weight score of sorted Set is a floating point number (float type), while the longitude and latitude are two numbers , need to use GeoHash encoding
GeoHash encoding is performed through "two-partition interval, interval encoding" method.
First convert the longitude and latitude into a coded format, and then perform the crossover

In fact, the purpose of the crossover is the concept shown in the figure below. After the crossover, you can actually locate the two-dimensional In a square in space, we use the Sorted Set range query to obtain similar coding values. In actual geographical space, they are also adjacent squares. For example, 1110011101 and 1111011101 are adjacent in space.

However, there may be situations where the codes are adjacent, but the squares are not actually adjacent. So in order to avoid this situation from happening, we can query 4 or 8 squares around a given longitude and latitude at the same time.

How to operate the GEO type?
When using the GEO type, the two commands we often use are GEOADD and GEORADIUS
GEOADD: used to record a set of longitude and latitude information and a corresponding ID into a GEO type collection.
Usage: Assume that the vehicle ID is 33 and the latitude and longitude location is (116.034579, 39.030452). We can use a GEO collection to save the latitude and longitude of all vehicles. The collection key is cars:locations. You only need to execute the following command to save the current longitude and latitude position of the vehicle with ID number 33 into GEO.

GEOADD cars:locations 116.034579 39.030452 33

GEORADIUS: Based on the location of the input longitude and latitude, query other elements within a certain range centered on this longitude and latitude

How to customize the data type?

The basic object structure of redis includes type, encoding, lru and refcount, *ptr

Develop a data structure named NewTypeObject, specifically there are the following four steps

How to save time series data in redis?

1. Saving based on Hash and Sorted Set: Why should we query based on two data structures?
The Hash type can realize fast single-key query, which meets the needs of time series single-key query
However, the hash type has a shortcoming that it does not support range query. In order to support timestamp range query, we need Through Sorted Set, because it sorts according to the weight score of the elements,
So how do we ensure the atomicity of these two operations?
You need to pass two commands, MULTI and EXEC:
MULTI means start. After receiving this command, redis will put the command into the queue.
EXEC means end. After receiving this command, it will start executing the queue. Command
However, if hash and Sorted Set are used, only range queries are supported and aggregate calculations are not supported. If aggregation calculations are performed on the client, a large amount of network transmission will occur. Therefore, aggregate calculations can be performed on redis through RedisTimeSeries.

Recommended learning: Redis learning tutorial

The above is the detailed content of Detailed explanation of redis data structure knowledge with pictures and texts. For more information, please follow other related articles on the PHP Chinese website!