How Redis Dynamically Grows Its Strings: Inside the SDS Allocation Mechanism

Redis stores string values with the Simple Dynamic String (SDS) data structure, which wraps a C character array to provide automatic length expansion. When a string is modified and the existing buffer is insufficient, Redis expands the SDS buffer.

Expansion Process Implemented by sdsMakeRoomFor

Check existing space : The function reads the free field in the sdshdr header to see if the current buffer can accommodate the additional data. If enough space exists, the function returns immediately.

Calculate new length : If the buffer is too small, the required new length is computed as the current length plus the length of the data to be added.

Determine expansion strategy : Redis uses a pre‑allocation policy. When the new length is less than SDS_MAX_PREALLOC (about 1 MiB), the length is doubled; otherwise, SDS_MAX_PREALLOC is added to the new length to avoid frequent small reallocations.

Memory allocation : Depending on whether the SDS type changes, Redis calls s_realloc_usable (same type) or s_malloc_usable (type change) to obtain a new memory block.

Update SDS header : After allocation, the header fields (length, free space, etc.) are updated and the original data is copied to the new buffer.

Handle type change : If the new length requires a larger SDS type (e.g., from SDS_TYPE_8 to SDS_TYPE_16), the function updates the type field and may move the data to a newly allocated region.

The full implementation of sdsMakeRoomFor is shown below:

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* If there is enough free space, return immediately */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s - sdsHdrSize(oldtype);

    reqlen = newlen = (len + addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    // greedy mode: 1 means greedy
    // decide whether to double length or add SDS_MAX_PREALLOC
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }
    type = sdsReqType(newlen);

    /* If type is SDS_TYPE_5 but we are appending, promote to SDS_TYPE_8 */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */

    if (oldtype == type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh + hdrlen;
    } else {
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh + hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = usable - hdrlen - 1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

The function first checks for sufficient free space; if none exists, it computes the new total length. In greedy mode, it either doubles the length or adds SDS_MAX_PREALLOC based on the size threshold. It then selects the appropriate SDS type, allocates memory (reallocating in‑place when the type stays the same, otherwise allocating a new block), copies the old data, and finally updates the header fields.

Changes Introduced in Redis 7.0

Before Redis 7.0, SDS used a struct sdshdr containing len, free, and a character buffer buf. The free field recorded unused space, enabling O(1) length queries and reducing reallocations.

Redis 7.0 replaces free with an alloc field that stores the total allocated size, and adds a single‑byte flags field to hold the SDS type. This makes the structure more compact, removes compiler‑added padding, and saves memory. The difference between alloc and len now represents free space.

Additional optimizations include using the __attribute__((__packed__)) annotation to ensure tight packing and leveraging s_malloc and s_realloc for flexible memory management while preserving alignment.

SDS Type Definitions (Redis 7.0)

SDS_TYPE_5

: strings shorter than 32 bytes; length stored in the high 5 bits of the flags byte. SDS_TYPE_8: lengths 1‑255 bytes; length stored in one byte. SDS_TYPE_16: lengths 256‑65 535 bytes; length stored in two bytes. SDS_TYPE_32: lengths 65 536‑4 294 967 295 bytes; length stored in four bytes. SDS_TYPE_64: lengths larger than 4 294 967 295 bytes; length stored in eight bytes.

Choosing the smallest suitable type reduces memory overhead, especially for short strings where SDS_TYPE_5 stores length directly in the flags byte without separate length or allocation fields.

Overall, Redis 7.0’s SDS redesign makes the string representation tighter and more efficient while preserving dynamic growth and binary‑safety, contributing to better performance and resource utilization in high‑throughput workloads.