Simple dynamic string SDS

1、 What is? SDS？

Redis No direct use C The traditional string of language , Instead, it builds a simple dynamic string （Simple dynamic string, SDS） Abstract type of ,Redis At the bottom of the string, we use SDS Structure for storage , For example, key value pairs containing strings are used at the bottom SDS The structure realizes .

such as ：set msg "hello redis" towards redis Insert a string object into . Keys and values are strings . key msg The underlying implementation of the object is a holding string msg Of SDS. value hello redis The underlying implementation of the object is also a stored string hello redis Of SDS

SDS It is not only used to save string values ,SDS It also plays an important role in the buffer ：AOF buffer , The bottom implementation of the input buffer of the client uses SDS

SDS Structure is defined in sds.h in

struct sdshdr{
    int len;//SDS Length of saved string 
    int free;//buf Number of unused bytes in the array 
    char buf[];// A character array , Save string 
}

The last byte holds the null character '\0', Retain the C Specification of string , bring SDS String of structure , You can reuse part of it C Functions of the library .

2、 Why? redis Customized SDS structure , Instead of using C String ？

Mainly because C Strings have the following disadvantages ：

• The time complexity of getting the string length is O(N)：C To get the length of a string, you need to traverse the whole string , encounter '\0' Until empty character .

• out of buffer ： For example, when string appending , If you don't allocate enough memory , It will cause memory overflow .

• Memory reallocation ： Each time the string is increased or truncated , Programs should be saved C An array of strings for memory reallocation , And memory reallocation involves complex algorithms , And may need to perform system calls , So it is usually time-consuming .

• Empty character problem ：C Spaces cannot be saved between strings , Otherwise, the program traversal will be mistaken for the end of the string . This limitation leads to C Strings can only store text data , Can't save images like 、 Audio and video 、 Compressed files and other binary data .

3、SDS What kind of design is adopted to solve C What about strings ？

1、SDS adopt len Properties record SDS length , Therefore, the time complexity of obtaining the length is O(1), namely strlen The time complexity of the command is O(1)

2、SDS The space allocation strategy avoids buffer overflow ： When the SDS When making modifications , Will check SDS Whether the space meets the modification , If not, it will automatically expand to the required size , Then the modification is executed .

3、 Less memory reallocation times when modifying strings ：SDS Medium free Record buf Unused bytes in byte array .redis adopt free Property to realize space pre allocation 、 Inert space release two optimization strategies .

• Space preallocation ： When the SDS When performing growth operations , The program will not only allocate the space necessary for modification , Also for the SDS Allocate additional unused space . Through pre allocation strategy , It reduces the number of memory reallocation when performing string growth operations continuously .

• Inert space release ： When the SDS When truncating , The program will not immediately reclaim the memory occupied by the extra bytes after shortening , But use free Attribute records the number of extra bytes , For future use . If you want to do this in the future SDS Conduct growth operation , Unused space may come in handy , And the growth operation does not necessarily perform memory reallocation .

4、SDS The structure of the buf Byte array , It's binary safe , Not only can you save characters , You can also save binary data .

5、SDS Retain the C Conventions for strings , Set the end of the data to an empty character '\0',SDS The reason why this specification is retained in is that it can be reused C Some functions of string function library , For example, append string .