Understanding Redis String Implementation: SDS, Encoding Optimizations, and redisObject

Preface

Redis is the most frequently used cache system, and strings are its most common data structure. This article explores whether you truly understand Redis strings.

Studying source code is the best way to learn from masters; let's examine how Redis implements strings at the low level.

Whether you are a fresh graduate preparing for interviews or an experienced engineer, we will revisit Redis strings from the underlying data perspective.

1. Why Redis does not use native C strings?

The article explains that Redis does not rely on C's native null‑terminated strings because operations like strlen would be O(n) and inefficient for long strings, and append would require copying due to immutable C strings, leading to high CPU usage.

Additionally, native C strings are binary‑unsafe because they stop at the first 0x00 byte, which would truncate binary data.

In summary, native C strings cannot meet Redis's performance and functionality requirements, so a custom string type was designed.

2. SDS String

Redis uses a custom structure called SDS (Simple Dynamic String). The structure is defined as:

struct
SDS
<
T
>
{
T capacity
;
// array capacity
T len
;
// actual length
byte
flags
;
// flag bits
byte
[]
content
;
// actual data, ends with a 0x00 terminator
}

The SDS design solves several problems:

O(1) length retrieval : a stored len field avoids O(n) scans.

Reduced reallocations on append : a redundant‑space strategy minimizes frequent expansions.

Binary‑safe terminator : a dedicated terminator byte allows binary data to be stored safely.

Flag field : indicates which header type (8, 16, 32, or 64‑bit) is used, allowing the structure size to adapt to the string length.

3. Expansion Mechanism

When an SDS has no spare space, Redis expands it. The rules are:

If the new length is less than 1 MiB, the buffer size is doubled.

If the new length exceeds 1 MiB, the buffer grows by an additional 1 MiB.

The relevant C code implements this logic:

sds sdsMakeRoomFor
(
sds s
,
size_t
addlen
)
{
void
*
sh
,
*
newsh
;
// remaining capacity
size_t
avail
=
sdsavail
(
s
);
size_t
len
,
newlen
;
char
type
,
oldtype
=
s
[-
1
]
&
SDS_TYPE_MASK
;
int
hdrlen
;
// if current capacity is enough, no need to expand
if
(
avail
>=
addlen
)
return
s
;
// current length
len
=
sdslen
(
s
);
sh
=
(
char
s
-
sdsHdrSize
(
oldtype
);
// new length after expansion
newlen
=
(
len
+
addlen
;
// if new length < 1MiB, double it
if
(
newlen
<
SDS_MAX_PREALLOC
// #define SDS_MAX_PREALLOC (1024*1024)
newlen
*=
2
;
else
newlen
+=
SDS_MAX_PREALLOC
;
// otherwise add 1MiB
// determine new header type
type
=
sdsReqType
(
newlen
if
(
type
==
SDS_TYPE_5
type
=
SDS_TYPE_8
// get size of new header
hdrlen
=
sdsHdrSize
(
type
if
(
oldtype
==
type
newsh
=
s_realloc
(
sh
,
hdrlen
+
newlen
+
1
if
(
newsh
==
NULL
return
NULL
s
=
(
char
newsh
+
hdrlen
else
// need to allocate new memory and copy data
newsh
=
s_malloc
(
hdrlen
+
newlen
+
1
if
(
newsh
==
NULL
return
NULL
memcpy
((
char
newsh
+
hdrlen
s
len
+
1
s_free
(
sh
// free old memory
s
=
(
char
newsh
+
hdrlen
s
1
=
type
sdssetlen
(
s
,
len
sdssetalloc
(
s
,
newlen
// update capacity
return
s

4. redisObject

The top‑level metadata for any Redis value is stored in a redisObject structure:

typedef
struct
redisObject
{
unsigned
type
:
4
;
// object type
unsigned
encoding
:
4
;
// encoding strategy
unsigned
lru
:
24
;
// LRU timestamp
int
refcount
;
// reference count
void
*
ptr
;
// pointer to actual data
robj