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

This article mainly explains "how to use the dynamic string sds of Redis data structure". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to use the dynamic string sds of Redis data structure.

Redis is written in ANSI C language, it is a high-performance key-value database, it can be used in database, cache and message middleware. Among them, the keys in the Redis key-value pair are all string type, and the value in the key-value pair also has the string type, so the string type is widely used in Redis.

Sds implementation

Data structure of sds:

Struct sdshdr {/ / buf occupied length int len; / / buf remaining available length int free; / / where the string data is saved char buf [];}

The structure sdshdr holds three attributes, len, free, and buf, recording the used length of the character, the unused length, and the array of actual saved strings, respectively.

The following is a new sdshdr structure that holds the hello world string:

Struct sdshdr {len = 5; free = 0; buf = "hello\ 0";}

The value of the free attribute is 0, indicating that the sds does not allocate unused space.

The value of the len attribute is 5, indicating that the sds holds a five-byte string.

The buf attribute is an array of type char. The first five bytes of the array hold the characters'h','e','l','l', and'o', while the last byte holds the empty character'\ 0'.

Sds follows the convention that the C string ends with an empty string. A byte space of a saved empty string is not counted in the len attribute of the sds. Operations such as adding an empty string to the end of the string are done automatically by the sds function, so the empty character is completely transparent to the user.

Through the len attribute, the length calculation of time complexity O (1) can be realized. In addition, sdshdr can reduce memory reallocation by allocating some extra space to buf and using free to record the length of unused space. This is one of the advantages of sds over c strings.

Why Redis does not use C language to represent strings

Redis was developed in C, and Redis does not use the traditional C string representation for the most frequently used strings, but uses a simple dynamic string (sds) that it builds.

In C, a string can be represented by an char array ending with\ 0. For example, hello world can be represented as "hello world\ 0" in C language. Generally, the length of an array is fixed after initialization, and string append append and length calculation operations are not supported:

The array is traversed every time the string length is calculated, so the time complexity is O (N).

Each time you append a string, you need to allocate memory to the string.

Sds optimizes appending character operation

As a database, Redis requires strict query speed and frequent data modification. If you need to perform a memory allocation every time you modify a string, it will take up a lot of time. So Redis chose sds over the C string, and sds reduces the memory allocation for appended characters. An example is given to illustrate the changes within sds when you do the following:

Redis > set msg "hello world" OKredis > append msg "again" (integer) 18redis > get msg "hello world again"

First, the set command creates and saves the hello world to a sdshdr. The value of the sdshdr is as follows:

Struct sdshdr {len = 11; free = 0; buf = "hello world\ 0";}

When the append command is executed, the corresponding sdshdr is updated and the string "again" is appended to the original "hello world":

Struct sdshdr {len = 17; free = 17; buf = "hello world again\ 0";}

When you call the set command to create sdshdr, Redis allocates no extra space to sdshdr, and the free property is 0. After performing the append operation, Redis allocates more than twice the required space for buf.

After executing the append command, it takes a total of 17 + 1 bytes to save "hello world again", but the program allocates 17 + 17 + 1 = 35 bytes to sdshdr, and if you append sdshdr later, as long as the length of the append does not exceed the value of the free attribute, then there is no need to reallocate buf.

For example, executing a later command does not cause memory redistribution in buf, because the length of the newly appended string is less than 17:

Redis > append msg "again" (integer) 23

The corresponding sdshdr structure is as follows:

Struct sdshdr {len = 23; free = 11; buf = "hello world again again\ 0";}

For redis memory allocation, you can see that the source code sds.s/sdsMakeRoomFor,sdsMakeRoomFor function describes the memory allocation policy. The pseudo code of this function is as follows:

/ / sdshdr: character / / addlen before appending: append string sds sdsMakeRoomFor (sdshdr, addlen) {/ / extra space is larger than append space, unordered redistribution of memory, directly return if (free > = addlen) return s; / / calculate the length of new characters newlen = (len+addlen) / / if the new character length is less than SDS_MAX_PREALLOC, allocate twice the new character space / / if the new character length is greater than SDS_MAX_PREALLOC, allocate the new character space + SDS_MAX_PREALLOC space if (newlen < SDS_MAX_PREALLOC) newlen * = 2; else newlen+ = SDS_MAX_PREALLOC; / / allocate memory newsh = zrealloc (sh, sizeof (struct sdshdr) + newlen+1) / / Update the free attribute newsh.free = newlen-len; return newsh;}

For character shortening, Redis saves the shortened string and does not reallocate memory at this time, but uses the free property to record the shortened character length.

At this point, I believe you have a deeper understanding of "how to use the dynamic string sds of the Redis data structure". 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.