Shulou(Shulou.com)06/02 Report--

How to implement string in Redis, aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and easy way.

Implementation of Redis string

Although Redis is written in C language, it does not use C language strings directly, but implements a set of strings by itself. The goal is to improve speed and performance, you can see that Redis is also painstaking for high performance.

Redis builds a simple dynamic string (Simple Dynamic String), or SDS for short.

1.SDS code structure

Struct sdshdr {/ / record used length int len; / / record idle unused length int free; / / character array char [] buf;}

SDS? What the hell? Friends who are strange to this may have doubts about the name. It's just a noun and don't worry about it. We should focus on appreciating and learning from Redis's design ideas. Draw a picture below to illustrate it at a glance.

Redis strings also follow the C language string implementation rules, that is, the last character is a null character. However, this empty character will not be counted in the len.

Dynamic expansion characteristics of 2.SDS

The most amazing thing about SDS is its Dynamic. Dynamically change the length. For instance

As shown in the figure above, S1 has only 5 free seats at first, and 6 characters need to be appended to S1, which is obviously not enough. What are we going to do? Redis does the following three actions:

Calculate whether the size is enough

Open up space to meet the required size

Open up free free space of the same length as the used size len (if len

= 1m)

Do you have any friends who think that this implementation is similar to Java's list List implementation? After reading the back, it will feel more like it.

Performance advantages of Redis strings

Get the string length quickly

Avoid buffer overflow

Reduce the number of space allocation and improve memory efficiency

1. Get the string length quickly

Take a look at the SDS structure above:

Struct sdshdr {/ / record used length int len; / / record idle unused length int free; / / character array char [] buf;}

Because the used character length len is saved in SDS, you can simply return len when you want to get the string length, with a time complexity of O (1). If a string in C language is used, the time complexity of the string length acquisition function is O (n), where n is the number of characters, because it is traversed and added from beginning to end (to the empty character'\ 0').

two。 Avoid buffer overflow

When strcat appends a string to a C language string, it needs to open up the required space in advance, if it does not open up the space, it may cause buffer overflow and affect other code of the program. As shown in the figure below, there is a string S1 = "hello" and the string S2 = "baby". Now you want to execute strcat (S1, "world"), and there is no space for S1 before execution, so there is a buffer overflow.

In the case of Redis, there is no buffer overflow problem because the space is checked every time a string is appended. The following actions are done before each append operation:

Calculate whether the size is enough

Open up space to meet the required size

3. Reduce the number of space allocation and improve memory efficiency

String append operation will involve memory allocation problem, but memory allocation problem will involve memory partition algorithm and system calls, so if it happens frequently, it will affect performance, so this is absolutely unbearable for performance-oriented Redis.

So the following two optimization measures have been taken.

Space and allocation

Inert space recovery

1. Space pre-allocation

For append operations, Redis not only opens up enough space but also pre-allocates unused space (free) for the next operation. The size of the unused space (free) is determined by the modified string length.

When the modified string length len

= 1m, unused space of 1m length is allocated (free)

With this pre-allocation strategy, the number of memory allocations will be reduced, because before allocation, it will check whether the existing free space is enough, and if so, it will not be opened.

two。 Inert space recovery

Contrary to the above, lazy space collection applies to string reduction operations. For example, there is a string S1 = "hello world" that performs a sdstrim (S1, "world") operation on S1. After performing this operation, Redis will not immediately recycle the reduced part, but will allocate it to the next program that needs memory. Of course, Redis also provides api for reclaiming memory, which can be called manually to reclaim reduced memory.

This is the answer to the question about how to implement the string in Redis. I hope the above content can be of some help to you. If you still have a lot of doubts to solve, you can follow the industry information channel for more related knowledge.

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.