How Redis Implements Strings: A Deep Dive into SDS and Encoding

Redis, an in-memory data structure store, supports various data types, with strings being the most fundamental. Unlike traditional C strings, Redis employs its own optimized string implementation called Simple Dynamic Strings (SDS). This document explores the internal mechanisms, design choices, and various encodings Redis uses to store strings efficiently.

The SET Command and Dynamic Encoding

When you execute a SET command in Redis, the system dynamically determines the most efficient way to store the string value. This decision is based primarily on the string’s length and whether it can be represented as an integer.

Consider these examples:

• SET k a: For short strings, Redis often uses EMB_STR (Embedded String) encoding.
• SET k "a very long string that exceeds the embedded limit": For longer strings, it switches to RAW encoding.
• SET k 10: If the string can be parsed as a long integer, Redis uses INT encoding.

This dynamic encoding is handled by functions like tryObjectEncoding within the Redis source code (specifically in t_string.c), which evaluates the input string’s characteristics to select the optimal storage method.

Simple Dynamic Strings (SDS): Redis’s Custom String Implementation

Redis does not use standard C strings because they come with several limitations that are unacceptable for a high-performance database:

1. Inefficient Length Computation: C strings are null-terminated, meaning strlen() requires iterating through the entire string (O(N) complexity) to find its length. Redis needs O(1) length access for many operations.
2. Inefficient Appends: Appending to C strings often requires reallocating memory and copying the entire string, which is inefficient. SDS pre-allocates memory to make appends faster.
3. Not Binary Safe: C strings terminate at the first null character (\0). This makes it impossible to store arbitrary binary data that might contain null bytes, as it would prematurely truncate the string. SDS is binary safe, allowing any sequence of bytes.

To overcome these limitations, Redis developed SDS.

SDS Header Layouts

SDS structures include a header that stores metadata about the string. Redis uses different header types to optimize memory usage based on the string’s length:

• SDS_HDR5
• SDS_HDR8
• SDS_HDR16
• SDS_HDR32
• SDS_HDR64

These headers are defined in sds.h.

SDS_HDR5 (Small String Optimization)

For very small strings, Redis uses SDS_HDR5. This is a highly optimized header that packs both type information and length into a single byte:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 LSB for type, 5 MSB for length */
    char buf[];
};

• flags: An unsigned char (8 bits).
  • The 3 least significant bits (LSB) are used to store the SDS type (e.g., SDS_TYPE_5).
  • The 5 most significant bits (MSB) are used to store the string’s length.
• Length Limit: With 5 bits for length, SDS_HDR5 can store strings up to 2^5 - 1 = 31 bytes.
• buf[]: This is a Flexible Array Member (FAM), a C99 feature. It’s crucial for memory efficiency.

SDS_HDR8, SDS_HDR16, SDS_HDR32, SDS_HDR64

For longer strings, Redis uses headers that explicitly store len (current length) and alloc (allocated capacity) fields. SDS_HDR8 is a common example:

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;    /* Current length */
    uint8_t alloc;  /* Allocated buffer size (excluding null terminator) */
    unsigned char flags; /* 3 LSB for type, 5 unused bits */
    char buf[];
};

• len: Stores the actual length of the string. This allows O(1) length retrieval.
• alloc: Stores the total allocated memory for the string buffer, enabling efficient appends by pre-allocating extra space.
• flags: Similar to SDS_HDR5, but only the 3 LSB are used for the SDS type. The remaining 5 bits are unused in this header type.
• buf[]: Again, a Flexible Array Member.

The char buf[] Optimization (Flexible Array Member)

The char buf[] at the end of SDS header structures is a powerful optimization. It does not occupy any space within the struct itself. Instead, when memory is allocated for an SDS object, the buf array immediately follows the header in the same contiguous memory block. This means:

• No Pointer Overhead: There’s no need for an extra pointer (char *) to the string data, saving 8 bytes per string.
• Cache Locality: The header and the string data are stored together, improving cache performance.
• Dynamic Sizing: The buf effectively uses all the remaining allocated memory after the header, making it highly flexible.

Redis String Encodings

Redis uses three primary encodings for string objects, each optimized for different use cases: EMB_STR, RAW, and INT.

1. EMB_STR (Embedded String)

EMB_STR is used for short strings, specifically those with a length less than or equal to 44 bytes.

Optimization Rationale:

Redis allocates memory in chunks, with the smallest allocation being typically 64 bytes. The redisObject structure, which holds metadata for any Redis key-value pair, has a fixed size:

