A brief discussion on the difference between Redis SDS and C strings

This article will introduce to you the difference between Redis SDS dynamic strings and C strings. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

#The bottom layer of redis does not use "C string" to represent it, but uses its own built "SDS abstract type" for default string representation. [Related recommendations: Redis video tutorial]

C string

The data stored in C string will have a null character at the end. For example, the actual form of "redis" is 'R' 'E' 'D' 'I' 'S' '\0'

SDS (dynamic string)

SDS is an abstract type built by redis, mainly used to store the default string representation of redis, the AOF buffer in the AOF module, and the client status input buffer.

SDS abstract type content includes:

• int len, used to record the length of the string

• int free, used To record the number of unused bytes in the buf array

• char buf[], the byte array is used to save the string

SDS The structure is as shown in the figure below

Difference

1. When finding the length

C string needs to be traversed to know the length of the string, the complexity is O(n).

SDS only needs to access the internal len attribute, and the time complexity is O(1).

2. Buffer overflow problem

The C string sets an S1 as "redis", but there is an S2 adjacent to it as "abc" on the bottom layer, and then here If S1 is spliced ​​to S3 "ccc" through the function strcat, the final result should be "redisccc". However, if the memory set for S1 is not enough, this will cause the S2 adjacent to it to be modified.

SDS will first determine whether the space is enough. If it is not enough, the space will be expanded to a sufficient location, and more free unused space of len length will be added. For example, the length of the redis string is 5, and then it will be added. The space is pre-allocated to the same length of 5, and the final actual space length is free len 1 to 10.

3. String memory allocation

c string, when data is added or reduced to a certain string, the memory will be re-applied. But if the Too many applications will inevitably lead to performance degradation, and if it is changed N times, it will be allocated N times.

SDS uses two mechanisms internally: lazy space release and space pre-allocation

Space pre-allocation:

Space pre-allocation: refers to when we perform a space allocation , we will allocate more space of len length on the original basis

Here, when the SDS length is less than 1M, it is free = len. For example, if the SDS length is 6byte, the actual space is 6byte 6byte 1byte

When it is larger than 1M, only 1M more will be allocated. free = 1M, for example, if the SDS length is 60M, the actual space is 60M 1M 1byte

Lazy space release

When we reduce a certain string At this time, the program does not immediately use memory reallocation to recycle the shortened bytes, but records them through free for subsequent use. SDS also provides corresponding APIs to prevent lazy space from causing memory waste.

4. Binary security

c The string is finally terminated by a null character, but if some special data requires a null character, the data cannot be saved. Will cause the data before the first null character to be recognized in advance. SDS Because SDS identifies strings based on length, it can ensure the accuracy of the data.

5. Compatible with some C language functions Because SDS also follows C's null character ending, it can use some functions in C

Summary

Record notes while studying, deepen Remember, keep it up. If you have any questions, please point them out. Thanks.

For more programming related knowledge, please visit: Programming Video! !

The above is the detailed content of A brief discussion on the difference between Redis SDS and C strings. For more information, please follow other related articles on the PHP Chinese website!