Why Redis Uses Its Own String Type (SDS) and How It Boosts Performance

The author recounts a Redis interview failure and then dives into the internal implementation of Redis strings, focusing on the Simple Dynamic String (SDS) data structure that Redis uses instead of native C strings to achieve high performance.

Redis String Implementation

Redis is written in C but defines its own string type called Simple Dynamic String (SDS) to speed up operations and avoid common C‑string pitfalls.

1. SDS Code Structure

struct sdshdr{
    // length of used bytes
    int len;
    // length of free (unused) bytes
    int free;
    // character buffer
    char[] buf;
};

SDS stores the current length ( len) and the amount of allocated but unused space ( free) alongside the actual character buffer, enabling constant‑time length queries.

2. Dynamic Expansion Characteristics

When appending data, Redis checks whether the existing free space can accommodate the new bytes. If not, it performs three steps:

Calculate the required size.

Allocate a new buffer large enough for the new data.

Allocate additional free space: if the resulting length is less than 1 MiB, allocate len bytes of free space; otherwise allocate a fixed 1 MiB.

This strategy resembles Java's ArrayList growth pattern but is tuned for Redis's workload.

Performance Advantages of Redis Strings

Fast length retrieval (O(1) via stored len).

Prevention of buffer‑overflow bugs because every append checks capacity.

Reduced number of memory allocations, improving overall memory efficiency.

1. O(1) Length Retrieval

Because len is stored in the header, obtaining a string's length is a simple field read, unlike C strings that require scanning until the terminating '\0', which is O(n).

2. Buffer‑Overflow Protection

Traditional C strcat can overflow if the destination buffer lacks space. Redis avoids this by always verifying capacity before each append, eliminating the overflow risk.

3. Reducing Allocation Overhead

Redis employs two complementary techniques:

Space pre‑allocation : after an append, Redis reserves extra free space ( free) based on the new length, so subsequent small appends often reuse existing space without new allocations.

Lazy space reclamation : when a string shrinks (e.g., via sdstrim), Redis does not immediately free the released memory; it keeps it as free for future use, and a manual API can trigger reclamation if needed.

These mechanisms together keep Redis operations fast and memory‑efficient, which is crucial for a high‑throughput in‑memory data store.

Source: juejin.im/post/5ca9d8ae6fb9a05e5c05c4e8