• type (4 bits) + encoding (4 bits) + lru (24 bits) = 4 bytes
• refcount (integer) = 4 bytes
• ptr (void *) = 8 bytes (on a 64-bit system)
• Total redisObject size = 4 + 4 + 8 = 16 bytes

When an EMB_STR is used, Redis stores the SDS header and the string data directly within the same 64-byte memory chunk as the redisObject.

Let’s calculate the space:

• redisObject size: 16 bytes
• SDS_HDR8 size (for EMB_STR): len (1 byte) + alloc (1 byte) + flags (1 byte) = 3 bytes
• Total occupied by redisObject + SDS_HDR8 = 16 + 3 = 19 bytes

Since Redis allocates a minimum of 64 bytes, the remaining space in this chunk is 64 - 19 = 45 bytes. This 45 bytes can perfectly accommodate a string of 44 characters plus one null terminator (\0).

By embedding the string directly, Redis avoids a separate malloc call for the string data, reducing memory fragmentation and improving performance for short strings. The redisObject’s ptr field, instead of pointing to a separate SDS structure, points to the redisObject itself, and the SDS header immediately follows it.

2. RAW (Raw String)

RAW encoding is used for strings that exceed the EMB_STR limit (i.e., strings longer than 44 bytes).

Characteristics:

• Separate Allocation: For RAW strings, the SDS header and the string data are allocated in a separate memory block using malloc. The ptr field of the redisObject then points to this separately allocated SDS structure.
• Binary Safe: RAW strings are inherently binary safe. They can store any sequence of bytes, including null characters, without premature termination. This makes them suitable for storing arbitrary binary data like serialized objects, Bloom filters, HyperLogLog structures, or other custom data types.
• Flexibility: This encoding provides maximum flexibility, allowing Redis to handle very large strings and complex data structures efficiently. Many Redis modules and internal components leverage RAW SDS to store their data.

3. INT (Integer)

INT encoding is a special optimization for strings that represent integer values.

Mechanism:

If a string can be successfully converted into a long integer (e.g., “123”, “42”), Redis will store it directly as a long within the void *ptr field of the redisObject.

// Pseudocode for INT encoding
if (string_is_convertible_to_long(input_string, &value)) {
    redis_object->encoding = OBJ_ENCODING_INT;
    redis_object->ptr = (void *)(long)value; // Store the integer directly
}

This avoids the overhead of storing an SDS header and the string bytes, saving significant memory for integer-like strings. When the string needs to be retrieved, the long value is simply typecasted back and potentially converted to a string representation if required by the client.

Note on INT encoding improvement: The video mentions a GitHub issue where this integer encoding could be further optimized. Currently, Redis might serialize/deserialize the integer to a string repeatedly. The suggested improvement is to store the integer directly as a pointer reference and avoid these conversions, enhancing performance for integer-backed strings.

Key Design Choices and Benefits

Redis’s approach to string implementation through SDS and dynamic encoding offers several critical advantages:

• O(1) Length Access: SDS stores the string length explicitly in its header, allowing constant-time retrieval of string length.
• Efficient Appends: By pre-allocating extra memory (alloc field), SDS minimizes reallocations and data copying during append operations.
• Binary Safety: SDS can store any arbitrary binary data, making it versatile for various use cases beyond simple text strings.
• Memory Efficiency:
  • SDS_HDR5 packs length and type into a single byte for very small strings.
  • The char buf[] (Flexible Array Member) avoids pointer overhead and improves cache locality.
  • EMB_STR leverages Redis’s 64-byte memory allocation chunks to store short strings directly within the redisObject, eliminating separate malloc calls.
  • INT encoding stores integer-representable strings as actual integers, saving substantial memory.
• Performance: These optimizations collectively contribute to Redis’s high performance, especially for string-related operations.

Conclusion

Redis’s string implementation is a prime example of how careful design and low-level optimizations can lead to a highly efficient and versatile data store. By moving beyond standard C strings and introducing SDS with its various header types and dynamic encodings (EMB_STR, RAW, INT), Redis achieves O(1) length access, efficient appends, binary safety, and significant memory savings. Understanding these internals provides valuable insight into why Redis performs so well and how it can be leveraged for diverse data storage needs, from simple key-value pairs to complex binary objects.

For those interested in a deeper dive, exploring the sds.c and sds.h files in the Redis source code is highly recommended.