How Redis Implements Binary‑Safe Strings with Simple Dynamic Strings (SDS)

Background

SDS (Simple Dynamic Strings) is a binary‑safe string implementation used by Redis. It stores the length of the string in an explicit len field, allowing O(1) length queries and safe handling of embedded null bytes.

Pre‑Redis 3.2 SDS implementation

Before Redis 3.2 the header was a single struct:

struct sdshdr {
    unsigned int len;   // used length
    unsigned int free; // free space
    char buf[];         // flexible array for data
};

The len and free fields each occupy 4 bytes, which is wasteful for short strings.

Redis 3.2–6.0: Five header variants

Redis introduced five packed header types to minimise overhead:

sdshdr5 – length < 1 byte (type 5)

sdshdr8 – length fits in 1 byte

sdshdr16 – length fits in 2 bytes

sdshdr32 – length fits in 4 bytes

sdshdr64 – length fits in 8 bytes

Each header starts with a flags byte. The lower three bits encode the type; the remaining five bits can store the length directly for strings up to 31 bytes. The structures are declared with __attribute__((__packed__)) to force 1‑byte alignment.

struct __attribute__((__packed__)) sdshdr5 {
    unsigned char flags;   // type + length (5 bits)
    char buf[];
};

struct __attribute__((__packed__)) sdshdr8 {
    uint8_t len;    // used length
    uint8_t alloc;  // total allocated length
    unsigned char flags;
    char buf[];
};

struct __attribute__((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};

struct __attribute__((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};

struct __attribute__((__packed__)) sdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};

The pointer returned to the caller points to buf. The original header can be accessed by moving one byte backwards ( buf[-1]) to read the flags byte.

SDS creation API

The function sdsnewlen(const void *init, size_t initlen) selects the appropriate header type, allocates hdrlen + initlen + 1 bytes (the extra byte holds the terminating \0), copies or zero‑fills the initial data, stores the type in buf[-1], and returns the buf pointer.

sds sdsnewlen(const void *init, size_t initlen) {
    char type = sdsReqType(initlen);
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    void *sh = s_malloc(hdrlen + initlen + 1);
    if (!sh) return NULL;
    if (init == SDS_NOINIT) init = NULL;
    else if (init) memcpy((char*)sh + hdrlen, init, initlen);
    else memset((char*)sh + hdrlen, 0, initlen);
    char *s = (char*)sh + hdrlen;
    ((unsigned char*)s)[-1] = type;
    s[initlen] = '\0';
    sdssetlen(s, initlen);
    sdssetalloc(s, initlen);
    return s;
}

Key points:

Empty strings are forced to SDS_TYPE_8 to avoid immediate reallocation.

The allocation always includes space for the terminating \0.

The function returns the buf pointer, not the header.

SDS clearing

Two ways to clear an SDS string:

void sdsfree(sds s) {
    if (!s) return;
    s_free((char*)s - sdsHdrSize(s[-1] & SDS_TYPE_MASK));
}

void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

sdsfree

releases the whole allocation; sdsclear only resets the length, keeping the buffer for future writes.

SDS concatenation

Appending another SDS string is performed by sdscatsds, which forwards to sdscatlen. The latter ensures enough free space (via sdsMakeRoomFor), copies the new data, updates the length, and adds a terminating \0:

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);
    s = sdsMakeRoomFor(s, len);
    if (!s) return NULL;
    memcpy(s + curlen, t, len);
    sdssetlen(s, curlen + len);
    s[curlen + len] = '\0';
    return s;
}

Memory‑reallocation strategy

sdsMakeRoomFor

decides whether the existing buffer can accommodate the additional length ( addlen) or a new allocation is required. If expansion is needed, the new total length newlen = len + addlen is calculated and then adjusted:

If newlen < SDS_MAX_PREALLOC (1 MiB), the buffer grows to newlen * 2.

Otherwise it grows to newlen + SDS_MAX_PREALLOC (an extra 1 MiB).

If the required header type changes (e.g., from sdshdr8 to sdshdr16), a fresh allocation is performed and the old data is copied.

sds sdsMakeRoomFor(sds s, size_t addlen) {
    size_t avail = sdsavail(s);
    if (avail >= addlen) return s;
    size_t len = sdslen(s);
    size_t newlen = len + addlen;
    size_t hdrlen, type, oldtype = s[-1] & SDS_TYPE_MASK;
    if (newlen < SDS_MAX_PREALLOC) newlen *= 2;
    else newlen += SDS_MAX_PREALLOC;
    type = sdsReqType(newlen);
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype == type) {
        void *newsh = s_realloc(s - sdsHdrSize(oldtype), hdrlen + newlen + 1);
        if (!newsh) return NULL;
        s = (char*)newsh + hdrlen;
    } else {
        void *newsh = s_malloc(hdrlen + newlen + 1);
        if (!newsh) return NULL;
        memcpy((char*)newsh + hdrlen, s, len + 1);
        s_free(s - sdsHdrSize(oldtype));
        s = (char*)newsh + hdrlen;
        s[-1] = type;
    }
    sdssetlen(s, len);
    sdssetalloc(s, newlen);
    return s;
}

Key takeaways

SDS returns a pointer to buf, making it compatible with standard C string functions while remaining binary‑safe.

Five header variants (sdshdr5/8/16/32/64) minimise memory overhead for short strings.

All mutating operations invoke sdsMakeRoomFor, which uses a doubling strategy for allocations under 1 MiB and a 1 MiB increment for larger sizes.

Project repository: https://github.com/doocs/source-code-hunter