Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "what are the knowledge points of redis data structure". The editor shows you the operation process through actual cases, and the operation method is simple, fast and practical. I hope that this article "what are the knowledge points of redis data structure" can help you solve the problem.

Data structure of redis: String (string), List (list), hash (hash), Set (set), Shorted Set (ordered set)

Underlying data structure: simple dynamic string, two-way linked list, compressed list, hash table, hopping table, integer array

1. Hash table: a hash table is actually an array, and each element in the array is called a hash bucket.

Hash collisions and rehash may cause operation blocking.

Redis solves hash conflicts by chained hashes, while rehash increases the number of existing hash buckets.

The operation procedure of rehash: 1. Allocate more space to the hash table, for example, twice the size of the current hash table

two。 Remap and copy the data from hash table 1 to hash table 2

3. Free up space in 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, the thread will be blocked and other requests cannot be served. To avoid this problem, redis uses progressive rehash

The complexity of integer array and bidirectional linked list is O (N).

The compressed list has three data in the header, namely, the length of the list, the offset at the end of the list, and the number of entry in the list

The compressed list also has an element zlend at the end of the table that represents the end of the list

Skip list: the ordered linked list can only find elements one by one, while the skip list adds a multi-level index on the basis of the linked list to quickly locate the data through several jumps of the index position.

The time complexity of the following five structures

String Typ

The String type is not suitable for all scenarios, and one obvious drawback is that it consumes a lot of memory space when saving data. Because the String type requires extra memory space to record information such as data length, space usage, and so on, this information is also called metadata.

When the saved data contains characters, string uses a simple dynamic string SDS structure to save it

Len is the buf used length alloc is the buf actual assigned length

Because there are many redis data types, and different data types have the same metadata to record, redis uses a RedisObject structure to record the metadata uniformly.

When saving the Long type, the pointer of RedisObject is directly assigned to integer data, so that there is no need for additional pointers to point to integers, saving the space overhead of pointers.

If the saved string is less than 44 bytes, the sds and metadata are allocated to a contiguous area of memory, called embstr encoding

If the saved string is larger than 44 bytes, the SDS and metadata are stored separately, which is called raw encoding

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

What data structure can save memory?

Compressed list: zlbytes represents the list length, zltail represents the offset at the end of the list, zllen represents the number of entry in the list, zlend represents the end of the list, perv_len represents the previous entry length, encoding represents the encoding method, len represents its own length, and key is the actual stored data. Redis implements list, hash and Sorted Set based on compressed lists

How to save a key-value pair of a single value with a collection type?

When saving the key-value pair of a single value, the secondary encoding of Hash can be used, that is, the numerical value of the single value can be divided into two parts, the first part as the key of Hash and the latter as the value of Hash.

Taking the picture ID 1101000060 and the picture storage object ID 3302000080 as examples, we can use the first seven bits (1101000) of the picture ID as the keys of the Hash type, and the last three bits of the picture ID and the picture storage object ID as the key and value of the Hash type value, respectively. 127.0.0.1 integer 6379 > info memory# Memoryused_memory:1039120127.0.0.1:6379 > hset 1101000 060 3302000080 (integer) 1127.0.1 purl 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, the compressed list will be converted to the Hash table.

Hash-max-ziplist-entries represents the maximum number of elements in the hash list set when saved with a compressed list

Hash-max-ziplist-value represents the maximum length of a single element of a hash collection when saved with a compressed list

Aggregate statistical model

1. Aggregate statistics

two。 Ranking statistics

3. Binary state statistics

4. Cardinal statistics

Three extended data types of redis

1.Bitmap:

2.HyperLogLog

3.GEO:

GEO data types for LBS applications

The underlying structure of GEO is implemented according to Sorted Set. Sorted Set can sort according to the weight of elements and support range query.

The weight score of sorted Set is a floating point number (float type), while longitude and latitude are two numbers, which need to be encoded in GeoHash.

GeoHash coding is carried out by means of "binary interval, interval coding".

First convert longitude and latitude into coded format, and then cross

In fact, the purpose of crossover is the concept shown in the following figure. After crossover, you can actually locate it in a square in two-dimensional space. The similar coding values obtained by using Sorted Set range query are also adjacent squares in the actual geographical space. For example, 1110011101 and 1111011101 are adjacent to each other.

However, there will be situations where the codes are adjacent, but the boxes are not actually adjacent. So to avoid this, we can query four or eight squares around a given latitude and longitude at the same time.

How to manipulate GEO types?

When using the GEO type, the two commands we often use are GEOADD and GEORADIUS.

GEOADD: used to record a set of latitude and longitude information and a corresponding ID into a collection of GEO types.

Usage: assuming that the vehicle ID is 33 and the latitude and longitude position is (116.034579Magi 39.030452), we can use a GEO set to save the longitude and latitude of all vehicles, and the set key is cars:locations. Simply execute the following command to store the current longitude and latitude position of the vehicle with ID number 33 in GEO.

GEOADD cars:locations 116.034579 39.030452 33

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

How do I customize the data type?

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

To develop a data structure called NewTypeObject, there are four steps

How to save time series data in redis?

1. Saving based on Hash and Sorted Set: why query based on two data structures?

The Hash type can realize the fast query of single key, which meets the demand of single key query of time series.

But the deficiency of hash type is that it does not support range query. In order to support timestamp range query, we need to use Sorted Set, because it is sorted according to the weight score of the element.

So how do we ensure the atomicity of these two operations?

You need to use the MULTI and EXEC commands:

MULTI means to start. When you receive this command, redis will put the command in the queue.

EXEC indicates the end, and when you receive this command, you will start to execute the commands in the queue.

This is the end of the introduction of "what are the knowledge points of redis data structure". Thank you for your reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.