SDS

Simple Dynamic Strings. The string type used everywhere in Redis — keys, values, query buffer, output buffer, internal labels.

Source layout

File	Role
src/sds.c	Implementation (53,826 bytes).
src/sds.h	Public API.
src/sdsalloc.h	Allocation hooks (overridable for tests).

Why a custom string

C strings are bad for Redis because:

• They have no length — strlen is O(N).
• They can't contain \0.
• Concatenation requires reallocation with no size hint.

SDS solves all three by storing a length prefix in the bytes immediately before the C-string data. From the user's perspective an SDS is still a char * and works with printf("%s", sds) and strlen (because the buffer is null-terminated). Internally there is metadata in the header.

Five header types

The header size is variable to minimise overhead for short strings:

Header	Used for length	Header size
sdshdr5	< 32 bytes	1 byte (flags + length packed)
sdshdr8	< 256 bytes	3 bytes
sdshdr16	< 65536 bytes	5 bytes
sdshdr32	< 4 GiB	9 bytes
sdshdr64	< 16 EiB	17 bytes

The flags byte at s[-1] encodes which header is in use. Macros in src/sds.h like SDS_HDR(T, s) cast s[-headersize(T)] to the header.

Key API

sds sdsnew(const char *init);                   /* From a C string */
sds sdsempty(void);                              /* Empty */
sds sdsnewlen(const void *init, size_t initlen);
sds sdsdup(const sds s);
void sdsfree(sds s);
size_t sdslen(const sds s);
size_t sdsavail(const sds s);                   /* Free space remaining */
sds sdscat(sds s, const char *t);
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscatprintf(sds s, const char *fmt, ...);
sds sdscatfmt(sds s, const char *fmt, ...);     /* Faster than printf, limited specifiers */
sds sdstrim(sds s, const char *cset);
void sdstoupper(sds s); void sdstolower(sds s);
sds sdsrange(sds s, ssize_t start, ssize_t end);
sds sdsfromlonglong(long long value);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
sds *sdssplitargs(const char *line, int *argc);  /* Like shell argv splitting */

Growth strategy

sdsMakeRoomFor(s, addlen) ensures addlen bytes are available. The doubling strategy is:

• If the resulting length is < SDS_MAX_PREALLOC (1 MiB), allocate 2 * len.
• Otherwise allocate len + SDS_MAX_PREALLOC.

This caps the absolute over-allocation while still amortising appends to O(1).

Embedded mode

When a small string is used as a value, the EMBSTR encoding co-allocates the robj and the SDS in a single zmalloc to save an allocation. sdsembed* helpers in src/object.c deal with the layout.

Splitting and quoting

sdssplitargs parses a config line or a wire command in a way that supports 'single' and "double" quotes, \xNN escapes, and \n, \r, \t, \b, \a, \\, \", \' escape sequences. This is the parser used by redis-cli for input lines and by CONFIG SET for argument splitting.

Embedded tests

#ifdef REDIS_TEST in src/sds.c defines sdsTest, registered in the dispatcher in src/server.c. Run with ./redis-server test sds.

Performance characteristics

Operation	Cost
sdslen	O(1). One byte deref.
sdscat/sdscatlen	Amortised O(addlen).
sdscmp	O(min(len1, len2)) memcmp.
sdsdup	O(len).
sdsfree	O(1).

Where to start modifying

• Add a header variant — extend the SDS_TYPE_* enum, add a header struct, update sdsHdrSize/SDS_HDR/sdsReqType.
• Tune growth — SDS_MAX_PREALLOC in src/sds.h.
• New helper — pattern after sdscatprintf. Keep allocation visible.

Related pages

• robj — uses SDS for OBJ_ENCODING_RAW and OBJ_ENCODING_EMBSTR.
• dict — uses SDS as keys most of the time.