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

This article mainly explains "what are the reasons why Redis designs simple strings as SDS". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the reasons why Redis designs simple strings as SDS?"

We know that redis is written in C, but instead of using C strings directly, it reconstructs an abstract type called simple dynamic string SDS (simple dynamic string).

Redis also supports traditional strings in C, but it can be used in places where there is no need to modify strings, such as static character output.

When we use redis in our development, we often modify the value of the string frequently. At this time, we will use SDS to represent the value of the string. It is worth noting that in redis databases, key-value key-value pairs that contain string values are implemented by SDS.

For example, when the simplest set command is executed in redis, redis creates a new key-value pair.

127.0.1 6379 > set xiaofu "AAA"

At this point, the key and value of the key-value pair are both a string object, and the underlying implementation of the object is two SDS structures that hold the strings xiaofu and AAA, respectively.

Another example: I press data into a list and redis creates a new key-value pair.

127.0.0.1 BBB 6379 > lpush xiaofu "AAA"BBB"

At this time, the key of the key-value pair is the same as above, it is still a string object implemented by SDS, the value of the key-value pair is a list object containing two string objects, and the underlying layer of these two objects is also implemented by SDS.

SDS structure

The data structure of a SDS value is mainly composed of three attributes: len, free and buf [].

The number of unused bytes in the struct sdshdr {int free; / / buf [] array the length of the string saved by the int len; / / buf [] array char buf []; / / the array of saved strings}

Where buf [] is the char type array that actually holds the string; free represents the number of unused bytes of the buf [] array; and len represents the length of the string saved by the buf [] array.

For example, the figure above shows that buf [] saves a string with a length of 6 bytes, and the number of unused bytes free is 0, but sharp-eyed students will find that this is clearly 7 characters, and there is a "\ 0" ah?

As mentioned above, SDS does not use C strings directly, but still uses some C features, such as following the rule that C strings end with spaces, so that you can also use functions of some C strings. In the case of SDS, a byte occupied by an empty string is not counted in the len attribute and extra space is allocated to him.

After a brief understanding of the SDS structure, let's take a look at the advantages of SDS over C strings.

High efficiency

For example: when we use redis in our work, we often get the length of a string through the STRLEN command, and the len attribute records the length of the string in the SDS structure, so we get a string length that directly takes the value of len, with a complexity of O (1).

If you use a C string, when you get the length of a string, you need to traverse the entire string until the space character ends (C encounters a space character that represents a complete string), and the complexity is O (N).

Frequently traversing strings in high concurrency scenarios, getting the length of strings is likely to become the performance bottleneck of redis, so SDS performance is better.

Data overflow

The C string mentioned above does not record its own length, and the two adjacent strings may be stored in the following figure, allocating appropriate memory space for the string.

If I want to change "AAA" to "AAA123" at this time, but the memory allocated before is only 6 bytes, the modified string needs 9 bytes to put down, how to do?

There is no way but to encroach on the space of adjacent strings, and its own data overflow causes the contents of other strings to be modified.

SDS avoids this point very well. When we need to modify data, we will first check whether the current SDS space len is satisfied. If not, we will automatically expand the space to the required size for modification, and then perform the modification, as shown in the following figure.

However, there is a special place. After expanding the 6 bytes of "AAA" to 9 bytes of "AAA123", it is found that the value of the free attribute has become the total length of the expanded string, which involves the memory reallocation strategy described below.

Memory reallocation strategy

The length of C string is fixed, so every time you increase or shorten a string, you have to do memory reallocation, and the memory reallocation algorithm is usually a time-consuming operation, which is acceptable if the program does not modify the string often.

Unfortunately, as a database, redis's data is bound to be modified frequently, and if a memory reallocation is performed for each change, it will seriously affect performance.

SDS solves the memory allocation problem when strings are growing and shortening through two memory reallocation strategies.

1. Space pre-allocation

The space pre-allocation policy is used to optimize the SDS string growth operation. When the string is modified and the space of the SDS is expanded, not only the necessary space for the modification is allocated to the SDS, but also the additional unused space free is allocated for the SDS. The next time you modify it, check whether the unused space free is satisfied, and if it is satisfied, you do not need to expand the space.

Through the space pre-allocation strategy, redis can effectively reduce the number of memory redistributions caused by string continuous growth operations.

Rules for allocating additional unused space free:

If the len value is less than 1m after modifying the SDS string, the size of the additional unused space allocated at this time free is the same as len.

If the len value is greater than or equal to 1m after modifying the SDS string, the size of the additional unused space free allocated at this time is 1m.

two。 Release of inert space

The lazy space release strategy is used to optimize the SDS string shortening operation. When the SDS string is shortened, memory reallocation is not immediately performed to reclaim the excess space, but the space is recorded with the free attribute. If there is a growth operation later, it can be used directly.

Diversity of data formats

The characters in the C string must conform to certain encoding formats, and as we mentioned above, the C string ends with a\ 0 null character to mark the end of a string, so the string cannot contain\ 0, otherwise it will be mistaken for multiple.

Because of this limitation, C string can only store text data, and data in binary format such as audio and video, pictures and so on can not be stored.

Redis manipulates the data in the Buf array in a binary way, so there is no restriction or filter on the data stored in it, as long as it is saved in and out.

At this point, I believe you have a deeper understanding of "what are the reasons why Redis designed a simple string as SDS?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.