Redis Design and Implementation — Simple dynamic string SDS

Redis, as a database, is used in situations where speed is critical and data is frequently modified.

Redis redefines the String, called Simple Dynamic String, or SDS.

In Redis, C strings are used only as string literals for things that do not need to change string values, such as printing logs:

RedisLog (REDIS_WARMING,”Redis is now ready to exit,bye bye…” );

Definition of SDS

In Redis database, key-value pairs containing string values are implemented by SDS at the bottom.

The value of the free attribute is 3, which means that the SDS has 3 bytes of space to allocate.

The len attribute has a value of 4, which means that the SDS holds a 4-byte string.

The buF attribute is an array of type char. The first four characters hold ‘j’,’a’,’v’, and ‘a’ respectively. The last character holds the null character ‘\0’. Assigning an extra byte of space to a null character and adding a null character to the end of the string is done automatically by the SDS function, so the null character is transparent to the user.

SDS and C strings

Get the length of the string.

A C string does not record its own length, so to get the length of a C string, the program must traverse the entire string, counting every character it encounters. For SDS, the program only needs to access the LEN attribute of SDS to know the length of the string.

② Prevent cache overflow

If there are two C strings s1 (‘R’ ‘e’ ‘d’ ‘I’ ‘s’ ‘\0’) and S2 (‘M’ ‘O’ ‘n’ ‘g’ ‘O’ ‘d’ ‘b’ ‘\0’) that are adjacent to each other in memory, if the contents of s1 are changed to “Redis Cluster”, However, if s1 is not allocated enough space, the data of S1 will overflow into S2, and the content of S2 will be modified unexpectedly.

When the SDS API needs to modify the SDS, the API checks whether the SDS space meets the requirements for modification. If not, the API automatically expands the SDS space before modifying the SDS.

③ Reduce the number of memory reallocations when modifying strings

C string If the operation is to increase the string, the program needs to expand the size of the underlying memory array through memory reallocation, otherwise, memory overflow will occur.

C string If the operation is shortening the string, the program needs to free up the unused portion of the underlying memory array through memory reallocation, otherwise it will leak memory.

SDS realizes two optimization strategies of space pre-allocation and inert space release through unused space.

Space preallocation policy:

When the SDS API modifies an SDS and expands the SDS space, the program not only allocates the required space to the SDS, but also allocates additional unused space without the SDS.

Before expanding SDS space, the SDS API checks if there is enough unused space, and if there is enough, the unused space is used directly without the need to reallocate content.

Lazy space release:

When the SDS API needs to shorten a saved string, the program does not immediately reallocate the memory, but uses the free attribute to record the number of bytes and wait for future use.

Binary security

C string characters must conform to an encoding (such as ASCII) and must not contain null characters except at the end of the string. These limitations allow C strings to hold only text data, not binary data such as images, audio, compressed files, and so on.

SDS apis are binary safe, all SDS apis will process SDS data stored in BUF in binary manner, and SDS is also null-terminated, so it can be compatible with C string.