Understanding Redis Simple Dynamic Strings (SDS): Structure, Benefits, and Memory Management

Welcome, Messenger

In a whimsical narrative, a messenger from the Redis empire arrives at the C‑language kingdom to introduce a new data structure called Simple Dynamic String (SDS).

C‑Language Empire Hall

The king explains that SDS stands for Simple Dynamic String and shows its definition.

Traditional C strings are null‑terminated character arrays ( char buf[] ending with \0 ), which require O(N) time to compute length.

Redis’s SDS augments this with a struct that stores the buffer, the current length ( len ), and the free space ( free ).

struct sdshdr {
    // character array, same as C string buffer
    char buf[];
    // number of bytes used (excluding the terminating null)
    int len;
    // number of unused bytes in the buffer
    int free;
}

The three fields provide O(1) length access because len is maintained directly.

Note: The terminating null is added automatically by SDS functions to keep compatibility with C string libraries.

Compared with C strings, SDS prevents buffer‑overflow bugs because any modifying API first checks available space and expands the buffer if necessary.

Memory Allocation Talent

SDS uses a pre‑allocation strategy:

If the new length after modification is less than 1 MB, SDS allocates exactly the new len bytes plus an equal amount of free space (so free = len ).

If the new length is 1 MB or more, SDS adds a fixed 1 MB of extra space.

This reduces the number of reallocations; the number of expansions is bounded by the number of modifications.

When a string is shortened, SDS employs “lazy free” – the excess space is kept for future use and can be released later via a dedicated API.

Code Examples

Appending a C string to an SDS:

sdscat(s, "QuJing");

Before concatenation, the API checks free . If insufficient, it expands the buffer according to the rules above.

Example of the SDS struct definition and a typical strcat misuse that leads to overflow in plain C strings:

strcat(s1, " QuJing"); // may overflow if s1 lacks space

Through these mechanisms, Redis achieves faster string handling, avoiding O(N) length scans and costly reallocations.

Overall, SDS provides O(1) length queries, safe concatenation, efficient pre‑allocation, and lazy space release, which together contribute to Redis’s high performance.