“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

instructions

We all know that Redis has five basic data types: String, List, Hash, Sorted Set, and Set.

But what about the implementation of their underlying data structures?

Let’s take a look at the data structures that correspond to the five data types.

As you can see from the figure above, only String is implemented by one data structure, and the other four are implemented by two data structures.

Let’s start by looking at the underlying implementation of the String type, simple dynamic strings.

Simple Dynamic Strings (SDS)

Redis is implemented in C, and C also has functions to store strings. Why not continue to use the functions provided by C?

C uses char* to define character arrays, but for Redis, there are some problems in the use, does not meet the needs of Redis.

  • In C language character array, the length of the string is obtained by traversing the string, and the end of the string is indicated by ‘\0′. If there is’ \0 ‘in the middle of the string, the string will be truncated, so arbitrary binary data cannot be stored

  • The character array of C language is more complicated to operate. For example, a normal operation to get the length of a string requires traversing the entire string. The append string operation iterates the appended string to the end, and then the appended string iterates to the end of the appended string.

Redis Because of the above C character array problem, the String type is implemented by Simple Dynamic String (SDS).

Below is a diagram of the STRUCTURE of SDS

Data Storage Example

SDS directly stores the length of the string, which can be obtained without traversal. When appending strings, you can directly put the string at the end of the appended string. SDS improves the operation efficiency of Redis.

In C, when you need to modify a string, you need to reallocate the memory of the character array. Otherwise, buffer overflow or memory leak will occur.

SDS uses the space allocation strategy. When changing the string, more space is needed. If the string is smaller than 1M, the space of the original string is allocated. If the string is larger than 1 MB, 1 MB space is allocated to the original space.

In addition, if the string is smaller than the original size, the memory will not be released immediately, waiting for the next use.

At the end

Write an article for the first time.

Please feel free to comment if you have any questions.