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

This article mainly introduces "what are the String types in the Redis data structure". In the daily operation, I believe that many people have doubts about the String type in the Redis data structure. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the questions of "what are the String types in the Redis data structure?" Next, please follow the editor to study!

Redis is often used as a distributed KV cache, and many people only know how to use it, but they don't know that there are a lot of hidden secrets at the bottom.

String Typ

String is the most basic data type supported by Redis. First of all, let's take a look at String, its data structure and storage.

Redefine SDS to store String

As we all know, redis is written in C language, while C language has no String type, only char [], and cannot be changed after the size must be specified when initializing. In order to achieve dynamic addition and extension and other functions, such as incr command, append command, so redis defines and maintains a SDS (Simple Dynamic String) to achieve these functions.

Let's first take a look at the data structures defined in the redis source code. There are five types here to save space.

1. Len: to get the length of char [], you need to traverse the array. Time complexity of len (char []) is O (n).

2. The alloc:c language has no String type, only char [], and char [] must first allocate the space length. Char [] pre-allocates the length, and needs to expand the capacity when the data grows.

3. Falgs: always occupies one byte. The lowest three bit are used to represent the type of header. There are five types of header, which are defined by constants in sds.h.

4. Buf []: the char array of c language ends with'\ 0', which means that the storage of binary data cannot contain'\ 0'. There will be problems with using binary storage for pictures, audio, etc.-this is why Redis says that the SDS implemented by itself is a binary secure string.

Improvement of c original char array by SDS

1. SDS implemented by Redis supports capacity expansion.

2. Include length len and get length complexity O (1)

3. Pre-allocation of space

4. Release of inert space (which will be discussed below)

Advantages and disadvantages of SDS

Advantages

Able to support capacity expansion

Include length len, get length complexity O (1)

Space pre-allocation

Shortcoming

Additional memory needs to be allocated

Efficiency problems caused by frequent allocation and recycling

Jemalloc, the memory allocation library used by Redis

When jemalloc allocates memory, according to the number of bytes we applied for, we will find a power of 2 that is larger than N but closest to N as the allocated space, which can reduce the number of frequent allocations. For instance. If you apply for 6 bytes, jemalloc actually allocates 8 bytes; if you apply for 24 bytes, jemalloc allocates 32 bytes. So, in the scenario we just talked about, the dictEntry structure takes up 32 bytes.

Space pre-allocation

Space pre-allocation is used to optimize the string growth operation of SDS: when the API of SDS modifies a SDS and needs to expand the space of SDS, the program not only allocates space necessary for SDS modification, but also allocates additional unused space for SDS.

Where the amount of additional unused space allocated is determined by the following formula:

If the length of the SDS (that is, the value of the len property) will be less than 1 MB after you modify the SDS, the program allocates unused space of the same size as the len attribute, and the value of the SDS len attribute will be the same as the value of the free attribute. For example, if the len of SDS becomes 13 bytes after modification, the program will also allocate 13 bytes of unused space, and the actual length of SDS's buf array will become 13 + 13 + 1 = 27 bytes (an extra byte for holding empty characters).

If the length of the SDS is greater than or equal to 1 MB after making changes to the SDS, the program allocates 1 MB of unused space. For example, if the len of SDS becomes 30 MB after modification, the program will allocate 1 MB of unused space, and the actual length of SDS's buf array will be 30 MB + 1 MB + 1 byte.

Through the space pre-allocation policy, Redis can reduce the number of memory reallocations required to perform string growth operations continuously.

Inert release

Lazy space releases string shortening operations used to optimize SDS: when SDS's API needs to shorten strings saved by SDS, the program does not immediately use memory redistribution to recycle the shortened extra bytes, but uses the free property to record the number of these bytes and wait for future use.

KV storage structure of Redis

In redis, all storage is in the form of KV key-value pairs. K is a string type, that is, SDS;V may be a string, list, hash, etc. (data structures supported by Redis). V is not directly defined into a specific type, but encapsulates a layer with redisObject; the actual stored data structure is specifically pointed to by the ptr pointer.

And, redis in order to better save space, ptr pointers also have different ways of storage, on the one hand, when saving Long type integers, the pointers in RedisObject are directly assigned to integer data, so that there is no need for additional pointers to point to integers, saving the space overhead of pointers. On the other hand, when string data is saved and the string is less than or equal to 44 bytes, the metadata, pointer, and SDS in RedisObject are a contiguous area of memory, thus avoiding memory fragmentation. This layout is also known as embstr coding. Of course, when the string is larger than 44 bytes, the amount of data in SDS starts to increase, and Redis no longer lays out SDS and RedisObject together, but allocates separate space to SDS and points to the SDS structure with a pointer. This layout is called raw encoding mode. As shown in the figure

Embstr coding

Store short strings, one-time memory allocation

It is read-only and becomes raw encoded if the content is modified (even if it does not exceed 44 bytes)

Raw coding

Multiple memory space can be allocated to store long strings greater than 44 bytes.

If the raw native SDS character length is reduced to less than 44, will it be reversed to embstr encoding?

No; the underlying Redis code is irreversible after transformation (no fallback).

At this point, the study on "what are the String types in the Redis data structure" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.