[redis]-[redis underlying data structure]-sds

Preface

Redis No direct use C Language string , Instead, they built their own model called Simple dynamic string ($SimpleDynamicString$,SDS)

Structure definition

struct sdshdr{
    
	int len;    // Record buf The number of bytes used in an array , That is, the length of the string saved by the variable 
	int free;   // Record buf Number of unused bytes in the array 
	char buf[]; // The byte array is used to hold the actual contents of the string 
};

SDS follow C The string is empty ‘0’ Convention ending with , But this character does not count in the string length , namely len In attributes . For the operation of this null character ,SDS The interfaces of have been encapsulated , This null character is transparent to the user ; The advantage of keeping this Convention is , You can use it directly C Some functions in the string library

SDS Characteristics

Constant complexity gets the length of the string

C The string itself does not record its length , Each time you get the length of a string, you need to traverse the entire string , The complexity is O(N);

and SDS Use a variable len Maintain the length of the string contents , Each time you get the length, you only need to access len The value of the property , The complexity is O(1)
The time complexity of the operation to obtain the length of the string is ensured from O(N) Reduced to O(1), Ensure that this operation is not a bottleneck affecting performance , Especially in the case of frequently obtaining string length

Buffer overflow is eliminated

because C The string does not record its own length , Easy to cause out of buffer The problem of . for example ,<String.h>/strcat function , When splicing one string to the end of another string , Because I don't know the length of the target string , Executing the function will default that the space occupied by the target string is enough to splice the spliced strings , Therefore, the spliced string will be directly connected to the subsequent space of the target string , This may cause the contents in the subsequent space of the original target string to be overwritten by the concatenated string , That is, there is a buffer overflow problem

and SDS Records the length of the string itself , When performing a similar splicing operation , First, it will judge whether the space occupied by the target string is enough to splice the spliced strings , If not enough , You will first expand the space size of the target string and then perform the splicing operation

Reduce the number of memory reallocation when modifying the string

A contain N A character C Strings always occupy N + 1 An array of characters , So increase or decrease one at a time C character string , Will perform a reallocation operation on the array of this string
Memory reallocation takes some time , If this operation does not occur frequently , It is acceptable to reallocate the memory every time you modify the string ; but Redis As a database , It is often used with strict speed requirements , Scenarios with frequent data modification , Each modification takes a certain amount of time to reallocate memory, which will have a certain impact on performance

SDS Used Unused space Methods , namely buf Arrays can contain unused bytes , The number of bytes is determined by free Attribute maintenance . adopt Unused space ,SDS Realized Space preallocation and Inert space release Two optimization strategies

Space preallocation

When it's necessary to SDS When you do spatial expansion , Not only will the program be SDS Allocate the necessary space for modification , Also for the SDS Allocate additional unused space ：

1. If the SDS After modification SDS The length of (len attribute ) take Less than 1 MB, So program allocation and len Property of the same size of unused space
2. If the SDS After modification SDS The length of will be Greater than or equal to 1 MB, Then the program will assign 1 MB Of unused space

adopt Space preallocation Strategy , You can reduce the number of memory reallocations required for continuous string growth operations , Before we do that , Will first determine whether the unused space is sufficient , Use unused space directly if enough
Through this strategy ,SDS Will continue to grow N The number of memory reallocations required for the secondary string from Certainly N Time Reduced to most N Time

Inert space release

Lazy space release for optimization SDS String shortening operation ： When you need to shorten SDS Save the string , The program does not immediately use memory reallocation to reclaim the extra bytes after shortening , But use free Property records the number of these bytes , And wait for future use

Through this strategy ,SDS It avoids the memory reallocation needed to shorten the string , And provides optimization for possible future growth operations ： When you need to grow the string later , If the space required for growth is less than the size of unused space , Then you can directly perform the growth operation without memory reallocation to expand the space of the string

Binary security

C The characters in the string must match some encoding ; And besides the end of the string , The string cannot contain empty characters , Otherwise, the contents saved in the string will not be as expected . These properties make C String does not conform to the nature of binary security

and SDS Of API It's all binary safe ,API Will be handled in a binary way SDS Store in buf The contents of the array , There will be no restrictions on the data in it , Filter , Or suppose , What data looks like when it's written , What happens when it is read , There is nothing here “ Special characters ” The concept of , All characters are just themselves . in addition ,SDS Use len Property to determine whether the string ends , Instead of using empty characters , This avoids the impact of empty characters

With the features of binary security ,Redis Not only can text data be stored , It can also save binary data in any format

Compatible with the part C String function

SDS follow C The Convention of ending a string with a null character , This makes it possible to reuse some functions of the string library , Avoid unnecessary code duplication